AHC031参加記【最終72位】

解説

最終解法の概要

　平均空き面積によって、複数の解法を切り替えています

　共通区画幅焼きなまし解を適用するケースが最も多かったです
　下図のような、縦長のエリアを全日使うことを考え、この幅を焼きなましによって探索します
　日を跨ぐことによるパーティションの変更は、この区画幅の中でのみ行われるため、そのコストを抑えることが出来るのでは。という思惑があります

seed=1, Score=137,514

　近傍は3つで、

• 20%で、分割数を増やす
• 10%で、分割数を減らす
• それ以外の場合、2つの区画幅を乱数でリバランスする

　これによって得られた幅リストを降順ソートして使います
　幅リストを辞書のキーにしてスコアを保存しておくことで、スコア計算の頻度を抑えています

　スコア計算も、制約によって厳密な値まで計算するか、速度優先でざっくりな計算をするかを切り替えています

　幅リストから解の作り方は、希望面積の降順に最も面積余りの少ない幅の場所に割り当てていく貪欲で実装しています

　ちなみに、上記解法を適用できない場合は以下のような解になりました
　恐らく希望面積を満たせていないテストケースはないと思われます

seed=61, Score=610,638

提出コード

　pypy3です

atcoder.jp

参加記

はじめに

　せっかくの長期コンですが、事情によりコーディングに時間が割けません
　空き時間に細かく考察を進めて、効率よく頑張りたいです

　今回から、手元でNimを実行できる環境構築をしたので、高速化バトルになりそうであれば言語の持ち替えも行いたいと思っています

1.問題

atcoder.jp

　のイベントホールを、日間、団体に貸し出したい
　希望面積以上の長方形区画を、出来るだけ境界を変更しないように分ける

　ホールサイズは、1000固定
　日数は、
　予約数は、
　希望面積の総和は、以下が保証される

　希望より小さい区画を提供した場合、差の100倍コストがかかる
　日を跨ぐ際に、パーティションの相違があれば個数分コストがかかる

2.開始直後の考察

• 情報が全て出されている上、時間制限が3secなため焼きなましが強そう
• 用意した区画は、希望より大きければ良いため空きスペースは不要
• 大きい希望区画ほど、優先して希望以上の面積を提供すべき
• 小さい希望区画は、パーティションの変更量が少なく済みそう

解法のアイディア

• 全日程区画を固定した場合に、最小コストをなる配置を焼きなましで求める
  →日ごとの希望面積昇順で区画は決めてしまう
• 最適に近い配置をいくつか持って、各日ごとにどの配置を使うか探索する
  →パーティションの変更量も考慮する

3.区画固定焼きなまし

　最初の解法は、全日程区画を固定した場合に、最小コストをなる配置を焼きなましで求める方法にしました
　簡単のため、短冊状に区切って幅や高さを変更する近傍を使いました

　ACできるコードを投げましたが、当日24時頃で104位/208人とイマイチな結果です
　パーティションを移動させない<区画を満たす 方が重要なようです
　次は、パーティションの変更を気にせずに、希望面積を満たせる解法を考えてみたいと思います

4.希望を満たす区画貪欲

　各日について、大きい区画から決めていく貪欲を作ります
　簡単のために、前の解法と同じく短冊所に区画を作り順番に詰めていきます

　収まらない場合、最大長方形をで探索しそこに出来るだけ大きい区画で置くようにしました
　最大長方形のアルゴリズムは、以下のサイトを参考にさせて頂きました

ALGORITHM NOTE 長方形探索： 最大長方形の面積 Largest Rectangle

5.短冊形貪欲解法

　焼きなましをしたい！と思い、AHC001のような感じで四角を動かして良い配置を探索しようとしましたが、どうもうまくコードが書けません
　各日の盤面だけならまだしも、日を跨いだパーティションの判定までやるのは骨が折れます

　考え方を変えて、探索可能そうな制約に置き換えることにしました
　具体的には、区画は全て上から下まで()使うものとする。としました
　これであれば、幅方向だけを見ればパーティションの増減が割と高速に判定できそうです

　ただ横に並べるだけだと、幅が1000を超えることがあるため区画を上手く併合する必要があります
　高さは1000固定なため、希望面積を満たす幅は
　その時、無駄となる面積は、で求めることができます

　この無駄となる面積の大きい順に、併合する区画を全探索することで無駄となる面積を小さくした盤面を作ることができます　

　一旦この貪欲解法で投げてみるとスコア61,142,184を得ることが出来ました

6.短冊解法山登りver

　上で作った盤面を初期解として、区画の幅方向の順番を入れ替えてパーティションの変更によるコストを最小化していきます（縦方向の分割をしている横線は無視）

　全日程を同時に焼いてもいいのですが、2日目から順番に盤面を確定させていくと差分計算が簡単そうに思えます
　→後ろの日の盤面との差は考えなくてよい

　このような考え方で、幅方向の入れ替え近傍で山登りをした所スコア25,818,021になりました

　現状、幅方向に余った分については最後の区画を端まで伸ばす処理にしています
　余りを上手く使って、パーティションの共有ができると更にスコアが伸びるはずですが、余りを利用した遷移が難しいです...
　ただ、今の解法から伸ばすには避けられないので、頑張って考えてみます

7.オフセット遷移追加焼きなましver

　各区画について、オフセット量を記憶する配列を別で設けて、コストが下がるまで幅を増やしていく遷移を追加しました
　また、低頻度で全てのオフセット量を0にする遷移も入れています

　下は、seed=1のビジュアライザです
　所々黒い縦線になっていて、パーティションの変更が減らせていることが分かります

seed=1, Score=534,685

8.再考察

　8/25(月)時点で126位という状況です

　今の方針だと伸びしろがあまり無さそうなので上位の解法を想像してみます

　理想の盤面は、最初から最後までパーティションの増減が無く、全ての希望面積を満たすような形になるはずです
　そんな配置が可能なのか現実味がありませんが、どれくらいの密度の配置になるのか確認していなかったので、入力生成方法を読みます

　パラメータ
　平均空き面積　とあります
　実際に計算してみると、平均空き面積は2,500~250,000の範囲のようです

　を求めて、集合を生成して、、、と書かれています
　要はは希望面積の累積値のようです
　こちらも実際に計算すると、625,000~998,750の範囲のようです
　最悪パターンでも、1,250は面積に余裕があるということは分かりました

　逆に最も余裕のあるケースだと、貪欲に実装しても満点を取ることができそうです

9.区切り幅を焼きなまし

　前の解法では、各日毎に区画をマージしていって幅を作っていました
　全日程で同じ幅を使うことを考えると、その幅の増減と区切り数の増減を近傍とした焼きなましをすると、良い解が得られるような気がします

