yukicoder contest 503

　Eを考えていたが解けず、Cのみ一完。

コンテストへのリンク

コンテスト後のツイート

yukicoder contest 503のE、任意modでの掃き出し法か～と思って実装していたら、不定方程式の処理に困って解けなかった。
解説を見たら全然違っていてびっくり。ちゃんと考えないと……

— titia (@titia_til) July 3, 2026

No.3580 二成分の和

　解説AC。

　一目見て、連立方程式だから行列……と思ってしまったが、それが間違いだった。

　グラフの問題だと思えば、自然と、連結成分ごとに一つの要素の値を決め打つ、というのが思いつく。

　行列で上手くいかないと思えば、この解法に至るのがそう難しい気はしないんだが……。一旦思い込んだものを方針転換するのは難しい。

No.3581 分数対称差更新区間計数取得

　TLEが取れず、ChatGPTにPyPy→RUSTに変換してもらってAC。

　各クエリにおいて、変更すべき点が√i個に収まるので、BITで管理してACした。

　だが、解説を見ると、平方分割した方が高速になるらしい。言われてみればそういう高速化を要求されたことがあった。忘れていた。

yukicoder contest 480 (Gemini Tester)

　AB二完だが、BはHackされた。

コンテストへのリンク

No.3250 最小公倍数

　マージテクの練習問題だった。

　ただ、PyPyだとTLEし、PyPyで通している人もいなかったので、PyPyのコードをChatGPTにRUSTに翻訳してもらってAC。

　今はこういう翻訳もAtCoderでは禁止されているし、この問題はアルゴリズムの練習問題みたいなものだから、自力で書いた方が良いとは思うけど。

yukicoder contest 501

　A一完。

コンテストへのリンク

コンテスト後のツイート

yukicoder contest 501 AだけAC。
連続する数字をまとめて管理するようにしたら色々やりやすかった。

— titia (@titia_til) June 5, 2026

No.3566 Subsequence Sum

　解説AC。

　そもそも通常の部分列DPでK=1の場合を解くことができなかったのは反省。

　しかし、そこを理解しても難しかった。

　まず、部分列DPでNEXTを使わずにやる方法があることを知らなかった。それを行列累乗に持ち込むためにどういうコードを書けば良いかも分かっていなかった。

　勉強になった。

No.3567 Modulo Grid

　実験して、行の数が足りていればいけそうな解法と、ギリギリでも大体大丈夫な解法を作り、組み合わせることで無理矢理ACしたが、多分Hack caseがあります……。

　とりあえず、良いペアという条件が、gcd(a,M)%gcd(b,M)==0 or gcd(b,M)%gcd(a,M)==0と表せることだけは理解しておこう。（ACしたのにそれすらよく分かっていなかった）

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で持って探索した）。

No.3553 Good Quartet

　自力AC。

　実験すると、良い集合が実質四通りしかないことが分かるので、あとは実装を頑張る。

yukicoder 499 contest

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

コンテストへのリンク

No.3537 Thank You!

　解説AC。

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

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

No.3538 Not First Place

　解説AC。

　形式的ベキ級数を用いて立式するところまではできたが、その後の式変形ができなかった。形式的ベキ級数の練習が足りない。

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テーブルを使い回して解くという解法を忘れていた。結構汎用性がある解法のようなので、ちゃんと身に着けておきたい。

N - ナップサック

　この解説記事を見てAC。

　証明はよく分かってないが、「DP[j]を求めるのに、最大重量Bに対して、3*B*B/j個効率良いものを見れば良い」ということは押さえておく。

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が打ち消し合うというのはどこかで見たことあったと思う。

No.3529 2p Teleportations

　自力ACしたが非常に苦労した。

　サイクルに分解して何かするのだろう、というのは分かるが、そこからが難しかった。

　まず、サイクル長が奇数の場合は、2pと互いに素なことを利用して、全てをiの位置へ持っていくことができる。

　サイクル長さが偶数の場合、一般にはできないが、一つを除いてiの位置に持っていくことが可能。（ここの実装が意外と大変！　かなり混乱した）

　さらに、同じサイクル長さのものが複数ある場合は、サイクルを二つ並べて偶数番目を一つ目のサイクル、奇数番目を二つ目のサイクル、のようにすることで、全てiの位置へもっていける。

　よって、iの位置へもっていけないものは各偶数サイクルについて高々一つなので、

2+4+...につき高々一つ。これは√n未満という条件を満たしている。

　これは公式解説通りだったのだが、難しいし実装も大変だった。

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

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

コンテストへのリンク

