Spectral::Cup 2026 Round 2 (Codeforces Round 1100, Div. 1 + Div. 2)

　Dまで四完。E解きたかったね。

コンテストへのリンク

コンテスト後のツイート

C2 index iについて、j<iなるA[j]はプラス、A[i]はマイナス、j>iはそのまま、としたときの最大値
D 答えで二分探索。混乱したけど、答えより小さいものを、答え以上のものより少なくしたい。
E 二乗なら解けるけど高速化できない。遷移先が区間になったりしないか、とかもらうDPなら、とか考えていた。

— titia (@titia_til) May 23, 2026

E. Deconstruction Tree

　解法ツイートなど参照してAC。

　コンテスト中に配るDPでのDPは書けていて、それをどう高速化するのかが分からなかった。ツイートで書いたことがあっていて、もらうDPにするともらう先が区間になり高速化可能だった。なんで正しいことを考察しているのに、答えに至れないのか……。

　ただ、その上で、答えが何か？　というところでもう一考察必要だった。頂点Nに対して、DPがどこから遷移するか？　というのをちゃんと考えなければならない。それが上手くいかず、結局コンテスト中に書いたDPとランダムテストでチェックしてACした。

　惜しくなかったわけではないんだけど、実際にACするには遠かった気もする。

東京海上日動プログラミングコンテスト2026（AtCoder Beginner Contest 459）

　Eまで。

コンテストへのリンク

コンテスト後のツイート

東京海上日動プログラミングコンテスト2026（AtCoder Beginner Contest 459） Eまで。F分からず。
B 良い書き方を思いつかず。辞書に26個入れた。
C SortedSetを使った。PyPyだとTLEしたのでcodonでAC。
D 奇数番目→偶数番目に、多いものから順に並べる。
E 木DP。二項係数に注意。

— titia (@titia_til) May 23, 2026

F - -1, +1

　解説放送を見てAC。

　操作を、「ブロックを右にずらす」というイメージで捉えられると考察が進みやすい問題だった模様。コンテスト中は差分をとって考えている時間が長かったけど、それほど筋が良さそうではなかったのだから、元の問題に戻って絵を描くべきだった。

Codeforces Round 1099 (Div. 2)

　ACの二完で過去最悪順位。青に落ちて呆然自失。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 1099 (Div. 2) AC二完。過去最悪の順位なんですが。
A 1 3 5 7...
B 分からず。
C min(A)<=2のときは、1や2への回数の小さい方。そうでないときは、どこで合流させれば良いか定まる。
D dfsで決定できる値を決定した後、nの小さい方から適当に決めて良いと思ったがWA。

— titia (@titia_til) May 21, 2026

B. Another Sorting Problem

　破滅した原因の問題。

　（多少解説を見たけど理解できなかったので）大体自力でAC。

　まず、i<jでA[i]>A[j]なら、iには足さず、jには足さない、しかあり得ないと気付かなくてはいけない。

　ここで、足すものと足さないものを分けて考える。

　足す方、足さない方それぞれは広義単調増加でないと条件を満たさない。

　index iが足す方だとしたとき、それ以降のことを考えると足す値はできるだけ小さい方が良い。それは、それ以前のmax-自分の値である。

　この最大値をkとして良い。

　kが決まれば、具体的に、A[i-1]>A[i]であるようなiについて、A[i]+=kする、というのを左からしていき、それで広義単調増加になるかチェックすれば良い。

　コンテスト中は、kを決めてからもう一回……というようなやり方が見えず、for文一回でどうにかなる気がして嵌ってしまった。

　ただ、解法自体は簡単だが、正当性の証明とか、直感的に理解するのは結構難しい気もする。

D. Maximum Prefix Sums

　自力AC。

　解法はあっていた。十分性をチェックしたらACできた。

　dfsするとき十分性をチェックしていたつもりだったが、漏れていたのね。

yukicoder contest 500

　Cまで三完。

コンテストへのリンク

No.3550 Another Rurumaru Function Problem

　自力AC。

　上のbitから順に見ていけばOK。これはすんなり解けた。

No.3551 Regions by Random Points 2

　自力AC。

　線分と線分が交差する確率が分かれば解けると思ったが、よく分からず。とりあえず、線分で分けられた円周の一方の長さをaとしたときの確率は2*a*(1-a)なので、これを積分してみたらsampleがあったので正解できた。

　公式解説通りだが、積分すればこの確率になる、というのがしっくりきていない。

　→二つの線分が交差するか？　というのは、線分の操作順によらないと気付いて納得した。

No.3552 Triangular Coloring

　自力AC。

　