　各日でその幅をどう使うかは、面積の大きい方から貪欲にあまりの少ないように詰めていきます（ここも探索した方が良さそう）
　貪欲に詰めていくだけでも、くらい掛かって非常に重いですが、seed=0のような簡単なケースでは結構良いスコアを出すことが出来ました！

seed=0, Score=8,461

　一部のケースとはいえ、最良に近いスコアを出すことは相対評価スコアにおいてかなり重要なことなので、これを提出して100位以内に入ることが出来ました

　平均空き面積の時は前の解法を採用するようにしたところ更に順位が上がりました！

10.満点解法の実装

　各N毎にD日間の希望面積の最大値で区画を用意すれば、コスト0を実現することができます
　ただ、の一部のケースでしか実現しないため、現時点の順位にはあまり影響はないような気もします

11.平均空き面積が厳しいパターンの貪欲解法

　平均空き面積がの場合、「7.オフセット遷移追加焼きなましver」の解法を用いていましたが、途中まで各日で共通のパーティションを持てないか考えました

　探索で求める方法が難しいため、貪欲に解を作ってみます
　具体的には、全ての希望面積の内で最大のものを選び、一つの区画を作ります
　他の日は、その区画に収まるような組み合わせの内、最も面積のあまりが少なくなるように区画を分割して納めます
　この組み合わせは、 n番目の区画までで、高さkとなるように選んだ場合の面積余りの最小値。のような感じのdpで求め、復元することで得ることができます

　最後に幅が溢れてしまった場合、最後に作った区画を棄却し、日ごとに余りが最小になるように縦長横長を選択しつつ埋めていきます

12.パラメータ調整

　終わりの5日辺りは新しい案が浮かぶこともなく、焼きなましの温度や近傍設計を変えてみたりしていました
　無駄という訳ではなく、得点自体は結構改善していったので何もしないよりはマシだったように思います

　高速化することで改善できそうな気もしましたが、700行ほどあるpythonコードを使い慣れないnimに変換する気力はなかったため、次は最初からnimで書きたい気持ちが強くなりました

　最終的に、seed=0のような簡単なケースではかなり良いスコアとなりました

seed=0, Score=362

13.終わりに

　コンテストに取り組んだ方々、お疲れさまでした
　今回も難しいながらも期間を通してしっかり楽しむことが出来ました！

　大きく方針は外れていなかったものの、各幅の中にどの区画を入れるかの箇所を妥協して貪欲に実装したのが致命傷だったようです
　dpや2分探索で解を作った方が多くいて、アルゴ力が足りないが故の発想の足りなさが順位を下げる結果となりました

　nimへの持ち替えと、アルゴ強化をして次の長期AHCに備えて引き続き精進を進めたいです

【色変記事】入水しました

はじめに

　Atcoderに触れてから約3年、本格的に取り組み始めてから約8カ月で、当初目標にしていたアルゴ水になることができました
　ここまでやってきたことなどを振り返ってまとめたいと思います

横軸を回数に

精進量

　基本は緑diffまでの問題に取り組んでいました

入茶まで

　競プロを始める前は、業務改善でエクセルVBAやPythonを使って「動けばいい」程度のプログラムを書いていました
　そんな中、偶然AtCoderを知ってる人と話す機会があり、改めて取り組み始めました

　毎週ABCに出るところから始めて、時間中に取り組んだが解けなかった問題(CかDまで)を終了後に解説ACするようにしていました
　新しくデータ構造などを学ぶことはあまりなく、出来ない問題に直面してから学ぶような感じでした

　学んだ事

　set(集合)、二分探索、dfs、グラフなど

入緑まで

　前までと同じく、週末にABCorARCに出て問題を解いて、終了後に振り返るといった感じで取り組んでいました
　dp(動的計画法)が全然理解できずに、2週間くらいスマホで色々な記事を眺めたりしたのをよく覚えています
　自前のライブラリを作り始めたのはこの頃からで、同じ言語の提出を見て、良さげな関数や書き方があれば手元にコピーさせてもらっていました

　学んだ事

　DP、UnionFind、heapq、最短距離探索など

入水まで

　今のままABC参加だけしていても、水色にはなれそう。と漠然と思っていましたが、年内に到達したい気持ちもあったため、秋頃からはコンテスト外で精進する時間が増えていきました

　解けない問題は、解説を読む→理解できなければ人のコードを読む。の順で解くようにしていました
　そこまでしても理解できなかった場合は、提出せず未ACで放置して後からまた取り組めるようにしています

　以下、取り組んだコンテンツと進捗です

Problems Training

https://kenkoooo.com/atcoder/#/training

　Hardは、解けそうで解けない問題がいい感じに並んでいて、考察力を付けるのに役立った気がします

競プロ典型90問

競プロ典型 90 問 - AtCoder

　★4まではほぼ埋めました
　実際に埋め始めたのは年明けからでしたが、もっと早くやっておけばと思っています

その他

　時々まよコンに参加させてもらったり、過去のコンテストをバチャで走ったりしました
　ARCにも、毎回ratedで参加していました
　レートが下がるリスクより、2時間真剣に取り組むことの方が大事だと思っています

コンテスト参加環境紹介

　他に紹介する機会がないのでここで
　VScodeで開いたnotebookで実行しています
　テストケースは毎回手作業でコピペしています...

　それでも、dpや配列の中身を実行後からでも手軽に確認できるので、この環境は割と気に入っています

未習得・今後学びたい内容

　内容をあまり理解していないものも多く、同じ意味の言葉があるかもしれません
　逆に、この辺りは知らなくても水色にはなれるのかなと思います

• 桁DP、確率DP、木DP
• トポロジカルソート
• 最大流、最小費用流、SCC
• BIT、双対セグ木、遅延セグ木
• 2-SAT
• ダブリング
• 平方分割
• 畳み込み
• Grundy数、Nim

今後

　青パフォを一度も出していないので、青パフォを出すことと水色安定を目指したいと思います！

AHC030参加記【最終149位】

解説

最終解法の概要

　(基本)1マスずつ掘って、油田の位置を絞り込んでいく解法です

ざっくり埋蔵量把握

