競プロ始めました-kaede2020-

競技プログラミング初心者向けのブログです

実録!RECRUIT 日本橋ハーフマラソン 2022夏(AtCoder Heuristic Contest 013)参加記

0.はじめに

はじめまして、もしくはお久しぶりです、競プロ歴2年半のかえでです。

今回は、RECRUIT 日本橋ハーフマラソン 2022夏(AtCoder Heuristic Contest 013)に参加しました。開催期間は2022年8月9日(火)21:00から2022年8月16日(火) 21:00まで。1週間の長さの長期コンテストです。

この参加記は、コンテストの期間中に、自分がどんなことを考えて、どんなことをしたのかをリアルタイムで書いています。そのため、どうしても冗長な部分があります。そんなときは適当に読み飛ばしていただければと思います。

ヒューリスティックコンテストって何?」という人も、これを読めば、コンテストに参加した気分を味わえることでしょう。そして、「何だか面白そう。自分も参加してみようかな」と思ってもらえれば、これを書いてよかったなとうれしく思います。

これまでの私の参加記は、初心者でも楽しめるということを伝えたくて書いていたところがあります。だから、どきどきしたり、わくわくしたり、悔しかったり、できる限りそんな心の動きを伝えたいと思っていました。しかし、ヒューリスティックコンテストに参加している回数もそれなりに増えてきて、だんだん上位を狙いたいと思う気持ちが強くなってきました。だから、このブログは今までのように読んで楽しいと思ってもらえる内容ではないかもしれません。しかし、記録することとヒューリスティックコンテストの相性がとても良いので、今回もブログを書きながら参加することにしました。内容は考察重視のブログになると思います。

さて、時刻は8月9日の午後10時。1時間ほど前にちょうどコンテストが始まったところです。それでは長くなりますが、どうぞ最後までおつきあいください。

---(後日談)---

8月14日午後8時です。正直、初日の文章を読み返すと、恥ずかしくて消してしまいたい気持ちになります。参加記を読めばわかりますが、ああ、やっぱりいつもの私なのでした。もうちょっとクールに決めたかったのですが。失敗することと、熱くなってしまうこと。どちらも私からは切り離すことができないものなのだなあとしみじみ感じています。さあ、私といっしょにドキドキわくわくした気分を味わって、コンテストに参加した自分を想像してみてください。

---(8月16日午後8時47分)---

あと少しでコンテストが終わります。私の心臓はものすごくドキドキしています。はぁ。本当だったら、コンテストが終わった後の解法を見るためにわくわくして待機しているはずだったのに...。がんばれ自分!

※コンテストの結果を2022年8月17日に更新しました。

1.問題文の概要

atcoder.jp

・N×Nの広さのサーバ室に、K種類のコンピュータが100個ずつランダムに置いてある。

・できる行動は2種類。

  ①コンピュータを上下左右に1動かす。

  ②コンピュータどうしをまっすぐなケーブルで接続する。

・行動回数の上限は、①と②をあわせて100×K回まで。

・スコア計算は、ケーブルを使って互いにたどり着くことのできるコンピュータを「同じクラスタに属する」とし、同じクラスタに属する2個のコンピュータ選んだときに、同じ場合は1点、異なる場合は-1点として、全てのコンピュータの組み合わせを足す。これを各クラスタについて行う。

・スコアの最大を求める。

2.最初の考察

コンテストが始まる前は、仕事から帰ってきてふらふらだったので、問題だけ読んで寝ようと思っていたのですが、案の定、まだ起きています。お風呂に入りながら、いくつか考えてみたことを忘れないように書いておきたいと思います。

①コンピュータを移動しないで、同じ種類のコンピュータをつなげられるだけつなげる。

②N×NのマスのエリアをK分割して、種類を全く考慮せずにコンピュータをつなげられるだけつなげる。

ここでサンプルコードをダウンロードして、seedの出力をビジュアライザに表示します。サンプルコードでは、適当にコンピュータの位置を動かした後に①を行っているとのこと。サンプルコードのseed0の出力を見ると、①が良さそうに見えました。

サンプルコードのseed0(スコア2963)

しかし、サンプルコードでseed1を出力し、ビジュアライザを見ると様相が変わりました。

サンプルコードのseed1(スコア376)

今回悩ましく感じていたのは、コンピュータの位置を動かすことができることです。移動と接続を合わせて100×K回行うことができるということは、コンピュータの1マスの移動は接続と同じ価値があると言えます。

②を初期解にしてみたいと思ったのは、適当にコンピュータをつなげたところから種類が異なるコンピュータを移動させると必ず得点が高くなるので、山登りや焼きなましができるのではないかと思ったからです。

何となく①からスタートすると、これ自身が局所解だと思うので、コンピュータを動かしたりコンピュータの連結を削除したりすると必ず得点が現状より下がるので、もっと良い解にたどり着くことが難しそうだなと思いました。

③Nの大きさで初期解を変えてみる。Nが小さいときには①を使用しても良さそう。

