yukicoder contest 475 (ゆるCafe)

　ABDEの四完。

コンテストへのリンク

コンテスト後のツイート

yukicoder contest 475 (ゆるCafe) ABDEの四完。
B -→0→1の順に状態が変化。DP
D 二分探索。(MIN+MAX)/2あたりが半分になるように調整。
E 深さがKに一度到達したかどうかで状態が変化。あとは深さをもってDP。

— titia (@titia_til) July 25, 2025

No.3211 NAND Oracle

　多少解法ツイートを見たけど、大体自力AC。

　「何度か操作したら、どの場合でも必ず0」という操作を手作業で探した。

　ただ、この方法だと1WAになり、実はQ=5、K=4の場合も構築できた。（これも手作業で探した）

No.3214 small square

　解説AC。

　平面走査を思いつかなかったのは本当に良くない。片方の座標を順に見ていき平面走査……というのは、こういう問題ではまず考えるべき解法でした。

No.3215 Make K types-able

　解説AC。簡単だと言っていたツイートを見たので考えたけれど自力で解けず。

　木を、ROOTとそれ以外の二つの部分に分割して考えるという方針が思いつけなかった。解説を見た後も、ベキ乗のmodに関する部分で詰まってしまい大変だった。

　

Order Capital Round 1 (Codeforces Round 1038, Div. 1 + Div. 2)

　Cまで三完。DとEはできなくてはいけない問題だったよう。

コンテストへのリンク

コンテスト後のツイート

D mod degでダイクストラを書いたけどWA。
E 右上と左下の組を考えればDPできると思ったがRE。

— titia (@titia_til) July 19, 2025

E. Greedy Grid Counting

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

　実装ミスがあったためデバッグは結構大変だったけど、コンテスト中考えていたことは正しかった。

　右上と左下のマスをペアで見ると、「左回りルートが右回りルートをいくつ上回っているか？」（これが0未満になるとダメ）が分かり、この値を持ってDPできる。

　この値は高々kなので、計算量はn*k*kで収まる。

　累積和を使えば計算量がn*kに落とせるはず……などと考えたのが時間を食った原因か（実際落とせるはず）。ただ、そのときは状態数がkより大きくなる（n*kになるのでは？）と思っていたから考えてしまったのだけど。

日本レジストリサービス（JPRS）プログラミングコンテスト2025#2（AtCoder Beginner Contest 415）

　全完して黄色復帰。良かった！

　一時期（今年はじめ～四月ごろ）、ABCで良いパフォーマンスを出すのがかなり難しくなった気がし、黄色に戻れるか不安に思っていたのだけど、ここ数回はそれほど厳しくない気もする。

コンテストへのリンク

コンテスト後のツイート

G 最初はa/bが一番良いやつを使って、その後DP。ABを枝狩りしないといけないことに注意。類題をyukicoderでやったはず……と探しにいったけど見つからず自分で書いた。

— titia (@titia_til) July 19, 2025

yukicoder contest 474

　A一完。

　10分以上Bを考えても何も思いつかず、疲れているんじゃないか？　と思い寝てしまった。起きたらすぐ思いついたので、本当に疲れていたのかも。

コンテストへのリンク

No.3204 Permuted Integer

　自力AC。

　コンテスト中は、「事前列挙するのは良いが、8桁の数を並び替えたら8!個必要だし……」などと考え分からなくなってしまった。

　今回は、sortした文字列で持っておけばOK。クエリ毎に調べる際も、その数字のstrをsortした文字列がどの数を作れるか？　と考えれば解ける。

No.3205 Range Pairwise Xor Query 

　自力AC。

　各bitごとに考えればOK。これは迷わなかった。

No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑

　大体自力だけど、どこかで全方位木DPというキーワードは記憶に残っていた。

　全方位木DPで検索し、このときの自分のコードを使ってAC。

　しかし、このコードのUPとDOWNが何を指しているか分かりにくくて時間がかかった。

yukicoder contest 473 第1回 生成AI作問コンテスト

　遅刻参加でEまで。

　AIでこれくらいの問題が作れるのか、という思いもあるけれど、実際に作ったときのプロンプトを見るとかなり苦労しているのが分かるので、現状だと、AIによって時間節約になるか？　にはあまりならないのかなぁ。

コンテストへのリンク

No.3200 Sinking Islands

　自力AC。

　後ろから見るのはすぐ分かったけど、何を求めれば良いか（後ろから見たときの答えの求めかた）が分からなくなり間に合わず。

　落ち着いて考えれば難しくないが、残り五分では解けなかった。……とはいうものの、五分で解けて良い問題だと思うので、ここで詰まったのは良くなかった。

No.3201 Corporate Synergy

　色々資料を見ながらAC。

　燃やす埋めるだと分かってからも時間がかかってしまった。

　特に「Aが赤でBが赤だとC円報酬」の形のときどうするかが分からず調べた（参考：ここやここ）。このときは頂点を追加すれば良いのね。

No.3202 Periodic Alternating Subsequence

　解説AC。生成AIが作った問題を解けなかったのは良くないねぇ。典型といえる内容だし。

　制約から行列累乗を使いそうとは分かるが、そこへもっていけなかった。つまり、K=1の場合のDPが構成できなかったということ。

　こういう、スコアが二乗の形で表される問題は、二乗という特性を使って何かすることが結構あるが、上手く使えず解けていないことが多い。とりあえず、l^2が(l+1)^2になったらどうなるか？　というのを式で書き眺めて見なくてはいけない。

ミラティブ プログラミングコンテスト2025（AtCoder Beginner Contest 414）

　Eまで五完。

　またレートを落としてしまったが、大失敗というわけでもないので……。

コンテストへのリンク

コンテスト後のツイート

F 子方向に何歩進めるか？　と、親方向へ進むものを別に管理しようとしたが上手くかけずTLE。
自分でも計算量が悪化してそう、と思って書いていたのでダメ。

— titia (@titia_til) July 12, 2025

F - Jump Traveling

　解説＆解説放送でAC。

　後一歩で解けたのではないか？　とコンテスト終了時には思っていたが、本質が分かっていなかった。

　ウニグラフのときの遷移の処理が難しいが、各頂点について、「その頂点についてk歩目に行く」というのは二回遷移してあれば十分、というのがポイントで、それで計算量を減らすことができる。

　言われてみれば分かるが、思いつきにくい計算量の減らし方だった。

　辺属性のDPを考えているとき、頂点の出入りで計算量を減らせる、というのは気付きにくい。

G - AtCoder Express 4

　解説放送を見てAC。

　「区間に辺を張るテク」は聞いたことはあった気もするが、内容は覚えておらず、今回初めて実装した。

　理解するのは難しくないが、実装は結構面倒くさいね。

Codeforces Round 1035 (Div. 2)

　Cまで三完。

　Cまでが遅かったのは集中力が足りなかったせいだけど、Dは普通に難しかった。

コンテストへのリンク

D. Token Removing

　解説AC。

　色々見たけれど、一番参考にしたのはmaspyさんの解説でした。

　（制約を見ると）二乗のDPっぽいことは分かるし、後ろから見ると良さそうとも考えた。しかし、そう思っても上手くいかなかったし、解説を理解するのもかなり時間がかかった。

　なんというか、問題を整理して把握する能力が足りてなさそう。

　とはいえ、（自分に合った）解説を読めば理解できるのだから、改善の余地はあるはず……。