　Mが6以上 かつ 埋蔵総量がエリア(N^2)の4割以下の時、(N//5+1)^2分割の正方形でエリアを占って、ざっくりとした埋蔵量を把握します
　後述しますが、0を狙って掘りたい時と、1以上を狙って掘りたい時があります
　全く埋蔵量の期待ができない箇所を掘っても意味がないため、その優先度を決める際に使います

seed=19

埋蔵量0位置による油田配置箇所絞り込み

　埋蔵量が0の位置によっては、油田を置くことの出来ない場所を判定することができます
　実装上は左上を基点として、最大N^2の要素をSortedSetで持って管理しました
　ただ、未探索エリアが広いと中々絞り込みが進みません

埋蔵量1以上位置による油田配置箇所絞り込み

　埋蔵量が1以上の位置について、その場所に置かれ得る油田の種類数が同じ時、その油田については必ずそのマスを使うことが確定します(説明画像略)
　実装上は各マスごとに、置かれ得る油田の種類をsetで持って管理しました

　油田の配置を必ずしも1つに確定する絞り込みではありませんが、かなりの量を絞れるため他の絞り込みと複合して大きな効果を発揮してくれました

埋蔵量オーバーを加味した油田配置箇所絞り込み

　埋蔵量が1以上の位置と、既に確定した油田の位置がある場合、他の油田を置くことができないことを判定できます
　実装上は各マスごとに、確定した油田の種類をsetで持って管理しました

油田配置可能箇所による埋蔵量0位置の確定

　ここまでで絞り込んだ、油田配置可能位置を全探索して一度も触れられなかったマスは、必ず埋蔵量が0なことが確定します
　いずれかの絞り込みで変化が発生した場合は、絞り込みをやり直しています

1マス掘り場所取得・実行

　未調査マスについて、評価値の一番高いマスを調べます
　評価値の基本は、油田配置可能位置を全探索してマス位置に値を加算していきます
　より多くの選択肢に影響を与える位置を調べたい気持ちがあります

　油田サイズ(マスの量)の最小が9以下の時、1以上の埋蔵量位置を含む油田配置にボーナス点を付与しています
　その理由としては、油田サイズが小さいと埋蔵量0マスを埋めていくことによる、油田配置の絞り込みが機能しにくいためです
　また、埋蔵総量がエリア(N^2)の3割以下の時、その傾向を強くしました

　ε=0.01の場合、2マス占ってもほぼ100%真値が得られるため、埋蔵量0が確定したマスと一緒に2マス占うことで、コストを抑えました

その他の工夫

　油田の置き方の絞り込みが進んで10^5パターン以下になった場合、現状の配置に矛盾しない配置を一つ探し、そのマスの評価値を下げました
　直接掘るより、他を掘って絞り込みを進めた方が良いスコアが出た気がします

提出コード

　pypy3で書いています

atcoder.jp

参加記

はじめに

　久々の長期AHCということで、かなり楽しみに待っていました
　それなりに時間は取れそうなので、納得するまでやり切りたいです

　意識すること
　・評価関数は指標(単位)を揃えて考える
　・説明できるレベルまで考察してから実装する
　・差分計算を頑張る
　・推定から逃げない

1.問題

atcoder.jp

　N×Nマスの島に、M個の油田がありその形状は示されている
　少ないコストで、油田を含むマスを特定せよ

　島の大きさ 10≦N≦0
　油田の個数 2≦M≦20
　エラーパラメータ 0.01≦ε≦0.2

2.開始直後の考察

　苦手意識のあるインタラクティブ形式だ...
　v(i, j)>0であるマスを特定する=全油田の場所を特定する(とは少し違う？)

　1マスを掘ると確定するなら、N^2のコストが下界になる
　複数マス掘る場合の分散を含んだ値をどう扱うかがキモになりそう
　　低コストで大量に掘る方が高得点になる場合があるかも
　　全てv=0の集合を掘った場合に、全て0であると確定できるkの範囲がありそう

　バラツキのある情報は、ベイズ推定でやれそう（使ったことない
　　各マスについて石油埋蔵量v=xである確率とか？
　　　ポリオミノをそこに置いた時の確からしさが見れそう！

　ビジュアライザを見て、思ったより空の区画が多い
　　形状によってはv=0の区画を最初に確定できる

3.貪欲解

　Pythonのサンプルプログラムが用意されていたので読みます
　全てのマスを掘って実際に石油が出たマスを出力するだけなので、これよりマシな貪欲解法を考えてみます

　既に得た情報(特に石油量0のマス)から、各油田がどこに置けそうかは全探索で試せば見つけることができます
　出来るだけ石油量0のマスを掘らずに～ということを考えていたら、石油が掘れそうなマスから掘っていけば良いのでは。と思いました

　0で初期化したN*Nの変数に対して、各油田が置ける場所を全探索しマスに加算していきます
　最も大きい数字となったマスが、期待値が高くなるはず。という算段です

左:加算後の配列　右:油田の形(例)

　また、石油量が0だった場合でも、そのマスを含む油田の置き方はできないことがわかるため、探索位置の絞り込みに使えます

　以上の解法でseed=0を解いた時の出力が以下になります
　見るからにサンプルより強い解法にすることが出来ました

seed=0, cost=50.0

　現在、コンテスト開始初日の25時で、9位につけることが出来ました
　筋は悪くない。という感じだと思いますが、1マス掘りだけではこれ以上は厳しいかもしれません
　複数マス掘るやり方を頑張って考えてみます

4.複数マスの考察

　複数マスを占った際、埋蔵量の総和にバラツキを含めた値を得ることが出来ます
　以下は、エラー率εと総和v(S)を固定してマス数kを振った時のデータになります

　正規分布の累積分布関数を用いることで、ある値xが得られたとき元になった総和の値についての確率を得ることができます
　例えばk=2の時、v(S)=1は24%、v(S)=2は71%であることがわかります

　問題は、各マスの情報をどう更新するかですが
　2マス調査して総和が2である確率が71%だとして、2マスの埋蔵量の組み合わせは(0,2) (2,0) (1,1)の3パターンあることになります
　71%を3分割して、この調査について各マスがその埋蔵量である確率に累積して、最後に各マスの情報を更新していけば良い気がします

　今わかっている問題点としては、エラー率が高い場合は4マス調査をしても埋蔵量の判定をしきれない→1マス掘ったほうがマシということです
　ここで、埋蔵量が0のマスを効率的に調べていけば油田の場所が一意に定まり、調査回数を減らせそう。と気付きました

　調査する対象は貪欲に決めたいですが、焼きなましやシミュレーションで期待値を求めるやり方もありそうです

5.エラー率調査

　複数マス計測時のエラー率について、どれくらいまで使えそうか確認しました
　seed=0について、計測値を1に固定した上で4マス計測し、エラー率を振った際に得られる値になります
　エラー率0.05あたりから、結構外れた値が返ってくるように見えます
　エラー率0.2までいくと、平均値も上がっている影響でほとんどの場合で真値とは違う値が取得されてしまうようです

　ちなみに、2マス計測時は以下のようになります
　これくらいなら使えそうですが、今はどう使うか思いつかないので後回しにします

6.1マス掘り戦略再検討

　1マス掘り戦略に立ち戻って、別の戦略を考えます

　油田mが(i, j)を基点としたマスに配置される確率を考えると、
　全マスについて、埋蔵量の期待値を出すことができます

　1マス掘った際の実際の値と期待値の誤差を修正するように確率を補正していけば、正解の配置に近づくような気がします
　計測した結果と期待値の差diffに学習率θを掛けた値を、そのマスに影響している箇所に引き算をして補正します

　4,5時間かけてなんとか実装しましたが、N,Mが大きいパターンだとTLEしてしまう上に制約が小さいパターンでも優位な結果にはなりませんでした...
　ただ、期待値という考え方はアリに思えます

7.ボツになった戦略たち

• 　各油田の基点(i, j)確率を推定
• 　各マスの埋蔵量期待値を推定
• 　各マスの埋蔵量が0~5である確率をそれぞれ推定
• 　埋蔵量1以上のマスからBFSで埋めていく
• 　判明しているマスに矛盾しない油田配置を探索（検討中

　埋蔵量期待値を求めるアニメーションはいい感じだったので、ここに貼りつけて供養とします...

8.1マス掘り戦略再々検討

　最後の週末まで、推定で頑張れないか色々トライしていましたがいよいよ諦めて、1マスずつ掘っていく方針を詰めていくことにします
　自分のやり方としては、手元で100ケース回して苦手そうなケースやまだ伸ばせそうなケースについて、随時対策していく感じで改善してきます
　今回は、相対得点なのでスコアのlogをとった値の総和を評価しています
　(cost100→99より、cost10→9になるほうが大事)

　詳細は最終解法の方に書くことにしますが、以下のような改善をしました

• ε=0.01の時、埋蔵量0のマスと一緒に2マスで占うことでコスト低減
• 埋蔵量0のマス配置的に、油田の配置を確定できるときは確定する
• 掘り済みマス目線で、ある油田しか配置しない場合は、そのマスを使用しない油田の配置箇所を探索しないようにする
• マップに対して埋蔵量が少ない時、広めにサーチしてざっくり埋蔵量の分布を見る
• 油田の最小サイズによって、0を埋めるor埋蔵位置を埋めるかを切り替える
• 判明している埋蔵量に矛盾しない配置を一つ決めて、それ以外を優先して調査

9.おわりに

　バラツキを考慮した方針をなんとか使いたいと頑張りましたが、結局扱いきれずに終わってしまいました

　ベイズ推定について、自分なりにコードに落とすことまでは出来たので、延長戦までしっかりやって理解を深めたいです

AHC028参加記【最終97位】

はじめに

　短期AHCの場合は、深い考察をしている時間がないためとにかく筋の良い貪欲解を目指していきます
　あわよくば橙パフォとれたら良いなと思っています

1.問題

atcoder.jp

　N×Nのキーボードがあり、M個の縁起の良い文字列を入力したい
　できるだけキーの移動量が少ない操作を求めよ。という問題でした

seed=0, score=7289

2.開始直後の考察

　M=200という制約と縁起の良い文字列は長さ5であるということから、最大でも1000文字の入力で足りることが分かります
　つまり、操作回数の上限5000回は無視できます
　→出力回数や操作回数の上限の余裕度を理解しておくことは大事

　前の文字列と後ろの文字列で重ねられる所は、重ねていく方が良さそう

　M=200の文字列の全組み合わせは、200!=10**375なので全探索は不可能
　→文字列を連結しておけば可能になる？

3.最終解法(DP+貪欲)

　いきなりですが、最終解法の解説になります
　解説放送(0:26~くらい)にあった、DP+貪欲とほぼ同じ解法になります

ALGO ARTIS プログラミングコンテスト2023 冬（AtCoder Heuristic Contest 028）解説 - YouTube

・前処理

　全文字列を比較して、4,3,2文字の重なりがあれば適宜合体させます
　strMap[i][j][s] i行j列から見て、文字sについての (移動コスト, 座標) のリストを作成

・次に打ち込む文字列の全探索

　現在位置(cy, cx) から文字列seachStr を入力するときの最短経路をdpで計算します
　dpは、遷移先座標をキーにして、(最小コスト, 遷移元座標)を値として入れていますが、もっと良い方法があると思います

　文字列seachStrについて、直前の文字入力と被る文字は省くようにしています

・打ち込む文字のdp経路復元
　上で作ったdp[-1]の最小コストとなる座標から、遷移元座標を辿って経路復元します
　i文字目のdp[i]内の最小コストを辿ろうとすると、正しい遷移が出来なかったため座標もメモしておいて辿る処理にしました

　以上の処理を文字列分繰り返しています

4.細かい工夫

　次に打ち込む文字列の全探索の際に、文字列長さと5の差の絶対値でコストを割った値を使っています

　普通の文字列より、合体した文字列や直近1文字と重なっている文字を使った方が良いのでは。という気持ちで入れ、スコア向上しました

5.最終提出

　pypy3で書いています

atcoder.jp

6.終わりに

　短期コン難しい。という感想です
　文字列のDPで最適経路までは思いつきましたが、実装が悪く遅すぎたため焼きなましには持って行けなかったと思います
　長期コンの予定もいくつか決まっていて、今からわくわくしています
　次も楽しめるように引き続き頑張ります

AHC029参加記【最終42位】

はじめに

　2300perfを取れば入黄できるので頑張りたいです！

1.問題

https://atcoder.jp/contests/ahc029/tasks/ahc029_a

　M個のプロジェクトに対して、N枚の方針カードを持っている
　1000ターンの中で方針カードを使って、プロジェクトを進めたり、キャンセルして入れ替えたりしながら所持金の最大化を目指す

2.考察

　正直問題を理解するのが難しいと感じました（参加者少ないかも？
　栄冠ナインのようなゲームをやったことがあればイメージしやすい気がします

　最初に考えたことをまとめたスクショです
　インタラクティブ形式なので、プレイアウトが良いかなと思いました

　隠しパラメータx0~4は、問題文に内容が書いてあります

　プレイアウトを精度よく行うには、カードの種類の傾向を捉えることが重要そうです
　とりあえず、強い貪欲を作りつつ本質理解を進めていきます

3.1日目)貪欲解