④Nが大きいときにはうずまき型のエリア分割を試したい

③はビジュアライザを見ていて思ったのですが、Nが小さくて、スペースがなく、コンピュータを動かしづらいときは、①の貪欲がかなり最適に見えるなと思ったからです。コンピュータをスライドさせて山登りとかでも良いかもしれません。

④は、MM128を思い出していました。

コンピュータを移動するとしたら、この形がいいなと思いました。

考察はこれくらいにして、今日は眠りたいと思います。

3.2日目の考察

2日目の朝(8月10日)です。

昨日考えた④うずまき型配置でのコンピュータ接続をやってみたいという気持ちでいます。

去年のRECRUITの問題では、盤面上を自由に行き来できるより、固定してあげた方がよかったことを思い出していました。

kaede2020.hatenablog.com

普段はwataさんがwriterですが、リクルートはオリジナルの問題を出題してくるので、いつもと傾向が違うと思っています。

問題文で気になっているのは、入力とNとKの制約です。

入力の制約(問題文より引用)

完全なランダムではない場合、出力解も場合分けが必要だと考えています。

また、seed0とseed1の見た目の差からも、それは必要ではないかと思っています。

だから、Kが2から5、それに対応するNが24パターン、計92種類しかないので、全パターンのうずまき型で接続するエリアを最初に決定して、それに合わせて最適解を求めても良いのではないかと思っています。

なぜうずまき型がよいのか。それはMM128の経験からなのですが、移動距離が少なくてすみそうというのが一番の理由です。

4.現在の順位表を見ての考察

8月10日10時現在、simanさんが231,570で1位です。simanさんはヒューリスティックコンテストで常にトップの方なので、指標にさせていただくにはとても良いと思っています。50ケースの和なので、1ケースの平均スコアは約4631。

また、26901という得点がコンテスト開始時の提出に並んでいるので、これがサンプルコードのスコアではないかと推測できます。1ケースの平均スコアは約538。

これが何を意味するかといえば、サンプルコードのseed0が2963、seed1が376でしたので、seed0はサンプルコードで実行した際、かなり特殊な高得点のテストケースだということです。逆に、seed1の方が一般的なサンプルコードの結果に近そうだといえます。

やはりseed0を考察のサンプルに使うのは不適切かなと思いました。出題者側が皆が見るseed0のサンプルとして、どうしてこれを選んでいるのかを思うと、やはり恣意的なものを感じずにはいられません。

企業コンテストなので、望む人材にマッチするように、わざといろいろな仕掛けをして試しているのではないかと、自分はそんなふうに想像しました(見当違いかもしれませんが)。

考察の結論です。

1.テストケースの分布が偏っている(これは後ほど計算する予定)ので、一つの解き方では全てにとって最適な解は出ない可能性が高い。

2.したがって、細かく場合分けを要求してきそう。

3.その結果、実装はかなり重くなる。

そんな風に考えています。

5.<最初の提出に向けて>できあがり盤面をExcelで作成する

K=2,N=15の最小サイズと、K=5,N=48の最大サイズの2つを作成してみます。

K=2,N=15

K=5,N=48

2つの違いは一目瞭然だと思うのですが、数値で2つを比較します。コンピュータを各色に100個置いたときの割合です。

K=2,N=15

K=5,N=48

(K,N)=(2,15)のときはぎゅうぎゅうに埋まり、(K,N)=(5,48)のときは空いているマスがかなりあります。

これについての自分の考えです。

・(K,N)=(2,15)のときは同じ種類のコンピュータが隣り合う確率が高く、適当にやっても同じクラスタに所属するコンピュータをそれなりの数作れる。

・(K,N)=(5,48)のときは、同じ種類のコンピュータが隣り合う確率が低く、さらに、同じ行、もしくは同じ列にある確率となるとさらに低くなる。

さらに厳密に確率も計算できそうですが結果に影響はないのではないかと思うので省略します。

結論です。

KとNが大きくなったときはコンピュータの移動が重要になりそう。

6.<最初の提出に向けて>連続テストケース用のコードとサンプルコードのクラス化

そろそろコードを書きたいと思います。

サンプルケースでいちばんうれしかったのは、スコア計算がついていたことです。スコア計算を間違えると、本当に良い解が出ないので。

当たり前といえば当たり前なのですが、これが結構自分にとって難しく感じています。というわけで、サンプルコードを全部使うつもりはないのですが、使えるところは使いたいと思います。

さて、先日ついにGitとGitHubを使ってコードのバージョン管理をする方法を覚えました。これで失敗したときもバージョンを簡単に戻せるはず。

知らない技術も競プロのためなら、がんばれることがわかりました。

ちょっと余談です。仕事で残業をしないことが私のポリシーなのですが、「そうやって仕事が終わった後にコンテストに参加してること自体が残業してるようにしか見えないんだけど。それも”タダ働き”」と友人に言われて、絶句しました。確かに…。残業があっても転職してお金をもらった方が良いのか、趣味は趣味のままが良いのか。…悩んでいる間にコンテストが終わりそうなテーマです。しかし、仕事はもっと条件が複雑で大変だと聞いたこともあるので、きっとこれは”遊び”なんだと思います。うん、多分。

