AtCoderへのDDos攻撃 : ABC301
ABC298から突如はじまったAtCoderへのDDos攻撃...
ABC300は対策できたようでちょっと安心していたがABC301はダメそう。。
提出はできるけどコードテストが重すぎて動かないよ！
AtCoder tools とか使っている人はいいのかもだけど…。
クラッカーのくせにプロコンを狙うなんて。。同好の士とは呼べないな。
DDosというのもダサい。が、それくらいしか攻撃方法がないくらいには対策できてるということかな…。
あまりに動かなくて途中で諦めたのでRatingはど下がりの予感。
すごく好きで毎週末の唯一の楽しみにしてたんだけど、しばらく参加は見送りかな。。
こう頻繁に止まるようではね。安定して開催できるようになったころにまた参加します。
↑この状態で1時間ほど動きません。
ABC 151 D - Maze Master のコーナーケース
グラフが与えられて、最も離れている点同士を求めるような問題の場合、
「どこでもいいのでテキトウな点から一回BFSして、最も距離遠い点Aを見つけ、点Aから再度BFSをして最も遠い点Bを見つける」
という二重BFSをやると、最も離れている点のペア(A,B)を見つけられる。
…と思っていたが、
”迷路上の最も離れている地点同士を求める”という問題である、このABC151 Dでこれをやると、WAになる。
例えば、スタートする"テキトウな点"を、左上から順に見て最初に壁ではなかった点にする場合、ケース【hand_04】だけがWA。
公式解説も、スタートする点を全探索するような方法をとっている。
手元で迷路をいくつも書いて、やってみる。全例通るんだけど？
何で【hand_04】だけ二重BFSでは通らないのか？
やっと見つけた”コーナーケース”は、
こんな迷路。
二重BFSをやってみる。
緑色の点を”テキトウな”スタート地点とした場合、こんな感じ。
最大距離は「6」にみえるが…？
真の解は、このパターン。
最大距離は「8」。
…ということで、この問題は、二重BFSでは通りません。
とりあえず「木」なら、二重BFSでよいけど…、ということのかな？
閉路がある場合は、ダメっぽいのかな（嘘解法で通るときもありそう？）。
AHC 019 のおもいで (MC Digital プログラミングコンテスト2023)
AHC 019 Silhouette Block Puzzle Creation
2023/3/18-4/2
概要
ブロック積み木をデザインしたい。指定した2セットの影の形を作れるような積み木セットを提案してください。子ども用なので、少数の大きいブロックだけで、無駄なブロックがでないように作ってくれると嬉しい。
（説明が難しいので詳しくは問題を参照）
取り掛かり
第一印象
・ビジュアライザがすごい。まわる！拡大縮小も無限！作った人すごい。
・説明文が丁寧。
（「ブロックは全て使い切らなくて良い。（が、全て使い切る方が良いスコアが得られる）」、「評価値は低ければ低いほど良い。」）
・評価式がわかりやすい。
・制限時間６秒でちょっと長め。
・最大でも14**3= 2744 で少なくともO(全ブロック数**2)まではいける。
ぱっと見では最適解がすぐ出そう？と思ったが、よく考えてみるとすごく難しい。
ある一つのブロックの形を仮に確定させたとして、それをどこに配置するのかでまったくその後が変わってくる。
二つの図形をランダムに分解して共通する立体を選んでいく方法もありそうだが、回転させた二つの立体が相似であることをどのように検出するのか？
前回(AHC018 - Excavation)のようにグラフに帰着させてみる…？立体で？
…これは無理。実装はできない。誰もできていないんじゃないかと、スコア表をみるとちゃんと有効な点数をとっている方々がちらほら。天才か。
そしておそらくテストプログラムをお試し提出した横並び点数がずらり。多くの方が苦労している感じはうかがえる。
とりあえず力ずくでやる。
なんとなく、トップの人の解法を想像すると、ブロックをちょっと消してまた増やして、とやっていそうな気がする。きっと最適な方法は適当に作った後の焼きなましなのだろう。
しかし、それにつながるような実装の方法が、取り掛かりすらわからない。AGCとかの1000点問題くらいわからない。
3日間ほど、1行も書かずに悩み続けたあと、なにもしないよりは、とランダムで運任せの解答をまずやってみる。
評価式からわかるのは、
・ブロック数は少ない方が良い。
・同じブロック数なら、一つ一つは大きいほうがいい。
・同じブロック数で合計の大きさが同じなら、一つ一つは大きさのムラがない方が良い(例：1/19 + 1/1 > 1/10 +1/10)。
・片方でしか使わないブロックはないほうが良い（大事）。
・片方でしか使わないブロックがある場合は、合計サイズのみが問題で、ひとつひとつの大きさは関係ない。
これをできるだけ満たすように…。
-流れ-
①f1,r1(と、f2,r2)両方に投影される位置は、それぞれのブロック組みでの"必要かも"Setとして、その(x,y,z)座標のtupleとして、連想配列で持っておく。これは、同時に"あっても良い位置"Setとしても別に持っておく。
②第1シルエット組で"必要かも"とされる位置と、第2シルエット組で"あっても良い"とされる位置を、ランダムに対応させて、ブロックを置くと決める。
③このブロックについて、第１シルエット組と第２シルエット組での対応させる回転方向を決める。24通りあるので、全部試して一番広がりそうな方向を決める。
④広さ優先探索で、第１シルエット組と第２シルエット組の両方で"あっても良い位置"Setに含まれる隣接区画がある限り、ブロックの大きさを広げていく。広がらなくなったら、そのブロックには番号を与えて確定。
⑤使ってしまった位置は"あっても良い位置"Setから外す。ブロックを置いたことにより、ブロックを必ずしも置かなくても良くなった位置は"必要かも"Setから外す。
⑥第１シルエット組、第２シルエット組の両方から"必要かも"の位置がなくなるまで繰り返す。途中でどちらかの"あっても良い"位置が枯渇した場合、残りの"必要かも"位置には、必要最低限の数の大きさ１の積み木を敷き詰める。
⑦出来上がった答えを採点して、点数が改善していれば採用。②からまた繰り返す。規定の時間が来たらループから抜けて、点数が一番良い答えを出力する。
--
色々とバグも出しつつ半日ほど掛かってpypyで書き終える（今回はnumpyは使わなかった）。
得点：5411億点
順位：51位 /提出450人くらい
まさかの２ケタ台！おもわず順位表をスクリーンショットしてしまう。
まさかこれでいいのか…。。
数日の考察と超高速化。
AHC解説放送はすごく参考になる。
「手元で時間をかけて回してみた結果がこちらです。一本に繋がる道を一緒にやってしまった方がいいのがよくわかります」(AHC017-Road Repair 解説放送)
…ということで、とりあえずできたプログラムを、手元で10分くらいじっくり回してみる。
わかったことは、
・ランダム方式も時間をかけまくれば結構いい感じになる。
・しっかり時間をかけていいパターンを掘り当てれば、片方の組でしか使わないブロックはほぼ発生しない。
しかも、数秒間から10分間くらいまでの間なら、計算時間をかければかけるほど、いい結果がでることがわかった。
理論的なアプローチが思いつかない以上、やることは高速化しかない。
AHC018の解説放送で「今回は久しぶりにpythonでも優勝できる可能性があった回でした」
と聞いてからこの数週間、０からRustを学んでいた成果を発揮するときが来た。
入門書を引きながら、所有権でエラーを出しまくりながら、トレイトも構造体も全く使わず（使えず）に、４日間かけて、「pypyのコードと全く同じことをするだけ」のRustコードを完成させる。
得点：1252億点
順位：102位→42位 /提出500人くらい
得点は1/4以下まで改善。Rustすごい。
n = 14で一番計算量の多そうなseed19が5秒間で何回トライできているか確認してみると、
pypy：19回
Rust：787回
書き方にもよるのだろうが、もはや勝負にならない…！！
細かくいじる。
ビジュアライザをみると、他のブロックに隠れてしまってもはや不要なのではないかというブロックが散見される。試しにいくつか手動で消して試してみると、なんと、丸ごと消しても成立するブロックがある！
ブロックの個数は少ない方が評価は良くなるので、
「丸ごと消しても問題ないブロック塊を探して、その中から構成ブロック数が小さい方ものを優先的に消していってブロック番号を詰める（正確には出力時に参照するブロック番号変換表を一緒に返す）」関数を作って、各ループごとに、「ブロックセットをとりあえず組み上げる→不要なブロックを消す→採点して暫定採用するか決める」の流れにする。あまり得点に変化なし。
少しトライ回数が落ちているために効果が相殺されている様子。「ブロックセットをとりあえず組み上げる→（無駄ブロックがあるかもしれない状況で）採点→結果が良いときだけ不要ブロックを消す→採点して暫定採用するか決める」に変更。少し良くなった。
ビジュアライザ的には、n = 5 とかではもはや最適解に近そうなので、nが大きいところで改善が必要そう。
衝撃の発見。
手掛かりがないか問題文を眺めていて、衝撃の事実に気づく。
問題文にあるseed 0 のf1,r1,f2,r2の画像をよくみると…
M C 2 3 ！！！
うーん、おしゃれ。
そういえばMC Digitalのロゴがすでにシルエットぽいし。
気づいてやる気が出たが、点数は伸びなかった。
完全運任せから、ちょっと運任せに。
ここまで、あるブロックを生成するときは、第1シルエット組みでの位置と第2シルエット組での位置を対応させるときに、ペア選びはランダム一発決めで確定し、そのペアのうちで一番いい回転方向を探す流れだった。これを、ランダムで仮のペア選びを行ったあと、24方向回転で対応させてみて、上下左右前後の6方向に伸ばせる方向数が一番多い回転方向をキープしておき、（シルエット1側は固定しておいて、シルエット２側の）ペア選びからやり直して何回か繰り返した後、一番都合の良いペアと回転方向で確定するように変更した。
（この流れで全てのブロックが組み上がったあとは、採点してまた０からブロックを組み始める、のを延々と繰り返す。）
スコアの比較には、相対スコアを使用する。
「合計スコアが変わらなくても、相対スコアが伸びるときがある」
「自分の過去のスコアに対して比較するのが良い」
(AHC解説)
ここまでの最良スコアを出したコードを2回回して、その平均を基準スコアとして相対スコアで評価していく。
nペアx24方向回転で、最適なnを探す。
速度とのトレードオフのようで、10〜20ペアの比較が最適な様子。
相対スコアは1.2倍前後になる。
得点：959億点 ※桁が一つ下がった！
順位：62位→61位
62位の人ごめん。
迷走してはまる。
上下左右前後の6方向が合うかどうかだけをみてペアを選んでスコアが改善するなら、周囲26マス(3*3*3-1)が合うかどうか見れば、スコアがすごく改善するのはないだろうか？
と、試してみるが、相対スコアは0.6倍に悪化。
どうも計算量が増えてしまっただけではないようだ...。
おそらく、斜め方向「だけ」一致していても良い一致だと判断されるのが、悪さをしているようだ。
上下左右前後の一致は「すごく良い一致(良さポイント10倍、的な)」としてみたが、相対スコアはさらに悪化して0.4倍。
ビジュアライザとにらめっこし続けて原因を考えたところ、最初の数ブロックが一致しすぎて巨大化して、最後に1マスだけ取り残されて、「大きさ1ブロック」ができやすい状況になってしまっている？ような気がする。
この26マス方式の実装は結構苦労したので捨てがたいが、どんどん深みにはまっていくので、この方針は原因不明のまま諦める。3日間分のロールバック。
速度を上げて運勝負。
回転の計算に使っていた行列は、コードの中で簡単な前計算をして算出してmutable vectorとして使っていた。
これはseed値によっても全く変わらない定数なので、constantなglobal配列として直接コード内に書き込んでみた。これで、関数に飛ぶたびに引数として渡さなくて良くなるし、僅かな前計算も要らなくなるし、immutableで置けるから事故もなくなるし、で良し。
また、vectorのiteratorで回していた処理の一部を、連想配列に変える。
そして、std::HashMapはクラッキング対策のために少し遅いアルゴリズムを使っているらしいので、rust_c::FxHashMapに変更してみる。
相対スコアは1.6倍に改善。
n=14のseed 19で何回試行できているかをカウントしてみると、
(pypy)19回→(rust実装直後)787回→(今回)1500回前後
不要ブロック消しや6方向一致確認作業など処理は増えているのに、計算速度はかなり良い感じ。
得点：795億点
順位：73位→53位/提出700人くらい
良いアルゴリズムがあるのかもしれないが、自分としては速度での殴り合いになってきた感じがある。
※↓あとから考えてみると一番高速化に効果があったような気がする回転パターンの前計算による連想配列化。前計算時間1.5msくらいで辞書型を作成できる。
ループを抜ける時間はどのくらいがいいのかな？
「システムテストでは実行時間が数％延びる」ので、TLEにならない程度でできるだけ十分な実行時間が欲しい。
以前のAHC(python3で提出)では、制限時間6秒に対して、whileループを４秒を超過した時点で抜けるように設定したのに、システムテストでの実行時間は5.2秒ほどで、危ない思いをした。
過去のコンテストでTLEになっている他の人のコードを見てみると、whileを抜けるのが500ms前でも全てTLEしている人もいれば、100ms前でも１個だけTLEして済んでいる人もいて、様々なようす。
結局は、どのくらいループ一回あたりが重いかで、変わってくるのだろう。
自分のコードをAtCoderサーバーでチェックしてみると、1ループあたりの必要時間は、ほとんどのケースで0.2ms〜5ms程度。時々、10〜30ms。非常にまれに、90ms。
出力には、最大で4msec。
今回、６秒の制限に対して、whileループをmain()の開始から5500 msec以上で抜けることにしている。
システムテストで「10%」のびるとすれば、実行時間予測は最悪でも
5500+(90+4)x(1.1) = 5603 ms
で、いけそう？
AHC017の1位の方(C++)は5930msで設定していて本番は5988msで全てACしている…のを真似していいのだろうか。
結局、5400 msにした。
すべて1割増しでも5940msで、安心感。
おわり。
最終の土日、nの値で調整かけてみようとしてちょっとだけいじって全く変わらず（むしろ悪化するのでやめた）、まあ良いかとのんびりしている間に50位くらいだったのがいつの間にか80位近くまで下がっている。みんなすごい。
結構難しくて理論的には攻められなかったけれど、高速化というところで学ぶところは多かった回でした。でもまさかの暫定100位以内！自分のような素人でもこんな位置が取れることもあるんだなとちょっと満足。
二週間一緒に走った皆様、お疲れ様でした。
↑最終提出で作ったseed 0。
システムテスト終わったら、TLEだったかどうか追記するかもしれません。
システムテスト後。
TLEしてませんでした。実行時間は、5406ms。
ちょっともったいなかったかな。この結果は次回に活かせそう。
wata-adminさんがRustで書いていたのでみてみると、注釈付きで実行時間の管理もコード内で解説されていた！ちょっと自分のスキルが足りなくて十分に解読できないけれどよく読んでみよう。
結果はまさかの100位以内。おどろきの黄パフォ！
他の参加者の解説を読むと上位の方はやっぱり"壊して足して"をやっているようす。
自分もやりたかったことだけど、２つの立体が連動していて、どう壊せばバグらないのかてんで見当がつかず、難しくて結局手がつけられなかった。解説読ませていただきます！
AHC 018 のおもいで（RECRUIT 日本橋ハーフマラソン 2023冬）
AHC 018 2/18(土)-2/26(日)
【概要】
水源がいくつかと、家がいくつかある200x200の土地がある。
水路を掘って、全ての家を水源と接続したい。
ただし、地面には隠しステータスとして「硬さ」があって、掘る時にそれに相応する「体力」を必要とする。
消費する「体力」がなるべく少なくなるように、水路を掘ってください。
掘り直しになるよりも掘り抜きすぎるほうが問題かもしれない。8日目。
おまけ：「Atcoder Heuristicのローカルテスタの使い方」
【難しそうなので手をつけるかどうか迷う、1日目。（2/18 土曜日)】
日中は他用で手をつけられず。開始したのは夕方。
インタラクティブきた
ABCとかでもインタラクティブはコンテスト時間内に解けたことがない。
インタラクティブはAtCoderの「コードテスト」が役に立たないし…
岩盤の硬さは与えられないと。
全くわからない状態から動きながら試行錯誤するのかー。
ビジュアライザでは硬さは緩やかに分布してそう。柔らかい真横にめちゃ硬いものがあるわけではない。
うーん。難しいな。やめとこうかな。
…
AIかなー…
ルンバ的な...
（寝落ち）
（ABCも寝過ごした）
【試し掘りでのマッピング戦略。初回提出の2日目。 (2/20 日曜日)】
問題文を再確認。
・斜めには接続できない。
・水源に直じゃなくて水路にも接続できる。
まったく硬さの情報がない状態から、「近道（でも柔らかいところ）を探しながら掘っていこう！」では難しそう。
連続した部分を掘らないといけない制約はないようだ。
硬さを先にちょっとテストして、硬さマップだけ先に取得してしまってはどうだろうか。
適当に20マスごとくらいに間隔をあけながら力200くらいで最大5回ずつ掘って、掘った回数をプロット。（掘りきれなかった時は５.5をあてる）
matplotlibの出番。
普段は計算速度で割を食ってるけど、この辺の視覚的にできる感じはpythonistが有利か？
元々の図がこれ。
仮掘削の結果のプロットがこれ。
その結果を周囲のマスにも伸ばしてみる。
元々の図にちょっと似てるぞ！
もう一息。
マンハッタン距離10マス範囲内の平均値を各マスの値にする。
それっぽくなった。
最初は逆プーリングとか考えたがスキル的にもできないのでやめる。
「力200くらいで」とか「掘りきれなかったときは5.5」とかは、再生した図と、元々の図を見比べて、何回か（手で）数字を書き換えてoptimizeした。面倒なのでseed0で過学習状態。
本当はoptimizerとかで回すのだろうが…
再現図が書けたところで、次は動き方。
点自体は4*(10**5)個で、何度かならO(N**2)でも回せるかもしれない。
でも、隣接するマス同士はそんなに変わらないから、間引いて近似できるかもしれない。
線に重みをつけると8*(10**5)個くらいになるけれども優先度付きキューやデックで回せるだろうか？
やったけどだめだったこと
・unionfindで水源と家が全部一つのグループになるまでくっつけ続ける。
・クラスカル法で最短全域路を作成する。
→水源でも家でもないマスまで全部くっついてよくわからないことになったのでボツ。
最終的によさそうだったこと
・ダイクストラ法で接続する。
全ての水源の上流に、「仮の総合水源」を作成する。そこからのそれぞれの家への最短距離（重み付き）を得る。一つ最短の家を見つけたら、一旦全ての重みをクリア。
そこまでに作る水路と、発見済みの家の座標を、全て水源として扱い直し、「仮の総合水源」に直接接続して、改めて残りの家に対してダイクストラを最初から行う。
を繰り返す。全ての家が接続されたら終了。
仮掘削で穴が既に開いているところはまた掘らないように気をつけて…。
完成。
Rustの環境構築にエラー出まくって大変だったのはまた別のお話。
５時間くらい、夜の２時までRust周りで格闘し、やっとローカルテストが通り、提出した。
ここまで遠かった。今回は諦めようと何度も思った。苦心の末の提出。わくわく。
な なんと！！！！
WA！！！！！
なんでやねーーーん
ローカルテスト通ってるのに。
エラー箇所がどこかを探しまくった結果、「numpyを使っているのにpypyで出した」が原因でした。
30分待って再提出した結果は。
score：1481万 順位：275位/正解550人
いつの間にか、とっくの昔にARCの時間は過ぎていた。
明日以降でパラメータチューニングしてみるか。
↑seed0の結果。
【綺麗なマップ作りは不要かも。3日目。(2/20 月曜日)】
問題の制約を再確認。
・システムテストでは、それぞれのCの値について、375個ずつのテストケースが存在する。
・水源と家の位置は、Sijに反比例する確率で選ぶ。（家と水源はほぼ柔らかい位置にある）
やったこと
ジャッジの役割をするクラスをつくり、google colabで延々とケースを読み込みながら採点結果を吐く関数を作成。その関数をbayesian optimizerに渡して、いくつかのパラメータを最適化する（グリッドサーチは夜が明けても終わらなそうなので諦めた）。
主にマッピングのための試し掘りについて、「どのくらいの間隔で」「最大何回まで」「どのくらいの力で」掘ればいいか。掘りきれなかったマスの硬さをどのくらいと仮置きするか。
といったところを一気に調整してしまう。
Cの値だけ不連続なうえに、７通りしかなく、しかもシステムテストでは均等に用意されるということで、Cの値ごとに分けてそれぞれ20ケースずつ、35回くらいのベイズ最適化を回す。
正直20ケースでは少ないが、今回の延べ140ケースでも3時間以上かかったので、無料のcolabではこれが限界（体力的にも）。
試し掘りの最適回数は、Cの値にかかわらず、「１」。意外。
一回適当な力で掘って、掘れなければ「硬い」。
その周りも「硬い」ので、適当に避けていけばいいようす。
綺麗なマップを作る必要はないことがわかった。
こんなふうに見えているようだけど結果はそれなりにいい。
score 1074万 334位→205位 / 正解621人
だいぶ改善。
試し掘りの結果からの予想図を、周辺の平均値でならしてみてよりスムーズにしてみる。
きっといい結果が！と思ったら、評価は悪くなった。
せっかく、「硬い」「柔らかい」で明確に２パターンに分けられるプロットをしたのに、それをぼかして「見栄え良く綺麗に」してしまうと動きにくくなるようだ。
pythonなのに実行時間が1200msで、まだ全然余裕なので、この辺で何かできそう。
水源からも家からも全く逆方向で、絶対にかすりもしないような場所がある場合、そこは試し掘削する意味はない。節約できないだろうか。
↑seed0の結果。掘る回数を１回ずつにしてもそれなりに山を避けている。
【やっぱりマップをなんとかしたくて迷走。4日目。（2/21 火曜日）】
"柔らかい"場所から一定距離以内の場所はまた"柔らかい"のではないか。
そんな考えで、"柔らかい"場所からのダイクストラを行い、マンハッタン距離が一定以内なら”柔らかい”、それ以上なら距離に比例して"硬い"としてマップを作成。各”柔らかい”グリッドに光源を置いて、明るさで各地点の”柔らかさ”を表すようなイメージ。
見た目は良い。
が、ローカルテストの結果はむしろ悪化。
この案は一旦ボツ。
前日の結果の、計算式が少し意図と違っていたところを修正して再提出。
240位。みんなすごい。
【Pの値を正確にしていきたい。5日目。 （2/22 水曜日）】
今回、実際に掘っていく時の"力"は、マッピングで置いた数値を「硬さ推定値」として、その値をそのままPとするようにしている。推定値をより正確にすることでPをより正解値に近づけたい。
適当なseedで推定値の最小値・最大値を取得してみると、50-800くらいになっていた。それを10-5000の範囲に線形に引き伸ばしてみる。
最大値を5000まで引き伸ばすと、「硬い」判定の部分が多い影響で、全体の値がだいぶ上にずれてしまうので、色々な値を試した結果、10-1500くらいに引き伸ばすのが良さそうということになった。試し掘りはCの値に関わらず、力200くらいでやるのが一番いい図ができそう。こういう処理は重くなるかと思ったが実行時間にほぼ影響はない。これが「定数倍は軽い」というやつか。
あと、x = 199 or y = 199の試し掘りは、近隣の試し掘りが近いことが多いので代用できそう。ここは試し掘りしないことにした。これで40回くらい試し掘りの回数が減る。
【実際に掘りながらPを修正していく方針をとる。6日目。（2/23 木曜日）】
硬さ予測値に対して、係数をかけて定数を足して、修正したもので提出（係数と定数は、スコアが最小化するように、最適化探索をして決定）。
score 950万 順位:290位→240位
思ったより変わらず。
入力の生成方法をよく読む。
「パーリンノイズ」を勉強する。格子点を作って、その距離によってマッピングするというのは、あながち外れてもいないようだ。
値は、その後ロジスティック変換で0〜1になり、2〜4乗され、線形に10-5000まで変換されている。
これに着想を得て、「柔らかい」ところからのユークリッド距離の3乗が一定以内なら「柔らかい」として1か0かの値だけのマップを作ってみる。
↑できた図。
↑内部データをそのまま描画した図。
何か近い…けれど今使っている図とあまり変わらない。ちょっと使いにくいので保留。
マップをいじくるのはあきらめて、掘りながらPを修正していく方針をとる。一回で掘り抜ける状況が続く場合、推測マッピングと実際値がずれていると考えて掘る力を節約するモードに入る。一回で掘りきれなかった場合、次のマス以降の何回かの掘削では掘る力を割り増しする。ということをしてくれるクラス"class MrX"を作成。
提出。むしろ下がる。308位/822人
ビジュアライザを見ると、硬いところ(硬さ3000あたり)を通ってしまうとき、ぎりぎり30とか残ってしまった時に２回目もフルパワーで掘っているのが問題のよう。
修正。岩盤の「最大残りHP」を5000に設定して、一箇所にとどまる限りそれを削っていく。「最大残りHP」以上の強さでは掘らないようにする。
提出。ちょっとだけ良くなる。でもMrXがいないときの方がよかった。
301位。
【Xさんに頑張ってほしい（気持ち）7日目。 (2/24 金曜日)】
なんとかMrX（掘る力をリアルタイムで修正していくクラス）に頑張ってもらうしかない。
掘ってきた結果を入力値、新たな予測硬さ値を出力値として、実際の硬さ値との差を埋めていくようなMLP（仮）を想定してみる。テストデータで学習させて、、と思ったが実装が厳しそうで断念。特に成果なし。
【掘り直しよりも掘り抜きすぎるほうが問題かもしれない。8日目。（2/25 土曜日）】
ビジュアライザを見ていると、掘削結果として-600とか-1000とかが出ていることが頻回にあることに気づく。
-600ということは、Cが1だとしたら、600回掘り直ししないと起こり得ない損失なわけで、このあたりは改善できそう。
一発で掘れなかったときにもう一度Cのコストが乗せられるのがもったいないと思っていたが、Pが必要以上に高すぎるほうがもったいないのかもしれない。
・一発で掘りきれなくて、掘り直しするときには、勢いあまって-1000まで掘り抜いてしまわないように、同じ岩盤を掘り直す際は、n回目(n>=2)以降は元の硬さ予測値のn分の1のPで掘る。
・class MrXが力割り増しモードに入っていないときに、連続で一発掘りの状況が続く場合、オーバーキルと判断して、次回以降、一発掘りではなくなるまで、次のPをmax(C*2,予測値//(1+オーバーキル連続回数))にする。
score:837万 順位:290位/正解884人
200位台を奪還（？）した！
参加者は996人！ほんとにみんなすごい。
【力尽きた9日目。(2/26 日曜日)】
もうアイデアは出し尽くした感があり、細かくステータスをいじって何度か提出するが大きな改善はなし。順位は350位近くまでになってしまった。上位の人は自分の３倍(1/3)近いスコアをとっているわけで、一体何をやっているのか、解説が楽しみ。”試し掘り”の方針自体が違うのかも。
提出者数は1000人に達する勢い！自分の提出までの実装が重かったから参加者は増えないのではと勝手に思っていたけどそんなことはなかった。
夢の中まで考え続けて楽しい９日間でした。皆様お疲れ様でした。
↑最終結果。scoreは836万。気持ち程度に迂回してくれている。
【おまけ】
「Atcoder Heuristicのローカルテスタの使い方がわからない！」
と、調べたけれど、解説記事がほとんどないので、自分なりに書きます。
確かに、プログラミングコンテストで「ソフトの使い方がわかりません！」というのもなんだとは思うが、実際に自分が困ったので仕方がない。
参加者の多くがパソコンが得意だから困ることがないのだろうか？
大事なこと
1. 「Windows用のコンパイル済みバイナリ」だけダウンロードしても使えない。
2. READMEをちゃんと読む。
3. 自分の使用言語はローカルでも環境を構築しておく。
1.「 Windows用のコンパイル済みバイナリ」だけダウンロードしても使えない。
Q:「わーいコンパイル済みだー ダウンロードしてダブルクリック。
あれ？開かないな？ダブルクリック。あれ？ダブルクリック。あれ？あれ？」
A:綺麗なUIの整ったソフトが提供されるわけがなく、コマンドプロンプト（Macならターミナル）で操作する必要があります。ファイルを置く場所やらなんやらと色々決まっています。コンテストページから、「ローカル版」の方もしっかりいただいて、解凍しましょう。
2. READMEをちゃんと読む。
Q:「で、どこにファイルを置けばいいの？コマンドプロンプトとかわかんない。」
A:READMEに、どこに実行ファイルを置けばいいか、書いてあります。丁寧に実行コマンドまで書いてくれています。
コマンドプロンプトはwindowsならウィンドウズボタンの検索窓からcmdで検索すればいいよ！カレントディレクトリの変更はcdコマンドですよ！
3. 自分の使用言語はローカルでも環境を構築しておく。
Q:「実行したのになんかエラーで終了するんだけど」
A:その言語はローカル環境で実行できていますか？私の場合は、普段google colabかatcoderの「コードテスト」で実行していたので、今回は久しぶりのローカル実行でした。windowsではそもそもpython環境を作っておらず、macではanacondaがいつのまにか他の設定とconflictを起こしていて、どちらでもうまくいかずに戸惑いました。一回Hello worldでもローカルで実行して、動くことを確かめましょう。
自分の場合、結局MacにRustを入れて実行するのが一番うまくいきました。
Rustはcurlコマンドでは自己証明書のエラーで導入できず、配布ページから.pkgをダウンロードしました。conflictはエラー番号で検索して、解消させるコマンドを探して実行しました（コマンドの実行後、Macが唸り続けて2時間ほどかかって解消）。
心が折れかけましたが。
できなくて困っている方の参考になれば。cargo runできますように。
AHC 017 のおもいで (THIRD プログラミングコンテスト 2022)
AHC017 1/28(土)-2/5(日)
概要：
N個の地点とそれぞれの地点を結ぶM本の道路があり、それをD日間ですべて1回（1日）ずつ工事したい。工事できるマンパワーは1日あたり道路K本まで。
工事中の道路は通れないので、各地点にいる人たちは別の地点に行くために迂回する必要が出てくる。N*(N-1)通りの地点同士の組み合わせそれぞれでの、迂回しなくてはいけなくなった距離の合計値（というか期待値）が不満度として毎日加算される。
不満度ができるだけ低くなるような工事計画を考えよ。
制約
500 <= N <= 1000
500 <= M <= 3000
5 <= D <= 30
ceil(M/D) <= K <= 2*ceil(M/D)
制限時間 6秒
1日目（1/28 土曜日）
とりあえずABC287だけ参加。
マラソンに参加すると時間が溶けるし脳のリソースが全部持っていかれるのでその覚悟をつける日。
2日目（1/29 日曜日）
参戦。
問題文から、１つの点からは２つ以上の道路が出ているのが保証されている。
なので、できるだけ同じ日に同じ点からの道路を２つ以上潰さないようにすればいいんでは？なら、その点から別の道路通れるでしょう？
できれば遠い道路同士を工事したほうが通せんぼにならなくて良さそうだけど、それは実装がよくわからないからちょっと置いておく。
各点ごとの持っている道路のリストを作って保持。一つの点から出る線のそれぞれを、1日目から均等に振り分けていく。
なかなか良い線かと思って提出したが… 全然だめ。
得点 : 23930843999 (=2x10^10)
ビジュアライザを見ると黒くなってしまう点がいくつもある。到達できない点ということか。なんで？同じ点からの道路はできるだけ潰さないようにしたのに。
そもそも毎日全ての点に到達できるような方法が常に存在するのか？
もしくは、1日くらい到達できない日があっても他の日が全て直通になるならむしろそのほうがいいのか？
ということは平均的に工事をやっていくより、どかっとやって残りの日はフリーにしたほうがいいのか？
到達できないとペナルティは10**9だが、wの上限が10**6でMの上限が3000なら、到達できないほうがむしろ満足度高いとかある？
重みのパラメータは読み込んですらいない。どうやって使おう？
※どうでもいい苦労したこと
コードテストでのoutputをビジュアライザに貼り付けてみようと思っても、outputが長すぎて最後が省略されてしまい使えない。
google colabでやるしかない。まずは環境構築から…
入力を全部コードとして貼り付けたらcolabが固まる。
ファイルから読み込むようにする。
with open('/content/0032.txt') as f:
s = f.read()
s = s.splitlines()
これで、
N,M,D,K = map(int,s[0].split())
で、やっとスタート地点に立てた。
3日目（1/30 月曜日）
スコア計算関数を実装。
ある点を引数にとって、その点から全部の点に対してダイクストラ法をする関数を作成。
その関数に対して１から順番に点を渡して行って戻り値を合計していき、合計の戻り値を返す別の関数を作成。
流石に全部やると重すぎなので、全体の1/10くらいの点だけで評価するようにした。
2日目の結果からスタートして、randomをとって、適当に辺をswapしていく。渡した日から、一個もらう。Kの上限があるので、それを超えないようにするため。
スコアが上がれば、swapを確定。悪くなれば、swapを取り消し。
提出したところ、スコアが爆発的に高くなる。喜んで順位を見ると、AC内での順位はほぼ最下位。
得点：849794673368 (=8x10^11)
うーん。
あ！今回の場合、スコアは「不満度」なので、低いほうが良い結果なのか！
ということで、”スコアが下がれば、swapを確定"にした。
注釈を消し忘れてWA。
いつの間にかAM3時。とりあえず寝よう。
4日目（1/31 火曜日）
クラスカル法でやってみることを思いつく。
この３日間やった分はもったいないが全部消す。
とりあえず、「たどり着けない」場所があるとスコアが悪化しそうな雰囲気があるので、それを避けるような方法をとってみる。
最小全域木その１に挙げた道路がまったく全て使えない状態を作って、そこからもう一度、クラスカル法をして、最小全域木その２を作成。
作戦としては、「最小全域木その１の道路は全部開通してます」の日をできるだけ作って、その間にそれ以外を済ませてしまう。とくに、最小全域木その２はとっとと（初日に）済ませてしまう。
最小全域木その１以外の道路が全て済んだら、残りの日でゆっくりと最小全域木その１をやっていく。その間は少なくとも最小全域木その２は開通しているから、ほぼ「たどり着ける」はず。
問題点としては、
①最小全域木その２が成立するかどうかという問題
②「最小全域木その１の道路が全部開通しています」のうちに、他の部分の工事を全て終わらせられるかどうかという問題
①に関しては、もう仕方がない。できるだけ多くの場所にたどり着けるならいいでしょう。
②に関しては、まず、最小全域木その１の道路数はN-1。KがN-1以上なら1日で最小全域木が終わるのでK>=N-1を、制約からなんとか数学的に保証できないか紙の上で試行錯誤したが、どうも保証できないことがわかった。しかたなくテストケースを当てはめようとしたら余裕でKはN-1以下だったので仕方ない。諦める。けれども、実際やってみると大体のケースではうまく行っているようすに見える。
提出してみると…
あまり良くはなっていない。
得点：18682571846 (=1.8x10^10)
前回のAHCでは「焼きなまし」やらなんとかキーワードがあったな…と思い出し、スコア計算をしてなにか改善をしていく感じかとおもったが、良い計算方法がわからない。普通に計算量多そうなんですけど…。何かスコア計算の良い方法があるのか…？
ビジュアライザがめちゃ重いところから考えると、偉い人がつくった計算方法でもある程度の計算量はかかりそう。
なので、
スコア計算は難しそうなので諦める。
ランダムでうんぬんよりは、理屈で良い方法を探していく系なのだろうか。
5日目(2/1 水曜日)
ある１本の道路について考える。
その道路がないことで、その道路の両端の点同士の距離はどのくらい変わるかを考える。
すべての日で、「ある一本の道路」がない状態を仮定して、「片方の点から出発して、反対側の点についたら終了」のダイクストラ法で計算して、
「その道路がないときでも、両端の点同士の距離が一番短い」日に、その道路の工事をすることにする。その日の工事数がK以下なら。
これはいける！と提出したが、あまり変わらず。
もう、これ以上の改善は無理かも。みんなどれだけ天才なの
得点：20660002917 (=2.0x10^10)
6日目(2/2 木曜日)
考えていたら寝落ちしてしまった。
7日目(2/3 金曜日)
思いついたけど実装が大変そうすぎてやっていなかったことを気合い入れてやる。
川に橋がかかってるとするでしょう。目の前に橋が一本、もうちょっと行ったところにももう一本、橋があって、向こう岸に行くならとりあえずどっちか使えば良いかなと思っていたとする。それが２本とも工事中で、その次に（３番目に）近い橋はめちゃ遠かったら…、辛くない？ということで、
ある１本の道路について、その両端の点同士の、「２番目に近い順路（迂回路）」を検索する。
全ての道路について、tuple(道路i, set[道路a,道路b,道路c])といったような組みをあらかじめ作成する。
道路iの工事日と、(道路a,道路b,道路c)のいずれかが同じ日に工事をしていた場合は、そうはなっていない日（で、かつ工事件数がK以下の日）に道路iの工事日を投げる。swapは面倒になるのでしない。
投げた元の方の日に他の日から道路iの工事をまた渡されてしまわないように、「その日は開けとかなければいけない道路」setにメモする。
投げられた方の日は、道路a,b,cの工事はもう受け取れないので、「その日は開けとかなければいけない道路」setに道路a,b,cをメモする。
というのを、全ての道路でやる。
提出すると、スコアはものすごく改善。
得点：901396620 (=9.0x10^8)
500位くらいだったのが一気に200位台に！
でもこれ以上思いつかない。
8日目(2/4 土曜日)
ABC288がんばる。
難しいんですけど。
9日目(2/5 日曜日)
もういいか、バグ作ってWAになるのも嫌だし。
とおもいつつ、7日目のコードだと500msecで終わるのがなんだかもったいなくて、少しランダムで改善させてみる。
「ある点からある点まで」の最短経路を適当にみてやると、工事中の場所を迂回したあと、元のルートに戻らずにそのまま別ルートで進んでいることが多くあるように見える。
ということは、日によっては、「その道路ほぼ使っていないよ」な日があったりするのでは。その日にちゃっかり工事日をずらせないだろうか。という考え。
でもこれはどうやって実装すればいいのかわからない。別の点同士でとても重要な道路になっているかもしれないし…。
コンテスト期間も終わりなので、とりあえず一部分だけでもと思い、実装する。
適当な2点x,yをとって、7日目までの「出力」にしていた全ての日と、まったく工事をしない日に対してxからyへの移動コストと移動ルートを計算する。
移動コストが最大の日について、注目する。
その日に「まったく工事をしない日」のルートと同じルートを使わせられるように、その日の工事をずらせないか検討する。
まず、工事をずらさなければいけない道路をピックアップする。おそらく複数の道路が拾われるので、それぞれの道路の工事日について、適切な移動先がないか検討する。
条件は、
移動先の日で、その道路が「開けておかなければいけない日」になっていないこと。
移動先の日に、その道路の「迂回路」がすでに工事されている状態ではないこと。
移動先の日の、元々の「xからyへの最短ルート」にその道路が含まれていないこと。
計算量が多くて大して回らないうえに、条件が厳しすぎて、改善できたのは１ケースあたり道路20本程度。ただ、スコアはやや改善。
得点：777213859 (=7.7x10^8)
コードは注釈や空白行も含めてだが300行程度に。
WAがこわい。
TLEもこわい。ので4秒でbreakするようにした。
まとめ
・まずクラスカル法で基本型を構築。「行けない」状態は発生しないようにする。
・「最短路」か「最短の迂回路」のどちらかは開けるようにする。
・遠い点同士でも、コストがかかりすぎの場合は、他を犠牲にせずに「最短路」が開けられないかどうか繰り返し試してみる。
終了後の放送
・少ない点で近似スコアを得る。毎回フルスコアをとるのは時間的に厳しい。
・とりあえず高速化して山登りは基本。
・手元で１時間とか回してみるのがいい。その結果をビジュアライズすると気づくこともある。
・近い道路はむしろ一緒にやったほうがいい。工事の移動先日は隣接する道路の工事日にしてみたほうが賢い。
両方向で見られる優先度付きキュー
最大値と最小値を両方O(logN)で見たい、ワガママな人のための優先度付きキュー。
要素の追加はO(logN)、要素の存在確認はO(1)。
ただし、heapqを２つ使っているので使うメモリも２倍、計算量も２倍。
import heapq class HeapBiq: def __init__(self,A=[]): self.low = A self.hi = [-1*a for a in A] heapq.heapify(self.low) heapq.heapify(self.hi) self.dic = {} for a in A: if a in self.dic: self.dic[a]+=1 else: self.dic[a] = 1 def hpush(self,x): heapq.heappush(self.low,x) heapq.heappush(self.hi,-x) if x in self.dic: self.dic[x] += 1 else: self.dic[x] = 1 return def hpopmin(self): self.l = "error" while self.getlen() > 0: self.l = heapq.heappop(self.low) if self.l in self.dic: if self.dic[self.l] == 1: del self.dic[self.l] else: self.dic[self.l] -= 1 break return self.l def hpopmax(self): self.h = "error" while self.getlen() > 0: self.h = -1*heapq.heappop(self.hi) if self.h in self.dic: if self.dic[self.h] == 1: del self.dic[self.h] else: self.dic[self.h] -= 1 break return self.h def getlen(self): g = len(self.dic) return g def remove(self,x): if x in self.dic: if self.dic[x] == 1: del self.dic[x] else: self.dic[x] -= 1 #存在しないxを削除しようとしてもerrorは返らない。 return def getmin(self): if self.getlen() == 0: return "error" while True: ret = self.low[0] if ret in self.dic: return ret else: heapq.heappop(self.low) return def getmax(self): if self.getlen() == 0: return "error" while True: ret = -self.hi[0] if ret in self.dic: return ret else: heapq.heappop(self.hi) return def look(self): return self.dic def is_exist(self,x): if x in self.dic: return True else: return False
#使い方
A = [2,3,4,3,5,6,4] hb = HeapBiq(A) print(hb.hpopmin()) #2 print(hb.hpopmax()) #6 print(hb.look()) #{3: 2, 4: 2, 5: 1} hb.remove(5) print(hb.hpopmin()) #3 print(hb.hpopmax()) #4 hb.hpush(8) print(hb.look()) #{3: 1, 4: 1, 8: 1} print(hb.is_exist(9)) #False print(hb.is_exist(4)) #True print(hb.getmin()) #3 print(hb.getmax()) #8 print(hb.hpopmin()) #3 print(hb.hpopmax()) #8 print(hb.hpopmin()) #4 print(hb.look()) #{} print(hb.hpopmax()) #error
行列の累乗
行列の累乗を計算する方法。
実行時間はgoogle colabのGPUなしで計測。
Blocks POJ No.3734 (蟻本P182)などで使用できる。
①対角化して累乗。数学的な感じ。
#input
import numpy as np np.set_printoptions(precision = 0) A = np.array([[2,1,0],[2,2,2],[0,1,2]]) def diagonalization(x): eig = np.linalg.eig(x) e = np.diag(eig[0]) p = eig[1] return e,p e = diagonalization(A) D = e[0] P = e[1] P_inv = np.linalg.inv(P) B = P@(D**3)@P_inv print("Aの3乗：") print(B) import time t = time.time() C = P@(D**(10**18))@P_inv print("Aの10**18乗：") print(C) print("処理時間：") print(time.time()-t)
#output
Aの3乗 [[20. 16. 12.] [32. 32. 32.] [12. 16. 20.]] Aの10**18乗 [[inf nan nan] [nan inf inf] [nan inf inf]] 処理時間 0.004506111145019531
→累乗が大きいとオーバーフローしている。
②numpyのライブラリを使う。
#input
import numpy as np np.set_printoptions(precision = 0) A = np.array([[2,1,0],[2,2,2],[0,1,2]]) B = np.linalg.matrix_power(A,3) print("Aの3乗：") print(B) import time t = time.time() C = np.linalg.matrix_power(A,10**18) print("Aの10**18乗：") print(C) print("処理時間：") print(time.time()-t)
#output
Aの3乗： [[20 16 12] [32 32 32] [12 16 20]] Aの10**18乗： [[0 0 0] [0 0 0] [0 0 0]] 処理時間： 0.003349781036376953
→累乗が大きいとオーバーフローする。
意外とタイムアウトはしない。スカラーの累乗とは計算方法が違うのだろうか。
③numpyのdot()を使って計算。
単純に繰り返しをおこなう。
#input
import numpy as np def mat_power(A,num): result = A for j in range(num-1): result = result.dot(A) return result B = mat_power(A,3) print("Aの3乗：") print(B) import time t = time.time() C = mat_power(A,10**18) print("Aの10**18乗：") print(C) print("処理時間：") print(time.time()-t)
#output
Aの3乗： [[20 16 12] [32 32 32] [12 16 20]]
→計算時間10分以上で途中で手動中断。
繰り返し部分がめちゃくちゃ時間がかかる。
④繰り返し二乗法を使って計算。
np.dot()を使用した。
#input
import numpy as np A = np.array([[2,1,0],[2,2,2],[0,1,2]]) def linearpow(A,n): if n == 1: return A if n%2 == 1: B = np.dot(A,linearpow(A,n-1)) return B B = linearpow(A,n//2) B = np.dot(B,B) return B B = linearpow(A,3) print("Aの3乗：") print(B) import time t = time.time() C = linearpow(A,10**18) print("Aの10**18乗：") print(C) print("処理時間：") print(time.time()-t)
#output
Aの3乗： [[20 16 12] [32 32 32] [12 16 20]] Aの10**18乗： [[0 0 0] [0 0 0] [0 0 0]] 処理時間： 0.003695964813232422
→なんにしてもオーバーフローはする。速度はmatrix_power()と変わらない。ただ、この方法が一番わかりやすくて自作プログラムで使うなら間違いがなさそう。
⑤結果のmodを取りたい場合のやりかた。
繰り返し二乗法とnp.dot()を使った。
#input()
import numpy as np A = np.array([[2,1,0],[2,2,2],[0,1,2]]) mod = 10 def linearmodpow(A,n,mod): if n == 1: return A%mod if n%2 == 1: B = np.dot(A,linearmodpow(A,n-1,mod)) return B%mod B = linearmodpow(A,n//2,mod) B = np.dot(B,B) return B%mod B = linearmodpow(A,3,mod) print("Aの3乗のmod：") print(B) import time t = time.time() C = linearmodpow(A,10**100,mod) print("Aの10**18乗のmod：") print(C) print("処理時間：") print(time.time()-t)
#output
Aの3乗のmod： [[0 6 2] [2 2 2] [2 6 0]] Aの10**18乗のmod： [[2 4 6] [8 8 8] [6 4 2]] 処理時間： 0.00898122787475586
→計算結果は合っているようす？
計算時間も速い。
オーバーフローせずに済んでいる。
numpy.linalg.matrix_power()は途中でmodを挟めないので、
解答としてmodを出すならこちらで用は足りそう。
numpyはCの型の制約を受ける。とのこと。
オーバーフローには注意。
参考：
対角化とmatrix_power()について：
assam-blog.com
np.dot()について：
amaharawaya.livedoor.blog
オーバーフローについて：
ikatakos.com
