週記(23/03/05)：卒園式

今週のまとめ

• ABC290バチャ。出てたら冷えてた
• 体調不良でダウン
• 下の子の卒園式

と体調不良で半分以上寝込んだ一週間でした。

(本文中にABC223 C, 290 D, E, Fの解法を含む話題が出てくるのでご注意ください。)

3/5(Sun)

水Diffの練習でABC_062「C – Chocolate Bar」を解きました。ABC223「E – Placing Rectangles」の記憶が残っててありうる長方形のパターンを列挙してAC。

3/6(Mon)

ABC290のバーチャル参加

33分4完でパフォーマンス1359相当。Eが難しくFはもっと難しそうで太刀打ちできず。

「D – Marking」も結構難しい。周期がLCM(N, D)/Dで1周ごとに始点が+1されるのを使ってK番目の位置を計算。合っているか不安で手でサンプルを追加して通しました。

「E – Make it Palindrome」は最初DPが使えないか？と思うも回文の性質上、先頭と末尾の要素に依存してうまく部分問題を導けず時間だけ過ぎる…。

ラスト20分くらいで

• すべて数字が異なる場合の操作回数を出す
• 同じ数のペアが何回カウントされるかを計算して差し引く

という方針にたどり着くもサンプルは合うが出すとWAになったところで終了。

振り返ると回文で要素を追加していくDPは筋悪なんですが、関係式っぽいのが出てきて何とかできないか？と時間を溶かしてしまったのは反省。

3/6(Tue)

昨日のEで愚直解と比較するも合う…あれ？と思い愚直解を投げるとTLEだけでなくWAも出る…。あーこれは…と思ってチェックするとやはりオーバーフローでした。

定期的にABCでもAHCでもオーバーフローを踏んで苦しんでいますね…。

「F – Maximum Diameter」も解けて面白い問題でした。[math]N=5[/math]くらいまでを書き出してみていると最大直径は「次数2以上の要素+1」なんですね。考えてみると次数2以上の頂点を横に並べてあとは葉を適当にくっつけると確かに最大になります。

次数の合計は[math]2(N-1)[/math]なので[math]N[/math]個に分割して「2以上の要素数+1」を数えれば良くて

[math]
f(X) = \displaystyle \sum_{k=2}^{N-1}(N-k+1){}_{N}C_{k}\cdot {}_{N-3}C_{k-2}
[/math]

になります^[1]かなり端折りましたが1を[math]k[/math]個、2以上を[math]N-k[/math]個となるような[math]2(N-1)[/math]の分割の仕方は[math]{}_{N}C_{k}\cdot … Continue reading。まずサンプルが合うことを確認して計算量を落としにかかります。ググって「ヴァンデルモンドの畳み込み」という使えそう式を見つけて[math]\Sigma[/math]を外すことに成功。無事通せました。

解説放送見ると「この形は畳み込みが使える形」で考察を終えていてて、この辺はまだ分かっていないのでそろそろ勉強したいところ。

この日の夜ごろから体調が悪化してダウンしてました。

3/11(Sat)

水～金は風邪で完全にダウン。

• 熱は39℃台まで上昇
• 頭痛
• 食欲がなくなり丸2日絶食

と結構重めの症状に苦しみましたが、土曜にはなんとか下の子の卒園式に出られるくらいには回復しました。

上の子も下の子も0歳から保育園に通ったので通算9年通ったことになります。

子育ては奥さんに頼り切りで頭が上がらないですが、数少ない分担の一つが保育園の送りで毎朝通ったこの道もあと2週間ですね。

少し寂しい気もしますが朝の時間に少し余裕ができるので4月からの生活も楽しみです。

関連記事

• 前週の週記: 「アルゴ青コーダへ」
• 翌週の週記: 「体調が…」