時刻は8月10日21時40分。

いつものローカルでの連続テストケースの実装を行い、サンプルコードをクラスに変更して切り替えられるようにしました。自分の解法の実装はこれからです。

100ケースのサンプルコードのスコアを出しました。

100テストケースのサンプルコードでのスコア

サンプルコードでの100ケースの結果

ああ、やっぱりそうなのですね、と思いました。seed0はMAXのスコアを持つテストケースでした。初心者にやさしくないな、と思います(個人の感想です)。そしてジャッジは50ケースなので、100ケースの和56229を2で割ると28114.5。なので、26901という値が順位表に並んでいることと合致するな、と思いました。

以上で最初の検証終了です。

以前はこのくらいの段階で一回提出していたのですが、今は特に不安を感じていないので、提出せずに自分の実装を進めます。その理由は、ローカルでテストケースを実行できるようになったからだと思います。提出をしてスコアを確かめる必要がなくなりました。繰り返しになりますが、特に今回はスコア計算がサンプルコードについているのが大きいことがあげられそうです。

さて、自分の解法を実装するにあたって、必ずコンピュータを置かなければならない箇所があります。下の図の赤字部分です。コンピュータを置かないマスがあっても構いませんが、角にはコンピュータを置かないと、「まっすぐに接続する」ことができません。

角にコンピュータを配置する

したがって、ソースコードは以下のようにしたいと思います。

  1. 各種類の角の座標を計算する
  2. 角の座標にコンピュータがあるかを調べる
  3. 角の座標にコンピュータが無い場合、いちばん近いコンピュータを持ってくる。
  4. 最初に目標とする形でコンピュータを接続する
  5. 各うずまきにどの種類が多いかを調べ、割り当てを決める
  6. 同じ種類ではないコンピュータを移動させる
  7. 最初に目標とする形でコンピュータを接続する

1から4まで実装を終えたら、スコアを計算して、提出したいと思います。がんばるぞー。

7.最初の提出…がまだできません

コンテスト3日目。8月11日です。

余談ですが、Longest Streak が900日になりました。900日連続でこれまで解いたことのなり新しい競プロの問題を1問以上解き続けたことになります。Longest Streak を続けるとたくさんほめてもらえるので、自己肯定感アップにはとても良いと思います。たとえばソシャゲのログインボーナスでも900日連続って結構厳しそうかなと思うと、がんばっている感があります。継続するためのモチベーション維持に役立つので個人的にはおすすめなのですが、これを重く感じる人には向かないと思います。客観的に見て、今は問題数が多いので、Streakはつなぎやすい環境だと思います。

夜です。

何をしていたかというと、うずまきのコードを書いていました。while文で書いたのですが、どうも最後の部分(どこで終わりとするか)の条件がうまく書けず、悪戦苦闘していました。結局ここは後回しにしたいと思います。

NとKの最小と最大で、盤面が重ならないことは確認しました。

うずまきのコードを書いて盤面を出力したところ

ということで、やっと1に取りかかれます。ふと脳裏によぎる、これで解法の選択を間違えていたらやり直せるのだろうか、という不安。しかし今さらどうしようもないので、頭を横に振って、良くない考えを振り払います。順位表では1位のsimanさんが308,105というスコアを出していました。

 1.各種類の角の座標を計算する

頂点は書き出しました。これは10分で終了。次にいきます。

 2.角の座標にコンピュータがあるかを調べる

あ、これはif文1個で終了しました。次にいきます。

 3.角の座標にコンピュータが無い場合、いちばん近いコンピュータを持ってくる

BFSを書きましょう。そして経路復元を。ライブラリにしておくと楽なのかな?でも毎回書いていますね、今は。メンバ関数にBFSと経路復元を追加します。

BFSを書き終えました。

でもこの1行を書く前に、何か実装がいやだなあという気持ちになって、Twitterを見に行ったら、9月にこどげ(CodinGame)があると思って、こどげを見に行ったりして、だいぶ時間が経ちました。

経路復元を書き終えました。

日付が変わったので、寝ます。明日はコンピュータを連結して、最初の提出を行います。

8.今日こそ最初の提出をしたいコンテスト4日目

8月12日、コンテスト4日目の朝です。順位表を見ると、1位のwanuiさんが319,757というスコアを出していました。そして、iwashi31さんが提出をしていて、300,479のスコアを出していました。自分の「2.最初の考察」でできあがりの盤面をイメージしてツイートを引用したiwashi31さんです。解法が一緒だったら熱いなあと思います。

今日こそは提出したい!

さて、今日のやることは、コンピュータをつなぐことです。まずは、

①各うずまきでどの種類が多いかを調べて、どのルートにどの種類を揃えるか

を決めます。そして、

