計算量がなぜ間に合うのか自信がない。 fig.1fig.2ある頂点P（色c）に注目したとき、パスをつくれる頂点は図のようになる。 DFSで戻るときにパスの数を計算しながら、部分木の色のヒストグラムをマージしていく。 （色c以外は合計して、色cは1にする。） 深…

公式解説は、インデックス1まで移動してきた敵を一気に倒す。 使わずに余った弾丸は次のターンに持ち越すことにしても結果は変わらない。 というもの。 気づかずに少しめんどくさい解法をつかったのでメモしておく。 敵を攻撃し始めないと間に合わない締め切…

めちゃくちゃ苦労したけど、コンテスト外でやっと解けたので記録してくおく。 最初に考えたこと。 差分計算したい。 更新時に未使用の色のうち、インデックスが一番小さいものを採用すればよさそう。 ある色が採用されたとき、いくつのボールが利用されるか…

解説をよんで最初分からなかった部分が腹落ちしたので書いておく。 疑問に感じたのは、途中で使ったボールの操作を打ち消すのに、最新の状態のDPテーブルへの操作で良い理由。 合計K以上のDPテーブルを持たなくて良い理由の部分。 の2点。 直感的にはボール…

公式解説の通りです。 実装の方針だけ。 任意の頂点pを選んで2回操作した場合もとに戻る 操作の順番が違っても結果は同じ 任意の頂点pだけを反転するには、頂点pにたいして操作をして、頂点pの子に操作する（戻す操作）で可能 以上により必要な操作の最小回…

AtCoder ARC127 A. Leading 1s 地獄のような桁dpを書いた。 dp[i桁目][先頭から連続して使用した1の個数][1が連続しているか][未満フラグ] として、遷移はnext = 0から9 leading zeros に注意（nextが1の時だけ初期状態に+1）。 dpの結果（場合の数）にたい…

主客転倒がすんなり発想できたけど、実装バグって間に合わなかった。 残念だったので簡単に書いておく。 2点だけを決めると真ん中に一つの不動点ができる。 いわゆる主客転倒で、この不動点が現れる組み合わせを数える。 任意の2点 , ()を決めた時、 ,の間に…

まずは条件を整理する。 インデックス があって（ ） 、 から までで条件が「2」のとき、長さ1に 両方を含むことはできないので明らかに0通り。 から までの条件が「1」で までの条件が「2」のとき までに2種類を含むので0通り。 以上から答えが「0」のとき…

。をの素因数の集合とする。 が答え。 とは互いに素なので両方が、の素因数の倍数であることはない。 またがの倍数なのでがの倍数の場合、もの倍数。 よってとは共にの倍数ではない。 以上からとにある数を足すことで両方をの倍数にできる。 のすべての素因…

にたいしてを最大値として採用できるように、かつをできるだけ小さくするを求めて、これらの最小値が答え。 どうやって計算するか。 2進数で考える。 より30桁考えれば良い。上の桁から決めていきたいので、以下では左から0,1,2..桁目と数えることとする。 …

グラフを作ってからメモ化再帰で答えをもとめる。 数字が大きいところにしか辺を貼れないので、グラフはDAGになる。 あるマスから行または列の、自分の次に数が大きいマス（複数ありうる）に辺を貼る。 「自分の次に数が大きいマス」にだけ辺を貼れば良い。…

kyopro_friendsさんの公式の解説の通り。 解説動画がくれば詳しく解説してくれそうだけど、実装に時間がかかったので残しておく。 dp[i][j] = i番目の試合でj番目の選手が勝ったときの、得られるポイントの最大値とする。 遷移はdp[i+1][j] = (i+1)番目の試…

スコアの計算式とxorの性質から幅は1か2だけ考えれば良い。 任意の範囲（幅=x）を0にするとき、一個ずつ消してx秒か、2個ずつ操作して残った一個を消して、x秒で出来る。 2個ずつ操作していって、最後の2つが同じ値のとき「幅-1」秒で0にできる。 2個ずつ操…

NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253） F問題 Operations on a Matrix 状態が多くて脳が破壊された。 だいたいの情報は両端キューで管理して適宜pop_front()するとすこし楽になる。 まずタイプ1(l,r,x)のクエリによってj列目…

https://codeforces.com/contest/1674 E. Breaking the Wall 難しいのは隣り合う2つの壁を壊すパターンだと思うが、3分探索で提出したらACした。 正当性があるのかはすこし疑問があるが参考まで。 片方の2で割る回数を、整数の3分探索で調べて、合計手数のmi…

https://codeforces.com/contest/1668/problem/D 難しい。 公式解説のままです。 まず愚直なDPを考えるdp[i]=i番目まで決めた時のベストスコアとする。 このときAの累積和を求めておけば、j=0からi-1までためして、dp[i]= max(dp[j]+score(j,i)) となる。sco…

https://codeforces.com/contest/1673/problem/C 問題特有の考察はできたけどDPが解けなかった。 分割数って有名問題らしいけど難しい。 制約から40000以下の回文数はすくなそう（M種類）となって、dp[N][M] = 和がNのとき最後に使ったのがM番目の回文数のと…

言われてみればなるほど。 本番中は1を追加する場所を全部試すとMを追加する場所が高速に求まったりするのかな？という方向で考えてたけどちょっと外してた感。 まず、同じ値が並べばコストは0。 差が1ならコスト1なので、隣り合う値がaとbのときコストをb-a…

Codeforces Codeforces Round #779 (Div. 2) D1. 388535 (Easy Version) 2進数の桁毎（i桁目毎）に0,1の分布をみて、からまでとaに含まれる要素を比較する。 i桁目含まれる0,1の個数が異なるならxのi桁目を1にして、i桁目の0,1を逆にすればよい(A)。 問題は…

まず、の場所が最大値=Nなのは明らか。 また順列の並び替えなので最大値は常に1つで2つ以上存在しないので、の個数が1でないときは不適（条件1）。 PをローテートしたときはCもローテートされるので、を先頭にしておく。 いまでが確定している（以後決定した…

codeforces CodeTON Round 1 (Div. 1 + Div. 2) D. K-good codeforces.com 式変形した結果、偶数 × 奇数 になっていて、この条件を満たすようにするという問題はよくある気がする。 ポイントは、 0を使えないので1からKの和を使う。 余りの重複があってはい…

4時間くらい格闘してやっとACしたので 実行時間もメモリもカツカツ とくにメモリはMLEエラーを連発して、可能な箇所は64bit変数を32bit変数に変更して節約するなどした。 気づき xが変化する時、最小全域木の形が変わるポイントは少ない 最小全域木の形（使…

公式解説が丁寧だけど、累積和の理解に時間がかかったのでメモしておく。 公式とは少し違うみたい。 距離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の最大公約数より、は互いに素) とし…