AtCoder Heauristic Cotest 014 解説(9位)
日記はこちらです↓
penguin46.hatenablog.com
結果
pretest 、システムテストともに9位
問題概要
格子点上に頂点を1つ追加して軸に平行or45度傾いた長方形を作ることを沢山繰り返してください。既存の頂点を通ったり、辺を共有するような長方形は追加できません。
解法
一部の長方形を削除して貪欲で再構築する焼きなましをしました。長方形を削除すると宙ぶらりんになる長方形が生まれるので、それらも削除します。*1
長方形の全列挙
各頂点から8方向に線形探索し、直角な2方向で別の頂点に到達したら、その3点を使う長方形が作成可能かを判定することで全列挙します*2。長方形を追加すると、新たに作成可能になる長方形が生まれるので、追加した頂点を使う長方形を同様の方法で探します。ちなみに作成不可能になる長方形も生まれますが、この判定は必ずしも必要ではないので、評価値が高く使用したくなった時に遅延評価するようにしています。
貪欲パート
作成可能な長方形をから、評価値が高いものから使用していきます。使用する評価関数は1回の貪欲につき下記の2つの内1つをランダムに選択します。テストケースによって長方形の大きさや頂点の密度が大きく異なるので、評価値はタプルで持ちました。前の要素の値が大きいほど評価が高いです。
- （4頂点の次数の和, 追加する頂点の重み)
- （-長方形の外周の長さ, 4頂点の次数の和）
次数の和：1つの頂点が複数の長方形に含まれてほしいお気持ちです
外周の長さ：外周が長いと長方形を追加する際の邪魔になるので短くしたいお気持ちです
頂点の重み：場合によっては次数とか外周を捨ててスコアを稼いでほしいお気持ちです
焼きなましパート
以下の4つの近傍を作成しました。いずれも連鎖的に削除された結果、状態が大きく変化してしまう場合があります。大きな近傍はacceptされにくいので、削除された長方形の割合と同じ確率でその削除を拒否し、貪欲を走らせずに状態を復元するようにしました。
- ランダムに長方形を削除。追加する頂点の重みと残り時間に比例した確率で長方形を削除
- ランダムな直線を1本引いて、外側にある長方形をすべて削除
- ランダムな点を選び、距離が一定値以下の範囲に含まれる長方形を削除
- 最終的に出力する答えから、インデックスがランダムな範囲にある長方形を削除します。
その他・感想
ビームサーチやバックトラッキングするDFSも試しましたが、スコアは伸びなかったです*3。焼きなましで長方形を削除しすぎていてほぼ貪欲になっていることに中盤まで気が付かなかったりしたりするなど*4、スコアが上がってもプログラムが想像通りの挙動になっているかを確認してギャップを埋めていくのは大事だと思いました。あと、AHCではテストケースを無限に生成すればハイパーパラメータに過剰適合することを簡単に避けられるので、Optunaなどを使ってきちんとチューニングすることも大事でした。他の70M台の方たちが何をしてるのか全く想像がついていないので、感想戦を楽しみにしています。
*1:実装では、削除前の長方形を前から順番に追加しながら、削除する長方形と作成不可能な長方形をスキップしました。この時、辺の重なりとかは気にしなくてよく、頂点が存在するかだけ調べればよいです。
*2:他にも「各方向に探索した時に最初に見つかる頂点」をメモ化したり、直線ごとに頂点の座標をheapqueuで管理したりしましたが、却って遅くなりました。恐らく、殆どの長方形はサイズが1x1などと小さいので線形探索が想像より高速なのかと思います。
*3:原因は同じ状態に到達するまでの経路が多すぎるためだと考察しています。試しにタブーリストを持ちながらバックトラッキングすると、若干（pretest換算で1.5M程度）はよくなりました。
*4:これに気づいて諸々の失敗した実験をやり直すと54M→65Mくらいまで上がりました
AtCoder Heuristic Contest 014 参加記
参加中に書いていた日記です。殆どコピペなので長いです。解説記事は追って書こうと思います。
内容を整理した解説記事はこちらです↓
penguin46.hatenablog.com
9/17（土）
- ルールを確認した。
- 頂点を増やしてスコアが下がることはない。
- 同じ頂点を追加しても長方形は一つに決めらないから他の3点も出力するのか。
- 操作の順序が影響する。
- 最終的にはビームサーチか、AHC013みたいな焼きなましになる？
- まあとりあえず貪欲だよな。
- AHC013みたいな焼きなましが出来る？
- 大きな長方形を作ってしまうと、その辺上が重なれなくなって状態が悪くなってしまいそう。
- 何も出力しなければ、50ケース 13.8Mくらい。
- いろんな場所から作り始めちゃうとかみ合わせが悪くなりそうなので、BFSっぽくやってみるか。
- 追加した長方形の近くの頂点をqueueに入れて、取り出した時に周辺の長方形を探した。[localの50ケース 28M]
- BFSだから見つかった順の貪欲になってるけど、他にもいろんなやり方がありそう。
- 最大クラスタを拡張していく
- 長方形が小さいものから置いていく
- 隣接する頂点が多いものから置いていく
- クラスタを大きくしていってもどこかで別の長方形を追加しないといけない。
- その時のかみ合わせはどうやって調整するんだ？？
- 完全になんもわからんだな。
9/18（日）
- とりあえず小さな長方形から順番に作っていくか。
- 大きさ1x1の長方形を追加→1x2の長方形を追加→...。[100case: 37M]
- 長方形の列挙が雑で70回くらいしか最後まで到達してないな。
- BFSの挙動がそれっぽかったので、同じサイズなら早く見つけた方を優先するか [100case: 38M]
- 小さな長方形から作るのは正しいと思うんだよな。
- 辺が共有できなくて使える辺の長さの総和が決まってるので、沢山頂点を増やしたければ小さな長方形じゃないといけない。
- 可視化してみたけど、最初から用意されてる頂点はほぼ使い切れてる。
- 連鎖的に頂点を追加していけるようにしたいが。
- スコアが中心からのユークリッド距離の二乗なので、個数を増やすより外側に置く方法を考えた方が良い？
- 長方形の列挙はO(K)でできるな。
- 各頂点について8方向を線形探索して、角度が90度な2つを使った3点で長方形を確定させて、違反してないか確認すればいい。
- 線形探索は重そうなので、直線ごとに二分探索すると良さそう。
9/19 (月・祝)
- 上の全列挙をやった。[LB 40M]
- まだ二分探索にしてないけど、プロファイラを見る感じ問題なさげなので後回し。
- 簡単にビームサーチにしてみるか。
- スコアを評価値にしたらスコアが下がった。
- 先を見越した評価値を作るのが難しいな
- 他のクラスタとかみ合うかどうかを評価するの、かなり難しそう。
- 絶対かみ合うようなパターンを用意してもいい？
- 見つからない。
- アルゴ緑～水でも45M出してる人がいるな。
- 天才パズルだったりするのかな
- これ、もしかして操作回数に上限がないか？
- 各頂点は次数8で最大4つの長方形で使えるけど、1つ長方形を作ると8消費するので±0。
- ということは次数を使い切れずに埋もれてしまった頂点が増えるほど苦しくなっていくのか。
- 埋もれたかの判定をできれば評価値に使えそう。
- この判定も難しいな。作成可能な長方形の中でその頂点を使っているものがあるかを見てもいいと思ったが、なんかいまいちな気がする。
- 逆に上手く使い切った個数を数えるなら簡単か。
- 「その長方形に含まれる頂点の次数の和」を評価値にした。[100case: 42.6M]
- ビームサーチでも試したけど、相変わらずスコアが低いな。
- AHC002のwalking on tilesみたいな感じで、追加できなくなったらバックトラッキングするのはどうかな。
- 外側に置いていく方針試せてないな。
- なんかうまいこと先読みして外に置けないかな。
- 「ここに置きたい」⇒「ここに置かないといけない」⇒「ここに置かないといけない」⇒「置けた！」みたいな。
- 再帰で殴ればいけなくもないのか？
- なんかうまいこと先読みして外に置けないかな。
- 根拠はないけど、天才焼きなましな気がするな。
- とりあえず長方形列挙を高速化した。[LB: 46.1M]
9/20（火）～21（水）
- 長方形列挙、直線ごとのリストでもって二分探索するやつやるか。
- ほとんど変わらないな。8方向あるから定数倍が重いのかな。
- twitterの900Kのseed0を見たけど、やっぱり頂点数が圧倒的に少ないな。まだ頂点を増やすのが大事らしい。
- 長方形列挙、差分計算できるじゃん。
- 良さげ。ここらへんで1回提出するか。[LB: 47M]
- 辺上に頂点を置くのはOKで、頂点上に辺を置くのはNGなので、先に大きな長方形を置いた方が良い？
- 特に1x1の長方形があとから置けなくなることはない。
- 依存関係がDAGになってるから、トポソすれば答えの順番はある程度弄れるのか。
- 弄って何になるかはわかんないけど。
- あれ、これ焼きなませるんじゃないか。
- テキトーな長方形と、それらに依存している長方形を削除してから貪欲で作り直す。[LB: 50.7M, 100case: 51.3M]
- ランダムな確率で長方形を削除した。
- テキトーな長方形と、それらに依存している長方形を削除してから貪欲で作り直す。[LB: 50.7M, 100case: 51.3M]
- 焼きなましの近傍をもっと追加してみる？
- ランダムな領域の長方形を削除する
- 答えをシャッフルする
- 連続したいくつかを削除する
- 直線の外側を削除する
- 全部上手くいかないな。なんでだろう。
- GA使えないかな。
- 別の解と良さげな部分をいいとこどりしたいお気持ち。
- 貪欲の評価関数を次数重視とスコア重視でランダムにした。[LB: 51.1M, 100case: 53.0M, 1000case: 51.6M]
9/22（木）
- 次数じゃなくて、隣接してる頂点の個数を使うとかは？
- 上がらないなー。密じゃないケースもあるしそりゃそうか。
- 諸々を高速化した。[LB: 53.8M, 1000case: 53.8M]
- 焼きなましの経過を可視化したら、殆ど全部の長方形が消えてた。
- 20%くらい捨てるだけで、殆ど全部の長方形が消えてる。
- 確率を小さくして、さらに時間経過も小さくした [LB: 57.3M, 1000case: 56.9M]
9/23 （金・祝）
- 少し前にやったこと、削除する確率が大きすぎて機能してなかっただけな説ある。やり直すか。
- 焼きなましの近傍
- 長方形を切り抜く [1Mくらい向上]
- 直線の外側を消す [4Mくらい向上]
- 外側を優先して消す [1.5Mくらい向上]
- 連続したいくつかを削除 [ほぼ変化なし]
- 焼きなましで一定回数改善されなければベストからやり直すやつ。[1Mくらい向上]
- 貪欲の評価値
- スコア重視の評価値 [悪化]
- 評価値を見ないでランダムに詰める [悪化]
- 焼きなましの近傍
- とりあえず一通りやり直せた。 [1000case: 64.7M]
- スコアが改善されそうなところを集中的に破壊したいな。
- 大きな長方形を優先的に削除するとか [悪化]
- 次数が小さい長方形を優先的に削除するとか [悪化]
- N, Mで結構スコアが変わるので、焼きなましの温度も調整した方が良い？
- あんまりうまくいかないな。
- 5倍の時間実行したら、100caseで70.3M出た。
- 10倍実行したら72.3M。
- 高速化頑張るか。。。。。
9/24（土）
- 一部不要な判定を削除した 。[LB: 66.0M, 1000case: 64.7M]
- なんもわからんな。あと一週間あるのやばすぎる。
- 結構時間かかるしoptunaで焼きなましの温度チューニングして今日は別のことするか。
9/25（日）
- 真心チューニングと全然違う温度だ。[LB 67.9M, 1000case: 67.0M]
- なんもわからん。スプラ楽しい。
- 結局研究とスプラしかしてないじゃん。土日。。。かえして。。。
9/26（月）
- スプラ楽しい。
9/27（火）
- 気合い入れるためにchokudaiさんの根性論の記事読み直すか。
- 焼きなましのスコア遷移。赤は貪欲回しただけのやつ。
- 密度が低いケースで結構な悪化がacceptされてるな。
- 温度を下げたけどスコアは悪化したので、温度の問題ではなさそう。
- 頂点が少ないから1つの頂点の重要度が高くて簡単にスコアが下がりやすいだけなのかも。
- とりあえずここは問題なさそう。
- 密度が低いケースで結構な悪化がacceptされてるな。
- 削除された長方形の個数と、スコアの悪化量の関係
- 長方形が沢山消されると殆ど改善されてないな。
- 多く消されると貪欲も時間がかかるし、捨ててしまってもいいかも。
- 悪化した。大きな変化をする近傍は必要か。
- でも割合は減らした方が良いよな。残り時間の割合より多ければ捨てた。[LB: 68.5M, 1000case: 68.1M]
- 久しぶりの向上だ。。。！
9/28（水）
- 長方形列挙、同じ線分を2回見てるから、配列にメモすれば2倍以上速くなる？
- というか線形探索の結果も、「その方向に最初に見つかる頂点」を差分計算すればいいのか。
- 悪化した。1x1とかの長方形が多いから効果ないのかも。
- 1位が76Mとかだから、高速化以外の改善もあると思うんだけどな。
9/29（木）
- なんもわからん。
9/30（金）
10/1（土）
- 昨日の提出、温度を間違えてた。[LB: 70.6M, 1000case: 70.0M]
- 今までやったこと見直すために、解説記事書いた。
- 悪あがきしたけど特に成果なし。
2021年の振り返りと2022年の目標
はじめに
年末なので、今年1年間の振り返りをして、来年の目標を立てようと思います。振り返りは具体的なsolutionとかは書かず、当時のお気持ちを思い出として残す感じにしようと思います。（なので特に有用なことはないと思います。）
AtCoderで青色になる（~1/23）
今年の初めに、AtCoderで目標にしてた青色になれました。この時の振り返りは以前別の記事にまとめました。色変したコンテストではA~E問題をまとめて提出したのですが、5問とも一発でAcceptedされ、脳汁ドパーだったのが一番記憶に残ってます。
penguin46.hatenablog.com
Indoorコンペ参加（~5/17）
競プロ以外にもいろんなことをしたいと思い、競プロを中断してKaggleを始めました。このコンペでの目標はとりあえずメダルを取ることだったのですが、序盤～中盤は本当になにもわからず、公開notebookを弄って銅と銀のボーダーくらいにいました。1か月くらいひたすらEDAをするも、独自のアイデアで精度を伸ばせておらず、辛すぎて撤退してしまいそうにもなりました。
これは逃げ。あと1ヶ月もあるんだからなんとかしよう https://t.co/sZ2KcdziN2
— penguin46 (@ryota_cpp) 2021年4月19日
その数日後、ふと思いついたアイデアを試してみると50cmくらい精度が上がりました。やったことはパラメータを調整しながら後処理を繰り返しただけなのですが、順位が48→13位まで一気に上がって、競プロでACしたような嬉しさがありました。
その後、コッコさん、tuboさん、ころんびあさんの3人とチームマージをしていただけることになり、4人で残り期間を走りました。3人が機械学習パートをやってくださり、僕はずっと後処理芸人をしていました。知識量に差がありすぎて、後処理でも貢献できなかったらどうしようと震えていたのですが、その後もいくつかのアイデアが当たってくれたのでなんとか耐えました。
最終的にprivate 15位（銀メダル）でfinishしました。金メダルには届かなかったのですが、そばで皆さんがどんな風にモデルを作っているのかを勉強させていただき、とても貴重な機会をいただけたと思っています。Kaggleの楽しさを感じることができたコンペでした。
チームAlgorithm is All You Need、銀メダル獲得しました！！！！！！！！
— penguin46 (@ryota_cpp) 2021年5月18日
チームの皆さん、本当にありがとうございました！！！
めちゃくちゃ楽しかったです！！！！！ pic.twitter.com/wzPphGnT6k
Outdoorコンペ参加（~8/4）
Indoorが終わるとほぼ同時に位置推定コンペが来たので参加しました。序盤からIndoorでのチームメイトのtuboさんところんびあさんとマージしました。コンペ終盤にChrisさん、Saitoさんとチームマージをしていただき、private5位（金メダル）でfinishしました。
序盤から衛星測位に取り組んではいたのですが上手くいかず、簡単に精度が伸びる後処理に多くの時間を使ってしまいました。蓋を開けてみればドメイン知識が非常に重要なコンペで、戦略を見誤ったことを反省しています。このようなよく研究されたタスクでは、一般的な手法をきちんと調査するべきでした。
ころんびあさんが追実験をしてくださったのですが、ホストのベースラインに対して3人(penguin, ころんびあ, tubo)の後処理をしただけでは13位相当のスコアだったようです。私たちの後処理ではドメイン知識を一切用いず、kNNやLightGBMを使い機械学習ベースの外れ値判定などを実装したのですが、金圏のスコアを出すにはドメイン知識が必須でした。ChrisさんとSaitoさんのおこぼれで取れた金メダルでした。
outdoor5位でした！！！！
— tubo (@213tubo) 2021年8月5日
チームメイトの皆さんありがとうございました！
次位置推定コンペ来たら必ず優勝します🔥🔥 pic.twitter.com/GTRfhokvgs
NFLコンペ参加（~11/2）
ラスト1か月で同級生のTK、ラスト2週間でAriyasuさんとチームマージをしていただき、private12位（銀メダル）でfinishしました。
競プロで学んだAffine変換やハンガリアン法の知識があったので、序盤からラスト1か月まではソロで金圏上位に居座れたのですが、終盤アイデアが尽きて失速してしまいました。金メダルに届かなかった敗因は、機械学習の知識が乏しかったことと、スコアの評価が甘かったことだと思っています。特にスコアの評価に関しては、序盤から終盤までを通して、大量の実験をしたことで偶然CVが微増したアイデアをいくつか使ってしまったのがまずかったのだと考えています。（多重比較問題というらしい？）
いやー惜しかった。優勝したK_matさんおめでとうございます！日本人同士のチーム戦めちゃめちゃ楽しかった、チームメイトに感謝 pic.twitter.com/LdXYo7kBqF
— Aryyyyy (@aryyyyy221) 2021年11月3日
振り返りまとめと来年の目標
IndoorとNFLであと少し金メダルに届かなかったり、Outdoorでは(少なくとも金メダルを貰うに値するほどには)貢献できなかったなど、たくさん悔しい思いをし、反省しないといけないことばかりの1年間でした。
それでも、AtCoderで青色になれたり、チームを組んでくださった皆さんのおかげでKaggle Masterになれたり、ころんびあさんやtuboさんとはコンペ後も数理最適化の輪読会をしたりと、沢山嬉しいことや楽しいことがありました。ありがとうございました！
来年の予定ですが、諸事情で2月ごろまではまとまった時間が取れそうにないので、3月からKaggleに集中できるよう、それまではTOEIC、卒論、過去コンペの復習（直近2~3年分）に取り組もうと思います。来年の目標はKaggleで金メダルを2枚取ることです。来年もよろしくお願いします！
AtCoderで青色になったので2年間を振り返ってみた
はじめに
1/23のABC189で、青色になることができたので、例に倣って色変記事を書いてみました。少しでも誰かの参考になれば嬉しいです。
AtCoderとは
AtCoderはプログラミングコンテストを開催しているサイトです。ほぼ毎週コンテストが開催され、約1万人程度の参加者が参加します。問題が6問ほど出題されるので、データ構造やアルゴリズム、数学などを使って解法を考え、その解法を実現するプログラムを作成することで競います。
レートに応じて色が割り振られ、下から順に灰・茶・緑・水・青・黄・橙・赤となっています。各色の詳しい評価は下の記事に書かれています。
chokudai.hatenablog.com
競技プログラミングを始めるまで
某地方国公立大の電気情報系の学科に通っています。大学入学前はプログラムを書いたことも見たこともありませんでした。他の方の色変記事を見るに、恐らく青色になった人たちの中では平均～少し多いくらいの精進量ではないかと思っているので、天才や化け物の類ではありません。
大学が始まるまでの春休みにプログラミングを始めてみたいと思い、DXライブラリでSnakeや2048、テトリス等の簡単なゲームを作ってみました。プログラムのロジックを考えることや、計算した結果が画面に出力されることはとても楽しかったのですが、正直Unityなどで本格的にゲームを作ることには興味を感じられませんでした。
その後、同じ学科の友人に競技プログラミングに誘われて始めて見たところ、好みにドンピシャで、楽しすぎてやめられなくなってしまいました。
茶色になるまで(～1回生7月)
自分の書いたプログラムが動いて結果が出てくるのが楽しくて、ABCのA～B問題をたくさん解いていました。文字列の扱いにかなり苦戦していたのを覚えています。
ちなみに、初めて知ったアルゴリズムは累積和でした。友人に教えてもらい、すごく感動したのを覚えています。その他、灰色の間に勉強した内容は以下のものがありました。
| 配列 | ソート | 累積和 | bit全探索 | ナップサック問題 | 幅優先探索 | 深さ優先探索 |
茶色になるまでに解いた問題数です。(その他はdifficultyのついていない問題、CFはCodeforcesの略です。2021年1月25日時点の問題数を母数としているので、割合は当時のものではありません。)
| diff | 灰 | 茶 | 緑 | 水 | 青 | 黄↑ | その他 | CF | 合計 |
|---|---|---|---|---|---|---|---|---|---|
| AC数 | 217 | 11 | 5 | 2 | 0 | 0 | 9 | 0 | 244 |
| 割合 | 40% | 6% | 3% | 1% | 0% | 0% | - | - | - |
緑色になるまで(～1回生10月)
コンピュータについて全く無知でしたので、情報の分野全体の広い知識が欲しくて、夏休みはIPAの応用情報技術者試験の勉強をしていました。AtCoderのおかげで、午後のプログラミングの問題がとても楽になりましたし、逆にこの資格の勉強のおかげでデータ構造の理解が進んだこともありました。
10月ごろ、他大学の競プロ仲間ができて、お互いに作問した問題を解き合ったりしていました。作問は理解が深まるので、とてもお勧めです。そこのメンバーが異常精進をして信じられない速さででレートを上げているのを見て、「強い人はこんなに精進しているのか！」と、とても良い刺激を貰いました。
この頃は基本的には灰～茶diffをひたすら埋めながら、時々蟻本初級編の類題を解いていました。
qiita.com
緑になるまでに勉強した内容とAC数は下の表のとおりです。
| 逆元 | 二項係数 | GCD, LCM | 約数列挙 | 素数判定 |
| 素因数分解 | 素数列挙 | 二分探索 | 尺取り法 | imos法 |
| 繰り返し二乗法 | 拡張Euclid | 凸包 |
| diff | 灰 | 茶 | 緑 | 水 | 青 | 黄↑ | その他 | CF | 合計 |
|---|---|---|---|---|---|---|---|---|---|
| AC数 | 294 | 78 | 30 | 3 | 0 | 0 | 9 | 0 | 414 |
| 割合 | 54% | 42% | 16% | 2% | 0% | 0% | - | - | - |
水色になるまで(～2回生6月)
緑diffを埋めたり、引き続き蟻本初級編の類題を埋めていました。レートが1000を超えたあたりからは、水diffで解けそうな問題を解いたり、蟻本中級編や下のサイトの問題を解いていました。コンテストでは緑diff以下を速解きして、たまに来る水diffの数学問題をACすることでレートを稼いでいました。
qiita.com
水色になるまでに勉強した内容です。
| 集合 | 多重集合 | 連想配列 | 順列列挙 |
| 優先度付きキュー | 二次元累積和 | Union-Find木 | ダイクストラ法 |
| ベルマンフォード法 | ワーシャルフロイド法 | 順列列挙 | 3分探索 |
| トポロジカルソート | 半分全列挙 | LCS | LIS |
| diff | 灰 | 茶 | 緑 | 水 | 青 | 黄↑ | その他 | CF | 合計 |
|---|---|---|---|---|---|---|---|---|---|
| AC数 | 473 | 157 | 147 | 88 | 27 | 3 | 43 | 0 | 938 |
| 割合 | 87% | 84% | 81% | 45% | 13% | 1% | - | - | - |
青色になるまで(～2回生1月)
青は化け物だと思っていたので、この時点で競プロをやめようかと思っていたのですが、レートが伸び悩むまでは続けてみることにしました。
この時点での強みは、
- 緑diff以下の問題の解法を思いつくまでが速い
- 算数・数学的な問題が少し得意
という点でした。逆に弱みは、
- 精進時間が青を目指す割に少ない
- 実装をバグらせて時間を溶かすことが多い
- コーナーケースを見落とすことが多い
- 高難易度を解く考察力が身についていない
という点でした。コンテストで事故ってレートを大きく下げてしまうと、取り返すのに数週間～数か月かかってしまう上に、何よりモチベーションが失せてしまうことが怖かったので、特に弱点を克服していく感じで精進していきました。
まず、精進時間に関しては、Twitterの精進用アカウントを作って、生活に競プロを侵食させていきました。また、某ウイルスの影響で大学の講義がオンライン授業になり、1週間のどこでかで課題を提出すればいいという感じになったので、月・火(・水)曜日くらいに課題を一掃して、水～日曜日は出来るだけ競プロに集中するようになりました。
2・3番目の実装力に関しては、JOIの過去問を解いていくようにしました。JOIの問題は実装が重たいものが多いため、実装力を付けるのに向いています。僕の場合、実装をバグらせる主な原因は、頭の中で考察をして紙に整理しなかったり、「いける！」と思ったらコードを書きながら考察をしてしまうことでした。実装をバグらせることが多いと思ったら、コードにする前に考察を紙に整理すべきだと思います。「コードを書いている途中に考察が間違っていることに気が付いた」ということが減りますし、細かい条件分岐やコーナーケースにも注意しやすくなります。
4番目の高難易度の問題に関しては後述していますが、週に何問かだけでも青diffを埋めていくようにしました。最初は全然解けませんでしたが、次第に自力でACできる割合が増えていくのが実感できました。また、今まで勉強しなかったデータ構造・アルゴリズムもとにかく貪欲に勉強していくようにしました。
その他には、AtCoder Problemsの「くじかつ」という毎日夜9時に開かれているバーチャルコンテストに出るようにして、速解き力を鍛えたり、AtCoderの解説放送や、YouTubeでの実況、他の方の解説ブログなどを見たりもしました。特に解説放送や実況では、強い人がどんなことを考えて問題を解いているのかを説明してくれるので、とても学びが多かったです。
これらを続けると順調にレートが上がっていきましたが、11月ごろにレートが1500を超えたあたりで伸び悩みました。
典型はある程度揃っていると思っていたので、とにかく場数と演習量を増やそうと思い、Codeforcesというロシアのコンテストサイトに出たり、Educational Codeforces(通称エデゥフォ）という教育的な問題を集めたセットを埋めていくことで、無事に青色になることができました。Codeforcesは深夜にコンテストが開催されるのでおすすめはしにくいのですが、大学がオンライン授業になって、「俺が起きている時間が昼なんだ」などと考え始めている人は是非参加してみるといいと思います。
青になるまでに勉強した内容です。
| Grundy数 | 座標圧縮 | 平方分割 | セグメント木 | 遅延評価付きセグメント木 |
| 転倒数 | 分割数 | 行列累乗 | ダブリング | ポテンシャル付きUnion-Find木 |
| 括弧列 | 包除原理 | フロー | 最小全域木 | 最大安定集合 |
| 2部グラフ | Euler Tour | TSP | Z-algorithm | Kadane's Algorithm |
| 区間DP | 桁DP | 木DP | 全方位木DP | Binary Indexed Tree |
| Splay木 |
| diff | 灰 | 茶 | 緑 | 水 | 青 | 黄↑ | その他 | CF | 合計 |
|---|---|---|---|---|---|---|---|---|---|
| AC数 | 546 | 186 | 182 | 181 | 116 | 11 | 196 | 157 | 1575 |
| 割合 | 100% | 100% | 100% | 93% | 57% | 2% | - | - | - |
その他精進について
目標の立て方について
ある程度競プロをしていると、この界隈には化け物が一定数いることがわかると思います。これはchokudaiさんも言っていたことですが、自分より圧倒的に強い人と自分を見比べて、自分を卑下するべきではないと思います。
【競プロの各色に対する認識オススメ】
— chokudai(高橋 直大)🍆 (@chokudai) June 29, 2020
・２色上は人外だと思うのが大切！比較しちゃだめ！１色上に追いついたところで人間に戻してあげよう！
・１色上は強い人！目標にするのは良いけど勝てなくて当たり前！いつかは追いつけたらいいなくらいに思おう！
・同色でも成長がヤバいやつはやっぱり人外！
まずは自分の1色上、厳しければ1級位上などを目標にしたり、あるいは今まで解けなかった問題を解けるようになったことや、コンテストで粘って難しい問題を解けたことなどをモチベーションにするのがいいと思います。
難易度の高い問題の勉強について
上で述べたような化け物以外は、色変直後は自分の色より上の問題はあまり自力でACできないと思います。これは誰でもそうだと信じたいのですが、解けないのに精進を続けることは精神的に辛いです。僕も緑になったころは水diffはほとんど解けませんでしたし、水になったころは青diffはほとんど解けなくて辛かったです。しかし、そういった難易度の問題をなんとか自力で解いたり、解説を読んだり解説放送を見て理解していくと(僕の場合は30~50問程度)、特に類題という訳でもないのに解法が見えてくるようになります。そうすると今まで解けなかった問題がだんだん解けるようになってきて、かなり楽しくなると思います。最初はしんどいですが、1週間に何問かだけでも、やる気になった時に解いていくようにするといいと思います。
下埋め(低難易度埋め)について
これは精進の方針なので、人によって向き不向きがありますし、賛否両論もあると思いますが、僕は下埋めを積極的ににやりました。下埋めは退屈ですが、やっておくとコンテストで絶対に解けないといけない問題を取りこぼすことが減りますし、速解きにも繋がると思います。実際、なりたい色の一つ下のdiffをコンテスト中にしっかり通せれば、その色のパフォーマンスが出るということはよくあります。僕は「速解きで最低限のパフォーマンスを確保してから難しい問題を落ち着いて解く」という立ち回りが合っていたので、精進では目標の色より下のdifficultyをある程度埋め終わってから、目標の色に挑戦するようにしていました。
終わりに
このまま競技プログラミングを続けるかはかなり悩んでいます。ここまで熱中できる趣味はそう見つかるものではないと思いますが、時間も大量に溶かしてしまいます。完全に私事ですが、現状一番問題なのが将来やりたい仕事が決まっていないことなので、競プロ以外の色んなことにも手を出してみたいと思っています。
そういうわけで、競プロをやめてしまうかもしれないので、残しておきたいことや記録も含めて書き連ねました。長くなってしまいましたが、最後まで読んでいただきありがとうございました。少しでも役に立ったり、共感していただける点があればいいなと思っています。
Educational Codeforces Round 99(Div.2) D. Sequence and Swaps 解説
初投稿なので丁寧目に書きました。たぶん今後は徐々にテキトーになります（苦笑）
問題リンク
問題概要
個の非負整数からなる数列
と、非負整数
が与えられます。次の操作を好きな回数行えます。
操作: より大きい
の要素
を選択し、
と
を入れ替える。
数列を広義単調増加にするために必要な操作回数の最小値を求めてください。ただし、不可能な場合は
と出力してください。
制約
,
,
ただし、の和は500を超えない。
はクエリの個数。
解法
と交換する
の要素は必ず
より大きいので、スワップを繰り返すにつれて
は(狭義)単調増加することと、ソート後の数列は左に行くほど小さくなることを考えると、直観的に
とスワップできる要素の内、最も左の要素をスワップをしていきたくなります。証明します。
証明
と
がスワップできるとします。この時
が成り立ちます。ここで
とスワップした場合、数列の並びは
となり、
です。
でしたから、この2要素の並びはこのままではいけません。しかし、さらに
を
とスワップしても
なので大小関係が逆のままとなります。1回目あるいは2回目のスワップの直後に他から要素を貰ってくることもできますが、
は単調増加であり、
よりも小さな
を貰うことはできないため、
番目の位置には
以下の要素を置くことができません。よって、2つ以上スワップできる要素があった時、そのうち最も左の要素とスワップするべきであり、逆にその他の要素とスワップするとソートが完遂しません。従ってこれが唯一の手順となり、他の手順が存在しないため、当然最小の手順にもなります。
ただし、途中でスワップできたとしても、ソートが完了していればスワップする意味はありませんので、その時点で終了すべきです。（←自戒）
実装
- 数列がソート済みであるかを確認する。ソート済みなら終了。
- 数列を前から見ていき、スワップできるならばスワップする。
- 最後に数列を確認し、ソートされていれば回数を、ソートされていなければ-1を出力する。
感想
コンテスト中はソート済みかの確認を忘れて1ペナを出してしまいました。今回のコンテストは(少なくともDまでは)、解法がわかってしまえば実装は楽な問題が多かった気がします。あと、解説記事を書くとコンテスト中は適当になりがちな証明を詰めれていいですね。続けていきたいです。