②各ルートの角にコンピュータがない場合は、角にコンピュータを配置します。

さらに、

③各うずまきのルートを調べて異なる種類のコンピュータが混じっていたら移動させます。

このうずまき盤面にしたのは2、3回で適切なルートにコンピュータを再配置できると思ったからです。思った通りにコンピュータを移動させることができるでしょうか。

④各ルートごとにコンピュータを接続します。

これはつなぐだけだから簡単。

今、自分の中で結果がよくわかっていないのは、違う種類のコンピュータがルートに混じっていたときに、つなぐ方が良いのか、つながない方が良いのかということです。

現在の考えはつなぐ方が良いと思っているのですが、現実には移動でつなげる回数を減らしているので、全てのコンピュータをつなぐことができません。そのときにどうするのかということは、まだぼんやりとしか考えられていません。

ただ、そこまで実装できたらその先は、どこからどこまでつなぐかを尺取り法で調べるとか、同じ種類が続いて点数の高くなるルートを優先するとか、さらに高得点を目指す方法はまだまだありそうな気がしています。

---(時間経過)---

時刻は15時です。バグらせました。盛大に。結局、サンプルコードのスコア計算でバグっているとわかって、スコア計算を一旦消しました。これを見つけるのに半日かかりました。大事な時間を、たくさん使ってしまって落ち込みました。

しょぼーん。

気を取り直して、①です。seed0の結果です。エリア1は種類1、エリア2は種類2を集めることにすれば良さそうです。

各ルートごとのコンピュータの種類を数えたところ(seed0)

seed2ではエリア1は種類2、エリア2は種類3、エリア3は種類1を集めることにすれば良さそうです。

seed2

なぜ2つ並べたかというと、これって、本当に一意に決まるのだろうかと疑っているからです。したがって、重複が出る前提で、エリア1から順番に多いものを選択していくというルールにしたいと思います。

---(時間経過)---

またバグらせました。曲がり角にコンピュータを配置するのに、せっかく配置したコンピュータを別の場所に配置してしまったりして微妙に空きマスができてしまって、それを修正するのに時間がかかりました。なんかコンピュータをひたすら反復して置いてしまったり。

はぁ…。しょげた。疲れました。

というわけで②が終了。

うずまきの角にコンピュータを配置(初期配置との差分をとって移動したものを確認)

③の前に④をやろうかなぁ。

---(時間経過)---

う、バグらせました。seed0ができた!と思ったらスコアが15。

うずまき型(seed0,スコア15)

そして、seed1は角にコンピュータが配置できていませんでした...。うーん、先は長い。そして、コンテスト期間の半分が終了しました。

うずまき型(seed1)バグっています

直せた!!スコア-3766!すごいスコアです。マイナスだー。③をとばして④が終了した時点で23時21分。果たして今日中の提出はできるのでしょうか。ん?このマイナスのコードを提出しますか?いやいやいや、それはちょっと…。

うずまき型(seed1,スコア-3766)

さて③に取り組みます。あ、GitHubにコミットしようかな(コミットしました)。そして時刻が0時になりました。8月13日になってしまったので、今日中の提出はできませんでした。がっかり。

9.最初のコードを書き上げたけど、提出するのはやめました

コンテスト5日目になりました。コードを書きつつあるものの、現在のスコアはマイナス!ひぇー、焦ります。いや、焦らない、焦らない。気持ちを落ち着けて実装を進めます。ビジュアライザを見ると、上下左右に動くよりはBFSで空きマスに動いた方が良さそうです。さあ、続きをがんばろう。

今日やることは③です。

③各うずまきのルートを調べて異なる種類のコンピュータが混じっていたら移動させます。

昨日散々バグらせたBFSを適用するだけ。

と思ったけど、今度はコンピュータを空きマスに移動するので、そのままは使えないと気がつきました。←書いてみたけどうまくいかなかった。というわけで、一旦寝たいと思います。

<自分用メモ>寝て起きたらコンピュータを「どかす」部分の検証から。

---(時間経過)---

朝です。おはようございます。8月13日時刻は7時23分です。(こっそり書きますが、昨日寝たのは1時くらいだと思います。)

低血圧で目覚めが悪いので、目が覚めてもベッドでTwitterを見ながらごろごろしていますが、起きたら机に来て、いきなり競プロです。

何も予定がないときは「あさかつ」というバーチャルコンテストに出たいと思っていますが、AHCやMM、コドゲといった長期コンテストに参加していると、なかなか出られないでいます。

余談が続きますが、リビングの片隅に競プロ用に1畳くらいの自分用のデスクスペースを作って、そこで競技プログラミングをしています。最初に競技プログラミングを始めた頃はダイニングテーブルの片隅でノートPCを開いていました。今もノートPCですが快適に使えるものに買い替えて、デュアルモニターにして、かなり快適に競技プログラミングに参加しています。私のお気に入りの場所です。

順位表の1位はwanui さんで、スコアは356,296です。すごい!さあ、昨日の続きをがんばりたいと思います。

