週記(23/05/21)：七五三

今週のまとめ

• 下の子の七五三 前撮り
• ABC218バチャ。久々の黄パフォ相当
• ABC303で3度目の青に復帰

です。

(本文中にABC 123 D, 126 D, 218 C-F, 303 A-Eの解法を含む話題が出てくるのでご注意ください。)

5/21(Sun)

この日は下の子の七五三の前撮り。

私が七五三の時は足袋が嫌で大暴れしたという伝説^[1]30年以上経った今でも語り継がれている…を残してしまいその血を受け継ぐ我が子は大丈夫かと心配でしたが、ノリノリで着物を選んで終始ご機嫌でした。

七五三にちなんだ問題としてABC114「A – 753」がありますが、そのまますぎるのでお祝いネタでABC123「D – Cake 123」を解くことに。

二分探索か？と思いますが[math]K[/math]がそこまで大きくないので美味しさ上位[math]K[/math]個だけを保持しながら1, 2, 3の形のケーキの組合せを考えればOKですね。

5/22(Mon)

ABC218のバーチャル参加

全体的にスムーズに解け64分6完でパフォ2093相当。黄パフォが出るのは久しぶり。

「C – Shapes」は難し目。愚直だと間に合わないので#の位置を持ち端点を揃えて比較。

「D – Rectangles」は対角になる点の候補を[math]O(N^2)[/math]で列挙して長方形が作れるかを[math]O(\log N)[/math]で確認できるので間に合います。

「E – Destruction」は全体の報酬を出しておいて最小木＋マイナスの報酬で作ったグラフとの差分を求めればOK。これはすんなり。

「F – Blocked Roads」はサンプルを見ながら考えると最短路は高々[math]N-1[/math]本の辺しか含まないのがポイント。最短路中の辺は除いたうえで再度、最短路を求めても[math]O(NM)[/math]で間に合います。これも気づけばすんなり。

5/23(Tue)-26(Fri)

水Diffを解くか直近ABCのupsolveをして解いたのは

• ABC126「D – Even Relation」
• ABC126「E – 1 or 2」
• ABC302「G – Sort from 1 to 4」
• ABC139「E – League」

の4問。

印象に残ったのはABC126「D – Even Relation」で辺の長さが奇数だったら2頂点の色は変える必要があって必要条件で塗りきれるのでそれで出したらAC。

解説をみると任意の2頂点[math]u, v[/math]のLCAを[math]w[/math]とすると2点間の距離は[math]d_u+d_v-2d_w[/math]([math]d_v[/math]はrootから頂点[math]v[/math]までの距離)なのでrootからの距離の偶奇で色を塗ればOKと正当化できます。LCAは実装には出てきませんが考察の正当化として使えるのかーと目から鱗。

5/27(Sat)

45分5完パフォーマンス1872で三度目の青に復帰できました。

「A – Similar String」は片方が1でもう片方も1？はて？？と思ったのですが1(数字)とl(エル)、0(数字)とo(オー)を同一視なんですね。問題理解に時間を使ってしまいました。

「C – Dash」は移動、残体力判定、回復の順序を気を付けつつ愚直にシミュレーション。コーナーケースがありそうでちょっとドキドキ。

「D – Shift vs. CapsLock」は何文字目まで見たか、CapsLockのOn/OffでDP。

「E – A Gift From the Stars」は木をleafからDFSでたどると「Starのleaf⇒Starの中心⇒Starのleaf⇒別のStarのleaf」となります。

leafから親が中心かの情報を持ちながらDFSでたどって

• leaf⇒子は中心
• 親も自身もStarの中心ではない⇒子は中心

で中心の場所を確定させました。

終わってからTwitterを見ていると「leafからの距離 mod 3が1のノードが中心」や「次数が3以上なら中心で確定。残りはLevel=2のstar」でもっと簡単、簡素な実装で解けました。それぞれ本番中もチラッと考えたのですが詰め切れなかったですねぇ。

実力的に青Diffを本番で通せるかは五分五分より低いので水Diff以下は速く確実に解けるようになりたいですね。

関連記事

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