　互いに辺で繋がっている三点が見つかれば、後はdfsして探していけば良い。

　その三点は、一点と、そこに隣接する点を選び、残り一点を全探索して見つけた（辺をsetで持って探索した）。

Educational Codeforces Round 190 (Rated for Div. 2)

　Dまで。Eは惜しかった。

コンテストへのリンク

コンテスト後のツイート

D (2,2)を使うなら、次の(3,3)まで行くか、それ以前に(3,x)があればダメ。各(a,a)について何回使うことにか係数を足していく。
E 不要なものを取り除くとPの昇順、Cの降順になる。tp,tcにより、どの範囲ならp+cになるとか、tp+d+cになる、とかが分かるので、p、c、p+cについてセグ木を立てる。

— titia (@titia_til) May 18, 2026

E. Minimum Influence

　コンテスト中のコードのセグメント木をSparse tableに変更したらAC。

　TLEしたときは試さなくてはいけないことの一つだったのに、全く思いつかなかった。反省。

AtCoder Regular Contest++ 220

　A一完でさらにレートを落とす。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest++ 220 Aしか解けず。
A 6の倍数xとx/2、x/3を利用すると、35以上は全て作れる。34以下で作れないものについては、約数列挙を利用して全探索&埋め込みした。
Bはグラフの問題になる気がしたが分からず。Cはindexの小さい順に決めるしかないはずだが解けない。

— titia (@titia_til) May 17, 2026

B - Incomplete Shuffle

　解説放送を見てAC。

　グラフの問題だろうとは思ったが、問題特有の考察は全くできていなかった。あまり考察せず解説を見てしまったけど、まずは、操作をした結果どのようなものが現れるか？　を実験してから考えていく感じですね。

C - Range Increment

　解説放送を参考にAC。

　解説放送を見ても（他の解説を読んでも）なかなか理解できず、一時間くらいじっと考えたらようやく分かった。

　解説放送に出てくるmod=3で1 0 1のケースより、（実質的には同じだけど）mod=6で1 5 1のケースを考えた方が自分には理解しやすかった。

　解法自体は、左から決めていくしかなくて、単純な貪欲で上手くいかないのなら、heapqか何かを使うかも……と想像することはできるかもしれない。しかし、こういう風な推察から正しい解法に至るのは結構厳しそうなので、じっくり問題の性質を見極めるしかなさそう。

D - Long Trail

　解説AC。解法ツイートを見て大体解法は把握していたけど、解説放送も見た。

　解法を思い付くのも難しいけれど、実装も大変だった。コンテスト中にACするのはなかなか大変な問題。

SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）

　Eまで。またレート1800を割る。

コンテストへのリンク

コンテスト後のツイート

SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458） Eまで。Fの12WAが取れない。何故！？
C Cの文字からmin(最初への距離,最後への距離)
D SortedMultiset
E 1313……が何回続くかで考える。
F Trie木のnodeを使って行列累乗。Aho-Corasick法で遷移行列を見つける。で良いと思ったがWA

— titia (@titia_til) May 16, 2026

F - Critical Misread

　コンテスト中の方針で大まかなものはあっていたが、どこでWAになるか分からず、ランダムテストでACしている提出と比較した。

　ミスは次のようなものだった。

　たとえば、"bcb"と"c"がある場合に、"bcb"が出たらそもそもいけないのだが、"bc"や"bcb"もノードとして数えてしまっていた。

　そのようなものを削る前処理を行ったらAC。

　Aho-Corasick法を使う場合に、必要になることが多い前処理という気がするが、知らなかった。

　そして、AIに聞いたところ、Failure_pathを利用して"c"に印がついているなら、"bc"にも印がつくようにする、という構築を行うのが一般的らしい。勉強になった。

Polaris.AI プログラミングコンテスト 2026（AtCoder Beginner Contest 457）

　F以外の六完で久しぶりの黄パフォ。Gは公式解法と違うので嘘解法疑惑があるけれど、多分大丈夫？→とりあえず、ランダムテストではHack caseは発見できませんでした。

コンテストへのリンク

コンテスト後のツイート

E [S:?]と[?:T]で詰める場合と、[S:T]と[S,T]に入る何かで詰める場合二通り考える。前者は開始位置、終わり位置を持って調べる。後者はセグ木を使った。
G 座標が小さい順に詰めていく。SortedSetで管理すれば、どのロボに入れられるかを二分探索できる。

— titia (@titia_til) May 9, 2026

F - Second Gap

　解説AC。

　コンテスト中、maxとsecondのindexを持てばDPできるのでは？　みたいなことは考えたのだが、上手く分からず実験をはじめて考察をやめてしまった。