　最終的にプレイアウトを実装したいため、スコアを手元で計算できるように。という意識でコードを書き始めました

　考えるべき貪欲解は、方針カードを使う所と方針カードを補充する所です
　それぞれについて、貪欲解を作るための気持ちを書き出しておきます

方針カードを使う所
　・効率の良いプロジェクトから手を付けていく
　・できるだけ大きい労働力を使う
　・価値/残務量が1未満のプロジェクトはキャンセルしたい
　・増資はできる限り行いたい

方針カードを補充する所
　・通常労働カードは、労働力-コストで評価
　・全力労働カードは、労働力*プロジェクト数/1.5-コストで評価
　　→全体に作用する以上、すべて生かしきれないだろう
　・キャンセルカードは、多分不要なため-1評価
　・業務転換カードは、評価が難しいため0評価
　・増資カードは、残りのターン数とコストを比較して良さそうならINF評価

　それぞれのフェーズで、評価値最大の評価を採用します
　どれくらい良いのかわかりませんが、一旦提出してみます

seed=0, score=7,941

　が、提出したところ[RE]との表示が！
　問題文をよく読むと、ビジュアライザとジャッジ時の入力形式が異なることに気付きました（サンプルコードもちゃんと読みましょう
　出来る範囲で修正し、上手くいくことを祈りながら再度提出します

