ABC311 ABC311 参加． E,D の両方で変数名を勘違いしていた． 自分が馬鹿だった． E はギリギリ通ったけど，D は試験の後に AC. 対策： 2次元のときなどは，多少面倒でも 2次元配列を使ったほうが安全？ たとえば，サイズが \(N \times M \) のグリッドのと…

ABC202E Euler tour, sub tree, DFS. 取りあえず，木に関するクエリ問題なので， 少ない回数の DFS で多くのクエリの処理を同時に行いたい． 頂点 \(u\) 以下の部分木で，深さが \(d\) である頂点の個数がクエリ毎の答え． これは，深さ \(d\) となる頂点全…

ABC204E コストが変則な Dijikstra. 時刻 \(t\) に 頂点 \(v\) を出発すると，次の頂点に到達する時刻が \(f(t) := c + \lfloor d/(t+1) \rfloor\) となる． 出発するときに待てば良いので，それ以外のタイミングで待つ必要はない． 簡単のため floor を無視…

ABC196E clamp 関数の合成 は clamp 関数になる． 関数をそのまま持たずに，必要な情報にそぎ落とす． 今回の clamp 関数では，組 \( (s,l,r) \) を持っておけば 関数が復元できる． ここで，clamp 関数において， 全体を \(+s\) シフトする， 下限が \(l\),…

ABC205E カタラン数に近い計算． \(K\) に関する条件がなければ \({}_{N+M}C_{N}\) 通り． \(K\) に関する条件を満たさない場合の数は，グリッドを考えると分かりやすい． ある直線があって，その直線で折り返した場合の数に一致する． 通ってはダメな点を列…

ABC201E 距離の定義に XOR が用いられている． 桁毎に独立して計算して，集計するのが良さそう． Tree であることを用いると，根からの距離を用いて \(i , j \in N\) 間の距離が求まる． ここで，距離は XOR であることに注意する． \(l \in N\) を \(i,j\) …

ABC199E BitDP. 順列を決めていくが，次を決めるときに， 今まで選んだ元の集合が分かっていれば，選んだ順番は無関係． 実装\(M\) 個の条件を調べる． 数え上げるとき，常に条件を満たしている様にとっている． つまり，\(s \in 2^{N}\) を調べ終わっていて…

ABC197E 色毎に分けて考える． 回収したボールを並べると，色が広義単調増加なので， 同じ色がひと塊となるから． 色 \(i \in N\) を固定して，色 \(i\) の座標だけを考える． 最適手順として，左端または右端で終える物が存在する． よって，左端か右端か \…

ABC211E BFS で全探索． 丁度 \(k \in K\) マス塗っている状態全体を，入れ物 \(q\) に入れる． \(q\) の中から，次の1マスを塗って遷移すると，丁度 \(k+1\) マスを塗った状態となる． 実装塗ったマス全体の集合を \(2^{N^{2}}\) で管理する． long long で…