裏紙

ほぼ競プロ、たまに日記

2018/3 solved(1)

3/1

CF #411(Div.1) Virtual

ABCの3完。Cの解釈に時間掛けすぎたけど、木という条件を利用することでクリークがそれ以上大きくならないというふうに考えることができ、色は貪欲に決まる。Dも途中までは考察できてたので、Dは解説見ずに通したい。

3/2

3/3

3/4

[2017-2018 ACM-ICPC, Central Europe Regional Contest (CERC 17)] Virtual

dayamaと2人で組んだ。3完。そのうち2つは虚無だし、もうちょっと頑張りたかった...

3/5

3/6

Pythonitertools.combinationsを使うと綺麗に書ける(submission)。

D個のグループに分けて累積和をとっておく。クエリごとにDが変わるとしたら、Dの大小で場合を分けると(小さい方は累積和、大きい方は愚直にシミュレーション)、時間と空間の計算量の条件を満たせると思う。

3/7

3/8

漸化式の形から、普通にメモ化再帰しても呼ばれる箇所がO(logn)個しかないので、普通にメモ化再帰でよい。

3/9

パターンが少ないので、それを全探索する。外周にフィットさせるパターンを除けば、片方の種類の向きは1個しか置けないので、その位置を探索して、もう片方の向きを各列ごとにおけるか判定する(submission)。

CF #469(Div.1)に参加

No.662 スロットマシーン ABの2完。AもBもWAを出しまくったし、そのせいでCが間に合わないし色々ひどい...。青くなったし、はやく戻そう。

本当に問題文の理解にめちゃくちゃ時間がかかった。要するに、「subsetとして選んだ頂点のupdate-timeを+1しても条件をみたすようなnon-emptyな最小のsubsetを見つければいい」ので、+1すると時間がかぶってしまうような依存関係が有る時にゆうこうへんを張ると、SCCしてDAGになった後の連結成分で葉の部分で要素数が最小のところを選べばよいことになる(submission)。(またSCCか...)

3/10

とりあえず各リールにどの絵柄が何回現れるか数えておけば、それが実際に出現して揃うパターンはその位置の三つ組に対して5通りあることが問題文で言われているので、実際に何回そろうかは3つの列の出現回数の積の5倍になる。回数が分かれば、期待値はもらえるお金をかけ合わせて、全通りで割るだけ(submission)。

列を左から順番に決めて復元していきたいけど、循環しているので、今回は最初と最後を決め打ちにすることにした。すると、1つめのセルの状態から、2つ目のセルに0,1をそれぞれ選んでよいか、が決まるので、それをメモ化再帰しながら数え上げる。再帰の末端は、最後2つの要素が条件を満たしているかをチェックしている(submission)。

典型的なdp。dp[i][j] := 時間iにいて、j回売りをした時に持てるお金のmaxをすると、iで買って、売るタイミングをO(N)で遷移させると、O(N^2 M)で解ける(submission)。

ベルヌーイ数でググるとまさに求めたいものが見つかる1つのベルヌーイ数を求めるのにO(k)なので、全体ではO(k^2)になる。しかし、どうやらもっと制約がきつい問題が既出で、ラグランジュ補間を使って求められるらしい(submission)。

頂点から中心に向かって線を引くと、n個の二等分三角形ができる。その二等辺三角形から、くぼんでいる部分を引けば良い。引くべき三角形の面積は、三点が分かるのでそれによって求めることが出来る(submission)。

3/11

CF #470(Div.2)に参加

ABCDの4完。今日は調子良かった。Eも通したかったけど、さすがにこれは残り時間で考察しきれない気がする...

置換ルールをよく見ると、BはCに、CはBに変換できるので全てのCはBと見なして良い。まず、Bの個数の偶奇は変えられないので、気をつける必要が有る。次に、末尾のAはいじりようがないので、mod3で揃っている必要があるが、揃ってない時には無理やりAをBBに変換して揃えにいかなければならないので、デフォルトの状態でBの個数が完成形よりも少なくないといけない。この辺に注意して場合分けを頑張る(submission)。

スコアが得られる文字列の長さが8以下なので、普通にdfsしてなぞる全パターンを列挙出来る。そこからスコアパターンを何回なぞれるかカウントしておき、それが終わったらdpをする。文字列の長さごとに、考慮すべきのがT個以下なのは明らかなので、それでdpすれば良い(submission)。

これが想定なのか分からないけど、頂点に流量制約をつけてフローが2流せるかを毎回愚直にやった(submission)。

3/12

3/13

bitDPをする。こういう確率のdpは後ろから遷移するようにすると見通しが良い。ただ、最初の考察では、今何番目かと生き残っている猫の集合しか考えていなかったが、今どの猫が戦っているのかも考える必要がある(もしやられた時に次の猫を適切に選べるようにするためにこのパラメータが必要になる)(submission)。

3/14

二分探索(submission)。

Kが共通なのを利用すると、小さい方からK個だけ持つpriority_queueと、それより大きい部分を持つpriority_queueを持つことで、クエリを高速に処理することが出来る。クエリごとにKが可変だとしたら、座圧+BITで出現を管理して、それを二分探索する、とかが考えられる(submission)。

3/15

最初Euler tour + Segtreeでなんとかしようと思ったけど、どうしても逆行列が必要になりそうで、無かったら詰みだなあと思ってた。HL分解を使うと、クエリをO(logn)個のパスに分解出来て、それぞれに対して行列を乗せたSegtreeで積を高速に計算することで、全体でO(Q(logn)^2)になる(submission)。

この問題を解くためには、LCAで十分、u-vパスを根からのパスからの足し算と引き算に分解すれば良い(submission)。

想定会は木上でのimos法だったけど、HL分解の練習として解いた。パスの処理は区間add/区間sumのセグ木があればよいので、パスをそのようなセグ木で管理する(submission)。

HL分解の練習。部分木に対するAddを効率的に処理するために、vidの振り方をbfsでなくdfsで振るようにした。こうすると、部分木に通しで番号が振られるので部分木のサイズが分かっていると1つの区間への操作とすることが出来る。あとは、前の問題と同様にパスの重みは子側の頂点に乗せる重みとして考えて、パス上の和を取れば良い(submission)。

頂点を拡張してBFS(submission)。