　今度はACできました！
　順位は40位程度と微妙ですが入出力が正しいことと、点数計算が正しく出来ていることがわかったので、一安心です

　貪欲を改善しつつ時々提出しますが、なぜか一向に得点が伸びません
　というか、50ケース回してこんな得点にしかならないのはいくら何でもおかしい。と0時を過ぎてようやく気付きます

　結果的には、所持金を受け取る処理で間違った変数へ値を入れておりずっと0円生活を強いられていました！泣
　修正して提出したところ、647,203という得点を得ましたが順位としては30位程度であまり良い順位にはなりませんでした

4.2日目)ジャッジ傾向ハック

　当初より考えていた、プレイアウトを実装してみます
　1手進めるごとに、次の行動の評価値上位5つを最後まで貪欲法で進め最もよいスコアとなる行動を採用することにします

　が、何故かスコアが上がりません
　最上位のみを評価して選択するように書き換えて実行すると、貪欲法と同じスコアがちゃんと出ています
　何らかのバグがあるように思えますが、そもそも実行するのに1分くらい掛かっているため、Pythonでプレイアウト方針は厳しいような気もしてきました

　方針とは別で気になっていることがあるため調査します
　50ケースも回しているのに、900k程度の得点しか取れていないのはおかしい（seed=2は、1ケースのみで4Mくらい出る）ように思います
　本質ではありませんが、以下のようなコードを入れて提出してみました

　このことから、N<=3のケースが19/50、M<=3のケースが13/50もあることがわかります
　入力ケースの生成方法を見ると一様分布なため、テストケースが偏っているようです
　だからといって狙って上手いスコアを出せませんが、順位表に拘って提出を行うとシステス(3000ケース)で大幅に落とされることが想像できます
　ローカルで回した得点を最大化するように気を付けた方が良いことがわかりました

　ここで、ABC334に出ました
　結果は、ABDEの4完で正のレート変動を得ることが出来ました
　B, C難しすぎませんか？

5.解法毎のスコアまとめ

　貪欲解法のパラ調整をしていても、中々スコアが上がらないため方針とスコアを一旦まとめて、次のアイデアにつなげたいと思います

・0番目のカードのみ取得、最も効率の良いプロジェクトに使う
　seed0~99 合計 114,256

・増資カードを買える時は買ってすぐ使う
　seed0~99 合計 183,896

・増資カードを買って利益の出る時は買ってすぐ使う
　seed0~99 合計 294,354

・通常労働カードについて、[労働力-コスト]が最大のカードを補充する
・最も効率の良いプロジェクトに、最大の労働力カードを使う
　seed0~99 合計 1,083,720

・最も効率の良いプロジェクトに、極力オーバーしない最大の労働力カードを使う
　seed0~99 合計 4,919,369

・キャンセルカードを持っている場合、最も効率の悪いプロジェクトに使う
　seed0~99 合計 6,407,740

・全力労働カードを持っている場合、オーバーしないなら最優先で使う
・オーバーする場合、かなり大きいペナルティ
　seed0~99 合計 4,111,178

　ここで悪化しました。通常労働カードと全力労働カードを使うバランスを上手く考えないといけないようです
　全力労働カードを残す方向へ調整すると手札を圧迫してしまい、逆に使うようにすると無駄に使われる労働力が多くなります

　一つ考えたのは、手札の枚数に応じてペナルティの重さを変えたらどうかということです
　手札数N, 労働力w, 残務量h, 価値v, コストアップu(=2^L) とある時に、
　p1=w - max(0, w-h-u) * N, p2=-w として、配列[[p1, p2], .....]を昇順ソートした最後尾となる方針カードを使うことにしました
　気持ちとしては、大きい労働力・無駄な労働力は少なく・少ない残務量からを実現できるような評価としました

　seed0~99 合計 17,331,451

・全力労働カードについて、[労働力*M-コスト]が最大のカードを補充する
　seed0~99 合計 66,226,919

・通常労働カードについて、[労働力*0.7-コスト]が最大のカードを補充する
・全力労働カードについて、[労働力*M*0.7-コスト]が最大のカードを補充する
　→労働力を使い切れない判断をする場面があるため
　seed0~99 合計 279,160,538

6.大バグ発見②

　ローカルでのスコアは徐々に上がっていきますが、提出してのスコアが全然上がりません
　流石に何か大きな勘違いをしていないか、問題文やサンプルコードを読みますが特になにも見つかりませんでした
　ローカルとジャッジの違いを見ていた時に、ジャッジでは2^Lを含んだ入力なことに気が付きました！
　カードを選ぶところの処理でジャッジ時に、余計に2^Lを掛けており、カードコストが異常に高くて買えない状態になっていたようです

　修正して提出したところ、無事高い得点になっていました！
　順位としては40位程度ですが、ようやくスタートラインに立てた気がします

7.迷走

　貪欲解の改良以外にやることが思いつかず、だらだらしてしまっています
　また、提出した得点と順位の相対がとれずどの方針が正しいのか分からなくなってきました

　各ケースの理論値さえわかれば、それに対する比率で良さが測れそうですが、その理論値の導き方が分かりません
　また、少しパラメータを変えただけでも、増資カードが買えるか買えないかなどで大幅にスコアが変動してしまい困ってしまいました

