minus9d

競技プログラミングに入門し続けています

[minus9d @minus9d]

ABC472に参加。なんと9ヶ月ぶり。E問題は適当な頂点から白と黒で順番に塗っていて同じ色が連続したら奇数長の閉路が見つかったことにできるところまではできたけど、効率よく閉路を出力する方法がわからず…

[minus9d @minus9d]

はてなブログに投稿しました
文鎮化したReadyNAS 102を復旧する - minus9d's diary https://t.co/DHZzkxUdzS
#はてなブログ

[minus9d @minus9d]

ABC432はA-Cで惨敗…
C: a個の飴を配るときにありうる重量はaX, aX+D, ..., aY (D = Y-X)なので、aX mod Dが全員の子供で一致するのが前提条件なのを見逃して1WA。
Dが全然解かれていなかったのでEへ。クランプ範囲の外にある個数は分かりそうだが、クランプ範囲の中の和の求め方の見当がつかず。

[minus9d @minus9d]

ABC429はA-Eの5完。ちょっとだけレート上がりそう。もう緑には戻りたくない…
B: 全部試したけど解説のように式変形すべきだった...
D: 累積和テーブルを用意してlower_boundで。頭壊れそうになりながらAC
E: S点からBFSで探索し、2個の頂点から到着した地点で探索打ち切り。ぎりぎりでTLEが取れてAC

[minus9d @minus9d]

E: ユーザ解説 https://t.co/Bi6XDwEayO と同じ方法（優先度付きキューなどで長さと本数の組を管理）。あまり悩まなかった
F: 新しく引こうとする線分の端点2点が連続するなら文句なくYes。そうでない場合は、線分の両側に並走する線分があればYes。と思ったがWA、原因不明

[minus9d @minus9d]

ABC424はA-Eの5完、本当に久々にまともな成績。
C: 新たに習得したスキルをキューに入れていく。
D: 盤面サイズが小さいので、前行の全塗りつぶしパターン2^Wと、現在行での全塗りつぶしパターン2^Wとの全組み合わせを見てdp。あえて白を黒に塗り替えるパターンも区別なく実装して効率的に書けた

[minus9d @minus9d]

D: 入店時刻 OR 退店時刻をpriority_queueで管理して動的なイベントソートを実装したつもりが、同じ時刻を複数回pushしてしまって1WA。手元でケースをいろいろ作って偶然気付けた

[minus9d @minus9d]

ABC423は4完、2931位… CとDでハマりまくりで、2完になっていてもおかしくない出来...
C: 愚直にシミュレーションしようとして2WA、最初と最後の連続するLOCKEDを無視してLOCKED * 2 + UNLOCKEDすればいいのではと思って1WA、初期位置が最初と最後の連続するLOCKEDにいた場合に対応してAC

[minus9d @minus9d]

ARC205はAの1完...
Aはすんなり2次元累積和に気づけてよかった。
残り時間はBに全ベット。手元でシミュレーションなどするが全然いとぐちが掴めず。。解説読んで目からうろこ。結果論だが早々にCに行けばよかった。
いよいよ緑落ちが現実のものになってきた

[minus9d @minus9d]

ABC419はA-Dの4完...
Eは、a_iとa_{i+L}のmodが常に一致すべきというところから前に進めなかったのだけど、コンテスト終了後にGemini 2.5 Proに解かせるとあっさりAC…この誘惑に抗えない人は一定数いてもおかしくない

[minus9d @minus9d]

生成AIルールに則って、E問題でPython→C++変換を初めて使ってみた。Fractionクラスの置換とか適切なコメント付けとかやってくれて、しかも一発で動いて素晴らしいのだが、「アルゴリズムが変化しないような変換」かは枝葉の部分では正直少し怪しかった

[minus9d @minus9d]

Geminiに教えてもらってやっと理解…賢いが、なんとか気づきたかった

[minus9d @minus9d]

ABC418、A-Cの3完でまた撃沈…
C: やるべきことはわかっても実装の手が止まってしまった
D: 手元で1にたどり着ける文字列を逆生成する実験はしていたので、"0"の数が偶数というのには気づくべきだったが気づけなかった。しかし気づいていてもDP力が残っていたかどうか…

[minus9d @minus9d]

E: 平行四辺形を2回カウントする対策の部分でTLEが取れず。解説を読んだが、なぜ中点を見るだけで重複排除できるのかわからない

[minus9d @minus9d]

ABC416はA-Dの4完...
C: C++で再帰全列挙が書けなくて、結局itertoolsでやり直す。文字列の長さが全部同じという誤った制約のもとに無意味な時間削減をしようとして1WA
E: WFで辺追加したときの改善幅を記録するという着想はできたもののTLE。「「上空」を表す頂点を追加」という発想は遠かった。。

[minus9d @minus9d]

ABC415はA-Dの4完、レート下落に歯止めかからず…。
Cの解法を思いつくのに時間がかかり、ビット操作と添字の操作にも戸惑ったのが敗因。Dはこんな貪欲でいいんかいなと出したら通ったのだけはよかった…

[minus9d @minus9d]

ABC413はA-Eの5完。Dはr=1/-1のコーナーケースに気付けず1WA。Eは愚直にスワップを繰り返して時間に間に合うか不安だったが通った。FはTLEが取れず時間切れ、終了2分後にset→vectorとするだけで通った…

[minus9d @minus9d]

ABC407はA-Cの3完...Dは全探索できないものだと思い込んで放棄。Eは前半と後半とに分けてそれぞれDPするのかと思いきや答えが合わず。分けるのをやめてDPするとTLE。配列再利用するようにするもWA&TLEで絶望...

[minus9d @minus9d]

ABC395に約60分遅れで参加してABCEの4完。
Dは、「巣aにいる鳩をすべて巣bにマージ」と最初誤読。誤読に気付いたあとも、ラベルだけ張り替える発想に至れなかった。。

[minus9d @minus9d]

ABC394はABCDの4完、、、
E結構考えても分からず、類題の https://t.co/Wm8nutnwzy に辿り着くも糸口掴めず。
Fは次数 4 の頂点は 1 つしか存在できないと誤読した時点で負け決定、、（全方位木DPで深さが長い子を最大4つ持てるように改造しようとしてた）