---(時間経過)---

長かった。バグらせました。もうずっと同じことを書いていますね。スコアが15から309にアップしました。やったー!

③ができた~!(seed0,スコア309)

と思ったのもつかの間、seed1はバグっていました。

しょぼーん。

seed1はまだバグっています

直しました。スコアが-3766から-1081にアップしました。まさかのマイナスからのスタート。

直しました(seed1,スコア-1081)

ところで、今は移動の条件を制限回数の半分までにしています。だから、なんか中途半端な感じ。移動距離を絞ってみようかな。とその前に1回コミット。これ、もうちょっと良い管理方法がありそうな気もするのですが、まだGitとGitHubはよくわかっていません。それでもVSCodeのローカルとリモートリポジトリを結び付けられたので、かなり簡単にできるようになりました。

お、種類が違うコンピュータの移動距離を3以内にしたらスコアが-419になりました。

移動距離を3以内(seed1,スコア-419)

ん、距離を1にしてみよう。スコアが-58になった!

種類の違うコンピュータの移動を距離1のみに限定(seed1,スコア-58)

移動を3分の1におさえてみようかな。これはイマイチ。では移動を3分の2に増やしてみよう。

移動を制限回数の3分の1に減らしてみた(seed1,-2296)

ついに、スコアがプラスになったー!スコアが235になりました。最初が-3766だったから、4001もアップしました!(これが前向きな考え方です。)

移動を制限回数の3分の2にした(seec1,スコア235)

このくらいまで実装ができるとかなり楽しい気持ちになります。とりあえず、種類が異なるときに接続を切ってみたいと思います。

種類が異なるときに接続をやめる(seed1,スコア182)

あ、スコアが下がりました。なるほど。そういえば、スコア計算がエラーの原因となっていたのでとばしていたのを復活させることにします。コンテストの最初の頃は何でエラーが出たのかわかっていませんでしたが、今はわかるので、すぐに書き直すことができました。(スコア計算のためには初期の配置が必要で、初期の配置を書きかえてしまっていたので、エラーが出ていたのでした。)

というわけで、自分の実装の100ケースのスコアを出すことにします。

(ドキドキ)

最初の実装での100テストケースの結果

100テストケースのスコア分布

助けて~。ほとんどスコアがマイナスのようです。これを提出すると、3000くらいですね…。サンプルコードはすごいなと思いました。

いちばんスコアのよかったseed28のビジュアライザを見ることにします。

seed28,スコア1314
10.スコアを上げるにはどうしたらよいか

最初の提出をしたいとがんばってきたけど、思ったような結果が出なかったので、提出はもう少し先にしたいと思います。せめてサンプルコードより高い得点で提出をしたい。最終的には必ず提出しますが、まだ時間はあるので、先に考察をしたいと思います。やっと最初のコードを書き上げたので。本当は提出をして、ライバルたちと競いながら得点を上げる輪に加わりたかった。うーん、ここまで2日間くらいで書き上げられると良いのですが、私の実装力~!

というわけで、ビジュアライザをじーっと見ていたのですが、たとえば下の赤線の部分をつなげれば、得点がアップしますね。

赤い矢印部分をつなげれば得点がアップしそう

ということは...。そう、うずまき型にする必要はなくて、同じ種類のかたまりを作って、かたまりどうしをつなげていけばよかったのですね。こんな(自分にとって)難しいうずまき型の実装をしなければよかった~。ちょっと手動でつなぎ直してみました。

ビジュアライザをつなぎなおしてみたところ(seed1,スコア903)

もう、考察主体にブログを書くと言いながら、全然考察できていなかった…。つなぎかえていて思ったのですが、これって、DFS?グリッドといえばDFS?最初にやるのはDFSですか?

月曜からは仕事です。コンテストのために残された時間は今日と明日で、月曜以降は夜と朝のわずかな時間のみ。果たして、良いスコアを出すことができるのでしょうか。

あ、ちなみにただいまの時刻は午後5時です。また、午後9時からはABC264に参加してきます。今は(今も)競技プログラミングが楽しくてしかたがないのです。そして、一人でも寂しくない(こう書くと語弊があるのかもしれないけど)。

11.解法2

さて、気を取り直して、次の解法を試したいと思います。次はこんな感じ。

解法2:交互に種類別エリアを作って後からつなげる

ああ、何か良さそう。種類が5種類でもできるかやってみます。

解法2:5種類にしたところ

うーん、5種類のうち2種類が分断されてしまうけど、最初の解法もそこまではできなかったから良いのかも。

やり方です。

①j列目をKで割った余りで、コンピュータの種類を分ける(左右移動、もしくは上下に1個ずらしてから左右移動。移動は出力用に記録する。)

②同じ列で割り当てた種類のコンピュータが2個並んでいたら接続する(AnswerではなくUnionFind)

③まだ連結されていない隣り合った同じ種類の列の同じ行で割り当てた種類のコンピュータが2個並んでいたら接続する(AnswerではなくUnionFind)

