- 0.はじめに
- 1.問題文を読む
- 2.最初の提出
- 2.2回目の提出（最後の文字と同じ文字から始まる文字列を選ぶ）
- 3.3回目の提出（今いる場所からスコアが小さい文字列を選ぶ）
- 4.4回目の提出（最後の1文字と最初の1文字が同じときを省略する）
- 5.5回目の提出（ランダムでキーポジションを変える山登り）
- 6.解説放送
- 7.最終結果
- 8.終わりに
0.はじめに
はじめまして、もしくはお久しぶりです、競プロ歴約4年のかえでです。
今回は、ALGO ARTIS プログラミングコンテスト2023 冬（AtCoder Heuristic Contest 028）に参加しました。開催期間は2024年1月13日(土)15:00から19:00までの4時間短期コンテストでした。
さて、あっという間にコンテストは終了し、今は翌日です。最終結果は918人中324位、スコアは1,041,739でした。その結果パフォーマンスは1530でレーティングは10上がり1598になりました。1600に到達することを目標としていましたが、あと2足りませんでした。残念。
今回の参加記はメモ書きになりますが、どんなことをしていたのか、コンテスト開催中の動きを簡単に振り返りたいと思います。どなたかの参考になれば幸いです。
1.問題文を読む
詳しくは問題文を読んで欲しいのですが、簡単に書くとこんな感じかなと思います。
- N×Nのキー配列（N＝15で固定）で文字を打つ
- M個（M=200で固定）の”縁起の良い文字列”（5文字）を含める
- 指の移動が少ない縁起の良い文字列を全て含んだ文字列を作る
2.最初の提出
問題文中にある「例を見る」からビジュアライザを開きます。左側がキー配列で、右側が200個の5文字からできている文字列があります。
- キー配列の中から一番近い場所にある打ちたい文字を探す
- 答えの文字列の長さを短くする
この２つの要素をそれぞれ考えることが必要だと思います。今回はサンプルコードがなかったので、入力を受け取るコードを書くところから始めます。最初は1番目から200番目まで順番に文字列を打ちたいと思います。その際、キー配列では次に打ちたい文字が複数にあるので、今いるポジションから一番近い場所を選びたいと思います。
一体何をすればよいのだろうと思って、スコア計算にワーシャルフロイド法を使う？とかBFSを書いた方が良い？と思って書いてみますが、これはなくても良いかも、と思い書いたものを消します。どの文字がどの場所にあるかを知りたいと思ったので、vectorの2次元可変長配列で、Aは(0,0),(4,13),(7,11)…、Bは(0,12)...とZまで各文字の場所を格納しました。そして今の位置から移動したときにかかるスコアをその文字の全部の場所に対して計算して、一番近い場所に移動するようにしました。
提出するとスコアは849,393になりました。404人中144位になりました。約1時間が経過していました。
seed0のスコアは5837、ビジュアライザはこんな感じでした。全ての文字を打っているので、右側が全て黄緑色になります。
2.2回目の提出（最後の文字と同じ文字から始まる文字列を選ぶ）
今打った5文字目と同じ文字から始まる文字列があればそれを選んで打つようにします。無いときには前から順番に文字を打ちます。
コードを書き終わったときには1時間45分くらい経過していました。最初の提出での順位は390位まで落ちていました。提出するとスコアは891750になり、656人中350位になりました。
3.3回目の提出（今いる場所からスコアが小さい文字列を選ぶ）
1番目から順番に打っていた文字列を、常に残っている文字列の中で今いる場所から一番スコアが小さい文字列を選んで打つようにします。
コードを書き終えて提出します。時刻は17時半を過ぎています。残りは1時間半。2番目の提出の順位は522位まで落ちていました。提出するとスコアは1,017,618になり、780人中254位になりました。
4.4回目の提出（最後の1文字と最初の1文字が同じときを省略する）
最後の1文字と最初の1文字目が同じときはスコア計算と答えの出力で飛ばすことができるように修正します。スコアは1,034,879になりました。順位は提出前の289位でしたが229位に上がりました。時刻は17時55分。残りはあと約1時間です。
動揺に2文字重複を取れば良くなるはず、と思って実装します。seed0とseed1を試してみたところ、スコアが良くなりません。
何でだろう…。
コードを見直し、ビジュアライザを見ながら考えます。良い案が浮かばないまま時間が過ぎます。残り時間も少ないので、別のことを考えることにしました。
5.5回目の提出（ランダムでキーポジションを変える山登り）
8msしか使っていないので、実行時間が余っています。ランダムで出力予定の文字列から1文字を選び、ランダムで同じ文字の別の場所のキーポジションに変更することにします。スコアが良くなれば採用する山登りにしました。
ほんの少しだけ上がりました。seed0のスコアは7107になりました。
提出をします。順位は提出前の294位から266位に少しだけ上がりました。スコアは1,041,739に上がりました。時刻は18時23分。
ランダムで1文字を削除してみる実装を加えてみますが良くなりませんでした。
そして4時間が終了しました。
6.解説放送
コンテスト後は20時から解説放送が行われました。2文字重複削除がスコアアップにつながること。また、必ずしもスコアが良くなるわけではない2文字重複削除があるということを知りました。そしてDP解の説明を聞き、なるほどなぁと思いました。
7.最終結果
最終結果は918人中324位、スコアは1,041,739でした。その結果パフォーマンスは1530でレーティングは10上がり1598になりました。
8.終わりに
コンテスト終了後に振り返ると、もう少し何かできなかっただろうかと反省すべき回でした。100テストケースを回すことはあったものの、毎回ではなく、seed0とseed1の結果を見て判断していました。2文字重複削除の結果についてもう少しきちんと評価できていればもっとスコアを良くできたかもしれません。もったいなかったなぁと思います。
それでも改善するという意味では一歩ずつスコアを上げていくことができてよかったと思いました。提出前後での順位を比較するために、提出前に順位表を見ることにしていたのですが、時間の経過とともにどんどん順位が下がっていくのを見て、短期コンテストならではだなあと思いました。
次もがんばりたいと思います。