　得点がこれだけ違うのに、前に提出した方が良い順位になるのはなぜ？
　(タイミング次第での誤差にしか見えない

8.最終日

　午後休をとってAHCに全力労働するつもりでしたが、体調不良でほとんど取り組めませんでした...
　貪欲を詰めるにも限界があったので、そこまで影響はなかったかなと思います
　下は、1000ケース回して一番高いスコアの出たケースです（あと1回で完了できるプロジェクトあるのに！という気持ち

seed=935, score=5,244,768,750

9.最終方針

　方針としては、カードを使う・カードを補充する2つの場面に分けて一番評価の高い行動をする貪欲です
　評価値は、行動によっていくら稼げそうか。という観点になっています

　労働力power, コストcost, 残務量work, 価値reward, 増資回数L として説明します
　また、最大化したい評価値p1, p2（p1の方が優先度高い）と置きます

方針カードを使う所
　・通常労働カード　p1=power-max(0, power-work-2**L)*2, p2=-work
　　　労働力の高い方から使うが、はみ出す場合は大きめにマイナス評価をします
　　　2**L分ははみ出して労働力を使うことを許容します
　　　残務量の小さい方から取り掛かろうとします

　・全力労働カード　p1=Σpower-max(0, power-work-2**L)*2, p2=power
　　　通常労働カードとほぼ同様の考え方です

　・キャンセルカード　p1=work-reward-2*2**L, p2=work
　　　コスト0カード2回分よりお得そうならキャンセルをします

　・業務転換カード　p1=Σ=work-reward-2*2**L, p2=1
　　　キャンセルカードとほぼ同様の考え方です
　　　手元に2枚以上あるor労働カードが少ない時は最優先で使います

　・増資カード　p1=10**10, p2=2
　　　すぐ使います

方針カードを補充する所
　残りターンが10以下の時は、コスト0のカードしか選びません
　今の場に対して使う評価値をp1と買い置きする場合の評価値をp2としています
　ccdf(相補累積分布関数,生存関数)は、gauss(0, 1)の分布に対して値が小さい程1に近く値が大きい程0に近い値を返します

　・通常労働カード　p1=power-max(0, power-work-2**L)-cost
　　　　　　　　　　p2=power*ccdf*1-cost
　　　　　　　　　　p2=power*M*ccdf((cost-power*M)*3/power/M)*0.7-cost

　・キャンセルカード　p1=work-reward-2**L-cost
　　　　　　　　　　　p2=2**L-cost
　　　キャンセル系は、max(1, N//2)までにしています

　・業務転換カード　p1=Σ(work-reward-2**L)-cost

　・増資カード　stay=(T-turn)*2**L, exc=(T-turn)*2*(0.8+(K+M)*0.1)*2**L
　　　　　　　　p1=exc (if exc-cost>stayの時)
　　　今のまま(stay)で稼げる額と増資後(exc)に稼げる額を、KとMから作る係数を使って比較して、得そうなら買います
　　　また、rand(200, 1000)の結果が700-50*Kより悪い場合は買いません

10.最終提出

　pypy3で書いています

atcoder.jp

11.終わりに

　今まで参加した中で、一番分からない度が高いコンテストだったように感じました
　そんな中でも、50ケースの傾向把握して順位表に拘らない提出を選べたのは良い動きだったと思います
　終わったあと、相対評価の場合はスコアをlog取った総和で評価すると良い。という話は勉強になりました（ずっと生スコアの和で見ていた

　結果は、42位のperf2279で念願の入黄することができました！
　アルゴ緑と3色差ついてしまいましたので、アルゴも入水目指して精進したいですね

*1:cost-power)*3/power)*0.6-cost
　　　使う所とは違い、はみ出す分はそのままの差分として評価しています

