今月のまとめ
- 典型90を埋め始めた
- ABCは不調続き…「40才でも青コーダ！」目指すもレートは単調減少
- 暑くて死にそう
です。
(本文中に典型90の解法を含む話題が出てくるのでご注意ください。)
競プロ
先月はヒューリスティックコン祭りに踊った1か月だったので今月はアルゴメインで過ごしました。
今まで水Diff埋めをやっていたのですが飽きてきたので「典型90」を始めました。
1/3くらいを埋めた時にバチャが始まったので登録したのですが、進捗が可視化されて競争心がくすぐられますね。
バチャが始まる前に埋めた問題が未回答扱いになっていますが、★6があと1問、★7もあと6問まで来て順位も2位です。
以下、解説とは違う解き方をした問題のメモ。
「015 – Don’t be too close（★6）」
取り出す個数で場合分けすると妙に二項係数が現れるのでそこから答えをエスパー
「017 – Crossing Segments（★7）」
線分の端点[math](l, r)[/math]を
2次元平面にplotすると
となり黄色の線分と交差する線分は2次元平面上では長方形領域として表現できます。
ここから線分に対応する長方形領域の点の個数を数える問題になりLibrary Checker「Rectangle Sum」のコードを拝借して通しました。
「023 – Avoid War（★7）」
あるマスに注目したときに直前の[math]W+1[/math]マスのキングがあるかをbitで持ったDPで解けます…までは良かったのですが、その先がまだまだある問題でした。
MLE対策にダブル配列でもダメ(えぇぇ)で[math]2\times 2\times 2^{W+1}[/math]のdpテーブルにして1.8GB(上限2GB)に収めます。
さらにTLE対策にビット走査をアドホックに「1が連続する個所が2カ所[1]行をまたぐ場合に1が連続する可能性があります。2カ所以上あると必ずキングが隣接し解になりえないことを保証できます。以上あるbitは探索しない」を入れると7.7秒(上限8秒)でギリギリ通りました。大変だった…
「045 – Simple Grouping（★6）」
[math]K[/math]が10以下か大きいかで場合分け。前者はdfsで全探索、後者は[math]N[/math]個から[math]K[/math]個を選んでおいて残りをどこに入れるかを全探索。
「053 – Discrete Dowsing（★7）」
本質的には同じですがフィボナッチ探索で解きました。黄金比探索と比べ小数点が出てこないので妥当性が明確です。
「071 – Fuzzy Priority（★7）」
ヒューリスティックで押し切りました。[math]N\leq 10[/math]は全探索して前後関係を満たせるかチェック。
[math]N > 10[/math]は要素の前後関係を有向グラフで表して閉路があればNG。連結成分が2個以上あれば
1つの連結成分の間に別の連結成分の要素を順序を守りつつ入れると全体として前後関係を保てます。
面倒なのが連結成分が1つの時で連続する要素をrandom swapでは通らず
次数2以上で分岐しているところがあればその分岐先の要素たち(上図の赤枠部)を適当にswapして数列を作ると通りました。
「074 – ABC String 2（★6）」
愚直解を見ながら「末尾を変化」or「末尾より前をaaa…に変化させた後に末尾を変化」の2パターンを見れば良さそうなことをエスパー。
「089 – Partitions and Inversions（★7）」
suisenさんのRange Inversions Queryと尺取り法を使って通しました。
ABC
典型90埋めの成果を発揮！と言いたいところでしたが
- ABC309(バチャ): 41分5完(パフォ1496相当)
- ABC310: 15分3完(パフォ1232)！1年ぶりくらいに3完に沈む…
- ABC311(バチャ): 70分5完(パフォ1531相当)
- ABC312: 34分4完(パフォ1367)
とレートを溶かし続ける一か月でした。
今月40才になり40才になっても青コーダ！と言いたかったのですが
その道は険しそうです。
運動
さすがに7月になると夜でも暑くジョギングしてたら軽い脱水症になって危うく体調を崩すところでした（本末転倒…）
8月はさらに暑いので運動は無理せず食生活で節制するしかないですね[2]と言いつつAHC中は糖分補給をしがちなんですが。。
さて8/11から久々の長期コン「RECRUIT 日本橋ハーフマラソン 2023夏」があって楽しみですね～。今回は60位くらいまではオンサイト表彰もあって上位60位入りは実力的には厳しいですが、モチベーションの1つにして頑張ろうと思います。
関連記事
- 前月分: 「2023年6月: 短期AHCチャレンジは…」
- 次月分: 作成中
