- 0.はじめに
- 1.問題文を読んでビジュアライザを見る
- 2.最初の考察
- 3.雑談（AtCoder Daily Training と動画配信の話）
- 4.最初の提出
- 5.予測値
- 6.重さを1個ずつ比較する（その前にスコア計算の修正をする）
- 7.D個のグループに順位をつけて重いグループから軽いグループにアイテムを渡す
- 8.重いグループから渡すアイテムは重さが2番目以降のものにする
- 9.考察とビジュアライザ新機能の使い方
- 10.WAを特定するために1000テストケースを実行する
- 11.迷走中
- 12.スマホコーディング
- 13.終わりに
- 14.最終結果（2023年10月24日更新）
0.はじめに
はじめまして、もしくはお久しぶりです、競プロ歴3年半のかえでです。
今回は、AtCoder Heuristic Contest 025に参加しました。開催期間は2023年10月14日(土)12:00から2023年10月22日(日)19:00までの9日間の長期コンテストでした。
この参加記は、自分の行動を記録することとヒューリスティックコンテストの相性が良いこと、またヒューリスティック・コンテストの参加者をもっと増やしたいという思いから書いています。ヒューリスティック・コンテストは考察をし、自分のできる実装でより良い解を得るために試行錯誤するところが醍醐味です。失敗も多いのですが、それも含めて楽しいのです。上位者がもっと良い解法を教えてくださることは知っています。それでもこんなことをすると何点取れるという話はいくつあっても良いのではないかと思っています。ぜひ軽い読み物として楽しんでもらえたらうれしく思います。そして、AtCoderのAHCの解説には誰でも投稿することができるので、ぜひ多くの方に解法を書いてもらえればと思っています。
それでは、始めたいと思います。
1.問題文を読んでビジュアライザを見る
- N個のアイテムをD個の福袋に分割して入れる。そのとき各福袋をできるだけ同じ重さにしたい。
- N個のアイテムの重さは不明であるが、左右にアイテムを置くと、どちらかが重い、もしくは同じであるとわかる天秤を使って好きなアイテムをQ回量る。
- N個をDグループに分けて、そのグループ名を出力する。
問題はシンプルに思えました。スコア計算です。
スコア計算もシンプル…。
その分制約が固定ではないようです。場合分けが必要かもしれません。
ビジュアライザを見ます。問題文の中程にある「例を見る」をクリックします。
ビジュアライザ画面が開くので、再生ボタン（▶）を押します。
上が天秤で重さを量っているところ、下は自分の予測をビジュアライザ表示できるようになっているようです。
ビジュアライザに新機能が搭載されています。便利そうなので後で試してみたいと思います。
2.最初の考察
さて、実装する前に、seed0の各アイテムの重さを確認します。昇順に並び替えてみました。
今考えていることは、適当な平均を各アイテムに入れる。適当なグループを作り、天秤で量る。軽い方のグループからは一定の値を引き、重い方のグループには一定の値を足す。これをQ回繰り返すという方法です。
天秤で量るべきグループ分けの部分はどうしたらよいのか分からないので、毎回ランダムで行ってみたいと思います。
3.雑談（AtCoder Daily Training と動画配信の話）
さて、翌日です。2023年10月15日の朝です。
ちょっとだけ余談をするとAtCoder Daily Training - AtCoderをやっと開催する準備が整いました。入社して9か月、初心者向けコンテストを開くために苦心していました。こちらはアルゴの練習用ABCバーチャルコンテストにはなりますが、競プロを始めるハードルの高さを下げられればいいなと思っています。競プロを楽しむ人が増えることを望んでいます。
そうそう、動画の配信も始めました。このAHC025までに解説を読みながら実装を終えたかったのですが、間に合いませんでした。最初の貪欲法の提出までしかできていません。AHC025が終わったら続きを始めたいと思います。
ABCコンテストにも参加していますし、アルゴの精進も続けていますので、時間が足りない～！といつも思っています。睡眠不足を感じることが多くあります。正直疲労もたまりがち。だから今日も疲れたらお昼寝をしようと思っています。
4.最初の提出
昨日は簡単に見えましたが、インタラクティブ部分をローカルで実装しなければいけない、と気がつきました。こちらが重さを量るアイテムを指定し、どちらが重いか結果を返す部分です。というわけで、入力の受け取り、スコアの計算、インタラクティブの応答部分、ランダムでアイテムを選択してQ回量る部分、量った結果により予測を調整する部分、出力部分をそれぞれ関数で書きたいと思います。
1時間半ほどで書けました。
予測の部分は固定値1000を重い方のグループから均等に引き、軽い方のグループに均等に足しました。
グループ分けは予測の重さ順にソートして、D個に順番に振り分けました。
提出します。
無事にACしました。絶対スコアは2,291,517,706、相対スコアは48,180,232,564で541人中263位でした。ただ、ACしている人が351人で今回は少ないようなので、351人中263位という方が良いのかもしれません。
46,965,116,277というところに同点の人がたくさん固まっているので、自分の予測が正しく更新できていれば、もう少しスコアが良くなっても良さそうだなと思います。ちょっと予測部分を出力して確認したいと思います。
5.予測値
見直してみると、やっぱり予測部分が間違っていました。自分の予測と合っている場合にも値を変えていたので、更新しないようにします。（たとえば、1個と10個を比較して1個の方が小さいときにも1000を足す、みたいなことをしていました。）
あと、毎回左右の個数が違うのも良くないような気がしたので、左と右を10個ずつにしてみます。
お！
seed0の結果を見ると明らかに良くなっています。今回はスコアが小さい方が良い得点になりますがseed0のスコアは4,150,351になりました。何個ずつ選ぶかはseedによって変えた方が良さそうですが、最初の提出よりは良い結果になりそうなので提出することにします。
絶対スコアは1,811,598,651になり、最初の提出の79%くらいの得点になりました。また相対スコアは55,143,667,296になり、順位は242位になりました。
ここから少し真面目に予測を考えたいと思います。取り出したのは、E869120こと米田優峻さんの著書『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本』です。258ページの「5.10.6”状態数”を数える」で重りの重さを考える問題がありました。それを思い出したので、何かヒントにならないかと読むことにします。
Q回で当てられる個数を計算することにします。20個を62回くらいで当てられそうです。100個でも100log2(100)≒665回とのこと。ホントかな？
この本での当て方はトーナメントでした。この問題は実質的には配列をソートする問題と同じとのこと。実際に1個ずつ量ってみるコードを書いてみたいと思います。全部が完全にわからなくても重さのソートができると結果が改善しそうです。
6.重さを1個ずつ比較する（その前にスコア計算の修正をする）
ヒープソートとマージソートとクイックソートがどれも高速にソートできるアルゴリズムでO(NlogN)でできるようです。途中で終わったときに一番良さそうなクイックソートを実装することにします。
書き方を見ていたら眠くなってきたのでお昼寝をしました。目が覚めたら、そういえば正しくスコア計算ができているのだろうかと気になります。試してみるときちんとスコアが出ていないので、先にこちらを直すことにします。
修正をして、スコア計算が正しく計算できるようになりました。
クイックソートに戻ります。どれか一つを選んでpivotとします。pivotとそれ以外を1個ずつ比較して大小を比較します。pivotの位置が確定し、それより下のグループと上のグループに分かれます。下のグループと上のグループで同じことを繰り返します。イメージすることはわかるものの、Q回という制約があるという点でよくわからなくなってしまいます。また今回は並び順を決めるのではなく、ある値が入っているというところも異なっています。どうも実装方法がピンときません。
手が止まったまま時間が過ぎます。
提出できる回数は30分に1回なので、考えている間にも別のことを試しながら提出をします。その中でちょっと結果が良くなったものがありました。
- Q回調べたことのない組み合わせで1個ずつアイテムの重さを比較し、多い方にプラス、少ない方にマイナスを値を加えていくというものです。
提出すると絶対スコアは1,543,485,452になりさらに減少しました。相対スコアは良くなってはいませんが、それはトップの人のスコアが伸びている影響です。順位も上がらないのは他の人の提出が増えているからで、相対的なポジションはそれほど変わっていないのが予測パフォーマンス（1279）から伺えます。※予測パフォーマンスはac-predictorというツールを入れて表示しています。
highグループとlowグループは対決しなくても結果がわかるなぁと思って、1個ずつの大小のソートが思ったよりも早くできそうだと思います。実装してみると、100テストケースの結果も良くなっています。提出すると絶対スコアは良くなっているものの、相対スコアはあまり変わりません。
うーん。
悩んでいるうちに別のアイデアを思いつきました。
最初から適当にD個のグループにアイテムを分けて、重い方から軽い方にアイテムを1個あげるということを繰り返したらどうだろうかと。
早速実装してみることにします。
7.D個のグループに順位をつけて重いグループから軽いグループにアイテムを渡す
方針をまとめます。Q回終わるまで以下の手順で量ることにします。
- N個のアイテムをD個のグループに分ける。最初は同じアイテム数。
- D個のグループをソートする。ソートの仕方は1個のグループを選んで順番に残りのグループと重さを比較し、highグループとlowグループに分ける。highグループとlowグループどうしは重さの比較結果が分かるので入力する。比較していないものがなくなるまで順番に重さを量る。回数はO（DlogD）で済むので、Q回（2N以上）より十分小さい。
- 一番軽かったグループと一番重かったグループを取り出し、符号が変わるまで、ランダムで選んだアイテムを重いグループから軽いグループに渡す。その後処理済みに移動
- 残ったグループが1以下になるまで3を繰り返す
- 2に戻る
4以外の部分を実装し終わったので、100テストケースを回します。するとスコアを2割ほど減っています。
うれしくなって提出します。
提出した結果はWA。seed0の出力をビジュアライザを見るとエラーが出ます。左と右で同じものを比べていました。出力部分を修正して再度提出します。
30分間に1回しか提出できないので、ブログを書きながら待ちます。提出するとまたWA。えー！と思いながら詳細を見ると、今度は98ケースではACしていました。しかしWAなので絶対スコアは0点です。
順位表を見ます。提出前は410位だったので、少しだけ上がりました。提出者も増えてきて、869人中392位です。相対スコアは53,964,922,713でした。
グループ同士を比較するやり方の方がよさそうだと思いつつ、思ったよりもスコアが上がらず残念に思います。今日の日付は2023年10月17日火曜日。コンテスト開始から4日目です。何とか方針転換できたので、ここからがんばりたいと思います。
重い方から軽い方に渡すアイテムをランダムにすると100テストケースでのスコアが3割ほど改善したので提出します。しかしまたもWAが出て絶対スコアが分かりません。
それでも相対スコアは上がり、60,239,904,990になり、870人中353位になりました。
WAの原因を探します。100テストケースを公式のローカルテスタを使って調べたところ、スコアが0点になっているものがありました。エラーメッセージも出ます。
Out of range: 0
Score = 0
出力を見たところ、Q回比較を行っていませんでした。重さを量った数を数えていたカウンターを置く場所を正しい位置に修正します。提出するとやっとACしました。絶対スコアは722,327,643になり、相対スコアは62,121,779,860、883人中343位になりました。
重さが変わったときにあらためてＤ個のグループの順位付けをしていたものを、重さが変わったものだけを量り直すことにします。相対スコアは63,551,881,416になりましたが、TLEが4つ出て絶対スコアは0点でした。
一番重いグループのアイテム数が1個しかないときに無限ループに入ってしまうようだったので、一番重いグループのアイテムが1個しかないときは2番目のグループを対象にするように修正します。TLEがなくなったものの1個だけWAが出ます。相対スコアは63,399,108,139、927中360位でした。少し上がりましたがWAの原因がわかりません。
うーん。
8.重いグループから渡すアイテムは重さが2番目以降のものにする
わからないので次のアイデアに移ります。ビジュアライザを見て考察すると、一番重いものを動かさないのが良いではないかと思いました。
そこで、
- D個に分けたグループをソートし、一番重いグループの所持しているアイテムの重さを量って順位付けし、重さが2番以降のアイテムからランダムで軽いグループ渡す
ことにしました。
実装をバグらせはするものの、何とか書き終えます。グループ内の順位付けが思ったより回数がかかってスコアが悪化したので、
- 1回調べたグループは次回以降は調べないこと
- 一番大きいアイテムだけを調べて残りの順位付けはしないこと
この2つを取り入れるとスコアが良くなりました。一番大きいものだけを調べる方法として、最初はグループの最初のアイテムをベストとして、それ以外を全てキューに入れ、キューから1個取り出して重さを比べ、取り出したアイテムの方が重かったらベストを交替することにしました。
ローカルで100ケースを実行すると、スコアは35%ほど改善していました。
提出します。まだ1ケースだけREが出たため絶対スコアは0のままですが、相対スコアは68,299,778,766、934人中282位になりました。
上がったー！
順位表を眺めながら今日はもう眠ることにします。そして次のアイデアを考えたいと思います。
9.考察とビジュアライザ新機能の使い方
入力される数値についてしっかりよく読んでいなかったので、ここでもう一度確認します。
指数分布のリンク先を読みます。
うん。（よくわからない）
実際にseedを見ていた感想と合わせると、アイテムの重さはかなり幅を持っていて、大きな値と小さな値が生成されるようだと思います。ビジュアライザを見てもそれはわかりました。
ここでビジュアライザの新機能の説明をします。
１ファイルを選択をクリックします。
２出力したファイルを入れたフォルダを選択して「アップロード」をクリックします。（「output_0000.txt」から「output_0099.txt」までの100個の出力ファイルを「output1」というフォルダを作成して入れてあります。）
３確認メッセージが出るので再度「アップロード」をクリックします。
４ビジュアライザのFileを確認すると、ファイルが取り込まれていることがわかります。
５ファイル名部分がアクティブになった状態で矢印キー（下）を押すと、順番に自分がアップした出力に応じたビジュアライザを見ることができます。（seedナンバーは”_”をつけて後ろにつけると認識してくれます。）
おお、便利～！
考察に移ります。seed28のビジュアライザを見ると、もっとうまく調整できそうに見えます。やると良さそうなこととしては、
- D個のグループの真ん中の重さのグループを基準にして１個差でちょっと軽いかちょっと重いになるように調整する。
- 各グループ内の重さの順位付けをして、重い方から１個ずつ確定していって、最後に小さいもので調整する。（具体的な方法不明）
を考えました。
２個目のアイデアは実装がちょっと面倒なので、１個目のアイデアを実装したいと思います。今は重いグループから軽いグループにアイテムを移しています。これをどこかの段階で真ん中基準のアイデアに切り替えるのか、最初から真ん中を基準にしても良いのか。その場合、アイテムをどこからもらったり、どこにあげたりしたら良いのかがわからないなと思います。
うーん。ちょっと考えよう。
10.WAを特定するために1000テストケースを実行する
さすがに絶対スコアが0点のままだと考察をするのがつらいので、原因を見つけるために1000テストケースを回してみます。ローカルテスタを使うと、1000テストケースで4ケース得点が0のものを見つけました。
エラーメッセージは「Unexpected EOF」でした。
このseedを使ってバグっている箇所を見つけることができました。1個しかアイテムがないグループで大きい重さのときに渡すアイテムがなかったのが原因でした。それも毎回エラーが出るわけではないのが悩ましく思いました。修正をします。
提出すると、やっとACしました。絶対スコアは409,641,635、相対スコアは976人中325位でした。ほんの少し変えただけのコードを1000回実行したり、実際に提出をしてみてわかったのですが、かなりスコアが上下します。もうちょっと安定してスコアを出せるような工夫をしないといけないなと思いました。
11.迷走中
ふと思いついて、符号の向きが変わらないぎりぎりに調整するのはどうかなと思います。100テストケースの結果は悪くなったものと良くなったものが入り混じっています。ビジュアライザを見て、グループのアイテム数が3個以内のときは符号が変わるようににアイテムを受け渡すことにします。
100テストケースの結果はぐんと良くなりました。提出すると絶対スコアは296,701,539になりました。相対スコアは69,795,358,648、978人中276位になりました。
70Gに届きそうで届かないのがもどかしくて、ちょっと条件を変えた何かをいろいろと試し続けてしまいました。結局これ以上良いスコアは出せなかったのですが、Qの残り回数に応じて符号が変わるような受け渡しを少なくするようにしたものはもうちょっと改善できるのかなあなどと思いました。
12.スマホコーディング
コンテストが残り2日となった土日は家にいなかったのでパソコンを使えなかったのですが、諦めきれずにスマホコーディングをすることにしました。AtCoderのコードテストを使いました。
コードを書くのに時間がかかり、ローカルで100テストケースの実行もできなかったためWAを連発しました。クエリの回数が半分以上残っているときは重めのアイテム、少なくなってきたときは軽めのアイテムを選択するようにしました。
少しスコアが安定するようになった気がしますがテストケースを回していないのでこれを最終提出にしてよいのか悩みます。もう1回提出したときもそこまで絶対スコアが変わらなかったので、最終的に今日のコードを最終提出にすることにしました。
コンテスト終了後の暫定順位は373位でした。
13.終わりに
今回はコンテストに費やせる時間を何とかひねり出そうとしたのですが難しく、途中で睡眠を削ってしまいました。眠いのに目を閉じると、あ、このアイデアをちょっと試したいと頭に思い浮かんだアイデアを実装するためにベッドから起き上がってしまいました。日中は眠い目をこすりつつお仕事。社会人として何だかなあと思いつつ、それくらい問題のことを考えていました。
もっと良いスコアを出したかったなあというのが正直な感想ですが、どうしたらよいのかがわからなかったです。難しかった！
他の人の解法を聞くのを楽しみにしていますが、どうして思いつかなかったんだろう、悔しい～と思ってしまいそうです。
2023年10月25日（水）の午後8時からはAHCラジオもYouTubeでライブ配信予定です。どうぞ楽しみにしていてくださいね。
すっかりAHCの虜になってしまった人はそのまま、まだ始めたことのない人にも楽しんでもらえるよう、これからもヒューリスティック・コンテストがどのようなものかを伝え続けていきたいなと思います。
今回も楽しかった！
この参加記を読んで、自分もヒューリスティック・コンテストに参加しようと思う人が一人でもいたらうれしく思います。次はぜひ私といっしょにAHCに参加しましょう！
14.最終結果（2023年10月24日更新）
システムテストの結果が出ました。5000ケース全てACしていました。
相対スコアは323,803,364,030、1116人中388位でした。暫定順位は373位でしたのでだいぶ順位が下がってしまいました。やはり最終提出するコードは多くテストケースを回したものにしたいと思いました。
そしてAHCレーティングは7上がり、1456になりました。青になりたい～！