No.3519 A/B問題

　自力AC。

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

No.3521 接線の傾き

　自力AC。

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

No.3522 冪乗乗

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

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

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

　B一完。CとDを考えたが分からず、Bだけ解いた。しかし、Cは解けなくてはいけない問題だった。　→　後にBはHackされたんですが……。

コンテストへのリンク

No.3513 Greedy Yokan Party

　解法ツイートを見てAC。

　答えで二分探索して、大きい方から二番目の長さがmid以上になるような、K個の分割があれば良いということは分かったが、その判定問題が解けなかった。

　が、落ち着いて考えるとこれはDPで解ける。0/1/2回mid以上のものを取ったときのindexまででの最大分割数を配列として持てばOK。

　DPで解けると言われればすぐに気付いたので、落ち着けば解けたはずの問題だった。

No.3514 Majority Driven Tree

　解説AC。

　木DPは考えたのだが、遷移の式などが上手く立てられず、全方位木DPが必要か？　などと考えてしまった。

　DPテーブルを二つ用意すれば解けるというのはびっくり。「親が既に塗られていると仮定したときのコスト」を用意すると上手くいくとは気付けなかった。

　二つDPテーブルを用意すると知った後なら、遷移を書くことは難しくなかった。

No.3515 Anti EIKO

　解法ツイートで行列累乗を使うと知ってしまったけど、大体自力AC。

　Kが小さいときはDPで求められることに気付けば難しくなかった。

　これは自力で解けたはず、と思う。コンテスト中、最初にこの問題を開いたのに、ちゃんと考えずに違う問題に行ってしまったのは良くなかった。

　

　

yukicoder contest 496

　Fを考えたが解けなかった。

コンテストへのリンク

No.3492 区間冪乗加算一点取得

　解説AC。

　まず、D<=100に気付かなかったのが敗因。だが、解説を見ても、なかなか理解できなかったのは良くない。内容的には、D<=100に気付いたなら解けなくてはいけない問題だった。

　ただ、D<=100でクエリ問題だからやることが決まってくるから解法に気付きやすいというだけで、(i+C)^Dののd次数目が、CやDが変わっても似た形で表せるというのは意外だった。立式をすれば分かることとはいえ、こういう観点で見たことがなかったので面白かった。

No.3493 等比数列の和の素因数

　解説AC。

　いまだにフェルマーの小定理やオイラーの定理があやふやなのが敗因。

　等比数列の和の公式を考えた後、オイラーの定理を使う方向で考察を進めなくてはいけなかった。ちゃんと立式して、落ち着いて考えるべき。

　

yukicoder contest 495

　BとEの二完。あとはFを考えていたが分からず。Eは上手い方法が分からず、a,b全探索でcの範囲を定め、その後、ミラー・ラビン素数判定法を使って判定、で通ってしまった。良かったのかなぁ。

コンテストへのリンク

No.3483 A Forbidden Fruit

　自力AC。

　自力ではあるのだけど、たとえば、「M個の中からr個選んだとき、外れ（の一個）が含まれない確率」が1-r/Mであることも計算しないと気付かなかった。

　確率について直感が働いてないなぁ。

No.3484 Just a Maze Game

　大体自力ACだが、Wと書くべきところをMと書いたり、W=5, 7だけ書いてW=3の場合を書き忘れたりと、ミスが多かった。

No.3486 Draw a Rainbow

　解説AC。

　最初解説を見て、ゼータ変換やメビウス変換を理解できていないから解けなかったのかと思ったが、実際はDPの方針が立てられなかっただけでした。反省。

　ゼータ変換やメビウス変換は、（今回のように集合に関するものの場合）bitごとの累積和やimos法なだけなので、全く恐れる必要はない。フーリエ変換と違って集合や約数の畳み込みは難しくない。（フーリエ変換はいまだに難しい……）

　なお、今回の自分の解答ではBitwise OR Convolution自体は使わず、DPとして累積和を取ったとき（ゼータ変換したときの値）をそのまま持って計算し、最後に一回だけメビウス変換を行った。

　集合に関するこのあたりの変換が分からなくなったときは、この問題のりんごさんの解説放送を見るのが手っ取り早いと思う。

　

　

yukicoder contest 494 オムニバス

　Cのみ一完。Dを最初に考えたが分からずCに行ったのだが、Dを分からなかったのはまずい！

コンテストへのリンク

No.3476 {2^n-1}-gon

　円の中心を含まないものを引く。

　円の中心を含まないものは、最も左の点を固定し、そこから半周以内にM個全てが収まっているようなもの。

