AtCoder Regular Contest 213 (Div. 1)

　Aしか解けず。そのAで酷く時間がかかってしまった。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 213 (Div. 1) Aのみで破滅
A costは転倒数。転倒数は高々36なので36歩以上進む場所は必ずいけるとして良い。DP[i]でi番目を使ったとき獲得したお金として、累積maxを組み合わせればOK。が、DPの初期値を0にしてずっと気付かず13ペナ。序盤、絶対使えないやつがあるもんねぇ。

— titia (@titia_til) January 25, 2026

B - Hamming Distance is not 1

　ヒントだけ見て解こうとしたが、全然答えが合わず20ペナ以上を重ねた。

　bitcoutを2で割った余りが重要なのは分かる。

　bitcountが奇数のもののみ、もしくは、偶数のもののみを集めたものは条件を満たす。

　ところで、2nと2n+1はbitcountの偶奇が必ず異なる。（これを利用することはコンテスト中気付いていなかった）

　なので、全体の約半分は必ず含めることができる。

　問題は、Lが奇数、Rが偶数のとき、L～lastまではbitcount偶数（奇数）、last+1～Rはbitcount奇数（偶数）のものを採用すると、答えが一個増える場合があること。（このことにはコンテスト中気付いていた）

　そのようなlastをどう求めれば良いか？　というのが分からなかった。

　あるbit iについて、R^(1<<i)がL以上だったとする。すると、それとRが同じグループに入っていてはいけない。なので、lastはR^(1<<i)以上と分かる。

　これを繰り返していけば、lastの候補を絞っていってACした。

　公式解説では、LとRで異なる最上位bitに着目しているよう。なるほど。結果的には同じものを求めていそうですね。

　二部グラフへ持ち込む証明は思いつかない。というか、最大独立集合（参考）について理解していなかったことに気付きました。

yukicoder contest 491 Go on Back!!

　Cまで三完。

コンテストへのリンク

No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?

　一応自力AC。

　二分探索し、P番目の価格の値が求まれば、復元は難しくなさそう。が、コンテスト中は二分探索の判定方法で詰まり解けなかった。

　ソートして二分探索して……では、同じ色の場合の処理が難しい。

　こういうときは、片側だけ色で分類すると良い。半分全列挙のときと同じ感じでやれる。

　

　各トップスに対して、

・全体で何個が価格X以下か？

・同じ色のものについて、何個が割引せずに価格X以下で、割引した後価格X以下か？

　はどちらも二分探索で求められるので、判定できる。

　復元は簡単だと思ったが、復元でも詰まった。

　同じ色のものが答えになるときは簡単。

　そうでないときは、価格Xになるものの個数がbisect(A,X)-bisect(A,X-1)で求まることを利用した。

　全体で、価格Xになる個数と、同じ色で価格Xになる個数を比較し、全体の方が多くなっていればOK。

No.3437 [Cherry 8th Tune C] Silhouette

　自力AC。

　三点がどこに映るかを計算し、三角形の面積を求めれば良い。

　ただ、最初から割り算をmod 998244353で行うと正負が分からなくなる。なので、分数で計算し、最後にmod 998244353の形に直した。PythonのFractionをそのまま使ったらTLEだったが、入出力高速化してAC。

　模範解答は、三角形の向きを行列式で求める方法らしい（よく分かっていない）。

No.3438 [Cherry 8th Tune D] 競プロは向いてない

　自力AC。

　実験したら、凸包内部にあるときはNoそう。具体的な（A,B）を求める方法は分からなかったが、凸包の前後の頂点だけ見て乱択したらACした。

　しかし、凸包の前後の頂点だけ見れば良いという予想が正しいのなら、不等式を解くことで具体的な（A,B）を得ることはできそうですね……。後から気付きました。

　乱択は嘘っぽいけど、どういうときダメなのかはよく分かっていません。

AtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes)

　Fまで。

　Fは初めから解法は合っていたので、どうしたら良かったのか悩む。定数倍高速化を頑張るより、codonを試す方が良いんだろうか？

コンテストへのリンク

コンテスト後のツイート

F DPと復元をやるだけ。だが、普通に書くとPyPyだとTLE&MLE。高速化しても2caseでTLEが取れず困ったし、ランダムテストしてもどういうケースで落ちているか分からない→ダメ元でcodonで提出したらACした。えー。
G 遅延セグ木で解けそうだが……。

— titia (@titia_til) January 17, 2026

G - Takoyaki and Flip

　解説・解説放送を見てAC。

　遅延セグメント木を使うとは分かっていたが、基本的なことからおかしかった。

　もつデータを（最大値, flipしているか）だけで良い気がしていたが、それだと、複数の皿が「全て表か、全て裏か」の二通りの状態しか表せないので明らかに間違っている。

　それを解消するため、表の皿が何枚で裏の皿が何枚か、というのをもつようにすれば自然と遅延セグメント木に乗る。

　ただし、遅延させるものは、

・(a, b)　a回flipした後、b加算

　なのだが、(a, b)の後に(c, d)を行うのと、(c, d)の後に(a, b)を行うのとで結果が違うことに注意が必要だった。

