週記(23/04/30, 23/05/07)：ゴールデンウイーク

まとめ

ゴールデンウイーク中は水Diff練習くらいでのんびり
トレランで岩湧山へ
ABC288バチャ。95分イスを暖めて終わる
ABC287バチャ。出てたら冷えてた
ABC301参加。ちょっと冷えて水色に戻る

です。

(本文中にABC 113 D, 287 C-E, 288 D, 299 C, E, G, 301 C-Eの解法を含む話題が出てくるのでご注意ください。)

5/1(Mon)

ABCバチャをする予定でしたがGWの谷間でやる気がいまいち出ず？

強連結成分分解
行列の累乗計算

のスニペットの整備。強連結成分分解は実装が面倒な閉路検出ができて非常に便利。実装はこちらの記事を参考にしました。

昔、作った「閉路上での移動」（閉路部分をまとめて動かす）もまとめることできないかな？と思ったらドンピシャの記事がありこちらも参考になりました。

5/2(Tue)

ABC299「G – Minimum Permutation」は辞書順最小なので貪欲に。ですが、同じ数字が複数ありどう採用すればよいか考えては反例が見つかり…を繰り返して結局解説AC。

ただ、解説を見ても良く分からなくて、かんプリンさんの解説記事を見てようやく理解できました。

この絵がすべてで

かんプリンさんの解説記事より引用

「選んだ直後の要素」から「選んでいない数字で一番後ろに現れるものの先頭」の間の最小を求めればOK。図が秀逸ですね。

5/3-7(Wed-Sun)

1日1問ペースで水Diffを解いてました。

印象に残ったのはABC113「D – Number of Amidakuji」。順列の置換を管理するDPを書くとTLE。冷静に考えると求められているのは「1がKへ行くか？」だけなので1の位置だけ持つようにしてAC。

5/5にはトレランで滝畑ダム～岩湧山～紀見峠へ行ってきました。

秋のススキが有名ですが新緑もきれいで展望も良くリフレッシュになりました。

5/8(Mon)

ABC288のバーチャル参加

Cまで5分で解いて残り95分間イスを暖めて終わりました。D以降が異様に難しい回のようでこれでもパフォーマンス1522相当。

5/9(Tue)

ABC288「D – Range Add Query」は3時間以上かけてようやく解けました。

元の系列での区間加算は差分系列で考えると2点の+-になる
差分系列で間隔が[math]K[/math]の要素グループに分割して考える
操作に対してグループの総和は不変
元の系列を0にできるかは差分系列の各グループの区間和が0かどうかで判定可能

という考察を経て、実装も差分系列の区間和を出すのがまぁまぁ面倒で苦労しました。

青Diffになるのも納得でしたが、解説動画を見ると差分系列を取らなくてもできて

間隔が[math]K[/math]の要素グループに分割して考える
すべて0にできるかは各グループの区間和が同じかどうか判定可能

で、これだと実装が楽ですね。差分系列だとクエリで与えられる区間の両端の差分を出しなおす必要があって実装が大変だったのですが、これをやらなくて済みます。

5/11(Thr)

水曜に飲み会があり木曜は二日酔いで頭が回らずのんびり(笑)

5/12(Fri)

ABC287のバーチャル参加

94分(4WA)5完でパフォーマンス1232相当。

Dでサンプルは通るもののWAでバグ特定に時間＆WAを重ねた
EはSuffix array, Rolling Hashなど変に難しいアプローチで考えて時間を浪費

と反省点多めです。

「C – Path Graph?」は

次数1の頂点が2つで残りはすべて2

が必要十分条件かと思ったらWA。上の条件だけだと

もパスグラフと判定してしまうので連結性の判定も必要でした。

「D – Match or Not」はハマってしまいました。初期状態の設定がミスっていたのに差分計算部分が怪しいとずっとその周辺をいじって提出⇒WAをしてしまいました。

「E – Karuta」はSuffix array/Rolling Hashと色々考えて結局Rolling Hashで解きましたがもっとシンプルに解けました。無駄に時間をかけてしまったのは反省。

5/13(Sat)

ABC301の参加

35分4完でパフォーマンス1501で再び水色へ。Eは60分以上あったので解きたかった…。

あとDDoS攻撃の影響でB, Dの提出をした際にBad Gatewayになりました。2-3分後にリロードしたら提出/ACになっていたので結果的に影響はなかったですがTwitterを見ると

提出が届いておらずACだったが遅れた
リロードしたら複数回提出したことになりペナルティを複数回くらった

と影響が出ている方もいてて公平性という意味では難しい状況になっていますね。

「C – AtCoder Cards」は文字ごとにSなら+1, Tなら-1して過不足分を@で置き換え可能なら置き換えて最後に@が不足しないかをチェックしました。

「D – Bitmask」は上位ビットから貪欲に決めていけばよくてこれはすんなり。

「E – Pac-Takahashi」は

グリッド上でスタート、ゴール、お菓子間の距離を求めておく
スタート、ゴール、お菓子のみからなるグラフ上で巡回セールスマン問題を解く

という方針までは良かったのですがそこから手が止まってしまいました。

巡回セールスマン問題は文字通り巡回路を最小化するので始点、終点を固定する場合はどうだっけ？と悩んでしまったのですが、そもそも解き方として

巡回路なのでどこを始点にとっても良くノード0に固定
すべてのノードを訪問後にノード0に戻るための距離を足す

と始点を固定し始点以外のすべてのノードが終点になるケースを求めてますよね。ここで詰まるようでは頭が固いですね…。うーむ。

前週の週記: 「ABC300!」
翌週の週記: 「拡張整数ライブラリ」

週記(23/04/30, 23/05/07)：ゴールデンウイーク

まとめ

5/1(Mon)

5/2(Tue)

5/3-7(Wed-Sun)