　・全力労働カード　p1=Σ(power-max(0, power-work-2**L

AHC027参加記【最終40位】

はじめに

　前回の長期コンと同様に、記事の下書きを書きながらAHCに参加します
　とりあえず手を動かすより、考察を重ねていけるようにしたいと思っています

　長々と書いてしまったので、最終解法だけ見たい方は飛ばしてください

1.問題

https://atcoder.jp/contests/ahc027/tasks/ahc027_a

　N*Nの部屋があり、中には一部壁となっている箇所もある
　お掃除ロボを動かして、床面を出来る限り綺麗にするという問題
　床面には汚れやすさが決まっており、掃除した直後から時間経過で汚れていく
　10^5以下のステップで無限ループ出来るような操作が出力となる

2.1日目）貪欲解

　事前にHTTFの過去問は一通り見たので、お掃除高橋くん2号の文字を見てホッコリしていました
　問題の理解は比較的簡単でしたが、どう解いたらよいかかなり悩みます
　とりあえず、スコアの出る出力を書いてビジュアライザを見ました

　下端まで行って一つ右へ、上から1マス下まで上がって一つ右へを繰り返し、最後に右上から左上まで帰るだけの操作をしました

seed=0

　把握できたことを箇条書きで書きます
　・汚れやすい領域がある程度固まって数か所ある
　・汚れやすい箇所を放置するとどんどん悪化する
　・右のグラフでどのターンの盤面が悪いのかわかりやすい！
　・10^5という制約はあまり関係ない？(十分足りそう
　・出力長さLが決まらないと初期汚れが決まらない

　最初に思いついたのは、「現在値から移動した時に、最も汚れている箇所へ行く」という貪欲解なので、まずはこれを頑張って実装してみます

　前処理書いているだけで無限に時間がかかります...
　まず壁を考えたくないので、無向グラフ化しました
　また、毎回経路探索すると無駄な気がしたので、多始点BFSで全地点間の最短距離と経路を配列に用意しておきました

　それらしい解が出ることを確認していざ提出！

初提出

　seed=0~5くらいでしか確認していなかったので他でも確認したところ、出力文字数が10^5を超える時があるようでした
　角に汚れにくい床があると、探索しないということに気付いたので一定の移動量(適当にN^2.5)を超えたら、未探索床のうちで一番汚れている箇所へ行くようにしました
　N=40でも、11,000回程度でゴールできるはずなので再提出！

　1ページ目とはなりませんでしたが、とりあえず正の得点を得ることができました

　ビジュアライザを確認します
　一番濃い赤を消すように動けていますが、近くにある汚れた床を先に掃除するように動いた方が効率良さそうに見えます
　方針を考え直した方が良さそうですが、日を跨いでいるのでまた明日にします

seed=4, score=14,645,454

3.2日目）

　布団の中で「遠くを行ったり来たりするのが無駄なら、距離が遠いほど選びにくい方が良いのでは」と思ったので、そのように実装しました

　具体的には、f:現在の床の汚れ評価値, v:現在値からの最短距離, p:床の汚れやすさ
とした時に、(f + v * p) / (v + 1) を各床について計算して、評価が最大の場所へ向かうようにしました

　ビジュアライザを確認します（show_routeに気付きました！
　前回と比べると、周辺を綺麗にしてから遠くの汚れへ向かっていることがわかります
　ただ、近くを掃除する際のルートが重なっている挙動は無駄に見えます
　（掃除してすぐの床を掃除する必要はないため

seed=4, score=9,810,979

4.再考察

　12/2 18:00頃の時点で13位の位置にいますが、まだ1週間あるので一度落ち着いて考え直してみます

　汚れやすさdの生成方法を読みましたが、よく分かりません...
　dの分布を改めて見てみると、汚れやすい箇所とそうでない箇所がある程度分かれているように見えます
　また、壁を生成した後に汚れやすさが決定されることも説明文から分かります

seed=4, 汚れやすさdのマップ

　汚れやすい箇所を繰り返し訪問しつつ、全体を埋めていく動きをさせたい気持ちになります
　何も思いつかないまま時間が過ぎて、夜になったのでとりあえずABC331に出ました

　大きな方針転換が難しそうなので、次の汚れへ向かう時の処理の判定を工夫してみようと思います
　一番評価値の高い箇所へ向かうようにしていますが、上位n個について巡回するようにすれば、近場でいったり来たりしないような気がします（実装できるのか？

5.3日目）dfs探索

　前日に考えた、評価値の上位n個を巡回する案はTLEレベルの遅さですが実装できましたが、得点は下がる結果になりました
　恐らく評価値の高い箇所へ向かうのが遅くなるからだと思われます

　次の案として、(cy, cx)→(ny, nx)へ向かう最短経路のうち最も汚れを回収できるルートを探索することを考えました
　dfsを使って実装したところ、こちらは効果ありでした

　また、最短経路だけでなく迂回路も許可した実装もして試しました
　ただ、迂回距離数を増やすとスコアが下がる結果でした
　前述と同じく、価値の高い箇所へ向かうのが遅くなるのが良くないと思われます

　パラメータ変更に走り出したので、結構行き詰ってしまいました
　スコア計算が出来ていないので、明日以降はその方面も考えてみようと思います

6.4日目）経路dpとスコア計算

　前日に行った、(cy, cx)→(ny, nx)へ向かう最短経路のうち最も汚れを回収できるルートの探索について、よく考えたらdpで解けることに気付いたため書き直したところ、5%程度改善しました
　迂回路を使う場合でも、bitDPで解けるはずですが未履修のため止めておきます

　貪欲解の限界を感じつつあるため、意地でも焼きなましをしたいと思い、いよいよスコア計算を書くことにしました

　各床について、その場所に訪れたターン数を記録しておき、その差分の累積和に汚れやすさを掛けて、全体を足し合わせればスコアが出るはずです
　ちなみに、0~Nまでの数字を全て足した値は、0.5*N^2+0.5*N で求まります

　手元計算とビジュアライザの値が合うことが確認できました！
　ただ、貪欲に比べ倍以上悪いスコアしか出ないのと、計算が遅く2秒以内ではとてもループが回らないため今のままではとても焼けそうにありません

　現状のビジュアライザを見て、改めて作戦を立ててみます
　比較的、汚れの集合に向かって移動できていますが、近場で交差するように何度も動いてしまっています
　解決案は浮かびませんが、問題点は見つかったのでまた明日考えてみます

seed=4, score=8,738,531

7.5,6日目）全探索dp

　全床の中で一番汚れ評価値の高い箇所へ向かう考えでしたが、経路をdpで計算できるなら現在値から全ての床へ行く経路もdpで評価できるのではと考えました
　迂回路は考えず、全地点へ最短で行く経路のうちで 経路の評価値合計/通る床の数 の最も高い経路を使うようにしました
　グリッド上の最短経路の数え上げdpを履修していたお陰で、そこまで詰まらずに書くことができ、スコアが10%程度改善しました！（提出時21位）

気合の浮上😃 pic.twitter.com/z8qNhLCYi5

— uta (@uta_cccc) 2023年12月5日

　再度ビジュアライザで確認した所、近場の赤色を無視して遠くへ向かう場面がありました
　そこで、数マス進んだら再度探索をやり直す処理を加えたところスコアが良くなるケースがありました
　ただ、計算時間が増えるためNが多いケースは無理な工夫となりました

8.7日目）制限時間の活用

　朝起きたら急に閃きました
　これまで、全床に到達したタイミングで探索を打ち切って(0, 0)地点へ向かって終了としていましたが、更に時間の限り探索をしたらどうなるのか。ということです
　時間を延ばして実行してみると、明らかにスコアが向上しました！

　今の解法の延長のスコア向上程度ですが、時間をかけるほどスコアが出ることが分かったため、より多くループを回すためのコード見直しに入りました
　いくつか工夫をしましたが、一番効果が出たのは2次元配列を1次元配列に変更したことでした

　2次元変数と1次元変数で添え字の変換が発生しないように、扱う全ての変数を1次元配列用に書き換えたことで、探索量が倍程度(おそらく)になりました
　不要なコードも減らし、いよいよ貪欲解の限界が見えてきました

9.8日目）迂回路処理

　3日目に考えていた、迂回路を使った探索方法を改めて考えてみました
　上手くいかなかった点として、評価値最大の地点に向かう途中で迂回するという考えが、評価の仕方と相性が悪かったように思います
　今の処理は道のりの汚れ評価値も加味した探索のため、迂回路の探索が上手くいくような気がします

　bitDPで解くしかないと思っていましたが、拡張ダイクストラのような感じで解くことにしました

　dpの更新は「nマス通った時の汚れ評価値の最大値」とすることで、最も汚れを回収できるルートを探索することが出来そうです
　ただ、処理が重いためN<=30の場合に限定しました

　頑張りの割には、若干のスコア改善(1%以内)でガッカリしましたが、汚れが溜まっている箇所へより早くいく必要があることを考えると、迂回という方針はやはりイマイチなようです

10.9日目）PythonからNimへ

　いよいよ改善案が尽き、処理速度アップも限界になってきました
　処理速度を上げればスコアが多少良くなることは分かっているため、言語を変えることを考えてみました
　C++かRustで検討して、C++で少し書いてみましたが全然進みません！（泣

　そんな中、XでNimの布教をしていた人のことを思い出し、トライしてみることにしました
　過去のNim提出コードを参考にしたり、ChatGPTに頼ったりしながら４，５時間格闘した結果、PythonコードをNimに移植することが出来ました！
　Pythonに慣れ過ぎて型を意識するのが大変でしたが、エラー文が親切なためデバッグしやすいのは非常に良かったですね

　ほぼ同じコードを提出しましたが、処理速度だけでスコアが少し改善しました
　ただ、順位はあまり変化なかった(25位)ので、これより上は方針から違いそうです

11.最終日

　無理だろうなと思っていた、山登り法を書いてみて予想通り上手くいかなかったため少しのパラメータ調整だけして最終提出としました

12.最終解法解説

　大枠の方針は以下になります
　・現在地から各床へ行動した時に、汚れ評価値平均の最大経路を探索する
    ・探索した先へ一気に行かず、数ステップで止めて再度全体探索を行う
    ・スタート地点に到達する毎に出力列へ追記していく

　また、Nの大きさによって探索方法を少し変えています
　(N<=25) 迂回5マスまで探索し、評価値平均が最大の経路で移動
　(N<=30) 迂回2マスまで探索、評価値平均が最大の経路で移動
　(N<=35) 最短経路のみ探索し、3マス進んだら再探索
　(N<=40) 最短経路のみ探索し、5マス進んだら再探索

　各マスの初期汚れ(floor)は、d*(N^2)/2 として到達する毎に0にしています
　探索時に使用する評価値は、(floor+d*(N**0.5))/(check+1) としています
　※checkは、各マスの通過回数

13.提出コード

　Nim

https://atcoder.jp/contests/ahc027/submissions/48356451

　pypy3(Nim提出とほぼ同等)

https://atcoder.jp/contests/ahc027/submissions/48305607

14.終わりに

　今回のコンテストは、これまでの長期AHCの中でも一番時間をかけたのではないかと思います（リアルが割と暇なタイミングでもあったが、54回提出は多すぎた
　個人的にはやれるところまでやった気持ちでいましたが、結果や他の方の解法が出てくると、悔しい気持ちが出てきます
　年内入黄を目指して、まだまだ頑張ります
　

AHC026参加記【最終161位】

はじめに

　コンテスト開始2時間前くらいからそわそわしながら待機していました　
　4時間は長いようで短いので、無理せずバグなく書き上げることを頑張ろうと思っていました

1.問題

atcoder.jp

　1~200まで番号の振られた箱が、10個の山に均等な高さに積まれています
　小さい数字の順に取り出すことが目的で、箱は任意の数をそのままの並びで他の山に積み上げることができる
　最大で5000回の操作が可能だが、適当に実装しても十分間に合う　

コンテスト中

2.~0h30m

　1から順に箱を取り出す関係上、まず1より上の箱をどうにかすることを考えました
　正の得点を得るために、取り出したい番号より上の箱を、となりの山へそのまま置くことにしました
　バグなくACコードを書き上げるだけで、30分経過していました...
　とりあえず、初提出して1.22Mの得点を得ました

3.~0h45m

　焼いたりすることを考えてみましたが、何も浮かばないため貪欲解を最適化する方向で動きました
　初期解では、隣の山へ置くとしましたがこれを工夫します
　各山の最小番号を見ると、次にその山を操作したいタイミングがわかります
　そこで、各山の最小番号の最大値の山へ移動させることにしました
　この提出で1.35Mを得て、順位表を見ると同じ点数の人が大量に並んでいたので、この提出でようやくスタートラインに立ったようでした

seed=0 初動

4.~2h00m

　次の案を考えるために、ここまでの提出でのビジュアライザを見ました
　seed=0で、次に3を取り出したい場面です
　貪欲解では一つ右の山へすべて積み上げますが、山の中にある9や19,20という小さめの数字の箱が気になりました

seed=0

　全て一括で動かさずに、小さい数字の箱があるときは分割して運ぶことを考えました
　動かす候補の集合内の最小値で2分割して（例で言うと、9より上を運んだ後9から下を運ぶ）、各山の最小値の最大値の山へ移動させる処理を書いて提出すると、1.37M
　分割数を増やして移動させる処理を書いて、1.38Mまで上がりました

5.~4h00m

　上で書いた貪欲解から、別解も考えて試したりしました
・1箱ずつ、各山の最小値の最大値の山へ移動させる ⇒ 微悪化
・移動先の山の選び方に、箱の数も重みづけに加えてみる ⇒ 微悪化

　貪欲解から抜けられずに微妙な工夫を加えて、最終得点1.386Mでフィニッシュしました

6.コンテスト中の最終提出

seed=0, score=9284

atcoder.jp

延長戦

　終了後に、上位の方々の解法が流れてきて衝撃を受けました
　似た方針でより上位の方もいましたが、各山をソートする方針が非常に強いようでした
　各山ソート方針で、本番3位相当の得点まで出すことが出来ましたので、やった内容を解説したいと思います

7.最終ビジュアライズ

　見た方が内容を理解しやすいと思い、最初に出します
　虹色に綺麗な山が積みあがっていく様子が見えて気持ちいいですね

seed=0, score=9488

8.貪欲解

　最終的には山登りをしますが、ランダム性を加えるだけなので貪欲解から説明します

　まず、取り出したい番号の箱がある山を選びます
　その山の箱をソートするために、空になるまで箱を他の山へ分けていきます

　赤線が、元の山の高さです
　一番左や一番右の山を見てわかるように、上に行くにしたがって数字が大きくなるように積み上げます(差が小さい場所へ積んでいく)

　右から3番目のように、連番で積めるところは昇順で積みます
　ソートする山へ戻す際に2箱一緒に持っていきたいからです

seed=0

　上の状態から、ソートした山を作ったものが下の画像になります

　各山の最上位置を見て、大きい数字から元の山へ戻していきます
　また、更に下の段を見てより大きい数字&ソート山の最上段より小さい数字な時、一緒にソートする山へ持っていきます

　そうすることで、元の山にはなかった数字を巻き込んで帰ってきたり、元の山にあったのに戻らない数字が発生したりします（改善の余地あり？）が、結構高いソートの山を積み上げることができます

　ソートした山は、今後移動する必要がないため序盤は高ければ高いほど良いと思っています

　また、箱を移動させる毎に各山の最上位置を確認して、取り出せる箱があれば取り出すようにしています

　元の山の箱を、他の山へ分けていくフェーズで、置き場所が見つからないことがあります
　その時は、一番近い数字の上へ置きました（一緒に運べる期待を込めて

　細かい工夫として、山へ箱を戻していく際にすでにソート済みの山を崩してしまうことがあります（無駄な操作
　戻す箱を選ぶ際に、完全にソートされた山かどうか判定を行うことで、小さい数字の箱を無駄に運んでしまう操作をなくしています（上から昇順かを愚直に書いています

9.山登り解

　貪欲解ではどの山をソートするかを選ぶ際に、取り出したい番号の箱がある山を選んでいましたが、ここにランダム性を加えました

　ソートする山を選ぶ際に、60%で貪欲解を、40%でM個の山からランダムに選ぶことを繰り返します（確率はseed=0で試しての適当な値です
　最も良いスコアの回答を保存しておき、1.8秒経過したら打ち切り出力します

　pypy3で書きましたが、大体4000回以上は回りました

10.延長戦提出コード

atcoder.jp

おわりに

　コンテスト中は、良い解が出せずにちょっと悲しい感じでしたが、延長戦で新しい知見も得られて結果的にはかなり楽しめました
　この記事が参考になる方がいれば幸いです

　2回以内で黄色になることを目標に引き続き頑張ります