AHC028参加記
問題はAtCoderを参照。コードはGithubにあります。
ChatGPT(無料)とGithub Copilotを使っています。
準備
日課の散歩をして、昼寝をしてから万全の状態で挑むつもりだったが、テレビでデルタ・フォースという面白い映画がやっていた。それを見ていたら30分前まで何もできなかった。とりあえず15分仮眠をとった。AtCoderを開いて、CLionを開いて待機。
初動
問題文を読んで理解する。前回(AHC029)と違って、今回はC++向けの親切テンプレートコードがなかった。前回と同じくKotlinでやるためにIntelliJを起動する。
とりあえず、入力と適当な出力(合致した文字を貪欲に入力していく)を書いて提出する。このままコンテストが終わってくれ。
次に、合致した文字の中で、今指があるところに一番近いところを押していく貪欲に書き換えて提出する。この時点で14位ぐらいだったと思う。このままコンテストが終わってくれ。
ここまでは、入力ケース0000のみの結果を見ていた。ちゃんと100ケース実行したくなるので、ChatGPTにスクリプトを書いてもらう。IDEを使わずにKotlinのコンパイル・実行をする方法を覚えていないので、それも教えてもらう。
質問を英語でしているのは、かな入力と英語入力を切り替えるのが面倒だったから。ディレクトリの配置を変えたり、IntelliJがPythonをちゃんと認識できるように設定したりするのに手間取った。さらに、微妙にファイル名が違った。
それから、単語がせいぜい500個しかないので、全部の単語を見て、1文字目が今の指の位置から一番近い単語から入力していくようにする。
これで100ケース567017点。3時56分
シェル芸とタイブレーク
Pythonスクリプトがテストケースを逐次実行していくのが遅いので、シェル芸を使って並列実行できるようにする。月刊シェル芸は役にたつ。
Pythonでつかうコマンドを
seq 0 99 | xargs printf "%04d\n" | xargs -I@ -P8 sh -c "CI=true java -jar Main.jar < in/@.txt > out/@.txt"
にする。
プログラムでは、現在の指からの移動距離が同じやつをランダムに選ぶを繰り返し実行して、一番いい解を出力するようにする。
これで620802点。4時35分
被った入力を省略した(つもり)
一個前の単語の接尾辞と、次の単語の接頭辞が被っていたら入力を省略する(つもりになっていた)コードを書く。悲劇の始まりである。
626268点。5時2分
5文字全部のコストを計算
先頭1文字だけではなく、5文字全部入力した時のコストを使って貪欲をする。
679017点。5時17分
もう一回タイブレーク
5文字全部入力した時のコストが同じだったら、ランダムで選ぶようにする。これを時間いっぱい繰り返す。
680769点。5時24分
5文字入力する経路を最適化する
ダイクストラを使って、5文字入力するステップを最適化する。Github Copilotが作ったバグに悩まされて結構時間を食ってしまう。うちは晩御飯を6時に食べるので、呼び出しにちょっとコンテストの続きをさせてくれと頼む。
693984点。6時15分ごろ
ご飯を食べて順位表を眺める
ちょっぴり冷えたご飯を食べながら、下がっていく順位を見守る。6時40分ごろに食べ終わったが、もうやることもないかなと思い、リビングでダラダラする。
結果、340位
おまけ
自分が書いたプログラムを眺めていたら、衝撃の事実がわかる。
皆さんに悲しいお知らせがあります。
— blue_jam (@blue_jam) January 13, 2024
ああああああ・・ああああ・d・あ・あ・・あ・あ・あ・・ああああ・あ・・あ・あ・あ・・あ・あ・あ・・あああ。あ。ああああ・あああああああああああ・ああ・あ・あ・あ・あ・あ・・・あ・あ・あ・あ・ああ・・・ああ・あ・・・あ・・・・・・ああああああああ pic.twitter.com/rqCU2d6KTe
これがなかったら、200位以内に入れていたらしい。
教訓
Github Copilotのコードはちゃんとレビューしろ。