atcoder.jp 考察 2つ前までしか移動できないので、ロボットが2つ連続で並んでいる箇所があると自由にゴールさせられない。 逆にいうとそういう箇所がなければ任意の順でゴールさせられる。 あるロボットに着目し、前にあるロボットをいくつゴールさせれば自…

atcoder.jp 考察 青diffだが全然わからなくてかなり苦戦した。あることに気づけばあとは簡単。 各ゴーレムはあるゴーレムよりも向こう側に行こうと思うと、そのゴーレムと一緒に行動するしかない。すなわち、消滅するゴーレムは左右の端の連続した区間となる…

atcoder.jp 考察 D - 25個の整数で学んだように、最大値から順番に位置を決定していくのが筋がよさそう。 最大値から順に決めていくと、数字の位置を決めることで縦と横のそれぞれ最大値になるかならないかやその数が既に置かれたマスのx,y座標の集合を管理…

atcoder.jp 考察 最小費用流の形にできそう、超頂点S,Tを用意してコマの開始位置へSから容量1コスト0の辺を張って、好きなところから1つずつ回収してTに送る容量1コスト0の辺を加える。 元のグリッドグラフ上では各頂点から右と下に容量無限(コマの個数でよ…

atcoder.jp 考察 式を整理すると、を任意の整数としてが成り立つような最小のを求める問題である。 の素因数がにどのように振り分けられているのかが気になる。 と置き、がの倍数、がの倍数であるとしよう。の数はそんなに多くないのでこれを固定して全部試…

atcoder.jp 水diffだが解けなかったので自戒の意を込めて記録。 制約から2乗のDPかと思い考えたがうまく重複せずに数えられずDPでない方針を考えた。 その結果いろいろと言い換えはできた(各ブロックは下か左のどちらかから見え、どちらからも見えるものはな…

atcoder.jp 考察 独立なゲームが個あるのでGrundy数を考えてみる。が例えば十分大きい偶数なら以下の様になる 0, ..., K-1 | K, ... , 2K - 1 | 2K, ... 0, 0, ....0 | 1, 0, .... 1, 0 | 2, 1, 0, 2, 1, 0... Grundy数さえ高速に(くらいで)求められればXOR…

atcoder.jp 考察 をそれぞれとしよう。 実験をして、の右辺はすべての要素になるのではないかと思う もし右辺にC以外の要素があるなら、の形の式があって、1つ目の式の左辺のCと2つ目の式のnot Cを交換しても条件を満たす。 これを繰り返せばすべての式の右…

Dashboard - Educational Codeforces Round 96 (Rated for Div. 2) - Codeforces F. Realistic Gameplay 区間の始めに余っている弾を捨ててreloadする必要はない。(余っている分を使えばいいので)したがってreloadは区間の終わりに時間の余裕があるときのみ…

Dashboard - Educational Codeforces Round 97 (Rated for Div. 2) - Codeforces E: Make It Increasing 列を区切ってLISすればOK Submission F: Emotional Fishermen 順列の数え上げだし挿入DPだろうと決め打って考えたが解けなかった。この問題はよくある…

問題文 : Aizu Online Judge LPの定式化から2つのアプローチができて面白かったのでそれについて説明する。 考察1 先手が初めに各辺に確率を割り振り、後手はそれに応じてを確率で選ぶとする。値 を先手は最大化、後手は最小化する時、Xの値はいくらかという…

問題 https://codeforces.com/contest/1240/problem/D 解法 解説を見た。 各indexについてそこから順にstackに入れていった時に初めて空になるindex nxt[i]が欲しくなる(これが分かればあとはdpで数えるだけ)。 しかし直接nxtを求めるには少し情報が足りない…