AtCoder Beginner Contest 448

　Eまで。D・Eとも若干苦手な問題だったとは思うが、時間かかり過ぎてしまった。Eを飛ばしてFへ行った方が良かったか？

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 448 Eまで。D、E両方に苦戦して破滅。
C セグ木
D 座標圧縮してdfs。dfsは苦手意識があるが思いつけて良かった。（が、時間かかりすぎ……）
E mod 10007*M*9で上手くいった。行列累乗とか考えて苦戦。
F Moじゃダメだから2-opt焼きなましかなぁと考えていた。Moでいけるの？

— titia (@titia_til) March 7, 2026

F - Authentic Traveling Salesman Problem

　自力AC。

　コンテスト中、Moじゃダメだと思った理由は、MAX=2*10^7として、MAX√MAX>10^10だからダメだと思ったせいでした。

　MAX√Nと比較しないとダメですね。

　ただ、コンテスト後の実装でも、ミスで3ペナしてしまったので、コンテスト中にEを飛ばしていたら必ず通せていたとも言えなそう。

yukicoder contest 493

　AHC中だったのでAだけ解いて撤退。

　Bは読んで多少考えたので、すぐ解けたのなら解いていたと思うが。

コンテストへのリンク

No.3448 ABBBBBBBBC

　解法は自力で分かったが、WAだったためテストケースを見てAC。

　こういうのを合わせるのどうすれば良いんだろう？　本番ならランダムテストを書いて頑張ると思うが、短時間で解ける気がしない。

　割り算の感覚（商と余りなど）が重要そうだけど。

AtCoder Regular Contest 215

　Cまで三完。良い成績とはいえないが、ARCで黄パフォを出せたのは久しぶり。

コンテストへのリンク

コンテスト後のツイート

B 各数字を0と1で塗り分け、数字が異なる間に仕切りを入れる。できるだけ同じ色にしたいので貪欲。
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についてソートし大きい方から処理。

— titia (@titia_til) February 22, 2026

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に戻していけば答えになる。

AtCoder × Engineer Guild オンサイトコンテスト ～ACからはじまる27卒キャリア～予選 （AtCoder Beginner Contest 446）

　全完できた。

　簡単めの回とはいえ、全問解けると嬉しい。Gは想定の計算量ではなかったようだけども。

コンテストへのリンク

コンテスト後のツイート

F 可能かどうかは、max(fr,to)ごとに辺をもっておき、グラフを更新していく。可能な場所が増えたらDFS。消す個数は、iまでの頂点から行ける頂点を列挙。
G DPで更新する候補が多くなさそう。候補を持っておき、indexが進むごとに候補を減らした。次の場所をbisectで探したらTLE。bisectをなくしてAC

— titia (@titia_til) February 21, 2026

AtCoder Regular Contest 214

　ABの二完。ARCで連敗が続く。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 214 AB二完。Dが解けず。
A 斜めを一致
B ある点を0とし一回計算すると、答えはそれらにxor xしたもの。各bitについて、立っている個数と立っていない個数を計算。元のN+1個と比較して、同じものは必ず使う。（十分性は分からず）
D 2ベキで作ろうとしたがN=13を満たせない。

— titia (@titia_til) February 8, 2026

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通るのね。

yukicoder contest 292

　Cまで。Dはコンテスト後にAC。

コンテストへのリンク

コンテスト後のツイート

No.1490 スライムと爆弾

　自力AC。

　簡単だったけど、

・各マスのダメージがいくつかを求めるためのimos法

・矩形のダメージの総和を求めるためのimos法

　を両方やるので、二回累積和を取ることになるのが面白かった。