Codeforces
計算量がなぜ間に合うのか自信がない。 fig.1fig.2ある頂点P（色c）に注目したとき、パスをつくれる頂点は図のようになる。 DFSで戻るときにパスの数を計算しながら、部分木の色のヒストグラムをマージしていく。 （色c以外は合計して、色cは1にする。） 深…
公式解説は、インデックス1まで移動してきた敵を一気に倒す。 使わずに余った弾丸は次のターンに持ち越すことにしても結果は変わらない。 というもの。 気づかずに少しめんどくさい解法をつかったのでメモしておく。 敵を攻撃し始めないと間に合わない締め切…
主客転倒がすんなり発想できたけど、実装バグって間に合わなかった。 残念だったので簡単に書いておく。 2点だけを決めると真ん中に一つの不動点ができる。 いわゆる主客転倒で、この不動点が現れる組み合わせを数える。 任意の2点 , ()を決めた時、 ,の間に…
まずは条件を整理する。 インデックス があって（ ） 、 から までで条件が「2」のとき、長さ1に 両方を含むことはできないので明らかに0通り。 から までの条件が「1」で までの条件が「2」のとき までに2種類を含むので0通り。 以上から答えが「0」のとき…
。をの素因数の集合とする。 が答え。 とは互いに素なので両方が、の素因数の倍数であることはない。 またがの倍数なのでがの倍数の場合、もの倍数。 よってとは共にの倍数ではない。 以上からとにある数を足すことで両方をの倍数にできる。 のすべての素因…
スコアの計算式とxorの性質から幅は1か2だけ考えれば良い。 任意の範囲（幅=x）を0にするとき、一個ずつ消してx秒か、2個ずつ操作して残った一個を消して、x秒で出来る。 2個ずつ操作していって、最後の2つが同じ値のとき「幅-1」秒で0にできる。 2個ずつ操…
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…
まず、の場所が最大値=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が変化する時、最小全域木の形が変わるポイントは少ない 最小全域木の形（使…
累積和をとって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…
数式が与えられて、変形できそうであれば、なにはなくとも式変形。より とする。 (1)は最小公倍数、最大公約数を実装したことあればソースコードにこのように書いていると思う。 ここでfig.1のようなことを考えると、Aは、から共通因数を消した数だとわかる…
気づき 開始位置に戻ることができる 偶数ターンで訪れた頂点に奇数ターンに訪れることは出来ない 道路の進行方向が毎ターン切り替わるので、一つ進むと、次のターンに一つ戻ることができる。 また、どの頂点も行って戻るのに（aは進んだ街の数）ターンかかる…
左右から見て、スワップする場所をN通り試せるのだろうと思ったけど、それ以上詰めることが出来なかった。 気づき スワップする場所を全通り試す 石を減らす操作は貪欲に決まる 左右から操作結果を記録する 数列に対して、なんらかの操作をした結果、変更し…
Good Bye 2020 E. Apollo versus Pan まず、 シグマをみたら式変形 ビット演算は桁ごとに見る のが基本なのでやってみる はに依存しないのでシグマの外に出す との両者がに依存するので、シグマの順番を入れ替える これはプログラムで書くと、 let mut ans =…
テストケースを見ながらacceptした。 構造を見抜くだけでなく、条件を詰めてバグ無く実装仕切るのがむずかしい。気づき 減らせるだけ減らして、水を足す。 同じ状態になったらループするので成功。 たとえばk=100、y=3とする。 まず100-3-3...-3>lと3を引い…
全然わからなかった。 気づき suffixに操作を加えても一つ前の値との差は変わらない 一つ前の値と同じにすることだけ考えれば良い 操作はsuffix全体にたいしてインクリメント・デクリメントなので、A[0]の値に揃えるのが最善で、順番に揃えていくと、一つ前…
DP難しい。 全事象は塔を建てるか建てないかの2通りの組み合わせで、通り。このうち題意をみたす塔の立て方のパターン数の確率を求めれば良い。 良い塔の建て方は、奇数の和でNになる場合の数なので、これをDPで求めたい。 気づき 累積和＋DPは貰うDPのほう…
A. Add Candies A=[1,2,3,...,N]は図にすると階段状の三角形になるので、逆向きの三角形を足せば四角形になって、値が一致する（和の公式の考え方）。 よって、[N,N-1,..,1]を足せば良い。 B. Numbers Box 気づき マイナス記号を自由に移動できる 負 負 は正…
