WindowsでPython2/3の共存が壊れたらPYTHONHOMEを削除する
Windowsではpyとpy -2でPython2/3の共存ができますが、再インストールやマイナーバージョンのアップグレードなどで以下のように壊れることがあります。
>py
Fatal Python error: Py_Initialize: unable to load the file system codec
File "C:\python27\lib\encodings\__init__.py", line 123
raise CodecRegistryError,\
^
SyntaxError: invalid syntax
Current thread 0x00000e1c (most recent call first):
>py -2
File "C:\Python36\lib\site.py", line 177
file=sys.stderr)
^
SyntaxError: invalid syntax
これらは環境変数のPYTHONHOMEを削除すると直りました。このPYTHONHOMEはPython2/3の両方から参照されるらしく、削除するとそれぞれのデフォルト値が使われうまく動くようになるようです。
もしPythonをデフォルトのパス以外にインストールしている場合、さらに何らかのケアが必要かもしれません。
MM94 ConnectedComponent
問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16958&pm=14678
基本方針
順列の左端Ｎ個が確定しているとすると順列の後ろにどんな値を足しても左上Ｎ×Ｎの領域の値は変わらない。なのでこの確定領域の最良コンポーネントのスコアを途中状態のスコアとできる。
そして現在の順列の後ろに値を足して一番途中スコアが大きくなるような順列を次の状態とするgreedy/beamsearchをすると最良コンポーネントが徐々に大きくなり良い解が得られる。
高速化
途中スコアの愚直な計算はO(S2)であるためgreedyですら終わらないが、新しく足す値によって確定するマス（下図赤マス）と接するマス（下図緑マス）は現確定領域の"外周に限られる"ことを利用して差分計算/更新ができ高速になる。
具体的には緑マスそれぞれをノードとしたUnionFind（各ノードはそのマスが属すコンポーネントのsizeとsumを持つ）を現状態として持つ。次に緑UFを元に緑赤UFを作る。次に連結箇所をuf.unite()。最後に赤だけのUFを作ればそれが次状態になる。このとき連結を調べているのが外周付近だけであるためO(S2)がO(S)に落ちてgreedy/beamsearchが実行時間に収まる。また、UFを舐めればsumとsizeを持っているため最良コンポーネントとそのスコアがわかる。
このUnionFindを使って連結情報を右に右に伝えていくというのはこの問題でも使われてるっぽい。 http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2017%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=H.pdf
ビーム幅
同じseedで繰り返し実行したときのスコアの分散が大きめだったので、ビーム幅の増加によるスコア上昇よりも、細いビーム幅で繰り返したときの当たる確立の上昇のほうが強いと踏んで、ビーム幅1のビームサーチを時間いっぱい繰り返した。だけど1stと2ndは大きなビーム幅で1回ビームサーチらしいので外したっぽい。分散が大きいというのが違うのか、分散が大きいときは～のほうが強いというのが違うのか。
評価関数
最良コンポーネントの近くに他のコンポーネントがあって繋がると大きなスコアのプラスになるとき積極的に繋がりにいきたい。
これを評価関数に加える。他のコンポーネントはsumが大きいほど、sizeが大きいほど、近いほど（繋がりやすいことと連結に近づくため）良いとしたい。なので最良ではないコンポーネントそれぞれに対して、仮に最良コンポーネントと繋がったときのスコアの上昇量にpow(0.9, 最短距離)をかけたものを途中スコアに足した。
文章だとわかりづらいので擬似コード
double maxComponentScore = maxComponent.sum * sqrt(maxComponent.size); double score = maxComponentScore; for (auto& c : nonmaxComponents) { double connectedScore = (maxComponent.sum + c.sum) * sqrt(maxComponent.size + c.size); double diff = connectedScore - maxComponentScore; if (diff > 0) score += diff * pow(0.9, manhattanDistanceNearest(c, maxComponent)); } score; // これがビームサーチの評価値として使われる
1st, 2nd, 3rdまでの評価関数のプラスアルファがバラバラなのおもろい。
山登り
Sがごく小さいときはビームサーチの結果を山登り。ランダム解から登るより、ビームサーチからのほうが良かった。近傍は2つをswapと、1つを別のところにinsert(つまりrotate)の2種類。左上からビームサーチする都合、左上が高密度のコンポーネントができるので左上へのinsertで改善しやすかった。なのでその近傍を先んじて試すようにした。2つの近傍自体に優劣はないと思うんだけど、初期解が影響して優劣が生まれるというのがおもしろかった。
評価関数はO(S2)だがy_kawanoさんがchokudai contest（本問題と似ていて連結数を大きくする問題）で使っていたテクで数倍早くした。自力で思いつける類ではないので感謝
得点計算の高速化はDFSの基点となる位置をキャッシュしたのが効いた #chokudai_003
— y_kawano (@y_kawano) 2017年2月21日
やりたかったけどできなかったこと
非0マスの割合によって連結の容易さがテストケースごとにかなり変わる。最終コンポーネントがスッカスカだったりミッチミチだったり。この特徴に注目して何かヒューリスティクスを刺したかった。
Example scores:
0) 232.826115373684 1) 23147.483599734984 2) 7426823.502824272 3) 121935.2517568238 4) 148933.58515123444 5) 2259336.504998536 6) 733271.118536657 7) 3257617.5326836635 8) 4670802.284891322 9) 1676018.7939363925
Image
seed=2, score=21907 pic.twitter.com/iIdLh9hhtg
— hakomo (@hakomof) 2017年8月24日
seed=3, score=7488480 pic.twitter.com/sYuESDhLFf
— hakomo (@hakomof) 2017年8月24日
seed=7, score=726365 pic.twitter.com/oJEr6GoE1l
— hakomo (@hakomof) 2017年8月24日
TCO17MMR2 AbstractWars
問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16928&pm=14599
ヒューリスティクス的なアイデアが色々考えられて今までで一番好きな問題。
MMおつかれさまでした
— hakomo (@hakomof) 2017年5月25日
ビームサーチで速攻、序盤に奪う基地の探索
中終盤は1000をあふれるなら攻撃、攻撃箇所は最小費用流で決定
ビームサーチと最小費用流の評価関数は敵が同士討ちをしやすいほど良い
勝89.9% 負6.3% 分3.8%
— hakomo (@hakomof) 2017年5月25日
速攻は21.6% 速攻がtomerunさんの半分以下だ・・・
本当はもっとたくさん書いたんだけど長くなったのでがんばったところだけ。
以下抜粋。
敵同士をつぶしあわせる、ビームサーチの評価関数、最小費用流のコスト
自分が攻撃される確率が低いほどよい
初期配置を↓とする。
テキトーに近い敵baseを奪うと↓のようになり、これは敵自入り混じった乱戦になりpowerが不利な自分が負ける。
しかし↓のように敵baseを奪うと敵は距離の近いbaseを攻撃する確率が高いため自分をあまり攻撃せず敵同士でつぶしあってくれる。その間にsizeを着々と貯めれば100の倍数ボーナスで差がつくので勝てる。
このような自分が攻撃される確率が低い（相対的に敵同士でつぶしあいやすい）配置になるように敵を攻撃する。
敵の初撃に耐えるほどよい
序盤、敵baseを奪いすぎるとsizeが小さいため簡単に再奪取されることが多い。これを軽減するために奪えなかった敵base近くの自baseのsizeを大きくしたい。
localityを1.1とすると敵baseが各baseを攻撃する確率は計算できてattackTも決めれば初撃ターン・初撃サイズも求まり、自baseが奪われる確率も計算できる。そこでattackTの値域から均等に3つ583,750,917を選びその平均を初撃に耐える確率としそれが高いほどよいとした。
これで奪いすぎるのを軽減したり、敵baseの近くに壁をつくる効果が期待できる。
ビームサーチの評価関数
ビームサーチの評価関数 = 奪ったbaseの数 - 自分が攻撃される確率の和 - 敵の初撃で奪われる確率の和
狙ったわけではないが、自分が攻撃される確率が長期的な評価値で、敵の初撃で奪われる確率が短期的な評価値で、バランスがよさそう。
攻撃されやすい敵baseを攻撃するのは後回し
↓のような状況のとき上真ん中を奪うと左右からぼこされて再奪取されやすい。
しかし↓のように上右から奪うと真ん中の攻撃は左右に分散しやすく、左の攻撃は真ん中にいきやすい。そのため奪った後も守りやすい。
このように攻撃されやすい敵baseは奪った後も攻撃にさらされやすいので後回しにする。また攻撃されて弱った後なら楽に奪えるという効果もある。
最小費用流のコスト
最小費用流のコスト = 到着時刻 + 50 * -log(その敵baseが自分を攻撃する確率) + 40 * -log(max(1e-9, 1 - その敵baseが他の敵に攻撃される確率の和))
空を飛んでいるtroopはbaseと接触してはじめて効果がでる（敵baseを奪うにしろ、自baseに合流して100の倍数ボーナスを増やすにしろ、敵baseを削って100の倍数ボーナスを減らすにしろ）ので滞空時間、到着時刻は短いほうがよい。ので到着時刻にペナルティを加算した。
Example scores
0) 1700.3533398049744 1) 1806.7049780062375 2) 1978.8025098890039 3) 1962.538169965643 4) 1983.4413356595355 5) 1663.3656903521724 6) 1829.6786713895922 7) 1486.8174209242056 8) 1690.0970680903945 9) 1810.6962420903901
GIF
— hakomo (@hakomof) 2017年5月25日
— hakomo (@hakomof) 2017年5月25日
劣勢のときはまとまった数が残ってるうちに最遠２点間を往復する（これで２０００ターン逃げ切ることもある） pic.twitter.com/7IrIc1I4Fe
— hakomo (@hakomof) 2017年5月25日
Chokudai Contest 3 考えたこと
問題文 A: ○×ブロック - Chokudai Contest 003 | AtCoder
5864点18位でした。
. + -ブロックひとつを異なる種類の. + -ブロックに変えてスコアが上がるようなら保持、下がるようなら元に戻す山登りをした。
遷移でスコアが変わらなくても、連結ブロック数の２乗和が大きくなるときは遷移した（スコアに関係ない連結ブロックが成長したら良さそう）
上下にoとoもしくはxとxで挟まれた空間にはブロックを新設しない方がよさそうだった。連結を分断しやすそうなので。ただ間に合わなかったので確かめてない。
下の方からブロックを変えていくというのを２周した。
ブロックを変更していない列の落下処理はキャッシュして省略することで高速化（差分計算）、元に戻るときの情報を残しておいて元に戻すのを高速化などをして、試行回数は２２万回くらいだった。
ブロックは落下するので下の方にかたよる。なので落下しない-ブロックを上の方に置くのはよくない。なのでそもそも遷移を試さない。
むずかしかったー
MM92 考えたこと
問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16857&pm=14485
MMの方針
— hakomo (@hakomof) 2017年1月19日
誤差ゼロの焼きなましをひたすら高速化。
近傍はライトを１つ動かす。
最後に極近傍山登りで微調整（こちらも誤差ゼロ）
試行回数は１５万回～３５０万回
感想
CutTheRootsに高速化焼きなましって意味で似てるなー、CutTheRootsってたしか最上位厳密スコア求めてるんだよなーこれも厳密スコアかなーで突っ走った結果、近似スコアだったでござる。 初日で方針ミスって、しかも下手に良いスコアとってしまい方針ミスに気付けなかったので次からは気をつけたい。
自分の方針だと色んな箇所に色んな高速化をしていて高速化ゲー（もちろん高速化だけでは厳しいけど）としてはかなり楽しい（そして練習になる）問題だと思いました。（ただこの記事ではほとんど省略されてます）
焼きなまし
近傍はライトを１つ動かす。 焼きなまし序盤はライトを大きく動かして、終盤は小さく動かす。動かす距離は時間の経過とともに指数的に小さくした（試行回数の少なさを補うにはこれが良いと思った）。
壁の近くはすぐにライトがカットされるので良い位置ではないだろうと遷移しないようにしてみたがあまり効果なし。
遷移先に偏りのない605Kでるプログラムでinner_xとinner_y（小数点以下の座標）の分布を見ると、ものっそい偏ってた。
ヒートマップの色はテキトーだけど光源の45%がinner_x == 0 || inner_y == 0だった。おそらくライトの半径が整数で壁も整数刻みなので、inner_x == 0 || inner_y == 0だと壁と壁の間にすっぽりぴったし収まりやすいのだと思われる。なのでinner_x == 0 || inner_y == 0に遷移しやすくしてみたのだけどあまり効果なし（がーん）。
山登り
CutTheRootsしかりTerrainCrossingしかり座標が広い問題は最後に極端に狭い近傍で山登りというのをみなさまやってらっしゃる。のでライトを１つ周囲8dotに動かす山登りを最後にした。
高速化
100dot x 100dot（１セル）をunsigned long long[100][2]の格ビットで表現する。
放射光のビットパターンと円形の光のビットパターンのandビット演算をすれば１つのライトのビットパターンが求まる。ライトとライトのorビット演算をすればライトが重なったビットパターンが求まる。あとはビットの数を数えれば（__builtin_popcountll）厳密なスコアが求まる。
円形の光のビットパターンは事前に計算して持ってくる。
放射光のビットパターンは、 まず、放射光の境界線の角度が、光源から外に向かって貰うＤＰで求まる。 次に、境界線の角度と光源の座標から境界線の直線の式が求まる。 そして、直線の式に求めたいビット列のy座標を代入すれば何ビット目から何ビット目まで立ってるかがわかるのでビット列を求める。
他の（でも重要な）高速化
あるセルをあるライトが完全に照らしているとき、他のライトの処理の省略、代替、遅延、枝刈による高速化（これが重要だけど説明できず）。
壁による遮蔽なしライトの重なりなしなセルのスコアは２次元累積和でO(1)で求まる。
差分計算もしてます（これも重要だけど説明できず）。
Codeforces Marathon Round1 Online Exam
問題文 http://codeforces.com/contest/684/problem/A2
タイトルのマラソンで考えたことが書いてあります。過程を書いたので長いです。
暫定スコアは７７２６１点、暫定順位は３位でした！がんばった！
６９０００点
２つのアイデアが必要でした。
１．ビット区間を反転してスコアが下がったら戻す
テキトーなビット列をクエリに投げてスコアを確認します。
１．そのビット列の一部を反転したものをクエリに投げます。
２．その結果、スコアが上がればビット列は反転したまま、スコアが下がればビット列を元に戻します。
１．２．をくりかえせばスコアは上がり続けます。
ではどんな一部を反転すればよいでしょうか。
１回のクエリで反転するビットの数は際限なく多いほうがよいです。
１つのビットを反転させたときのスコアの改善は高々１
２つのビット～は高々２
３つのビット～は高々３
．．．と反転するビットの数が多いほどスコアの改善が大きいことが期待できます。
また、スコア番目以降のビットを反転してもスコアは変わりません。つまり情報がとれない。そして初期スコアはＫ＊２の４０００前後で、クエリごとに上がるので４０００ちょっとのビットから情報がとれます。
また、最初のクエリは初期ビット列のスコアの確認に使いますし、最後のクエリの結果を元にさらにクエリを投げることもできません。なので使えるクエリの数は９８で、めいっぱい使います。
また、同じビットを何度も調べるのは意味がない（一度調べて改善したビットを反転しても半分以上の確率でスコアが下がるため）のでクエリごとに反転するビットは重複しないほうがよさそうです。
以上より４０００ちょっとのビット列を等しく９８分割してクエリごとに順番に反転するという方針が立ちます。 4000 / 98 = 40.8... なので長さ４１のビット区間×９８あたりのスコアが一番よくなります。
２．クエリの結果－１番目のビットは確実に誤答
左端から順番に採点して誤答の数がＫになったら即座に終了ですから当然直前のビットは必ず誤答です。
この誤答はクエリを投げた直後に正し、以降このビットは不変としたほうがよいです。というのも正さずに放っておくと以降のクエリでこのビットが間違ってるやで～とまた言われてしまうので（間違っていることはすでにわかっているのでもったいない）。
１つのビットを正したときのスコアの上昇期待値は＋２ です。１つのビットを正しているので確実に＋１され、次のビットも正しければ＋２、その次のビットも正しければ＋３と続きます。次以降のビットが正しい確率は半分なので 1 * 0.5 + 2 * 0.25 + 3 * 0.125 + 4 * 0.0625 ... = 2 になります。＋２点×９９クエリ×１００ケースで１９８００点くらい上がります。
上述のビット区間の反転と組み合わせるときにずれるので補正します。
１．あるビット列のクエリを投げて古いスコアをゲット
２．確実な誤答を正す
３．ビット区間を反転してクエリを投げて新しいスコアをゲット。新しいスコアと古いスコアを比較
このとき古いスコアは確実な誤答を正す前のスコアなのでその分ずれます。じゃあ期待値分＋２すればよいかというと＋１．３３３くらいがよいようです。たいていは＋１か＋２のどちらかだからだと思います。
また、上述のビット区間の反転とこれが重なってしまうのももったいないです。上述のビット区間の反転の全体の範囲が４０００ちょっとが最適なのは（もっと広くてもよさげなのに）これが効いてるやも。んで、できるだけ重ならないようにするには速やかにビット列のスコアを４２００くらいまで上げればよい、これはビット列をクエリごとに改善してれば十分か。あるクエリであるビット区間を反転したほうがスコアが上がることがわかったときに、あえて反転せずにためてためて最後のクエリでどばっと反転させてどばっとスコアを上げるテク（後述）を使ったときにやりすぎて（１～９９クエリ目でほとんどスコアを上げなかったときに）死んだ。
この２つをやると６９３００点くらい出ました。
７４０００点
６９０００点の時点で７５０００点の人がいたのでその差を考えると１ケース６０ビットの差があり、これは１クエリや２クエリの差ではないことがわかります。毎クエリやっていることが違う、毎クエリもっとたくさんの情報が得られると考えました。
そこでクエリを観察するとスコアが大きく変わるときと小さく変わるときがあります。この大きく変わるときとは正誤が偏っている（めっちゃ当たってるかめっちゃ外れてる）ということです。そして小さく変わるときは正誤が半分ずつに近いということです。
このことよりスコアの変化量から正誤の偏りが推定できます。正誤の偏りはずばりそのビット区間の改善の余地を意味します。偏りが小さいほど改善の余地が大きいです。たとえば長さ１００のビット区間のうち９０が当たっているときはあと１０しか改善できませんし、９０が外れているときは反転すれば９０が当たっているときと同じですし、長さ１００のビット区間のうち５０が当たっているときは５０も改善の余地があります。
そこで改善の余地が大きい偏りが小さいビット区間に優先的にクエリを投げるとよさそうということがわかります。あるビット区間にクエリを投げるべきかどうかはある区間を含むより広い区間の偏りがわかっていないといけない、つまりそのより広い区間にクエリが投げられていないといけないです。
そこでこのようなクエリが考えられます。
誤答率というのは正誤の偏りの言い換えです、同じことを言っています。んでこのクエリの投げ方は以下のクエリの投げ方と同じクエリ数で同じ情報量が得られます。つまりその情報群から最適な戦略をとったきにまったく同じスコアになります（誤差を無視すれば）。
この２つのクエリの投げ方からは同じ情報量が得られ、相互に入れ替えが可能です。ここで６９０００点解法を思い出してみます。４０００ビットを９８分割して等間隔にクエリを投げていましたね。
これを
こうして
こうして
こうじゃ！
なんか Binary Indexed Tree っぽいな？ BIT 違いですあんまり関係ないです。これはまだ等価な置き換えをしただけなのでスコアは変わりません。ここで改善の余地が大きい偏りが小さいビット区間に優先的にクエリを投げるように変えます。
投げているクエリの数（赤線の数）が変わっていないこと、ビット区間を仕切る黒縦線がばらついているのに注目してください。これで同じクエリの数で改善の余地が少ないビットへのクエリを節約して、改善の余地の大きいビットにたくさんクエリを投げれています。
これを実装すれば７４０００点が・・・出ません。誤差が大きくなりすぎます。このマラソンは誤差との壮絶な戦いでした。この誤差マラソン中にやってよかったことは誤差を無視したらどうなるのかを常に意識するとです。それは正解ビット列をカンニングしながら推定値を使うところをすべて真値を使うプログラムを書くことです。これをすると実装がバグってるのか誤差が大きすぎるかの切り分けができる、誤差０のときのスコアつまり誤差に対する上界がわかる、上界を元に１位に届くか判断できる、誤差でどのぐらいスコアが下がっているのかがわかるです。
でまあ以上のようなことをやって上界が７８０００点（１位オーバー）ですが誤差ありでは７１０００点くらいしかでず誤差が大きいことがわかりました。そこで誤差を小さくできれば１位に届くと思い、誤差が大きい箇所を調べました。誤差が大きい箇所は３つでした。
１．広いビット区間の反転は誤差が大きい
さっき述べましたがたくさんビットを反転するとスコアの変化量が大きいのでそれにともない誤差も大きくなります。広いビット区間のクエリは控えたいですね。
２．区間ＡＣの誤答率と区間ＡＢの誤答率から区間ＢＣの誤答率を算出推定するときに誤差が累積する。
クエリ値からの推定は１次ソースなので誤差は常に一定値以下ですが区間と区間から区間の誤答率を求めるたびに誤差が累積します。ビット区間が狭くなるほど深くなるほど誤差が大きくなります。あまり深くしなければよさそうですね。
３．区間ＢＣの誤答率がわかった時点で区間ＢＣを反転した方がスコアが上がるかどうかがわかりますがこれを即時反転してしまうと誤差る
少し前に後述って言ってたやつです。わかった時点で反転してスコアを改善してしまうとスコアの上昇量を推定しないといけなくなり誤差がでます。反転したほうがスコアが上がるという情報を覚えておいて最後のクエリの直前にまとめて反転すると誤差を０にできます。
１．２．より長さ８８の区間４６個を初期ビット区間集合として深さを３に制限する。３．をやる。パラメーター調整をする。これで７４０００点がでました。上界が７８０００点なので軽減したとはいえ結構誤差がのこってます。
７７０００点
誤差は限界まで小さくしたので他に何か問題がないか考えてます。反転するビット区間が広すぎると誤差が大きすぎてよくないことがわかりました。逆に狭すぎるとスコアの変化量が小さすぎるのでよくないこともわかっています。
このことから誤差が大きすぎず（長さが広すぎず）、スコアの変化量が小さすぎない（長さが小さすぎない）最適なビット区間の長さがあるのではと考えました。７４０００点解法は広い区間から徐々に狭い区間に狭めていくという解法でこの考察が正しいとするとよくないですね。なんとかしたい。
そこで広い区間を狭い２つの区間に分割した後にもう一度統合すれば最適な区間の長さを保持できるのではと考えました。ここで統合という概念がでてきたのでここからは区間（連続している）という表現は正しくなくなったので以降ビット部分列という表現に変わります。
問題はどのビット部分列と部分列を統合するかです。これは誤答率ができるだけ近しい部分列と部分列を統合するのがよいです。理由は情報量の減少が小さいから。たとえば誤答率が１０％の部分列と９０％の部分列を統合してしまうと誤答率が５０％になり情報がうすまってしまいます。
以上のことから偏りが小さく、かつ誤答率が近しい部分列を２つ選んで統合、分割して片方のビットを反転してクエリを投げるというのを繰り返すと改善の余地が大きいところを集中的に最適な長さのビット部分列で殴り続けられるので７６０００点がでました。
あとパラメーター調整とかヒューリティスとか誤差を小さくしたりあやしげな工夫をいろいろして７７０００点がでました。
リファクタしまくってたら１００行くらいになった。
#include <algorithm> #include <iostream> #include <vector> using namespace std; const int N = 5000, K = 2000, X = 100; bool a[N + 1]; bool b[N + 1]; void invert(const vector<int>& v) { for (int i : v) { if (!b[i]) a[i] = !a[i]; } } int query(double prev, const vector<int>& v) { invert(v); for (int i = 0; i < N; ++i) cout << (int)a[i]; cout << endl; cout.flush(); int p; cin >> p; a[p - 1] = !a[p - 1]; b[p - 1] = true; if (p < prev) invert(v); return p; } struct S { vector<int> v; double w; double score(const S& s, int t) const { return s.w - w + abs(s.w + w - v.size()) * (t < 3 ? 0.74 : t < 9 ? 0.5 : 0.3); } bool operator < (const S& s) const { return w < s.w; } }; int main() { const int NUM = 42; const int LEN = 98; const int LEN2 = LEN / 2; const int Q = 3954; const double P = 1.34; const double DIFF = 4.8; vector<int> v; for (int i = 0; i < N; ++i) v.emplace_back(i); int p = query(K * 2, v); double prev = (p < Q ? query(0, vector<int>()) : max(p, K * 4 - p)) + P; S q[NUM]; for (int i = 0; i < NUM; ++i) { for (int j = i * LEN; j < (i + 1) * LEN; ++j) q[i].v.emplace_back(j); int p = query(prev, q[i].v); q[i].w = LEN2 - abs(p - prev) / DIFF; prev = min<double>(max(prev + P, p + P), N); } for (int t = X - (p < Q) - NUM - 3; t; --t) { sort(q, q + NUM); S* s = q; for (int i = 2; i < NUM; ++i) { if (s[0].score(s[1], t) > q[i - 1].score(q[i], t)) s = q + i - 1; } S ns[2]; for (int i = 0; i < LEN * 2; ++i) ns[i < LEN].v.emplace_back(s[i % 2].v[i / 2]); int p = query(prev, ns[0].v); double diff = p - prev; for (int i = min(p, (int)prev); i < max(p - 1.0, prev); ++i) diff += b[i] && (p > prev ? -1 : 1); ns[0].w = LEN2 - abs(diff) / DIFF; ns[1].w = s[0].w + s[1].w - LEN2 - diff / DIFF; s[0] = ns[0]; s[1] = ns[1]; prev = min<double>(max(prev + P, p + P), N); } auto& s = *min_element(q, q + NUM, [LEN2](const S& a, const S& b) { return abs(a.w - LEN2) < abs(b.w - LEN2); }); p = query(prev, vector<int>(s.v.begin(), s.v.begin() + LEN2)); if (s.w - (p - prev) / DIFF > LEN2) invert(vector<int>(s.v.begin() + LEN2, s.v.end())); s.w = 0; for (auto& s : q) { if (s.w > LEN2) invert(s.v); } query(0, vector<int>()); return 0; }
MM89 考えたこと
マラソン参加３回目、がっつり参加したのは初めてだけれど楽しかったです。
暫定 72.34点 15位 Python
問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16494&pm=10967
全部Ｓにしたら１００％になるよねーと思って上からＳＥ以外をＳにする。
３８点
初期解（ランダム解）でなぜ迷路がほとんどできないのか考えてみる。
境界からスタートしてランダムに動いてもその場からあまり動かない。迷路の中心に向かう力がない。大きな迷路ができにくい。
ビジュアライザを無効なパスを表示するように変えてみる。
Ｕに突っ込んでる。Ｕを変えればよい。
くるっと回転して自分のパスに突っ込んでる。回転しなければよい。直進すればよい？やっぱりＳが強い？
直進すれば迷路の中心に向かって迷路が大きくなり、回転して死ぬこともなくなる？
紙にいろいろ書いて思いつく。
ＬとＲが交互に並ぶようなライン（間にＳやＥはあってもよい）はどこから進入しても下から入れば上へ、上から入れば下へ抜ける。蛇行しながら直進する。
このラインを下端から上端まで積めば下端から上端、上端から下端へ抜ける迷路がたくさんできる。
このＬとＲが交互になるような修正をＸ座標が小さい順にＦ個とる。
６４点
ここでかなり迷走したので数多のソースが生まれそして死んでいった。
複数の迷路が密に重なっているのがよくないのではと思った。
複数の迷路で修正を共有しているのはメリットだけれど、マスを共有しているのはデメリットなのでトータル損してそう。もっと高効率な迷路をばらけさせたい。
ＬとＲが交互になるような修正を全体にしたうえで有効な迷路を列挙する。
厳密に列挙すると指数時間になってしまうので、上左右の移動だけ、下左右の移動だけでできる迷路を列挙する。列挙漏れはＥがからむときだけなので見なかったことにする。この制限でメモ化ができるようになってるはずなんだけど今自分の実装見るとしてない。あれ？
で、列挙した迷路をＦを超えない範囲で近似スコアが最大になるように選択する組み合わせ問題になった。
最初ＤＰしようとしたけどマスが共有されているのでできなんだ。
迷路ごとのマス数／修正数が大きい順にＦを超えない範囲で選んでいく（貪欲）。
７１点
選択した迷路をひとつのぞいて別の迷路を選択して近似スコアが上がれば採用（山登り）。
７２点
焼きなまそうと思ったけどよくわからず。
おわり
その他
方針さえあってれば Python でも探索時間減るだけやし上位狙わなければへーきへーきと思ったけど全然きつい。終わる前提の処理が終わらない終わらない。配列使いまわしたり、boolの２次元配列を整数の１次元配列に圧縮したり、なくなく迷路集合カットするなどした。
ＬとＲを交互にするというアイデアに固執しすぎた感。マラソン終わるまで現解法の発展が上位の解法だと信じて疑わなかった。反省。
ＥとＥを優先的につなぐように修正してみたけど微増だったのでやめた。テストケースごとのスコアは大きく上下するのがたまにある感じでＷＨＦに特徴がみられなかった。今思うとＥの割合とかもっとよく見ればよかった。平均じゃなくてＦが多いとか少ないとか個々のテストケース見るの大事。
結局乱数使わなかったんだけどこれでいいのか。
Python 240 行
from copy import deepcopy from itertools import compress, count, product, starmap from time import time class MazeFixing: def improve(self, maze, F): reverse = len(maze[0]) < len(maze) if reverse: maze = transpose(maze) else: maze = list(map(list, maze)) fixes = createFixes(maze) paths = createPaths(maze, F, fixes) pair = climb(maze, F, paths, *greed(maze, F, paths)) pair.fixed.i = -1 fixes = [(y, x, fixes[y][x]) for y in range(len(maze)) for x in range(len(maze[0])) if maze[y][x] is not '.' and pair.fixed.get()] if reverse: fixes = ((y, x, dest) for x, y, dest in fixes) return list(starmap('{} {} {}'.format, fixes)) def transpose(maze): return list(map(list, zip(*maze))) def createFixes(maze): fixes = [[''] * len(maze[0]) for _ in range(len(maze))] ux = -1 for y, line in enumerate(maze): for x, cell in enumerate(line): if cell in '.LRE': if ux >= 0: if left is cell is 'L': line[ux] = 'R' fixes[y][ux] = 'R' elif left is cell is 'R': line[ux] = 'L' fixes[y][ux] = 'L' else: line[ux] = 'S' fixes[y][ux] = 'S' ux = -1 left = cell elif cell is 'U': if ux >= 0: line[ux] = 'S' fixes[y][ux] = 'S' ux = x xs = [] for y, line in enumerate(maze): for x, cell in enumerate(line): if cell in '.E' or cell in 'LR' and xs and cell is not line[xs[0]]: for i in xs[1:-1:2]: line[i] = 'R' if line[i] is 'L' else 'L' fixes[y][i] = line[i] if xs and not len(xs) % 2: line[xs[-1]] = 'S' fixes[y][xs[-1]] = 'S' xs = [] if cell in 'LR': xs.append(x) return fixes def createPaths(maze, F, fixes): width = len(maze[0]) height = len(maze) paths = [] visited = [[False] * width for _ in range(height)] fixed = deepcopy(visited) for y, x, d in product(range(height), range(width), (1, 3)): if maze[y][x] is not '.' and maze[y + dy[d]][x + dx[d]] is '.': search(maze, fixes, visited, fixed, x, y, (d + 2) % 4, d) path = BoolsPair((width - 2) * (height - 2)) for i, j in product(range(height), range(width)): if maze[i][j] is not '.': path.append(visited[i][j], fixed[i][j]) visited[i][j] = False fixed[i][j] = False if any(path.fixed.a): paths.append(path) return paths def search(maze, fixes, visited, fixed, x, y, d, b): if maze[y][x] is '.': return d is (b + 2) % 4 for i in range(4) if maze[y][x] is 'E' else [ (d + 'SRUL'.index(maze[y][x])) % 4]: if not (i is b or i is (d + 2) % 4): visited[y][x] = search(maze, fixes, visited, fixed, x + dx[i], y + dy[i], i, b) or visited[y][x] if visited[y][x]: fixed[y][x] = bool(fixes[y][x]) return visited[y][x] def greed(maze, F, paths): src = BoolsPair((len(maze[0]) - 2) * (len(maze) - 2)) dest = deepcopy(src) mx = deepcopy(src) compressed = [True] * len(paths) while any(compressed): mx.visited.count = 0 mx.fixed.count = 1 for i, path in compress(enumerate(paths), compressed): dest.merge(src, path) if src.visited.count == dest.visited.count or dest.fixed.count > F: compressed[i] = None elif (mx.visited.count / mx.fixed.count < dest.visited.count / dest.fixed.count): mxI = i mx, dest = dest, mx if any(compressed): compressed[mxI] = False src, mx = mx, src return src, [c is False for c in compressed] def climb(maze, F, paths, mx, mxAdded): timer.limit = 8 while True: updated = False added = mxAdded[:] for i in compress(range(len(added)), added): if timer.elapses(): return mx added[i] = False src = BoolsPair((len(maze[0]) - 2) * (len(maze) - 2)) dest = deepcopy(src) for path in compress(paths, added): src.merge(src, path) for j, path in enumerate(paths): if not (i == j or added[j]): dest.merge(src, path) if (dest.fixed.count <= F and mx.visited.count < dest.visited.count): updated = True mx, dest = dest, mx mxAdded[i] = False mxAdded[j] = True added[i] = True if not updated: break return mx class BoolsPair: def __init__(self, n): self.visited = Bools(n) self.fixed = Bools(n) def append(self, visited, fixed): self.visited.append(visited) self.fixed.append(fixed) def merge(self, a, b): self.visited.merge(a.visited, b.visited) self.fixed.merge(a.fixed, b.fixed) def copy(self, a): self.visited.copy(a.visited) self.fixed.copy(a.fixed) class Bools: def __init__(self, n): self.a = [0] * ((n + 62) // 63) self.i = 0 self.count = 0 def append(self, v): self.a[self.i // 63] = self.a[self.i // 63] | v << self.i % 63 self.i += 1 def merge(self, a, b): self.count = 0 for i, a, b in zip(count(), a.a, b.a): self.a[i] = a | b self.count += bin(self.a[i]).count('1') def copy(self, a): self.count = a.count for i, a in enumerate(a.a): self.a[i] = a def get(self): self.i += 1 return self.a[self.i // 63] >> self.i % 63 & 1 class Timer: def __init__(self): self.start = time() def elapses(self): return time() - self.start > self.limit dx = 1, 0, -1, 0 dy = 0, 1, 0, -1 timer = Timer() # maze = [raw_input() for _ in range(int(raw_input()))] # F = int(raw_input()) # ret = MazeFixing().improve(maze, F) # print(len(ret)) # print('\n'.join(ret))
