公式解説が丁寧だけど、累積和の理解に時間がかかったのでメモしておく。 公式とは少し違うみたい。 距離D毎に射る。座標0付近を中心に左右にほぼ均等に割り振る。中心を0から距離Dより離す必要はない。 よって中心を0からDまで試せば良い。 （ここまで公式…

累積和をとってDPまでは気づけたのだが…… 肝心の割り算の結果がいくつできるのかがわからなかった。 DPを考える。 今の値をとする。まず1つ目の操作はX未満のどの値へも移動できるので、逆に見ると任意の値へはより大の値全てから移動してくることができる。…

桁ごとに考える。 をNのi桁目の数とする。 任意の桁iで答えのi桁目を「より大」にすると、i桁より下の桁は自由に値を決めてもN以上になる。 そこでNから初めて、下の桁から1ずつ増やしていくことを考える。 ①よりi桁目がより大なら下位の桁は自由に決めて良…

いまいち確信が持てないが、ACできたので書く。 数式を睨むと、は程度まで大きくなるのに対して、はよりちょっと大きい程度に抑えられるとわかる。 つまり基本的にはiとjの積が大きくなる、aの後ろの方を選ぶのが良さそう。 は間に合わないので、を固定して…

実はほぼ貪欲でOKだった。 ただサンプルが弱くて実装に罠があるから難しい。 先頭は任意の文字数消すことができる（①）。 先頭以外で、backspaceを押すことは、2文字スキップすることと等しい（②）。 ②より、最後に余る文字は偶数個（0を含む）である必要が…

まず操作を続けたときに何が起きるかを考察する。 A=[a,b,c,d] としたとき、一度の操作後は、 A=[gcd(a,b) , gcd(b,c) , gcd(c,d) , gcd(d,a)] となる。 もう一度操作すると、 A=[gcd(a,b,c) , gcd(b,c,d) , gcd(c,d,a) , gcd(d,a,b)] となり、結局、最後に…

明らかに再帰的な構造があるので、（メモ化）再帰かDPで溶けそうな雰囲気は感じる。 けど、具体的に考えているうちに頭爆発してしまった。 fig.1のように反射しないものは、そのまま通り抜けることにして、反射するときに＋1すると考えることにする。 こうす…

罠が多い問題 コンテスト中に解けなかったけど、仮に解けてもTLEだったと思う 気づき lcm gcd の関係から式変形 事前処理で計算量を落とす まず、与式にlcm、gcdが含まれているので を用いて変形する。 として、 (Gはa,bの最大公約数より、は互いに素) とし…

気づき と制約が小さいので、ギャグ味を感じる 全部を同じ値にできそう 上下左右との関係のときは市松模様でうまくいことが多い 制約が小さいので1から16の最小公倍数をとれば、全てのマスを同じ値にすることができる。 これの値は を満たすので、 とおく。 …

aとbしかないので結構できそうな雰囲気を感じる。 fig.1 Mが奇数の時 fig.1の(i)、(ii)のいずれであっても、2頂点を往復すれば、回文になる。 よって常に可能。 a aなら aaa... a b なら abababa... Mが偶数の時 (i)の場合往復で可能 a a なら aaaaa.... N=2…

全体を回転しながら、上となる辺を数えた。 全体を回転させて同じ処理を4回行うっていうのは、過去のABCの解説動画にもあった方法。 fig.1この方法でAC。 公式解説の4マスを調べる方法がよくわからなかった。 マスに注目しているというより、多角形の頂点と…

数式が与えられて、変形できそうであれば、なにはなくとも式変形。より とする。 (1)は最小公倍数、最大公約数を実装したことあればソースコードにこのように書いていると思う。 ここでfig.1のようなことを考えると、Aは、から共通因数を消した数だとわかる…

気づき 開始位置に戻ることができる 偶数ターンで訪れた頂点に奇数ターンに訪れることは出来ない 道路の進行方向が毎ターン切り替わるので、一つ進むと、次のターンに一つ戻ることができる。 また、どの頂点も行って戻るのに（aは進んだ街の数）ターンかかる…

左右から見て、スワップする場所をN通り試せるのだろうと思ったけど、それ以上詰めることが出来なかった。 気づき スワップする場所を全通り試す 石を減らす操作は貪欲に決まる 左右から操作結果を記録する 数列に対して、なんらかの操作をした結果、変更し…

Good Bye 2020 E. Apollo versus Pan まず、 シグマをみたら式変形 ビット演算は桁ごとに見る のが基本なのでやってみる はに依存しないのでシグマの外に出す との両者がに依存するので、シグマの順番を入れ替える これはプログラムで書くと、 let mut ans =…