　全体の個数も、引くものも二項係数で求められる。

　これ、概ね最初に考えた解法だったのだが、なんでNは2ベキ-1なんだろう？　とか、引く数はこれで良いのだろうか？　などと考えてしまい混乱。もっと落ち着いて自然に考えていれば解けたはず。

No.3474 Concat Decimal

　自力AC。これは普通に解けた。

　全ての(i, j)でなく、i<jなるペアのみなのがちょっと引っ掛けっぽいですね。

No.3473 AtCoder < CMS

　解法ツイートを見てAC。自力では分からなかった。

　2^M-1を含む場合を考えると、各bitごとに、0/1を割り振るもののうち、全て0を除いた場合の数と一致する。（ここが分からなかった！）

　あとは、2^M-1を何個含むか考えれば良い。

　式変形をすると二項定理が使える形になるので、それで計算すれば解ける。

　難しいが、解けないのはダメ。

No.3477 Yet Another LIS Triangle

　自力AC。

　これは簡単でした。

No.3478 XOR-Folding Primes

　自力AC。

　2,k,k+2という素数の三数がたくさなあり、その間を行き来するしかない。

　素数を列挙した後、行き先を考えてDP→行列累乗で解ける。

　Mまでにkが含まれるがk+2が含まれない場合、2→kみたいな行き方がありうると思ってしばらく悩んでしまった。このときは、P_iがk+2になるので、ありえないのですね。

yukicoder contest 493

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

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

コンテストへのリンク

No.3448 ABBBBBBBBC

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

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

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

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法

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

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。

　なお、これだけで良いことは、公式解説を開いても「帰納法などで証明可能」としか書いていなかった。現在も証明方針が分かっていないが、やろうとすれば自力で証明できるのだろうか（やる気はない）。

　

　

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。

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）を得ることはできそうですね……。後から気付きました。

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

yukicoder contest 286

　Cまで。

コンテストへのリンク

No.1425 Yet Another Cyclic Shifts Sorting

　自力AC。

　二種類あれば隣接要素SWAPができそうなので、答えは高々2。0回の判定は簡単なので、1回でできるかどうかを調べれば良い。

　一回でできるかどうかは、ソートした配列と比較し、最大値が一致していれば消していく。

　残った配列について、ソートしたものを巡回したものになっていれば良いので、ローリングハッシュを使って判定した。

　が、解説を見たらもっと簡単にできたらしい。なるほど。

　ところで、なぜタグが「動的計画法」なのだろう？　解けたと思った後タグを見たらそう書いてあって、何か間違っているのでは？　と疑心暗鬼になりながら実装した。

（タグに頼るのはいけないかもしれないけど、yukicoderのタグはいつも出したまま問題を考えています）

No.1426 Got a Covered OR

　解説AC。

　A_iが全て正、という条件の扱い方が難しい問題。

　包除原理で扱うのかな？　とは思ったものの、DPで包除原理でやるのかと考えてしまってダメだった。

・範囲を分割できること

・それぞれの範囲について、二項係数を使って計算していける

　ことに気付ければ解ける。

　bitの中で条件を満たさないものの個数で包除すれば良い。

　方針が分かれば難しくない。何で包除すれば良いかを考えるのが大切だった。

No.1427 Simplified Tetris

　解法は自力で分かったが、ACするのは苦戦した。

　盤面が与えられたとき、ちゃんと置けるかどうかは、この問題と同じ。

　なので、元の盤面の候補を全探索したい。

　ブロックが入っているマスの前後に何マスあるか？　をDFSで調べれば良さそうだが、何列必要かが分からない。高々2列で十分だろう、と思ったらWAで、3列必要な場合があった。

　そして、それで全探索するとTLEしてしまったため、ずるいけれど時間で打ち切る処理を入れてAC。

　解説を見ると、もっと上手にやる方法が書いてあった。気付かなかった。

yukicoder contest 490

　Gのみ解いて撤退。

コンテストへのリンク

No.3391 Line up Dominoes

　一応自力AC。

　DPで解く。DPで遷移したときの要素は区間和になることが分かるので、毎回累積和を取って流し込んだ。

　PyPyだとMLEになってしまったので、RUSTに直してもらいAC（コンテスト中だとできないが……）。

　解説を読むとPyPyでも普通にACできるようなのだが、よく分かっていない。

No.3392 Count 23578 Sequence

　自力AC。

　階差数列を考えると、回文の個数を数える問題に帰着できるので、Manacherを使って解ける。

　しばらく気付けなかったが、階差数列を考えると気付けて良かった。