　自分が解いてきた問題は、ここが可換なことが多かった気がする。順番に注意しなくてはいけなかった。

　ところで、PyPyだと1873msなのだが、codonだと301msでした。codon凄い！

AtCoder Regular Contest 182

　ABの二完だが、レートは上がった。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 182 ABの後ずっとDを考えていたが分からなかった。
A 左右を見て、それより前に使うものでV_iより大きいものがあってはダメ。それより後で使うものでV_iより小さいものがあってはダメ。
B 二分木
D 難しい場合、端の方は同じ方向に回しそう、から考察が進まなかった。

— titia (@titia_til) August 11, 2024

C - Sum of Number of Divisors of Product

　解説AC。

　積の和典型の練習をしようと思って解こうとしたが難しく、解説を読んでもしばらく理解できず非常に苦労した。

　公式解説のように積の和典型を適用すると、タワーと積み木の問題と同等になることは分かる。しかし、それがbit DPで表せることが分からなかった。（ChatGPTに聞いたりしつつ悩んだ）

・どこかで積み木を選ぶのだから、積み木を置いたそのときに選べば良い

　と考えると理解できた。

　たとえば、「6」の積み木を置くとき、それは、2と3の位置に積み木を一個ずつ選ぶことを意味する。

　そして、それまでに2の位置や3の位置の積み木を選んでなかったとしたら、このときに選べば良い。

　その、既に選んだかどうかでbit DPをしている。

　また、最初に積み木が一個ずつ置いてあり、それを選んでも良いので、bit DPの初期値は全て1になる。

　こういう考え方でDPを書いたものが、この提出。これを行列累乗で高速化するとACできる。

Codeforces Round 1072 (Div. 3)

　ACの二完。Bで詰まって一旦離脱して、最後に戻ってきてもう少し解こうと思ったけどDが間に合わなかった。

コンテストへのリンク

B. Hourglass

　難しくないか？

　mを2*kの余りとした後、sとkの大小で場合分けして考える……という方針は簡単に立つけれど、s=kやm=kのときどうなるか？　など注意すべきところが多い。

　コンテスト後にも2ペナを出してしまった。

E. Exquisite Array

　自力AC。

　差が大きい順に見て、Union-findで要素をつなぎ、答えを更新していく。しばらく思いつかず結構時間がかかってしまった……。

F. Cherry Tree

　自力AC。mod 3での可能な回数の集合を持って木DP。

　この解法はmod 3だからできたもの。maspyさんの解説によると、modが任意の場合にもできるらしいが理解できていない。

G. Nastiness of Segments

　自力AC。セグ木＋二分探索。問題文がやや難読だが、内容は簡単だった。

　結局、Bが一番難しい回だったみたい。

AtCoder Regular Contest 212 (Div. 2)

　ABDの三完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 212 (Div. 2) ABDの三完。
A 同じ頂点を含まない二辺の和の値を全探索。
B 有向グラフ→ダイクストラ
C 二乗にはなったつもりだが高速化できず。oeisをずっと見ていた。
D 操作は、i行とi列に*-1することに言い換えられる。負の行があったら操作を行う貪欲を繰り返す。

— titia (@titia_til) January 11, 2026

C - ABS Ball 

　解説放送を見てAC。

　積の和典型と言われても全然ピンと来ないし、積の和典型の解法自体も忘れているしで全然ダメでした。

　というか、最初この問題を見たとき、積の和典型を使うのでは？　と思ったはずなのに、苦手意識があるせいか、そう思ったことを忘れてDPを考えていたのもダメ。もっと練習した方が良さそう。

AtCoder Beginner Contest 440 (Promotion of Engineer Guild Fes)

　ABCDFの五完。

コンテストへのリンク

コンテスト後のツイート

F SortedMultisetに感謝。丁寧さが1のmultiset、2のmultiset（Bとする）と、機嫌が良い上位len(B)個のmultiset Cと、それ以外Dとを持つ。len(B)の大きさに従い、Cの小さいものとDの大きいものを入れ替えながら計算。定数倍で1testcase通らず、似たコードをたくさん投げたら通った。

— titia (@titia_til) January 10, 2026

E - Cookies

　コンテスト中に書いていた方針でAC。

　コンテスト中、例題を解いた経験があると思ったが、実際正しかった（どの問題かは探せなかったけど）。そして、Aを降順にソートして、[K,0,0,0,0]からはじめて、一つずつずらしていく探索をすれば良い……という方針もできていた。

　ただ、コンテスト中は、Kの値が大きいことに混乱して、[K,0,0,0,0]のような配列で扱えると気付かず、Counterを持ち出していた。そのため実装でCounterのhashを求めなければいけなくなったりし混乱。

　そして、hash値を求めているのにその値を使い忘れたり、値が0のときはじくのを忘れたりしてWAが取れぬまま終了した。

　コンテスト中は混乱して、正しいことを書いているのか分からなくなっていたけど、落ち着くことさせできればコンテスト中に通すことも可能だった気がする。