N*Nの正方形の盤面が与えられる。 使用可能なポリオミノの個数が与えられるので、盤面にうまく配置する。 - 1日め - ポリオミノは大きさごとに使える個数が決まっていて、形は決まっていない。 ひとつのポリオミノで覆ったマスに書いてある数字の積がスコアになる。 覆われていないマス目は、-1000点になる わかること ・マイナスは偶数個で揃えないと負のスコアになってしまう ・大きい数字は、できるだけ大きいポリオミノで大きい数字と一緒にまとめると得になる ・7-ominoで獲得できる最大スコアは9^7=4782969点、平均的には5^7=78125点くらいだろうか？ ・6-ominoだと5^6=15625, 5-ominoだと3125くらいが相場か →実際には大きいポリオミノほど大きい数字を使おうとするのであれば、もう少し差は開くだろう ・0を組み込むと0点になってしまう→2-ominoで小さいマイナスと相殺くらい？ どう考えても7-ominoを優先的にいい場所に置くべきに見える。 大きいポリオミノから順番に貪欲においていくなどの方法が考えられる。 盤面の大きさは最大で2500マスあり、7-ominoひとつ置くのでさえ最適解を求めるのは難しそうに見える →これはどう考えても嘘で、隣接するマスしか同じ集合に含まれないので2500C7みたいな見積もりは駄目 これ第一回日本橋ハーフマラソンと酷似してませんか？ 日本橋ハーフマラソン multiple pieces →マイナスがない、すべて8-omino、使わなかった場合のペナルティがない この場合は、一番大きな数字から幅優先探索をして、周囲の大きな数字を取り込んでいくという方針が良かったらしい これは今回も有効であるように見える 7-ominoは760種類しかない →どの位置に始点をもってくるかで×7？ ポリオミノを列挙するのは難しい？ 7-ominoの始点として使えるのは使える7-ominoの数だけ（当たり前） →ここでできるだけ多く点数を稼ぎたいので、7-ominoに計算量を多く使ってよいのでは？ 7-ominoの配置を焼きなまして、その後6-ominoを焼きなまして、5-omino以降はペナルティ消しのためだけに使う？ 7-ominoは7個しかマスを使わないのに対し、マスの数字は絶対値で0~9まであるので(0は少し少ないが)、使える7-ominoよりも9,-9のほうが期待値的には多いハズ →でも9はまとめたいんですよね 数字が大きい順にひとつとって、そこを始点にしてスコアを探索する？ 意外と適当につめてもペナルティはそんなに出ない？ そもそも7-ominoをうまく詰めれば1000*1000点くらいは出るんだから、多少の-1000点は誤差な気もする 7-ominoだけに限定した問題はそれこそmultiple piecesと同じでは 2500マス×760種類を全列挙すると2e6くらい →全部のピースを全列挙できる →0を含むものを消すともうちょい減る 6-ominoだと 5e5くらい 5-ominoだと 1e5くらい 4-omino以下ではスコア1000を超えることは難しいと考えられるので、これ以下はすべてペナルティ消し（ = 使われてないマスを埋める）に使ってよいのでは 使われてないマスを埋めるためには、使われてないマスどうしでUnion-findをしてsizeの大きさで埋めるだけでよい →Union-Findした結果sizeがめちゃくちゃでかい集合は当然出てくるだろうが、とりあえず適当に埋めといてそこの改善はあとに回してもいい気がする →7マス以下の集合についてはsizeで埋めとけ →7マスとかで何も考えずに埋めたりするとエグいマイナスになるかもしれないのでできるだけ4マスとかくらいまでで埋めたいね →7マスで埋めることになる機会はあまりないと思うけど 1マスのholeとかは埋めれないが、多少は許容できるだろう（少なくとも最初はそれでいいと思う） 最初の方針としては、7,6,5-ominoくらいを全列挙して、スコアの高いものから貪欲に入れていくみたいなのがよさそう →余裕あったらここで焼きなましみたいなことをしてもいいと思う →いやすべきだろ とにかく7を全部つめてから6に行くよりも、6で7よりスコアのよいものがあれば先に使うのがいいはず というか、N-omino全部列挙して最後まで貪欲につめたらいいんじゃないですか？ →このへん実際にやってみないとどっちがいいのかわからんな ポリオミノの全列挙はどうやってやるんですか？ →最初に形をBFSかなんかで全列挙しておいて、適当なマスを始点と決める →N*Nの各マスに対してM種類すべて見ていって、盤面をはみ出したりスコアが0以下になったりしたら捨てる →スコアが正になったら、記録しておく（始点の位置, 種類番号, スコア） →ソートして、使えるものから貪欲に使っていく 形の全列挙の方法を考えよう →760種類程度なら埋め込めるだろ ポリオミノを生成するコードを書いた →適当だが十分高速に動作するので埋め込まなくてよさそう →高速化の余地あるが、正直必要ないと思う できた →ソートがおそすぎて10秒に間に合ってない N=50のケースで890000要素しかないので間に合ってもよいと思うが →ソート用に軽いvectorを用意してみる 対して速くなってない気がする →最適化オプションをつけてないだけだった（は？） 提出してみる →提出方法が難しくて少し手間取ったが99.79872点で暫定1位。 滑り出しはgood - 2日め - 4位になっていた。 上に赤と黄上位しかないないのでまあOK. 1位との差は1%くらい 貪欲がクソ強いとはいえ1%は上がるだろう（たぶん） sizeが5より大きいミノだけしか使わなかったとき、ペナルティを除いたスコアは case2 で 127467735 提出したコードのcase2は127209435だったので、5より大きいミノはペナルティ潰しにだけ使ったほうがよくなる可能性が高い 同様に、 case1 は 1588250 > 1581248 case3 は 40766245 > 40665326 大体0.2%くらい？ ミノのサイズごとに平均的なスコアを見たい 1マスあたりの平均スコア size6は5000くらい size5は200くらい size4以下は10もない →4以下をスコア重視で置くことは無意味 ペナルティ消しに使おう ペナルティ消すと1マスあたり1000点なので、4以下で消しきれないようなら5も使ってよい 盤面を埋める方法を考える ・埋まっていないマスを始点にしてBFSをする ・各マスで →これこそ焼きなますべきでは 4以下を焼きなます時点で5以上を動かさないと決めるのであれば、有効なピースはかなり少なくなるので1秒くらいわりあてれば十分では？ 最初の貪欲の評価基準を1マスあたりのスコアに変えれば伸びるだろうか？ →ぱっと試した感じでは誤差レベル。保留 4以下を焼きなますやつを試す 最終的には5以上も焼きなましたい。 7などは状態数が多いので減らしてからにしたい →貪欲解以上を出したいのであれば、7を使える個数より1つ少ない数だけ7-ominoを貪欲に（置けるかどうかを気にせず）取ったときの合計を貪欲解の7-ominoスコア合計から引いたものよりスコアの低いピースはいらないはず →→これは下手すると全く絞れない可能性もありそう →→→絶対に同時に置けないピースなどもあるので、そのへんも使ってうまく絞れないだろうか →貪欲解で使われた一番安いピースの1/10以下のスコアしかないものは使わない、などは充分現実的か →そもそも7-ominoを置き終わるまでの間に6-ominoは置かれているのか？ →あとで調べる。 4以下を焼きなまし case2:12727****くらい 7,6,5ですでにどうしようもなくなっている隙間以外は埋まっているように見える →5も焼きなましにいれてみる →→短時間では全然スコア出ないが、100秒で焼きなますと12730****くらい出た →→嘘っぽい、偶然？ これよく考えると置くときに抽選をする必要がない →スコア差分が必ず正なのでそもそも必ず採用される 1秒でiteration = 25000回くらい よく見たら2,3,4は全部使われてて5だけが死ぬほど余っている →4から焼きなましにすると今度は4が死ぬほど余っている sizeNのピースの周辺に空きマスがあるとき、size(N+1)のピースに入れ替えるような遷移があれば解決しそう そもそも空きスペースが少ない状態での焼きなましは相性が悪いのでは？ 普通に埋める方法を考えてみる 隙間を埋めるときに困るのは、1マスだけの空間を作ってしまうこと 境界4つのうち3つをピースに囲まれている空きマスに対して、最後の境界を埋めてしまうと孤立する →各マスごとに周辺が埋まっている数をしらべて、3つ埋まっているものから順に埋めていくべき →境界が多いマスをひとつ選んで始点として、隣接するマスの中から境界が一番多いマスを選んで進むDFSを繰り返す。 →7,6マスは最初から使い切っている想定なので、1つの塊にできるのは5マスまで →6マスの空きマス集合を5マス貪欲に取ってしまうと1マス余るので困る →4+2? 3+3? そもそも、空きマス集合の大きさが5以下のものは貪欲に埋めてしまうべき 焼きなましの前にそれをするだけでも改善するか？ →とりあえずやってみた ピースを置くときに、ピースに隣接する空きマスをすべてみて、孤立する場合に置かないことにすればいいのでは？ →これなら焼きなまさなくても貪欲でよい スコア順じゃなくてピースでかい順に置くべきだと思う save→temp.cpp 最初の時点で別のピースに隣接している数でピースをソートしておけば、端の方から埋めていけるのでは - 3日め - 空きマスが孤立するときに置かないやつを実装できた →だいたいのマスを埋めることができた →5マスとかの形のせいで残りの空間が2,2とかに分割されているところがある →3マスのやつがめっちゃ余っている ピースに隣接するマスの数でソートするやつをやってみる →最初の時点での隣接数なので完全ではないと思うがたぶんやらないよりマシのはず やってみた →見た目よりスカスカになったように見えたが、たぶん大きい空間が残るようになったせいだと思う →→実際に、空きマスの数は減っている →→でもスコアも減ってる（スコアのソート基準が下がったせいだと思う） →→どっちがいいのかよくわからない →→両方やっていいほうをとることもできるが、とりあえず保留 というか、4マスの空間が残ってて3マスのピースが余ってるのに入ってないのは明らかに孤立させないように作ったせいなので、最後に孤立無視で貪欲に入れるべき →かなり良くなったので、とりあえず5以下の埋め方はこれでいいのでは →一応、4マスのところに2が入っているところがあって、それを3に入れ替えられれば1マス埋まって2をひとつ浮かせられるので更に詰められそうではある。とりあえず保留 提出してみる 98.28741(8位) → 98.34267(7位) 微妙に上がった 5以下はスコアの寄与としては小さいので、まあ想定内 1位との差は1.5%くらい 次は、7,6-ominoで高得点を目指す どうやったらうまく焼きなませるだろうか？ スコア順貪欲で最適解が出てない理由は？ 79999 99888 88880 もしこの15マスを分けるとき、スコア順貪欲なら 9^6*8 + 8^6 = 4513672 に別れるはず でも、実際の最適解は 9^6*7 + 8^7 = 5817239 である。こういったものがいくつかあれば1.5%くらい差がつきそうではある。 これをうまくやりたいね 思いついたこと 1. 基本貪欲で、後からきたピースが先にあるピースと被っている場合、被っているマスをどこかに動かしてみてスコアがよくなる（＝もとからあったピースを変えたほうが後からきたピースを変えるよりスコア合計が良くなる）のであれば採用 2. すでに確定しているスコアと貪欲スコアの差が今見ているピースのスコアと残り使えるピース数よりも大きくなったら枝刈りをする全探索もどきのようなもの そもそも、size7のピースのスコア分布を調べたい case2だけ見ると、size7を使い切る前にsize6は来ていない 7の最小スコアは500000ほど 15000程度番目くらいの候補で7を使い切っている 平均的なサイズ7のスコアくらい得したい ピース上から50個くらいみてどうなっているか見たい 始点がほぼ同じ場所になってる スコアは1番目も2番目もほとんど変わらないのに、必ず1番目を使うことにしているのは明らかに最適ではない 9,8,7あたりが密集している場所で、最もスコアが高いものを使っているせいでその後うまく行ってない場面がある →最初20ピースくらいをbit全探索したらいいんじゃないでしょうか？ →どんだけ変わるかわからないけどやってみる →その時点で置くことのできるピースを20個入れて全探索することを上から1000ピースくらいまでやるとどうなるんですかね →→やってみた →→時間がかかった割にスコアがほとんど伸びてない たぶん、一度に入れられる数が20個では少ないのと、最初の20個の時点では後々どれが最適になるかわからないためだとおもう save → temp2.cpp load ← submit3.cpp やっぱり焼きなましがいいのだろうか もし、上から1000ピースのなかで最適を選ぶことができれば充分強い（最大ケースであっても） 初期状態がかなり強いので、取れる可能性はあるか？ やってみる 遷移は入れる、抜く、交換の3種類 最初の1000ピースでやってみる 置ける7の数以上は常に置かないことにするが、最初は許容してペナルティをでかくしていくみたいな戦略も可能ではある →そもそも被ってもいいみたいな話もあるんですか？ →被ってることに対するペナルティを実装して、的な →→1マス違いのパーツでどっちを使うかみたいなことが可能？ →→交換でよくないか →→→保留！ 1000ピース目まででのスコアは上昇したが、全体としては下がった →1000番目までで使う数が増えるとそこまでのスコアは増えるが、その後使える数が減ったので下がったのだろう これ10000までにして超長時間やったらいい解でるんですかね →別にそんなことなかった →というか、評価関数が悪いのだろう いい方向に収束する理由がそもそもない 焼きなましってなんでうまくいくんでしたっけ 明日考える今日はねる（朝6時半） - 4日目 - よく考えると、1つ抜く、1つ入れる、1つ交換はどれも遷移として良いところがまったくない。 最初に貪欲でつめているのだから、この3種類の遷移1回で状態が良くなることはありえないので、例えば偶然いい場所をひとつ抜く→偶然いい場所をひとつ交換→偶然いい場所にひとつ入れる など複数の遷移が都合よく重ならないと良くならないし、遷移が終わってもそれが良かったのかどうか最後までわからない（一回の遷移の中で良い遷移かどうか全く判断できないのも駄目） →昨日のようにピースが増えても全体として損をしていたということがありうる しかも、スコアが100000単位で増えたり減ったりするのは急すぎる そう考えると、「2つ抜いて2つ入れる」遷移は強い気がする。 7と6を全部入れ終わってから「2つ同時に交換」だけで遷移すると、一回の遷移の中だけでスコアが増えるか減るかを判断できるので山登りができるし、(7と6を全部入れ終わっているので)スコアが増えたら必ず最終的にもスコアが良くなる。遷移ごとのスコア変化もかなり小さくなるはず。 →そもそも、山登りができないような遷移で焼きなましをやろうとしていたのはどう考えても間違い →頭使いましょう 置く2つだけを選ぶと、盤面だけ見て抜く２つを自動的に決められるのでは？ →出力する盤面を最初から用意しておいて、2つを置く予定の場所に重なっているピースが2つならそれを抜けばよい →もし1つしか重なっていないならば、そのとき置いてあるピースの中で一番スコアの低いものを取り除けばよい →こっちのほうがよさそう 実装した →ほぼ上がらない case 2で0.1%上がった程度 なぜなのか？ 最初に全部貪欲でつめてしまっているので、7と6の交換が難しい？ とりあえず提出 97.9279(10位) → () 結果が返ってこない save → submit4.cpp 交換が可能な候補はそもそもいくつあるのだろうか 最初に選ぶピースを変えるだけで焼きなましより良いスコアでますが…… →コード整形して提出してみたい これビームサーチとかもワンチャンあるんじゃないですか？ 最初の位置だけ変えるやつを提出してみた 98.5041(5位) ジャッジ中の人がいるのでたぶん本当は7位くらい save → submit5.cpp ここからどうやったらスコアが上がるだろうか？ 最終的に強い置き方は全部置いてみないとわからないので、最初の20個でbit全探索とかは弱かったのかなと思った。 やっぱりビームサーチをやってみたほうがいいか 各ピースを使うかどうかでビームサーチできるだろうか 最終的に強くなる置き方が途中で消滅してしまったりしないだろうか わからん - 5日目 - 最初の10個くらいをbit全探索するのをやってみたい 以前と違って、最初の10個で優劣をつけずに最後までいってからスコアを比べる 適切に枝刈りすればもっと行けそう？ →提出したが結果が返ってこない(枝刈りなし) save → submit6.cpp 枝刈りをうまくやって、より多くの状態を調べたい 全探索しているN個を調べた時点で、どれが実際に盤面に置けたかは整数として記録できるので、以前最後まで調べたものと同じ整数が出たらそれ以上調べる必要はない。 改善前は、case2でlast stateは2500程度 実装すると、相当早くなった→last state = 16677113 提出してみる これを利用して、かなり後の方まで全列挙できそう last state = 19732009であっても、最初の20個で考えられるパターンは25個程度しかない よって、40個を全列挙するとなったときに、最初の20個に関しては25パターン調べればよいので次の20個もすぐ終わるはず これを繰り返せば効率よく100個くらいまでは行けたりしないだろうか 提出 98.57341(6位) redcoder2人の間に入れたのでわりとよさそう save → submit7.cpp bitsetでうまくやりたい n個目までを全探索したら、有効な組み合わせをbitsetなどで保持して、それをsetで管理する。 次に、n個目までの探索はそのsetの中身だけにして、n+1個目を新たに探索して、新しいsetを作る これを繰り返す →実装してみた かなりよいので提出してみる →98.69139点(7位) save → submit8.cpp もっと時間をかければよりよい解をみつけられるのだろうか？ 現状、ある程度以上大きい盤面では結局最初の20個くらいしか全列挙できていない 枝刈りなどで高速化できないだろうか - 6日目 - 昨日書いた列挙を高速化したい 考える。 流石に60番目のピースとかになると、候補の数も10000を超えてくるので、減らす必要はありそう。 case 3で上から100ピースの置き方を全列挙しても最高点が9ピース目までのものなのは気になる case4で100秒くらい実行したら最高点がでた　 40で72373949 →とはいえ、これを永久にやれば理論上最適解が出るはず →5以下の配置に関しては依然貪欲だが、これで1%は伸びないと思うんだよなぁ ビームサーチであれば単純にスコアでソートして上から1000個くらい残せばいいが、今回は候補によって使っているピースの数が違うので単純なソートはできない →本当ですか？ 解決策としては、これから見るピースのスコア*足りない数だけ「使っているピース数」に補填するなどが考えられるが、スコア順にピースを見ている以上これは補填しないでソートすることと変わらないので、むしろそのままソートして良いのでは →やってみる ビーム幅50で、0.01くらい落ちた save → submit9.cpp ビーム幅200で再提出してみる 98.72183(7位) →強い。自分より上は全員黄色で、赤が全員自分より下にきている 1位との差を再び1%程度にもってくることができた 高速化したい！ ビーム幅を有限の値にしたことで、高速化の恩恵をかなり受けやすくなったはず もし十倍高速化できれば、相当なスコアが得られるに違いない おそらく、めちゃくちゃ高速化できても10000番目とかより下はほとんど貪欲になるはず よって、10000より下だけで貪欲して使われなかったピースはそもそもいらないということでは？ →これらを全部削るとピース集合をかなり小さくすることができて、高速化に貢献すると思う。 現状でも50個に1個くらいしかピースを入れられていないように見えるので、もしかしたらめちゃくちゃ早くなる可能性もある？ →これ嘘じゃないですか？ →10000番目より下だけで貪欲して使われなかったからと言って、今後も使われないとは限らないのでは？上のピースの配置が変わったら使われる可能性あるだろ 全探索じゃなくてビームサーチを採用した時点で厳密解を出そうとは思っていないので、サイズ7が埋まったらその時点で枝刈りなどをしてもいいと思う サイズ7まですべて見たあとで前回の200番目のサイズ7より明らかに小さければそれ以上計算しないなどはありうる →結局200個については最後まで計算するのであればどれだけ速くなるのかは正直微妙 →サイズ6も2%くらいスコアに寄与するので、これを見ずに優劣決めるのも正直微妙な気はする →とはいっても振れ幅でいうと多くても2%の3%(= 0.06%)くらいだと思うので無視しても良いのでは？ →サイズ7まででビームサーチして、最後に残った200個に対してサイズ6まで貪欲して一番いいのを採用するなどは十分考えられる。 →そもそもサイズ7が埋まるindexとサイズ6が埋まるindexはどれくらい違うのか →→普通に数十倍くらい差があるな やるしかねえ 提出した save → submit10.cpp 98.80952(7位) いい感じな気がする 実行時間がちょっと怖いかもしれない →最後の200個もどうせ上から見てるんだから時間で切って問題ないはず もっと高速化したい ビーム幅も検討する必要があると思う 時間10倍にするとやっぱりまだスコア更新できるんだよなぁ…… 結局ビームサーチをsize7までに変えても2倍程度しか速くなってないんですよね 使わないピースは結局イテレーション速いので、ピースの数が1/10になっても10倍速くなるわけではないのはそれはそうなんですよね 使うピースの判定を素早くできないだろうか？ indexを1000くらいまで見るようになったのであれば、stringで状態をもつことはやめて、置けるピースのindexをvectorでもつようにすれば速くなるのでは？ →盤面の状態も一緒に保存しておけば、そもそも今まで見た状態をもう見る必要がない →これってどのくらい速くなるんですかね 時間10倍にしたらcase1で最後まで回りきってワロタ 一番時間かかってるのはどこだろうか →もしかして、vectorのコピーだったりしませんか checked は最大で200要素×length1000程度なのでかなり重い説ある ans_copy は 高々length2500なのであまり問題にならないか →盤面が小さいと減るしな 他に時間がかかってそうなのは、ピースを置けるかどうかの判定 これbit演算でできませんか？ bitsetの演算は高速であることが知られているが、大体64倍程度で概算しても今のほうが速いのではないだろうか 調べてみると、なぜか後半になるにつれて加速していることがわかる なぜ加速しているのか？ →入れられるピースがわかってくるので、速くなるのだろう →vectorのコピーは速度に寄与してなさそう やっぱりピースを入れられるかどうかの判定が遅いんだよなぁ 置くのと判定は同じ重さのはずだが、判定のほうが数が多いためだろう これ減らせないんですかね range based forを参照渡しにするだけで2倍速になって草 →提出 99.91687(3位) 死ぬほど上がって草 もういいのでは？（よくない） 何が効いたのだろうか？2倍速くなったことがそんなに良いとは思えない。 最後に残った200個を貪欲するときに時間で切るようにしたので、実は1ケースTLEで落ちていたとか？よくわからない ジャッジのバグだったら嫌すぎるな save → submit11.cpp 調べるとbitsetは思ったより速いらしいので、ビームサーチをbitsetで実装してどれだけ速くなるか調べる 今は動的メモリ確保をしまくっているので、そのへんもうまくやれば5倍くらいになったりしないかな（願望） bitsetの長さはconst変数でないと確保できないらしいので、2500で取るしかないだろう 1位との差がなんと0.07%しかない 優勝目指せませんか？ bitsetで盤面を表すとき、ピースを置けるかどうかはどうやったら判定できるだろうか？ bitwise andしたあとに!noneでいいですね ビームサーチ部分をbitset+動的メモリ確保なしで書き直してみたが、むしろ遅くなった →やはり、判定が2500桁のbitsetの演算なのが普通に遅いらしい 悲しいね 普通に書いた方を高速化することを考えたほうがよさそう まずは、動的なメモリ確保をやめてみるところから save → temp3.cpp load ← submit11.cpp なんか最終submitのスコアが高すぎて信用できないのでもう一回submitしてみる →同じスコアが出た - 7日目 - やはり順位表が壊れているらしいとForumで言われている いつから壊れていたのかよくわからないので自分の順位が全くわからない スコアが全体的に高く出ているらしいが、相対的な順位は変わらないのだろうか？ なにもわからなすぎる 急に上がる前は7位だったが、今上位の人が大体壊れた(と思われる)後に提出して6位なので、相対的な順位はあっていると信じたいですね あと21時間でコンテストが終了するので、今日中に直ってほしいね とりあえず当初の予定通り高速化しましょう ・ビームサーチ内での動的なメモリ確保をやめる ・サイズ7だけのピース配列をつくる ・ピースの座標集合を(x, y)ではなくてx*N+yの形で保持しておく ・盤面はvectorで、状態はstringをやめてvectorでもつことにする →速くならない コンパイラの最適化が強いんだよなぁ save → temp4.cpp load ← submit11.cpps というか、selectIdxが置けない場合、その時点で打ち切ってよいですよね →めっちゃ速くなった 今までの苦労は…… ビーム幅も増やそう とりあえず提出するか（今提出して意味あるんですかね） →100点 草 save → submit12.cpp まだスコアアップの余地あり ソートするためのスコアが、selectIdxでの時点でのスコアになっていることが発覚した（実装ミス） これを7を置き終わるまでのスコアに修正すると、速度は少し落ちるだろう →とはいってもさっきまでよりは速いはず 現状2500番目くらいまでビームサーチできていて、これは充分大きい数字だと思う どこまで遅くなるかわからないが、スコアを7を置き終わるまでのものに修正してどうなるか見たい 盤面もvectorに一緒に突っ込んでソートすると速くなるのか、それとも逆に遅くなるのか？ 提出したやつのビーム幅を10000にしたら伸びたり伸びなかったりした 7を置き終わるまでのスコアにすると遅いのでやめる 盤面をvectorに突っ込むやつをやると、高々<ビーム幅>回の判定で1ピースのサーチができると思っているので速そう ただ、vectorのコピーが遅い可能性はある でも盤面は毎回コピーしてんだよなぁ 実装したけどバグってる気がする →しかも別にはやくなくないか もう高速化は諦めて、良いパラメータでも探したほうがよい気がしてきた 最終的に最大スコアになっているものが、途中でどのくらいの順位にいるのかなどは気になる →最初に上のほうにいたものは最後にどのくらい上にいるのか？逆もあるか？ - 7+1 日目 - ジャッジのバグが直らないのでコンテストが1日延長された。 順位表が手動で更新されていて、昨日提出したものの結果がわかった submit12 99.10922276 (8位) まあまあじゃないだろうか。 99を超えたのは嬉しい。 昨日考えていた、最後に上位にいるものが途中でどのくらい下にいるのかは調べたい 次の手動更新がいつ来るかわからず、無駄にしたくないのでビーム幅5000のやつを提出してみる 最後にcheckedを掘る時間を長くするほうが良い解が出やすいっぽい？ →提出 save → submit13.cpp →ビーム幅をあげると、サーバー上ではローカルよりもかなり遅くなるっぽい submit12のほうがおそらく優秀 checkedを下の方まで掘るのは、一定以上を超えると意味がなさそう ただ、1000までしか掘らないからといってビーム幅が1000でいいというわけではなく、ビーム幅を大きくすることには意味がある 配列を使いまわすことによって、ビームサーチを高速化できるか？ 盤面をvectorに突っ込むと、コピーが発生するので遅くなると思っている 最初にビーム幅*2個の盤面を確保しておいて、適切に番号を割り当てるとコピー回数を最小にできる？ 適切な枝刈りは可能か？ というか、普通に考えるとソートに時間がかかっているのでは？ →そんなことはなかった ソートにかかる時間は、それ以外にかかっている時間の1/20以下 間違えてsubmit13を消した 高速化したい〜〜〜 →状態の持ち方を工夫したらだいぶ速くできた うれしい〜〜〜 save → submit14.cpp 提出 99.2くらい 自分より上が全員赤と黄なので、悪くはない。 パラメータを調整してみたい ビーム幅5000にしてみた →提出 →99.24 前回の提出が下がっているので、まあ上がっている save → submit15.cpp 結局、ビーム幅は3000でいくことにした サーバーでのテストは100ケースなので少ないが、手元の10ケースよりは確実に信用できるはず 時計の呼び出しが多すぎるので場所を変えて、デバッグ出力もけして問題なさそうなら終了にする