はじめに
2300perfを取れば入黄できるので頑張りたいです！
1.問題
https://atcoder.jp/contests/ahc029/tasks/ahc029_a
M個のプロジェクトに対して、N枚の方針カードを持っている
1000ターンの中で方針カードを使って、プロジェクトを進めたり、キャンセルして入れ替えたりしながら所持金の最大化を目指す
2.考察
正直問題を理解するのが難しいと感じました（参加者少ないかも？
栄冠ナインのようなゲームをやったことがあればイメージしやすい気がします
最初に考えたことをまとめたスクショです
インタラクティブ形式なので、プレイアウトが良いかなと思いました
隠しパラメータx0~4は、問題文に内容が書いてあります
プレイアウトを精度よく行うには、カードの種類の傾向を捉えることが重要そうです
とりあえず、強い貪欲を作りつつ本質理解を進めていきます
3.1日目)貪欲解
最終的にプレイアウトを実装したいため、スコアを手元で計算できるように。という意識でコードを書き始めました
考えるべき貪欲解は、方針カードを使う所と方針カードを補充する所です
それぞれについて、貪欲解を作るための気持ちを書き出しておきます
方針カードを使う所
・効率の良いプロジェクトから手を付けていく
・できるだけ大きい労働力を使う
・価値/残務量が1未満のプロジェクトはキャンセルしたい
・増資はできる限り行いたい
方針カードを補充する所
・通常労働カードは、労働力-コストで評価
・全力労働カードは、労働力*プロジェクト数/1.5-コストで評価
→全体に作用する以上、すべて生かしきれないだろう
・キャンセルカードは、多分不要なため-1評価
・業務転換カードは、評価が難しいため0評価
・増資カードは、残りのターン数とコストを比較して良さそうならINF評価
それぞれのフェーズで、評価値最大の評価を採用します
どれくらい良いのかわかりませんが、一旦提出してみます
が、提出したところ[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回で完了できるプロジェクトあるのに！という気持ち
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で書いています
11.終わりに
今まで参加した中で、一番分からない度が高いコンテストだったように感じました
そんな中でも、50ケースの傾向把握して順位表に拘らない提出を選べたのは良い動きだったと思います
終わったあと、相対評価の場合はスコアをlog取った総和で評価すると良い。という話は勉強になりました（ずっと生スコアの和で見ていた
結果は、42位のperf2279で念願の入黄することができました！
アルゴ緑と3色差ついてしまいましたので、アルゴも入水目指して精進したいですね
*1:cost-power)*3/power)*0.6-cost
使う所とは違い、はみ出す分はそのままの差分として評価しています
・全力労働カード p1=Σ(power-max(0, power-work-2**L