④③で間に別の種類のコンピュータが入っていたら、間に入っているコンピュータを上下にずらす

⑤①から④を自分で決めた上限回数まで繰り返す

⑥盤面を元にコンピュータを接続する。

うまくいくかわかりませんが、やってみたいと思います。(このままではお蔵入りブログになってしまう...。すでに原稿用紙約27枚分、1万の文字を超えているというのに、まだ得点がないとは…。

12.解法2の実装をして、今度こそ初提出をしたいコンテスト5日目の夜

ちょっと横道にそれますが、21時からABC264に参加してきました。眠かったので30分ほど仮眠をとってから参加したのですが、ドキドキわくわくする感じとダメだ~と思う感じが交互に来るのが何とも好きで、今日も例外ではありませんでした。復習しなきゃと思う問題と、よくがんばったと思う問題の両方があって、参加してよかったと思います。

さあ、気を取り直してAHCの続きをやりたいと思います。コードを書き直してみました。先ほどのイメージは縦のストライプにしましたが、実装上は横縞のほうが間違いが少なそうなので、変更しました。まずは横縞を作りました。書き直しに約20分。コードも随分とすっきりしました。上から3→1→2と縞々ができているのが何となくわかります。(その後バグを見つけて「20分→1時間半」に変わりました。)

横縞につなぐ(seed1,スコア540)

100テストケースの結果

横につなぐだけでも5日間かけたコードより点数が高くなりました。悲しい。そして、まだサンプルコードより低い得点です。やっていて思っていたのですが、制限回数がなかなか厳しいなと思います。

①いちばん良さそうな1種類だけを改善する方向にしてみようかな。

②縦方向にもつなぎたい。

③サンプルコードの条件でつないでみようかな。

そしてまた、日付が変わってしまいました。

③を試してみたけどバグってしまったので、そろそろ寝たいと思います。

明日こそ提出したいと思います。

13.コンテスト6日目。ついに初提出をする日が来ました。

8月14日、日曜日の朝です。時刻は7時半。コンテスト6日目の朝です。コンテストは明後日の21時までですが明日から仕事なので、実質今日が自分の最終日です。

昨晩バグっていた③サンプルコードを使用して連結したところです。スコアがアップしている~♪ただ、スコア計算が合っていません。手元ではScoreが552でしたが、ビジュアライザでは1019でした。どうしよう。やっぱり一度提出してみようかなと思います。

うーん、スコアがわからずに提出するの、恥ずかしいな~。いや、でもちゃんとACするのも大事かもしれない。

③のサンプルコードで連結したところ(seed1,スコア1019)

一瞬で結果が出ました。初提出はスコア43572、329位(801人中)でした。

329位(801人中)スコア43572
14.改善あるのみ!

コンテスト6日目、8月14日の午後です。スコア計算は直しました。よかった。

100テストケースの結果です。(※表の2行目のNは21以上30以下です。)

最初の提出の100テストケースの結果(※表の2行目のNは21以上30以下です。)

テストケースの結果を少し詳しく出してみました。予想通り、Nが小さいとき、Kが少ないときが高得点でした。ちなみにサンプルコードのままだと下の表のようになります。なので、少しは改善していそうです。

サンプルコードの100テストケースの結果(比較用)
(※表の2行目のNは21以上30以下です。)

ここで、あ、と気がつきます。今は連結できる接続を全てをできていないので、制限回数以上をカットしています。もし、カットしないで接続できていたら、6万スコアくらい出るのだなと気がつきました。(最初の提出は約4万3千でした。)

現在の移動回数の上限は、100*Kの半分にしています。まずは、移動の上限回数を少なくしてみたいと思います。あとは上限回数以上のスコア計算をカットしたいと思います。

移動回数の上限を3分の1にして提出してみたら、スコアは42518でした。(下がった)

移動回数の上限を2分の1に戻して、移動するのを特定の色のみにしてみたいと思います。イマイチでした。(はっきりと悪いです。)

動かす距離を1だけに限定していたのですが、2以内にしてみました。イマイチでした。(ほぼ変化なし)

縦方向のコンピュータ位置を合わせるように移動する、もしくは縦方向の間に別の種類のコンピュータがある場合に左右にずらすをしてみたいと思います。

---(時間経過)---

余談です。眠くてお昼寝をしていました。そういえば、謎の筋肉痛(腱鞘炎?チックな腕の痛み)が。コードを書くだけで、筋肉痛になることがあるのでしょうか。コードは700行くらい。…とここまで書いてはっとしました。1万2千文字を超えたこのブログのことを。原因はこれですか?

1種類だけ横につなぎ縦にコンピュータを接続するように順番を変えてみました。明らかに良くなった感じがします。

1種類だけ先に横と縦に接続してみた(seed1,スコア2241)

100テストケースの結果です。

100テストケースの結果(※表の2行目のNは21以上30以下です。)

コードを提出してみることにします。提出しているときのジャッジ中の時間は、本当に緊張します。

提出中

結果が出ました。スコアは74175、順位は269位(829人中)になりました。うれしい。うれしいけど、まだまだ足りない。できることはまだまだあるから。

提出結果(スコア74175,順位269位/829人中)

一番スコアが高いテストケースを見ることにしました。seed16で4954でしたがビジュアライザで見るとスコアは2573でした。そう、スコア計算がまだ間違っています。(次の「15.ひらめいた!」の途中で直しました。)理由は接続回数のカウントが正しくできていないから。でも接続する回数が確保できたら、ここまでスコアが伸びるのかとわかって、目標にする形が見えた気もします。

一番ハイスコアが出ていると思っていたけど違いました(seed16)

そうか、縦の連結は1本あれば良いですね。ちょっと修正したいと思います。

スコアが良くなりました。

縦は最小の数でつないでみる(seed16,スコア4853)

100テストケースを試したら、結果が悪くなりました。なぜ?

100テストケースの結果(※表の2行目のNは21以上30以下です。)

悪くなっていたseed92を見比べてみます。(左が今回、右が以前)

スコアが悪くなったseed92

Union Find で管理していたのですが、なんかバグっていそうです。もう一回修正したいと思います。

---(時間経過)---

うーん、思ったようにいきません。このやり方は一旦あきらめたいと思います。

次に、今選んでいるコンピュータの種類は”1”に決めているので、いちばん種類がマッチしているものに変えてみたいと思います。

「いちばん種類が合っていたものを連結してみた」の100テストケース結果
(※表の2行目のNは21以上30以下です。)

そこまで良くならないですね。というわけで、小さなお試しはこのくらいにしたいと思います。

すっかり忘れていましたが、左右に1マス移動して上下の連結ができるように移動部分を変更したいと思います。

15.ひらめいた!

家事をしていて、ふとひらめいたのですが、違う種類のコンピュータが隣り合っていたら、斜めの位置に移動させると、すごく良さそうな気がしました。これを実装するために、後でまた戻ってきます。

---(時間経過)---

再開します。たとえば、seed96の青枠の箇所です。間に挟まれたコンピュータ”2”を1個横にずらして、”1”どうしを接続すれば、得点がアップします。2手でできます。

改善したい箇所(seed96)

これを実装する前に、スコアを修正しました。修正できてよかった。

うーん、やってみたけど、ほぼ変わりませんでした。

そういえば、今のコードで出力したseed100のスコアです。サンプルコードよりは良くなっていますが、10万を超えるにはスコア平均2000が必要なので、まだまだですね。

100テストケースのスコア

日付が変わりました。8月15日です。そう、今日から仕事なのでした。私のAHC013は終わりに近づいていました。あと1回提出できれば良いなあと思います。

おやすみなさい。

明日の私へ。スコアが低いものを改善できるか、ビジュアライザを見て考えましょう。

16.最終日前日の夜(コンテスト7日目)

8月15日の午後8時を過ぎたところです。これまでの結果やビジュアライザをもとに、日中考えていたことを書きだします。

①Kが2のときスコアが良くて、Kが増えるにつれ、結果が悪くなる。

②スコアは一つ大きな連結グループを作る方が高くなる。

①、②から、1種類だけをつなげるだけに変更しようと思いました。なので、揃える行とそれ以外の行を1対1、もしくは1対2で作ってみたいと思います。

まずは1対1から。

1種類だけをつなげることを目指す100テストケース結果
(※表の2行目のNは21以上30以下です。)

久しぶりにスコアが上がった気がします。高スコアのseedが増えました。

100テストケースのseedごとのスコア

いちばんよかったseed12のビジュアライザです。

いちばんスコアのよかったビジュアライザ(seed12,スコア4870)

提出をしました。結果はスコア81281、310位(880人中)。やっとスコアが8万を超えました。

提出結果はスコア81281、順位310位(880人中)でした

UnionFindで余計な縦の接続をしないことと、間にある邪魔なコンピュータの移動を今度こそきちんと実装しようと思います。1行おきにすることと、連結を1種類しか行わないと決めたので、実装もかなりシンプルになってきました。

ちなみにスコアが低いビジュアライザはこんな感じです。

スコアの低いseed47のビジュアライザ(seed47,K=5,N=35,スコア725)

今からやることです。

①上下で挟まれているときは、1マスずらす

②桂馬の位置にあって、間に何もないときは、1マスずらす

良くなった感じがします。

seed47,スコア1015

テストケースの結果です。Kが大きいときの値が改善しています。平均もかなり上がりました。K=2のときの値が下がっているので、これは場合分けをしても良いのではないかと思っています。モチベを上げるために提出してみようかな。

100テストケースの結果(※表の2行目のNは21以上30以下です。)

スコアは87014になりました。9万超えたかったな。残念。思ったよりもうれしくないのは、もっとスコアを上げたいと思っているからだと思います。だんだん贅沢になってきました。

提出結果は、スコア87014、306位(890人中)でした

はっと我に返ったら、翌日になっていました。8月16日、最終日。時刻は1時です。

バグらせました。ああ、どうしよう。Gitに保存もせずに、書きかえました。いろいろと。提出したところまで戻りますか?うーん、悩みます。

バグらせたこれを保存して、提出したところまで戻って、場合分けをしたものを提出したいと思います。

提出結果は90934、306位(898人中)でした

時刻は1時半。寝たいと思います。

17.最終日(コンテスト8日目)

8月16日の朝7時です。長かったコンテストも今日の21時で終わります。楽しかった時間が終わるとぽっかりと気持ちに穴が空いて、寂しくなります。最後、もう一回提出できると良いのですが。昨日は夢中になってしまって、ブログを書くのを忘れていました。

昨日の提出は、K=2だけ場合分けをしました。

K=2だけ場合分けをした100テストケースの結果
(※表の2行目のNは21以上30以下です。)

100テストケースのスコア分布(横軸はKの値)

100テストケースのスコア分布(横軸はNの値)

Kとの相関が高そうなので、K=2のときの得点をもっと高くすることを考えるかKが大きいときのスコアを改善することを目標とするか悩みます。ビジュアライザを見ながら考えたいと思います。

最終日の今日は、もう1回提出できるでしょうか。いちばんよいコードを出す必要があるので、あと1回チャレンジするのが限界かもしれません。

日中は仕事で、先ほど帰宅しました。残り2時間半です。失敗したときのために、30分は残しておかなければなりません。

19:36の提出前の100テストケースのスコア
(※表の2行目のNは21以上30以下です。)

19:36に提出をしましたが結果は良くなりませんでした。

19:36の提出

20:29提出の100テストケースのスコア
(※表の2行目のNは21以上30以下です。)

20:29の提出はWAでした。

20:29の提出はWAでした。

心臓がドキドキします。21時までにもう一度提出することができなければ、何点になるのか想像ができません。

20:29の提出結果は33AC、17WAでした。

ああ、落ち着いて今100テストケースのスコアを見れば、バグってそうなことが予想できるのに、右下の総スコアが上がっているのを見て、そのまま提出してしまいました。

やっぱり、焦るのはダメですね。残り30分、ぎりぎり残っているのが救いです。

こわかった...。本当にこわかった。緊張に耐えられずに、もう泣きそうでした。何とか再度ACして、私のコンテストは終了しました。

何とか再提出できました
18.最終結果(2022年8月17日更新)

8月17日の朝にはシステムテストが終了していました。

暫定352位でしたが、最終順位は357位でした。

スコアは3,769,068でした。

最終順位は357位(948人中)スコアは3,769,068でした。

wleiteさんが参加者全員のシステムテストの結果を統計資料として作ってくれました。

システムテスト(2000ケース)の結果

今回はいろいろと反省するべきことが多くありました。K=2のときに場合分けをしたのですが、しない方がよかったかもしれません。テストケースを1000ケース試すこともしませんでした。山登りやサーチも試さなかったし、もっと自分のできることはあったのではないかと思います。

コンテスト終了後には、感想会スペースを開きました。いろいろな方の解法を聞くことができました。またwriterのtomerunさんも来てくださって、お話を伺うことができました。

自分の中で興味深かったのは、得点の話です。1色を全部つなげると4950点。50テストケースで247500点になるので、スコアとビジュアライザを比較しながら解法ツイートを見ると、30万以上のスコアを出している人と10万台のスコアの人とでは、2種類つなげているのか、1種類のみをつなげているのかといった違いがわかるといった内容でした。また、1ケースでの最高点が1万を超えるのだろうかといった話題になり、高スコアを出している上位陣でもとても少ないことがわかりました。それでも出している人がいるとわかり、すごいと思いました。(制限回数の制約がある中で、どこまで高得点が出せるのかという話題です。)

約2時間のスペースが終わった後、本当は睡眠不足が続いていたので早く寝た方が良いことはわかっていました。それなのにベッドに入ってもなぜか眠ることができず、遅くまでTwitterやブログで解法を見続けていました…。

---(おしまい)---

こうして私のRECRUIT 日本橋ハーフマラソン 2022夏は終了しました。今回も楽しかった。そして終わってしまうと何だか寂しくなってしまいます。だからまたコンテストに参加するのだと思います。長くなりましたが、ここまで参加記を読んでくださってありがとうございました。次はぜひ、私といっしょにコンテストに参加しましょう。

パフォーマンスは1303、Ratingは16上がって1334になりました
19.追記:スコア結果を見やすくするために

スコアの結果はExcelで表やグラフを作成していました。

表1(Excelのピボットテーブルで集計)

ピボットテーブルで集計して、条件付き書式で色をつけていました。

条件付き書式で色をつけます

散布図のグラフは、データラベルを表示して色を赤に変更しました。

表2(Excelの散布図)

グラフのデータラベルを表示して、色を赤に変えました

※「自作ですか?」という質問をいただいたので、追記しました。