　実験自体は悪くないのだけど、ちゃんと考察しないといけない。

　実際は、maxのindexだけ持ってDP（挿入DPみたいなやつ）できる。maxとsecondを持つDPが書ければ、そこに気付くのは難しくないはず。

　Gが解けたから助かったものの、こちらも解けなくてはいけない問題でした。

AtCoder Regular Contest-- 219

　Cまで三完だが、Aは嘘だった。DもEも思いつきにくい部分は思いついていたのだが。

コンテストへのリンク

コンテスト後のツイート

C 右端のエレベーターを使わない場合と使う場合とで場合分け。使う場合、その行を突っ切らない場合の最短コストを求めて大きい順にソート。二つまとめてW-1にできる。
D 実験したが分からず。
E 外周から順に構築していったが失敗。（WA6個）

— titia (@titia_til) May 10, 2026

A - Similarity

　文字列Xの01を反転させたものをX'とすると、S中にX'が含まれないなら、Xを答えとして良い。

　ACした提出は、Sの文字を全探索してそれを調べたが、Sの要素が全て対になっているとき、これではダメ。乱択などしなくてはいけなかった。WAが出たら気付いてACはできていたと思う。

D - Grid Game

　解法ツイートを見てAC。

　コンテスト中、（一次元での）実験により、

・(i+j)%2==1の箇所しか影響しない

　ことには気付いていた。

　また、（K+1）での余りを考えて良いことも分かっていた。

　しかし、判定条件が分からず、交代和などを考えて迷走。分からなくなってEへ行った。

　実際は、NIMと同じなのでxorを取ると良かった。

　NIMに近いのでは？　と考えたことはあったはずなのに、なぜ試してみなかったのか。悔やまれる。

E - Equal Distribution

　解法ツイートを見てAC。

★「oが偶数個とxが偶数個で作られた配列があったとき、その連続部分区間でoとxをちょうど半分ずつ含むものが存在する」

　を使うことはコンテスト中に気付いていたのに、全体のハミルトン閉路を取ることを思いつかなかったという。

　外周から距離０、1、２の順に、oがちょうど半分か、一個少ないか、みたいなものを取って構成しようとしていた。

　この方法でもできなくはない気がするけど、外周ではAが右半分に、次ではAが左半分に……みたいなときに連結性が保たれない。連結性を保つような取り方はあるはずだけど、若干実装の手間が増えるし、コンテスト中はそもそも反例に気付いていなかった。

　★が本質だと思うのに、★に気付いても違う方針へ行ってしまったのは痛い。

　一番の鍵となる部分は思いついて実装していたため反省点も見出しにくく、冷静にならないと……くらいしか言えないのも辛いところ。

yukicoder 499 contest

　Fを考えていたが分からず、Dのみ一完。

コンテストへのリンク

No.3537 Thank You!

　解説AC。

　どのカードを1にするか決めたら貪欲で良い……というのはコンテスト中から分かっていたが、それは簡単に求められないと思って迷走してしまった。（安い方からあるところまで貪欲に買った後、それ以降で個数が一番多いものを1にする、とすれば良いと思ったが嘘でした）

　二分探索を使えば、実装はやや難しいが普通に計算できた。これは気付かなくてはいけなかった。

Next DP Contest

　F以外の4点以下の問題は正解。後は部分点を拾った。もう少し取れないとまずい。

コンテストへのリンク

コンテスト後のツイート

I 大きい数字から見て、右端や左端に置くか？　で場合分け。二項係数で遷移できる。
K Aをソートしても同じ答えになるっぽい&大体連続した数になるのでは？　で部分点をもらえた。が、WAも出たので嘘か？

— titia (@titia_til) May 5, 2026

F - 集合 

　解説AC。テーマ一覧とArcAkiさんの記事を参考にしてAC。

　そもそも考察が難しい。

　最小値を使うか使わないかで考えると、その左側のみ、その右側のみ、両方を使う、で場合分けされるが、両方使う場合は最小値も必ず使わなくてはいけない。このことから、再帰を使って書けそうだと分かる。

　……という考察部分に全く気付けなかった。

　この考察通り、再帰で書こうとすると、Cartesian treeの順にやることになり、そこでは二乗の木DPを行うことになる、という流れ。

　テーマを見てしまっていたので、この考察が分かった後はすんなり書けたけれど、実際はその後の部分も簡単ではない気がする。

J - 個数と総和

　この問題と同じテーマというのを見てAC。

　「繰り上がりを持つ桁 DP」と呼ばれているのは知らなかった。

