のメモです。
折り畳みました(なにもかも思ったこととか独り言とか全部書き捨ててあるので、読むものではないと思います)
5/22(木)
問題を読む。
cnt*areaとかムズそうな関数やなぁと思う。
とりあえずareaを最大化するように置いて出してみようと思ったけど、それすらもあんまり実装する気にならなかった。
とりあえず戦略を考えていこう。
その前に課題ー
5/23(金)
5/24(土)
パズル選手権が最高に楽しかったです。
5/25(日)
今日こそは実装しようと思ったが、時間があまり取れず・・・
というか、なんか実装する気が起きないなーこれ。
とりあえず、考察はしとこう。考察をちゃんとすればそのうち実装方針も見えるはずだー
最大化するもの、「cnt*area」じゃなくて「cnt^2*area」だったのか・・・
それでも大きいのと小さいので役割を分ける戦略は有効そうだ。
例えば、1x1のだけが1000個くらいあるとする。これを全部メッシュ状に並べると穴の個数は最大になるが、600個を個数要員、400個を面積要員とかにすると、10倍は軽くスコアが上がる。実際には長方形のサイズはバラバラなので、これらの戦略のスコア差はさらに開くと思う。
> 長方形たちをどういう風に４つの斜め部分に配分するのが良いのだろうか。
についても考えた。
上半分だけに注目して実験。
1x3が４個と2x2が４個あったとする。
これを1x3を全部左、2x2を全部右とする時と、２種類のを均等に割り振るのでは、後者が圧倒的に良いらしい。
イメージ的には「均等にふっくら」させるのが良さそうだ。
5/26(月)
とりあえず面積役の方を実装する方針は見えてきた気がする。
太さ(縦÷横)でソートして、順番に４つに割り振っていくという感じが良さそうか。
ちゃんと穴を作らずに輪っかを作るの結構実装大変そうなんだよなぁ。
個数要員からちょうど良さそうなのを引っ張ってくれば穴は塞げそうだけど、さすがに無駄な行為な気しかしない。
ちょっと狭めるのを我慢して長さが余ったところの真ん中らへんのブロックを少しずらして調整と言うのが良いと思う。
あんまり狭めたくないから、長さの差が出来るだけ少なくなるようにしたい。
DPは出来るだろうか。
状態としては
dp[i][d1x][d1y][d2x][d2y][d3x][d3y] = i個目まで置いた時に、0番と1番の差がd1x,d1y、0番と2番の差がd2x,d2y、0番と3番の差がd3x,d3yになっていることが出来るか。
まあ、厳密解出そうと思ったら絶対間に合わなさそうだわな。
ヒューリスティックス使えそうだ。ビームサーチか焼きなまし
ビームサーチ：差が小さいものからhoge個を保存しながら順番に置いてく
焼きなまし：とりあえず良さそうな感じに置いて、swapで局所改善
うーん、後者かなー。
心配なのは、局所改善の過程でせっかく均等に配分した厚みのバランスがバラバラになることだな。
じゃあ、swap可能なのは各パートでの厚さの順位が同じ物どうししか交換できないことにしよう。
うん、これでとりあえず実装しよう。
多分これで面積についてはある程度良いものが出来るはず、ここで何倍もの差はあまり付かない気がする。
個数をいかに増やすか勝負な気がするなー。
実装に関して、配分の方法は決めたけど、最後の調整はどうするのが良いかな。
ずらす場所はどこにするのが良いんだろうか。
余ったところをちょっと短くしたいんだから、外側にずらすんだよな。
だったら端っこでずらすのが一番面積大きくなるよね。
端からずらしていって、目標のずらし分を達成するまでどんどんずらしていく。というのを縦と横に両方やる。
縦が余るパートと横が余るパートはそれぞれ１個までにできるけど、それらが一致していない場合もあるな。
それらが独立しててもまぁ大丈夫そうだけど、どこに余るのを持ってくるかを決めておけるなら決めておいた方が実装楽そう。
いや待て、今まではノみたいなパーツを作ることを考えてたけど、)みたいなパーツを作る方が良さそうじゃない？
そうすれば、縦を吸収するのは上の左翼、横を吸収するのは左の上翼みたいに簡単に固定できるし、割り振りの時点で少し扱いやすい。
かなり本質じゃないところを考えてる感があるけど、実装しやすさというのも考える価値は大いにあるよねきっと。
嘘だな。)型にすると均等になりにくい。
ノ型でずらす位置を固定するには、上側で横が余って右上を横ずらしに割り当て、左側で縦が余って左下を縦ずらしに割り当てれば良い。そういう状況は、回転をさせれば必ず作れる。おk
だがしかしまた問題があるな。いまだと、厚み順で割り当てていってるけど、ばらつきがでそうだな。
８つに分割するか。というよりは、swap可能な範囲を８までにするか。
とかいろいろ考えてみたけど、ビームサーチ的にやった方が、今求めてる'均等'を実現できるのではないかなー。
5/27(火)
うーん、もう貪欲で良い気がして来た。改善するならそこからの話で、ちゃんと適切な評価関数考えたりした方が良いような。
貪欲でも差は高々2000(実際の結果はもっと低くなると思う)だし、ちゃんと輪っか作れそう。
なんかこのマラソン、日に日にやる気を失ってきてつらい。
順位表を見てみた。なんか荒れてるなぁ。確かにそういう系の問題っぽいけど。
とりあえず今日中に１回提出したい。
とりあえず４つの真ん中棒を除いた8m個の長方形を貪欲に配分して、4個の棒と8個のパーツをどう並べるかは、どうするか。
純粋に全部試すと、3!*8! ≒ 10^5くらい。まぁ、試しても良いか。
じゃあ、どういうものを採用するか。
・縦・横のあまりが少ない
・４つのノの幅と高さが均等、分散でもとるか(＝二乗和でも同じ)
２つ目が良いものは１つ目もある程度良いだろうし、２つ目だけで評価しよう。
真ん中の棒に関しては、半分で分けて左右に分配するとよさそ。
とりあえず、提出した。
112.89pts
まあ低いのは当たり前なんだけど、数字からなんとなく思ったより低い感じを受けるけどどうなんだろうか。
とりあえず計算しよう。
√(Top/自分) = 93.4
これに定数倍をしたくらいのものが、Topに並ぶために作るべき穴の個数か。
例えば長方形を半々で配分したとすると、面積が約1/4倍になる。
辺の長さの差もあるし、減り幅そんなに大きくないかも。
ということは、作らなければならない穴の個数は200くらいか。
実際にはNの値によって結構違いそうだし、よく分からん。
とりあえず、Nの平均/2 ≒ 250個の長方形で200個くらいの穴を作らねばならんと。
全部同じ大きさの正方形だとすると、だいたい210個くらい作れそう。結構ギリギリ。
大きさバラバラだからちょい難しいかな。
でもオーダー的には妥当な感じ。方針はそんなに間違ってないような気がする。
※配分はNによって変化させる必要はありそうだ！ということをメモ。
さて、面積パートはとりあえずある程度できたから、次は個数だ。
お腹へったし、晩飯食べてからにしよう。
大きさバラバラだからスコアが減るかと言えば、そんなことはなさそうだ。
例えば、めっちゃ細長いの２本と1x1の正方形N個なら、N-1個の穴を作れる。
まぁ、そう上手くは行かないにしろ、N-2√Nくらいの雰囲気の個数は出せる気がする。
N個の長方形でN個以上の穴を作るのは不可能そうだ。
証明は簡単で、穴の角には必ず長方形の角が来るから、角の個数を数えれば分かる。
１つの角が２つの穴と接することもあるが、そのときは必ず長方形の角も２つ来るから同じ話か。
上限はNくらい。
その付近を目指すなら、長方形１個あたり１個の穴を作っていく勢いが欲しい。
さっきの角理論からなにか見えて来ないか？
・作る穴は多角形ではなく長方形にするのが理想(直感的だ)
・どことも接しない角は極力減らす。
・多角形を作らなければ、穴の個数は「どこかと接している角の数/4」かな。
・長方形どうしが接すると、基本的に計２つの角を消費する。
・例外は、角どうしがピッタリ張り付いて、辺に成り下がってしまうケースか。
多角形と角の相殺がなければ、穴の個数を長方形が接している個数に言い換えられるというのは嬉しいかも？
多角形の出来る条件とは何だろうか。
・内側を向いた無駄な角があること
かな。うーん、よく分からん。
逆に、長方形にはどんなパターンがあるだろうか。
角には、
・角と角が接する
・角と辺が接する
の２通りある。
長方形には、角のパターン(角と辺のペアの場合向きが２通り)を組み合わせたものがたくさん考えられるな。
なんとか分類できないか。
角と角が接するパターンは微小にずらせば角と辺になるし、それで状況は多分あんまり変わらない。
角と辺のパターンのみで考えてみよう。
４パターンしか無いようだ。
手裏剣、はしご、鳥居、丘と名付けよう。
はしご
長いの２つに、同じ幅のを挟んだ形
同じ幅と言う制約が厳しそう。
手裏剣
４つはそれぞれどんな大きさでも良いから結構作りやすそう
鳥居
小さいのがひとつ挟まった形。
はしごで作った隙間にさらに突っ込んでやれば一気に２個作れる。
というより、穴にサイズの合う長方形を突っ込んでやれば作れる。
丘
よく分からんが、鳥居とキャラが似ている。
幅が固定される長方形の個数で分類すれば鳥居と同じ分類になりそう。
ふむ、穴の中に、ちょうど良い大きさの長方形をねじ込んで増やすと言う手法があるのだな。
無駄が無くて強そう。(面積を完全無視するなら)(個数要員で作れる面積鼻くそみたいなもんだし、無視していいとは思う)
細長い長方形は結構こういう使い方が出来て強そうだ。
厚い長方形はどういう使い方をすればいいだろうか。
挟まれる長方形として使うのは基本的にナンセンスな気がしている。
大きいのならはしごの周りとしても使えるけど、うーん微妙な気がする。
手裏剣みたいに使うのがbestっぽい気がする。
5/28(水)
さて、今日も頑張っていこー
面積要員の外周の窪みを利用して、丘を互い違いに重ねて行くと、「使った長方形-1」個の穴が作れて、効率良さげ？
まぁ、どれくらい重ねられるかにもよるか。あんまり重ねられないなら、手裏剣とかで地道に三角形状に作っていく方が良いのか。こっちは、作れば作る程無駄が減るという習性がある。
丘戦法と三角戦法、どっちがいいだろう(あるいはどう組み合わせる？)
・丘戦法に適しているのは薄い長方形
・三角戦法に適しているのは厚い長方形
だと思う。
うーむ、なんか、Tの字に組む事自体が効率良いんじゃないかと思った。
なんでだろう、多分露出する角が減るからかな。
うーん、どうなんだろう、紙で実験してみたけど、そんなに有効という感じもしなかった。
Tじゃなくてエの字なんだろうか。
穴を２つ作るために必要な長方形の最小個数は５個で、エの字が真ん中に入るケース。
エの字は凹が一気に２つ出来るから強そう？
でもそれって厚いのがたくさんあるケースの話ではなくなってないかー？
あるいは、厚いのばっかりでもそういう利用法が出来るか？
挟む奴を小さい奴にすれば出来る。
で？っていう。うーん、よく分からん。
お散歩しよう。
長方形の配分、辺の長さの合計にしてたけど、薄いのの方が需要あるし、二乗和に変えたらちょっとスコア上がった。
なんかこの巨大なエリアを眺めているだけで結構楽しい。
とりあえず半々の割合で分けたものを投げてみた。どれくらいスコア減少するのだろう。
112.32→46.95(0.41倍くらい)
なるほど。0.25倍として考えてたから結構差があるかなーと思った。
√(Top/これ) ≒ 145
そんなもんかえ？
ちょろそうに見えるけど、Nが一定でないから全然なんともいえんよなー。
ちょっと組んでみて出してみないとさっぱり分からん。
少なくともNが320以上くらいじゃないと145も作れなさそうだしな。
適当に組んで、手元で比較しよう。
小さいケースであまり大きな差が出ず、大きいケースで大差が付いているはずなので、この結果は全くあてにならんという結論に達した。
そんなにちょろいわけがないよ。
だけどまぁ、50位以内はいけるんじゃないのかなー。
とりあえず個数をある程度まともに作って出してみるしか無い。
しかしまぁ今回の変な問題やなー。
実装しなくていいなら楽しいわ。
個数について、
外周＋でかいの２つで囲いを作り、中に手裏剣を入れると、5/6を達成できる。
丘チェインで余ったのを使ってこれが出来れば、結構まともといえる個数を出せそう。
条件式をたててみた。
うーん、実験してみないと作れるものなのかどうかよく分からんなー。
とりあえず長さ7以上の丘チェインを置きまくるのを組んでから実験しよう。
ふむ、とりあえずseed6だと長さ10のができた。
丘チェインだけでどれくらい作れるのか（外周が無限にあるという仮定の元）を調べてみる。
cntN : 83, sum : 59
まあまともなチェイン4つくらいしか作れてないからsumは気にしないでおこう。
cntN : 203, sum : 152
seed1だと8以上が8個作れてる。
思ったより作れることが分かった。
たまに、後から作った方が長くなることがある。。
あー、長い方の辺が多少長くても薄いのを採用した方が良いというあれか。
改善すればもっとのばせそうだ。というか、かなり適当すぎるアルゴリズムだった。
さて、それでも6割くらいは残りそうだ。
３つくらい案がある。
A) 何も考えず、一カ所にまとめて置いて適当に穴を作りまくる。
B) 丘チェインをいくつか使い、あとはまとめて置く。
C) 丘チェインと手裏剣箱を作りまくる。
Cは数が少ない時に有効そうで、Aは数が多い時に良くなるかも知れない。
((√N)-1)^2 = N*5/6
となるのはだいたい、N= 131くらいらしい。
ふむふむ、ほとんどのケースではAかBが強いのか。
とりあえずAを組んでみたいところですよね、やっぱ。
はぁ〜、つらそう。
出来るだけ場合分けっぽいことを考えずに済むような方針はないものだろうか？
穴の個数を数えるなんていう面倒なこともしなきゃ行けなさそう。
うおー、むずい。
局所改善超しにくいのがつらいよなー
いい感じの置き方を考案して、ランダム要素を入れて、何回も試してみる。
とかそういう感じかなら出来そう。多分あんまし強くない。
それよりは、頑張ってビームサーチ的アプローチが出来た方が強そうだけど。
ビームサーチ路線で考えてみるか。
・置き方の候補
・評価関数
を決めよう。
置く順番は小さい方から的な感じで良いか。
置き方の候補
・角と角を接させて置く
・コの字にフタをする
・くの字のところに幅1の隙間を空けて置く
あたりで良いかな。２つめムズそう
評価関数
・穴の個数
・コの字の個数
・くの字の個数
・長方形たちが丸い範囲にまとまっている
あたりかな。
コの字・くの字検出が一番難しそうなところか。
5/29(木)
１週間経ってしまった・・・
進捗はあまり芳しくないかなー・・・
コの字・くの字検出か。
内側はどうでも良いから、外周だけ検出できれば良いよな。
動的に更新して行けば良い気がする。
辺を反時計回りに並べて、持つ情報は、
・長さ
・向き
位置は最後に計算すれば良さそ。復元に必要な情報は後で考えても間に合いそ。
これを使えばくの字もコの字も簡単に検出できる。
あとは置けるか判定かな。置けない条件は
・交差・包含
・角が辺に退化するケース
・多角形が出来てしまうケース
O(N)かければ判定くらい出来そう。高速化はまだいいや。
長方形との交点や接点を全部洗い出す。接線に関しては両端のみ。
んで、
・交点or線が長方形内にあれば交差または包含
・接線の端が角と一致すれば退化
・接点と接点の間に4本以上の線があれば多角形
ついでに今のうちにでかいとこの面積も求めとこう。
やったー外周のトレースが出来た。
これ利用したら面積も出たぜ。
多分この外周、個数要員配置した後でも面積計算に使えるな。(連結なら)
今日中には出来ないからとりあえず、N<370で0点を取るのを投げてみたけど、かなり点数減ったな。やっぱりか。こりゃあてにならん。まともに書いて出さんと分からんね。
今組んでるの何点くらいなんだろうな・・・
早く実装してしまわないとスタート地点にもたてねーぞー
上位を狙うなら個数要員でも面積ある程度作らんとあかんのかなー
5/30(金)
とりあえず、角どうし、コの字埋めの二つを実装してexampleに投げてみた。
0点が帰ってきた。
うーん、今のところ手元だとうまく動いてるように見えるから、環境の違いで何かが起きているのか。
10分待たんとアカンのつらい。
場所はだいたい特定できた。
あ、直った？直ってるわけねーよなー。
意味不明だ。わけわからん・・・・・・・・・・・・
もうやめたいっす＞＜
あー、ひどいことしてることに気付いたぞ。
it = hoge.end()まで回してる。
手元で動くのやばい。
ちゃんと動いたのでfulltest投げてみる。
雰囲気、Nの0.25~0.33倍くらいの個数の穴が出来てる。
前回と比べ、結果はええなー。
391946.07pts (41位)
ほうほう、まあまあじゃね？
1000000/391946.07 = 2.55...
穴の個数を1.6倍くらいにすれば良いらしい。
つまり、N/2の0.8~1.0倍くらい。
なるほど、妥当だ・・・
いちおう、面積:個数の配分をいじるというのもまだ出来るから、もうちょっと緩くていいかも。
まぁ、この感じだとレート上げにいくのは容易っぽい。
次は、ビームサーチ化か。
両方向差分と評価関数を実装すれば良いのかな。
イテレータには要注意やな。
どういう形が効率良いんだろう。
個数要員も別に極端に小さいわけじゃないから、斜面をもりもり使っていくってのも良いんだろうかなぁ。
分からん。
ある程度まとまってた方が良いっていうのは確かだろうけど、丸い方が良いのか、アメーバみたいに斜面にもりっとへばりついてるのが良いのか。
斜面って、中途半端に長いんよな。
何ともいえん。評価関数をいじって実験するのが良さそう。
とりあえず、両方向差分は出来た。
次は評価関数。っつても、置くメソッドのついでにいろいろ求めるのがメインかな。
holes,Ls,Usのカウント。
ただ、渦巻き状になっても嬉しくないので、Usのカウントは少し工夫がいるな。
一応組めた。
結構実行時間がかかるな。
seed7とか結構ギリギリ。
とりあえず、真ん中の方だけ試すようにしたけど、もっとちゃんと高速化しないとビーム打てない。
なんか組んで、見てみたら蛇みたいに伸びるようになった。なんだこれ。ああ、馬鹿だった。何でもない。
とりあえず、手元で100ケース走らせて、submitして寝よう。
おや、まれに0点になるようだ。3/100。
それと、なんか２グループに分かれちゃうケースもあるみたいだ。このあたり明日直そう。
0点は面積パートで変なこと起きてるっぽい。
は？list.insertができないと抜かしている。いや、iteratorがなにかバグってる？
なにこれは・・・
あっ、hoge.end()->fiに書き込んでる。やべぇ・・・
多分直った。
高速化どうしたもんかなぁ。
673784.51pts (22位)
これはレート上がりますね。間違いない。
ちょっとやってみたけど、半々分割は結構bestに近いっぽい・・・
だけど、4/10とかにすると結構上がるような物もあったりする。
この辺りはムズイな。
5/24(土)
今日はどうするかなー。
とりあえずビーム化して、
長方形が分離する問題もなんとかしないとな。
うーん、どうすればいいんだろうか。
今のところ、穴/長方形は2/3~4/5くらいらしい。
意味の無い置き方を結構してるなー。
多角形も許容したら結構伸びた。
多角形は小さいケースではあんまり出来てなさげ。
rep(i,n)rep(i,m)....みたいなのに警告でないんだな・・・ハマったぜ。
ビーム打てた。
かなりいい感じに見える。
ソースコードをいじるとへんなエラーが出ることがあった。頭の隅っこに置いとこう・・
ビーム幅を時間制御しよう。
サンプルだとあまり発生しないけど、100ケーステストだと結構-1点出るな・・・
2割くらいのケースで起きてる。のにサンプルでは起きないのか・・・
再現性が低いな。
ビーム幅を固定してみた。
減ったけど、結構出るっぽい。なんだろうこれ。
それでも再現性無いぞ。なんだこれ・・・
パソコン壊れてるんじゃないかレベル
おっと、実行するたびにスコアが変わるぞ？
srandしてないし時間に依存する部分無いと思うよ。
これはなにかやばいものを埋め込んでますね。
ある処理を消すと-1は出なくなったし、答えも一致するようになった。
あー、分かってしまったかも。イテレータまわりやばいっすねこれ。
おいおい、まだ一致しないぞ。
ああ、処理足りてなかった。一致した。
さてと、時間管理をもうちょいちゃんとしたら提出しよう。
しない方が点数良かったぞ。
提出
937536.35pts(7位)
まあまあ。レート爆上げ確定ですね。
1000000/937536.35 = 1.066...
6%スコアあげれば強そう。
さて、どこを伸ばすか。
出来そうなことは、
・配分調整
・高速化
・複数回試行
・評価関数
・置き方の候補
・その他調整
まだ伸びしろはありそうだ。
一日中引きこもってるのもアレだし、気分転換に散歩してこよう。
分割基準のソートを和、二乗和、三乗和で試してみたけど、いずれも有利になるケースがあった。
二乗和がこの中ではいちばん強そうだった。
478個で422しかつくれてないようなケースがあったりして気になるな。
多分ビーム幅不足。
うーん、高速化が一番効果高そうだ。
あと、多角形を作る手を候補に入れたいところでもあるが。
とりあえず、
・長方形の集合を木構造で管理(交差判定とかその辺りでは全く使わない)
・外周情報の不要なところ(裏側とか)を縮約
根本的ではないけど、２倍くらいは速くなったと思う。
最後の方でビーム幅が劇的に下がるの良くないっぽいかな。
もうちょいちゃんとしよう。
とりあえず提出してARC,GCJの準備。
965962.06pts (6位)
現在の4位の980625.80ptsが見えてきた。
980625.80/965962.06 = 1.015
1.5%の改善が必要らしい。
topには3.5%くらい。
個数にすると、500個の穴を503個〜509個にする勢い。
というと、いけそうに聞こえるが、まぁそんな甘くはない。
そろそろ配分について考えてみるかな。
配分に関する式を考えてみると、個数が同じだとすると、半々がかなりbestに近いのな。
面積は個数の二乗に比例し、穴数は個数に比例するから、cnt^2*areaはかなり頭良さそうな式なんだなぁ。
実際は、長さが異なるから、半々よりやや個数よりに人員を割いた方が良いのかな。
定数がどこにどうかかるのかまでは計算する気起きないし、実際にnごとにやってみるべしかな。
小さいケースには複数回試行、大きいケースには高速化が効きそう。
とりあえず雑い評価関数も見直そう。
あと、外周からじゃなく置いた長方形からどんどん伸ばしていくようにしないと、変な形の穴が出来て効率下がる気がしている。
それと、作った後に無駄っぽい長方形をバリバリ剥がして置き直すというのもいいかも。
とりあえず、大きい方３割だけ点を得る解を送った。
280705.61pts
が、しかし、29or30ケースだけ走ったんだなーということしか分からなかった。
29だとすると、967950.3。ちょっと得をしている。
30だとすると、935685.3。わりと損をしている。
よく分からん。
6/1(日)
さて。
std::listを配列実装に置き換えると速くなりそうな気がする。
ボトルネックを調べてみてる。
put - 2748, judge - 4696
put - 2646, judge - 3628
judgeがボトルネックだと思ってたけど、案外putも重いんだな。
seed6とかで分離が発生してる。これもなんとかしないとね。
今日は、
・角で接する時の候補を狭い範囲に限定して分離を回避(かつ高速化)
・std::listの置き換え
・評価関数
をとりあえずやろう。
小さいケースで余ってる時間リソースどうやって消費しようか・・・
評価関数だけど、U字の個数とかはあんまり多すぎても要らない。最後の方だと特に。
だけど、一番頑張らないといけないのは序盤の方なのか。後の方はある程度適当でもバンバン作れる。
置いていくのを小さいもん順にしたら伸びた。まぁ、そんな気はする。
ここから先は、いかにソースコードを愛するかにかかってる気がする。
ビジュアライズして気付いたんだけどさ、縮約ミスっててすごい形になってるwwwww
笑った。
EC2を借りた。
100ケース走らせても自分のPCが暑くならないの素晴らしい！！
たいして点が伸びない。
小さいケースでは僅かに伸びてる。くらいか。
ばらつきあるし、大きいケースでも複数回試行したいところである。
うーん、なんかEC2で動かすと変だ。
不安定な気がする。
何かおかしい・・・やめた方が良いかもなー。
と思ったらmicroはそういうものらしい。
取り直そう。いい感じに動いた。
うーん、今日進捗がないなー。
中央からの距離とか言う、いらんことするのやめたらスコア上がった。ビームサーチパワーですね。
リスト実装し直すくらいは今日中にやっておきたい。
一応書けたけど、当然のように果てた。
よっしゃ動いた。
速くなったのかどうかは分からん・・・。
メモリアクセスが結構ひどそうだから、定期的にreindexしてやるというのも良さそう。
そんなに変わらんよなぁ。
完全に無駄な努力であった。とほほ。
いつの間にか1.015%くらいの改善が出来ていたらしい。4位付近まで来ているのでは。
でもそこで満足していても無理だろうなぁ。
おっと、いつの間にかゔぁしるさんが３位になってる。
うーむ、穴の個数はかなり理想値に近づいているな。
面積の方ノータッチだけど、改善できんかな。
うーん。
とりあえず提出するかー。
面積パートなんか出来んかな。
とりあえず明日は小さいケースで時間をフルで使えるようにする。
6/2(月)
絶望的に馬鹿なことをしていた。
リストじゃなくてええやん。配列に直そう。
得られそうな恩恵は、
・交差判定の高速化
・候補列挙の改善
・座標ベースでの交点列挙
配列化をするにあたって、仕様を整理しよう。(だじゃれ)
・持つ情報は、外周の頂点の座標(向きも持った方が良いだろうか)
・候補列挙の前に、頂点の座標をソートして持っておく
・交差判定は、x座標とy座標でそれぞれ、長方形の範囲に入ってるものだけをチェックする。
・交点の情報は、添字と端点からの距離
・U、Lの個数を数えるのは端点付近だけにするか。
・穴の面積数えるのはどうするか。前処理によって高速化出来そうだけど、とりあえず消そう。
とりあえず、ひととおり配列実装で書き直したつもり。
アルゴリズムはあまり変えてないけど、無駄な操作は結構削れた。
面積要員に使う長方形の選び方を変えたら少し伸びた。
コンパイル通ったー。
makeAreaも通過していい感じに構成できてる。
makeCntでしんでる。
xcodeを縦分割したらそこそこ快適である。（挙動がなんか怪しいけど・・・）
動いたぜ！勝ったな(確信)
速い。
さて、配列実装の威力はこんなもんじゃないよな？
(UとかLとか数えてないのにスコアあんま変わんない気がするウケる。)
ソースコードに愛情が湧いて来た。
chokudaiさんが言ってた「我が子みたいに思えてくる」的なのってこういうことなんかなー。
交差判定若干めんどいー
一時1000行超えてたけど今1000を割ってる。
やった。
提出しよう。
あとは
・ULカウント
・複数回試行
・ビームサーチの幅管理
をやろう。
・候補列挙を磨く
・穴面積カウント
も課題ですかね。
おや、スコアが下がった。
というよりはこれは-1出てるのでは・・・？
特定の条件下で出やすくなる稀な現象だった。
多分直った。
いやまだだった・・・
なんかすごい勢いで配列外参照してるよ。
直したと思っていたところが直ってないとか言う、まじありえんミスで時間を浪費した・・・
あほや。。
Lの個数は減りこそすれ、２個ちょうどしか増えないよね。
Uは０〜２。間にはさんだ時に真ん中に出来るみたいなケースがあるけど、無視で良いかな。
Uの字を無視した方が点数伸びるのだが、なぜだ・・・
Uの字を意識するとふっくらする傾向があるらしい。
あ、そっか。アレを忘れていた。
ふっくらするよりも、うすべったい方がいいらしい。
ああ、Uじゃない何かを判定していた・・・ソリャアカンワ。
明日も早いし今日は寝よう。
あれー、ちゃんと判定したら悪くなった。
薄くなり過ぎてるな。
U字判定しない方が強い・・・
そろそろ切羽詰まってきたなー。
明日は、
・複数回試行
をやる。
・ビームサーチの幅管理
・穴面積カウント
・全体の形状
があとの課題っぽいな。
・丘チェイン
をやってみるのも良いかも知れない。
一時的に４位。
6/3(火)
なんかまだバグってる？よく分からん。
置き方の候補増やしたら点数が微小に増えた。
よく分からないし、あんまり入れたくないなーこれ。
もうちょい評価関数とかをちゃんとしてからにしよう。
評価関数ってずっと言ってるけど、今のところ穴の個数しか評価してないんだよなぁ。
それ以上になにか出来る？
うむ、なんか形状的にはふっくらさせるとかうすべったくするとかより、ある程度の幅で横にズルズル伸ばしていく感じが強いっぽい？
丘チェインと相性良さそう。
なんか、わけの分からんバグが埋まっているような気がする。
くっそ、いらいらする。
少し直った。
上へ上へ行こうとする習性があるのはなぜだろう。
カオスな植物が出来上がったりする・・・
なんだこのプログラム、グレたか・・・
初期化忘れで評価関数がすごいことになってただけだった。
やはり上に向かう習性がある。
統計的にそうなりそうではあるんだけど。
穴を作れなかった回というのは序盤に集中している(当たり前)
うむ、どうしようか。
丘チェインを実験してみよう。
一回の長さはDPで厳密解がそこそこ高速に求まるはず。
穴が作れる手が一定数以上あれば角に置かないとすると微改善した。
改善が良いわけではなくて、スコアが落ちなかったのが素晴らしい。
これは探索順を「１手ずつ」じゃなくて「作れなくなるまでやったときにhoge」とかにすると伸びる予感。
やりたいことが多すぎる。時間が足りないんじゃー
上に向かう習性は修正できた。
うーん、これはさすがにちょっとうさんくさいなー。
うさんくさいのを消そう。
うん。分かりやすくなった。
かつ高速。
モチベが若干回復。
wleiteさんがやっと来た。さすが。
提出したが、あんま変わらん。
割といじって変わらん(ちょっとだけ伸びた)のならまあいいか？
若干遅くなったらしい。
価格の安定しているlargeを選んでいるせいで性能が高すぎるなこれ。
今気付いたんだけど、数えた面積が結果と一致してない。
小さいケースでスコアががくっと落ちてるらしい。
面積、2.5乗和にしたら伸びたぞ。まえもやったはずなんだが。
焦ってイライラしてよくない。
丘チェインはだいたい組めた。
スコアが上がるものもいくつかある。
6/4(水)
最終日である。
ビジュアライズしてみた。
後半は本当にもりもり作れるね。
序盤だと、コの字があるのに長さが足りず塞いでない時とかあって、損している。
・コの字を検出して、それを塞げるものがあればそれを置く。
・ないなら角置き
ビジュアライズを眺めていたけど、
多角形の穴を作る手も候補に入れないとすごいことになるなこれ。
平行する辺を検出して、その間に噛ますという事をすれば良いかな。
これさえすれば、ビーム幅2,3くらいでも悪くないスコアが出ると思う。
なんとなく提出してみたけど、904326.28pts!?
これはまちがいなく0点が大量に出てるとかそういう類の点数だ。
手元やexampleで問題が起こってないあたり、systest環境がstderrに弱いのではないかと推測した。
書いてみたが、なんかうまくいってない。
たまに正しく判定してくれるけど・・・
なんだこれ、stderrのせいではない。
なんだこれ・・・・
意味不明だ・・・
ec2で1000ケース試しても何も起こらんのに。
なんだよこれ。
うむ、原因として考えられるのはもうTLEしかないな。
もう一回出来ると思って打ったらできませんでしたー！みたいな。
夢中になって書くの忘れてた。
多角形も作れるアルゴリズムを組んでひたすらバグと戦っていたけど、スコアむしろ下がったので完全に無駄であった。
最後の方、穴が作れる回は穴が作れるものだけを採用するようにしたら爆速になって、試行回数稼げた。
ビーム幅小さくてもあんまかわんない。
コンテスト後
