お久しぶりです。クラッカーです。
今回は競技プログラミングのAHC043に参加したので、その記録を残していきたいと思います。
参加経緯
半年以上前に1度、少しだけ競技プログラミングをやっていました。
当時の記事
(この時は1か月くらいで飽きました…。)
それから月日が経ち、1ヵ月ほど前に友人から競技プログラミングを始めたという話を聞きました。
私もいい機会だなと思い、友人が始めたのとほぼ同タイミングで復帰しました。
今回のAHC043は復帰して3回目くらいのコンテストです。
ちなみに友人にこのコンテストをやるのか聞いてみたところ、すでに飽きてそうな回答。
分かるよ、その気持ち。
問題概要
街に住民がたくさん住んでおり、その人達の家と職場をつなぐように駅やレールを建築して、たくさんの住民が通勤できるようにしてお金を稼ごう！という問題。
詳しくは下のリンクを見てください。
A – Railway Company
普段のコンテストは100分や4時間くらいの短めのものが多いのですが、今回参加するコンテストは期間が11日もある長期のコンテストです。
長期のコンテストは初めて参加するので、どんな感じなのかドキドキです。
2/14開始だったので、バレンタインデー絡みの問題が来るかと思ったけど全然違いました。
ちょっと残念。
1日目(2/14(金))
サンプルコードとしてPythonのコードが書かれていたので、これをC++に直そうと試みます。
サンプルコード何をしているのか全く分かりませんが、chatGPTに頼りつつ自分でも微修正することで何とか動くようになりました。
提出すると、同じ順位の人が並んでいました。
次に、お金が足りる範囲で一番距離が遠い人の家と職場を繋ぐように変更しました。
初提出よりも順位が上がり、また同じ順位の人が何人か並んでいました。
同じ順位で並ぶと、私と同じ思考の人が他にもいるのだなと思って安心します（？）
何とかして3つ目以降の駅を作りたいなと思いつつ、この日は就寝。
2日目(2/15(土))
すでに設置した2つの駅のどちらかに家か職場が隣接している人の中で、もう片方(家か職場)が一番遠い人の家か職場を作ることで、3つ目の駅を作ることに成功します。
4つ目以降も同様に駅を作ろうとしますが、5時間くらいバグと格闘していました。
無事バグを取り除き、なんとか複数個(7,8個レベル)の駅を作ることに成功します。
なお運が悪いと、「駅を作ったはいいけど他の駅と全く繋がってない」という現象が発生します。しょうがない。
下の画像は運が悪い例。左上付近の駅が1つ繋がっていません。
3日目(2/16(日))
7,8個の駅をコピペ処理で作るようにしていましたが、ループ処理で700ターンくらいまではずっと駅とレールを設置するように変更しました。
得点が3倍以上になりました。
また、「駅を作ったはいいけど他の駅と全く繋がってない」という現象も無理やり解消しました。
解消方法は、「すでにレールが置かれているところにレールを置こうとした場合は、レールではなく駅を置く」
ごり押しすぎる。
４～8日目(2/17(月)～2/21(金))
仕事で忙しくあまり着手できず。
何ターンまで駅を作るか等細かい修正をして少し点数は伸びましたが、周りの伸びの方が高いので順位はどんどん下がっていきました。
(月曜時点で150位 → 金曜日に300位台まで落ちていました。)
プログラムの修正はそこまで出来ませんでしたが、テストケースを一括で実行するバッチを作成。
デバッグや得点の評価がだいぶ楽になりました。
9日目(2/22(土))
駅を設置する際に、以下の点を工夫するように変更。
– 駅を設置する際に、レールの上に設置できるならレールの上に設置。
– 人がなるべく多く隣接する場所に駅を設置。
– 設置する駅を別の駅とつなぐ際に、新たに駅を置かないと繋げれない場合は違う駅を設置。
また、最初に作る2つの駅を変えながらループで処理を行い、1番結果が良かったものを出力するという風に変更しました。(イメージとしてはこんな感じ)
今まで
// Solver クラスに情報を設定
Solver solver(N, M, K, T, home, workplace);
// 処理実施
Result result = solver.solve();変更後
while(3秒経つまで){
Solver solver(N, M, K, T, home, workplace, ac);
//slove()の中で、最初に作る2つの駅を変えている。
Result result = solver.solve();
if (result.score > maxScore) {
maxScore = result.score;
bestResult = result;
}
}この段階で絶対スコアが1億点を超えました。
10日、11日目(2/23(日)、2/24(月))
ビジュアライザを見ていると、1つ駅を設置しただけで2人の住人が通勤可能になるパターンがあることに気が付きます。
これをうまく処理に組み込みたいが、、、なかなかうまくいかず。
中途半端に盛り込んだ状態で最終提出となりました。
絶対スコアは1億2千万ちょっとです。
最終日にREやWA,TLEなどのエラー出まくりで怖くなり、点数を上げることよりもバグがないプログラムを作ることに力を入れました。
まだバグがありそうで怖いです…。システムテストも通りますように。。。
最終提出のビジュアライザはこのような感じです。
seed0 の Score は 498798 でした。
3駅目を作るところ、あまりにもダサくて涙…
まとめ
初めての長期コンテストでしたが、かなり楽しかったです。
ほぼ毎日コンテストのことを考えていました。
200位以内に入ると景品がもらえる可能性があるので密かに200位以内を目標にしていたのですが、知識と頭の柔らかさが足りず難しかったです。
暫定（？）の順位は294位でした。
今回のコンテストをブログに書こうと思い始めたのが9日くらい経った後なので、解法やその時の考えを全然メモしていなかったのが悔やまれます。
次回も長期コンテストに参加する機会があったら、最初からしっかりメモしておきたいなと思いました。
みんなの解法を見てて、駅→レールの順番じゃなく、レール→駅の順番で作ればもう少しスコアが上げれたなと思った。なんでこんな簡単なこと思いつかなかったんだろう…。
「ビームサーチ」「焼きなまし」といった単語をよく目にするので、競技プログラミングのモチベが維持できればそのうち覚えたいなと思いつつ……
とりあえず終わり。
また何か追記するかも。
コメント