AHC中だったのでAだけ解いて撤退。
Bは読んで多少考えたので、すぐ解けたのなら解いていたと思うが。
No.3448 ABBBBBBBBC
解法は自力で分かったが、WAだったためテストケースを見てAC。
こういうのを合わせるのどうすれば良いんだろう？ 本番ならランダムテストを書いて頑張ると思うが、短時間で解ける気がしない。
割り算の感覚（商と余りなど）が重要そうだけど。
2026年2月27日金曜日
2026年2月25日水曜日
AtCoder Regular Contest 215
Cまで三完。良い成績とはいえないが、ARCで黄パフォを出せたのは久しぶり。
コンテスト後のツイート
B 各数字を0と1で塗り分け、数字が異なる間に仕切りを入れる。できるだけ同じ色にしたいので貪欲。
— titia (@titia_til) February 22, 2026
C (x,y,z)と(a,b,c)についてa>=x or b>=y or c>=zなら勝敗が付かないのでUnion-findでくっつける。くっつけたあと、(min(x,a),min(y,b),min(z,c))にして良い。x,y,zについてソートし大きい方から処理。
D - cresc.
解法ツイートを参考にAC。
Aの一つおきの配列が広義単調増加になることはコンテスト中に気付いていた。しかし、それだけだと重複があってダメ。
じゃあ、重複をなくすためどこか固定・場合分けすればいいのでは？ と考えるのが重要。
A[0]=0とした場合、A[1],A[3],...は全ての広義単調増加列を取りうる。
それ以外の場合、A[奇数]の最後の値がMにならなくてはダメ。なぜなら、A[偶数]を全てｰ1したものが同じ配列を作るから。
これで重複なく全て数えられているので、二項係数を使って計算できる。
初項を固定・場合分けする発想がもてれば決して難しくないし、重複をなくすためにどこか固定してみようと考えるのは自然。
今見ると難しくない気がする。
また、二項係数の何か（積か和か）になりそうなことはコンテスト中から見当がついていたし、実験コードも書いていた。
それで解けないのは、こういう二項係数を使う数え上げに苦手意識があるのかなぁ、と思ってしまう……。
E - CNOT Party
悩んだが自力でAC。
・最初にできるだけ0→1にする
のは最適そう。なぜなら、逆の手順をやれば1を0に戻せるので。
コンテスト中は、その後、今作ったトポロジカルソート順の逆順？ などと考えてしまいダメだった。
この後、
・1→0にする部分は別の問題
と捉えると分かりやすい。こう思いつくのが重要だった。
すると、B[i]=1のものは最後まで残ると分かるので、そこを根としたトポロジカルソートの逆順を考えれば良い。
ただし。x_i=y_iなるものがあればそれも起点になることに注意。
その順に1→0に戻していけば答えになる。
F - Scapus
自力AC。
直径は明らかに良いパス。
そこから考えると、直径上に通らなくてはいけない点が何点かあり、それを含む全てのパスが良いパスになると分かる。
あとは通らなくてはいけない点が一点になるかパスになるかで場合分け。
パスの場合は、二つの端点から距離xでいける点の個数は何個あるかを調べ、それらを足し合わせれば良い。これが畳み込みの形になり、FFTが必要になったのにはびっくりした。
一点の場合も同じなのだが、畳み込みの際の配列の長さを意識しないと計算量が落ちない。そこを気を付けて実装したらACできた。
実装は面倒だが、割合素直な発想で解ける問題だった。
AtCoder × Engineer Guild オンサイトコンテスト ～ACからはじまる27卒キャリア～予選 （AtCoder Beginner Contest 446）
全完できた。
簡単めの回とはいえ、全問解けると嬉しい。Gは想定の計算量ではなかったようだけども。
コンテスト後のツイート
F 可能かどうかは、max(fr,to)ごとに辺をもっておき、グラフを更新していく。可能な場所が増えたらDFS。消す個数は、iまでの頂点から行ける頂点を列挙。
— titia (@titia_til) February 21, 2026
G DPで更新する候補が多くなさそう。候補を持っておき、indexが進むごとに候補を減らした。次の場所をbisectで探したらTLE。bisectをなくしてAC
2026年2月18日水曜日
AtCoder Regular Contest 214
ABの二完。ARCで連敗が続く。
コンテスト後のツイート
AtCoder Regular Contest 214 AB二完。Dが解けず。
— titia (@titia_til) February 8, 2026
A 斜めを一致
B ある点を0とし一回計算すると、答えはそれらにxor xしたもの。各bitについて、立っている個数と立っていない個数を計算。元のN+1個と比較して、同じものは必ず使う。（十分性は分からず）
D 2ベキで作ろうとしたがN=13を満たせない。
C - Divide into 4 Teams
解説放送を見てAC。
コンテスト中、SUM/2の二つに分けることは考えたが、その後何も思いつかなかった。
ランダムテストを書いて実験すべきだった、ということはあるかも。SUM/2の二つに分ける方法と、答えとを比較したら答えが導けた可能性はあるね。
今回のSUM/2の二つに分ける方法みたいに、これを使いそうだと感じたのなら、とりあえずそれを求めてみて答えと比較して考えるのは一つの方針としてありそう。
D - Distinct Sum Grid Path
コンテスト直後にしばらく考えても解けなかったが、今考えたら簡単に解けた。
1から順に数字を作っていこうと考えるのは自然（コンテスト中も、まず考えたはずなのだが……）で、右上ルートより左下ルートが大きくなるようにしようとしたら自然に構築できる。
普段なら解ける問題という気もするので、あまり解けなかった原因を考えてもしょうがない気もする。
が、こういうのが解けるかどうかでレートには大きく差が出るんだよねぇ。
yukicoder contest 297
Bまで。コンテスト後にCをAC。
No.1520 Zigzag Sum
自力AC。
実験したらACできたが解説の考え方を再現するのは難しい。
No.1521 Playing Musical Chairs Alone
自力AC。
行列累乗が思い浮かべば難しくない。
一回遷移行列を間違えた（行と列を逆にした）けど、それでsample通るのね。
2026年2月17日火曜日
yukicoder contest 292
Cまで。Dはコンテスト後にAC。
No.1490 スライムと爆弾
自力AC。
簡単だったけど、
・各マスのダメージがいくつかを求めるためのimos法
・矩形のダメージの総和を求めるためのimos法
を両方やるので、二回累積和を取ることになるのが面白かった。
2026年2月15日日曜日
AtCoder Beginner Contest 445
Fまで六完。Gも解法はあっていた。惜しかった。
コンテスト後のツイート
G 二部グラフの最大独立集合だと思い、https://t.co/xw3a3nUvRfを参考に実装したが答えが合わず終了。
— titia (@titia_til) February 14, 2026
この前のARCでこの話が流れてたから思いつきやすかったけど、実装していなかった。
G - Knight Placement
フローした後、最大独立集合を求めるために色を塗るところで、色を塗った後間違ってもう一回初期化してた（塗った色を消していた）のが敗因だった。一行消したらバグは取れ、そのままだとTLEしたけどfloat("inf")を1<<63に直したりしたらACした。
（ただし、1<<30にしたらもっと早くなるかな？ と投げてみたらTLEしたので、運が良かっただけみたい。コンテスト中のACは厳しいかも？）
惜しかった……。
2026年2月7日土曜日
yukicoder contest 492
A一完。Bを考えているとき睡魔に襲われてしまった。
No.3441 Sort Permutation 2
自力AC。
index x→P[x]に辺を張り連結成分ごとに分解した後、その差のgcdがxなら、xの約数たちには連結成分-1をプラスする。
と、これが必要条件なのはコンテスト中に分かっていたが、それ以外にも答が増えることはありそうに思い、たとえば、「3 4 2 1」のとき2を使わないようにできるか？ と考えていた。
コンテスト後に実験してみると、結構簡単に使わずにソートできたので、上で書いた必要条件が十分性を満たしそう、と思って提出したらAC。
なお、これだけで良いことは、公式解説を開いても「帰納法などで証明可能」としか書いていなかった。現在も証明方針が分かっていないが、やろうとすれば自力で証明できるのだろうか（やる気はない）。
2026年2月2日月曜日
デンソークリエイトプログラミングコンテスト2026（AtCoder Beginner Contest 443）
Eまで五完でレートをまた下げる。
コンテスト後のツイート
デンソークリエイトプログラミングコンテスト2026（AtCoder Beginner Contest 443）Eまで。FもGも分からず。
— titia (@titia_til) January 31, 2026
B 愚直でOK
C シミュレーション
D 左右から更新
E ここに行けばその上全てを壊せる、というブロックがある。そこへたどりついたら、その上全てに行けるとして良い。
F - Non-Increasing Number
解法ツイートを見たら当たり前に感じたが、実際にACするのは結構大変だった。
最後に使った数字がxで、Nで割った余りがyのとき……というDPを考えるしかなさそう。
この(x, y)が被ってはダメ、という状況になれば状態数を抑えられる。そのためには、上の桁につけていくのではなく、下の桁に数字を付け足していけば良い！（桁DPで下の桁に足していくような発想ですね）
あとはDPの復元をすればOK。
なのだが、最小性を言うため、どの数字を使うか、という順番も大事。
普通にやればこの順番を満たすのだが、ソートしたりしてしまいハマった。
一桁のときは、
・[(1, 1), (2, 2), (3, 3), (4, 4),...]
となっており、これが一番上の桁なのだがから、
左から順番に、かつ次に使う数字が小さい順に探索していけばOK。
G - Another Mod of Linear Problem
解説放送を見てAC。
floor sumを使うと言われても、自力では全く分からなかったのでコンテスト中に解くのは厳しかった。
解説放送のように、X_k>C（定数）の場合を絵で理解できていることが大事な気がする。それが押さえられていれば応用できそう。
2026年2月1日日曜日
yukicoder contest 319
ABの二完。難しくないですか？
No.1715 Dinner 2
解説AC。
連続して同じ料理を食べてはいけないということから、二回の食事をまとめて行うことばかり考えてしまい、
・DP[j]＝最後にjの料理を食べたときの元気の最大値
という簡単なDPの立式を考えられなかった。
NとDが10^3以下という制約を見ても、自然なDPの立て方。これを思い付けないのはまずい。
No.1717 Levi-Civita Triangle
一応自力AC。
1と2が隣り合う状態は作れないと気付き、大抵の場合は0になるんじゃないか？ と思ったがそれだけではダメ。
実験すると、1になるパターン、2になるパターンは3種類ずつしかないと気付いてAC。
初手から実験すべき問題でした。
No.1716 Bonus Nim
自力AC。
普通のNimよりBobが勝つのは難しそう。
で、最初Bobは勝ちがないのでは？ と思ったのだけれど、sampleに一個勝つ例が書いてあり、真似っこ戦略なら勝てると分かった。
これ以外ないと予想し、AC。