　類題をACしたときは理解していたのだろうけど、DPテーブルを使い回して解くという解法を忘れていた。結構汎用性がある解法のようなので、ちゃんと身に着けておきたい。

AtCoder Beginner Contest 456（Promotion of AtCoder Career Design DAY）

　Eまで解いたが、Eは分からず、時間をかけて無理矢理嘘解法を通した。レートが1800を割ってしまった。

コンテストへのリンク

コンテスト後のツイート

E N*W頂点のグラフにした後、サイクルの検出方法が分からなかった。WAが三つ出る嘘解法とTLEが三つ出る嘘解法を思い付き、組み合わせたらACはできたが明らかに嘘。
F 二つ連続で使わないことはありえないので、平方分割で解くことを考えていた。

— titia (@titia_til) May 2, 2026

E - Endless Holidays

　結局敗因はよく分からないけど、多分、サイクル検出すれば良い、と言われていたら解けた気がする。dfsしても良いし、SCCを使っても良いし、出次数が正の辺を消していっても良い。

　曜日の概念があったせいで、一般的な有向グラフのサイクル検出問題とは別の問題に見えていたことが敗因だった気がする。曜日1から始める……みたいなところをコードから消せると気付けていなかった。

　自分がどんな問題を考えているのか、もっと一般化した問題はないか、一般化したら問題は解けなくなくなるのか、といったあたりを意識したい。

F - Plan Holidays

　セグ木で解けると知ってAC。

　公式解説では、min-plus 代数などと難しいことを言っているけど、左右の端を使っているか、使っていないか、で4通り場合分けしてセグ木に乗せればOK。

　これも、セグ木で解けると気付かなかったことが敗因。

　多分、クエリが与えられて、[l,r]の範囲での答えを求めよ、と言われていたら解けていた気がする。

　その問題が解けるならこの問題も解ける、と気付くのが大事。

yukicoder contest 聖光学院プログラミングコンテスト2026 day2

　A一完で睡魔に襲われ撤退。

コンテストへのリンク

No.3527 Minimum Abs Sum

　解説AC。

　最初はCHT（slope trick）に見え、その後も、係数が一番大きいところなどと考えて失敗。

　係数が全て1のときの解法は知っていたし、

・abs(a*x+b)=a*abs(x+b/a)

　という式変形も見たことがあったはず。

　それにもかかわらず解けなかったのは反省。

No.3528 Happy XOR Candy

　自力AC。

　総xorが打ち消し合うというのはどこかで見たことあったと思う。

Codeforces Round 1095 (Div. 2)

　Cまで三完。レートがひどいことに。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 1095 (Div. 2) Cまで。Cで勘違いして時間を失い、Dが解けずに終わった。
A 1は他の数字と一緒に処理。
B 隣接二項を見ればOK
C 答えで二分探索。xはx/2未満もしくはxとして使えるので、xを優先して使い残りはソートして小さいものから使う。
D ずっと実験してた。まとめられず終了。

— titia (@titia_til) April 28, 2026

D. Reserved Reversals

　解説AC。

　コンテスト中、初手実験に行ったのは良かったと思う。

　そこで、min(A)とmax(A)の偶奇が違う場合は、必ずYESになる……などということは分かった。

しかし、そこから良い性質が見つけられなかった。

　ここで、「min(A)とmax(A)の偶奇が違う場合は、必ずYESになる」のはなぜか？　などと考えれば良かったのかもしれない。

　たとえば、「4 3 1」のとき、1と3を入れ替えられるのはなぜか？　と考えるべきだった。

　それは、4が使えるからである。

　そこから、3より大きい偶数、もしくは1より小さい偶数があれば入れ替えられそう……と気付く……という流れはそんなに不自然に思えない。

　だが実際はそういう風に思考できていないわけで。

　実験すると、一直線に答えが求まるのでは？　と考えて思考することが疎かになりがちなのが問題。実験して得た結果について考察することに失敗していることが多い。

yukicoder contest 498 リアクティブコンテスト

　C一問完。DやEを考えていたが分からなかった。リアクティブ（インタラクティブ）形式の使い方が斬新な問題が多くて良かった。

コンテストへのリンク

No.3519 A/B問題

　自力AC。

　結果的には公式解説と同じ方法でやっていたが、これが筆算と同じだと気付いていなかった。解説を読んでびっくり。

No.3521 接線の傾き

　自力AC。

　コンテスト中、結構考えて思いつかなかったのに、今見たらすぐに気付いた。平均値の定理は知っていたのにねぇ。

No.3522 冪乗乗

　公式解説が賢い。こういう式変形をぱっとできたら嬉しいね。

　ただ、tester解は思いつける内容だったので、できなかったことを反省。