びったんびったん

ユーザビリティ・プログラミングについて。

MM94 ConnectedComponent

問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16958&pm=14678

基本方針

順列の左端N個が確定しているとすると順列の後ろにどんな値を足しても左上N×Nの領域の値は変わらない。なのでこの確定領域の最良コンポーネントのスコアを途中状態のスコアとできる。

f:id:hakomof:20170824194351p:plain

そして現在の順列の後ろに値を足して一番途中スコアが大きくなるような順列を次の状態とするgreedy/beamsearchをすると最良コンポーネントが徐々に大きくなり良い解が得られる。

高速化

途中スコアの愚直な計算はO(S2)であるためgreedyですら終わらないが、新しく足す値によって確定するマス(下図赤マス)と接するマス(下図緑マス)は現確定領域の"外周に限られる"ことを利用して差分計算/更新ができ高速になる。

f:id:hakomof:20170824194401p:plain

具体的には緑マスそれぞれをノードとした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回ビームサーチらしいので外したっぽい。分散が大きいというのが違うのか、分散が大きいときは~のほうが強いというのが違うのか。

評価関数

最良コンポーネントの近くに他のコンポーネントがあって繋がると大きなスコアのプラスになるとき積極的に繋がりにいきたい。

f:id:hakomof:20170824194416p:plain

これを評価関数に加える。他のコンポーネントは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(本問題と似ていて連結数を大きくする問題)で使っていたテクで数倍早くした。自力で思いつける類ではないので感謝

やりたかったけどできなかったこと

非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

TCO17MMR2 AbstractWars

問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16928&pm=14599

ヒューリスティクス的なアイデアが色々考えられて今までで一番好きな問題。

本当はもっとたくさん書いたんだけど長くなったのでがんばったところだけ。
以下抜粋。

敵同士をつぶしあわせる、ビームサーチの評価関数、最小費用流のコスト

自分が攻撃される確率が低いほどよい

初期配置を↓とする。

f:id:hakomof:20170525230804p:plain

テキトーに近い敵baseを奪うと↓のようになり、これは敵自入り混じった乱戦になりpowerが不利な自分が負ける。

f:id:hakomof:20170525230818p:plain

しかし↓のように敵baseを奪うと敵は距離の近いbaseを攻撃する確率が高いため自分をあまり攻撃せず敵同士でつぶしあってくれる。その間にsizeを着々と貯めれば100の倍数ボーナスで差がつくので勝てる。

f:id:hakomof:20170525230836p:plain

このような自分が攻撃される確率が低い(相対的に敵同士でつぶしあいやすい)配置になるように敵を攻撃する。

敵の初撃に耐えるほどよい

序盤、敵baseを奪いすぎるとsizeが小さいため簡単に再奪取されることが多い。これを軽減するために奪えなかった敵base近くの自baseのsizeを大きくしたい。

f:id:hakomof:20170525230847p:plain

localityを1.1とすると敵baseが各baseを攻撃する確率は計算できてattackTも決めれば初撃ターン・初撃サイズも求まり、自baseが奪われる確率も計算できる。そこでattackTの値域から均等に3つ583,750,917を選びその平均を初撃に耐える確率としそれが高いほどよいとした。

これで奪いすぎるのを軽減したり、敵baseの近くに壁をつくる効果が期待できる。

ビームサーチの評価関数

ビームサーチの評価関数 = 奪ったbaseの数 - 自分が攻撃される確率の和 - 敵の初撃で奪われる確率の和

狙ったわけではないが、自分が攻撃される確率が長期的な評価値で、敵の初撃で奪われる確率が短期的な評価値で、バランスがよさそう。

攻撃されやすい敵baseを攻撃するのは後回し

↓のような状況のとき上真ん中を奪うと左右からぼこされて再奪取されやすい。

f:id:hakomof:20170525230857p:plain

しかし↓のように上右から奪うと真ん中の攻撃は左右に分散しやすく、左の攻撃は真ん中にいきやすい。そのため奪った後も守りやすい。

f:id:hakomof:20170525230902p:plain

このように攻撃されやすい敵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

Chokudai Contest 3 考えたこと

問題文 A: ○×ブロック - Chokudai Contest 003 | AtCoder

5864点18位でした。

. + -ブロックひとつを異なる種類の. + -ブロックに変えてスコアが上がるようなら保持、下がるようなら元に戻す山登りをした。

遷移でスコアが変わらなくても、連結ブロック数の2乗和が大きくなるときは遷移した(スコアに関係ない連結ブロックが成長したら良さそう)

上下にooもしくはxxで挟まれた空間にはブロックを新設しない方がよさそうだった。連結を分断しやすそうなので。ただ間に合わなかったので確かめてない。

下の方からブロックを変えていくというのを2周した。

ブロックを変更していない列の落下処理はキャッシュして省略することで高速化(差分計算)、元に戻るときの情報を残しておいて元に戻すのを高速化などをして、試行回数は22万回くらいだった。

ブロックは落下するので下の方にかたよる。なので落下しない-ブロックを上の方に置くのはよくない。なのでそもそも遷移を試さない。

むずかしかったー

MM92 考えたこと

問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16857&pm=14485

感想

CutTheRootsに高速化焼きなましって意味で似てるなー、CutTheRootsってたしか最上位厳密スコア求めてるんだよなーこれも厳密スコアかなーで突っ走った結果、近似スコアだったでござる。 初日で方針ミスって、しかも下手に良いスコアとってしまい方針ミスに気付けなかったので次からは気をつけたい。

自分の方針だと色んな箇所に色んな高速化をしていて高速化ゲー(もちろん高速化だけでは厳しいけど)としてはかなり楽しい(そして練習になる)問題だと思いました。(ただこの記事ではほとんど省略されてます)

焼きなまし

近傍はライトを1つ動かす。 焼きなまし序盤はライトを大きく動かして、終盤は小さく動かす。動かす距離は時間の経過とともに指数的に小さくした(試行回数の少なさを補うにはこれが良いと思った)。


壁の近くはすぐにライトがカットされるので良い位置ではないだろうと遷移しないようにしてみたがあまり効果なし。


遷移先に偏りのない605Kでるプログラムでinner_xとinner_y(小数点以下の座標)の分布を見ると、ものっそい偏ってた。

f:id:hakomof:20170119224502p:plain

ヒートマップの色はテキトーだけど光源の45%がinner_x == 0 || inner_y == 0だった。おそらくライトの半径が整数で壁も整数刻みなので、inner_x == 0 || inner_y == 0だと壁と壁の間にすっぽりぴったし収まりやすいのだと思われる。なのでinner_x == 0 || inner_y == 0に遷移しやすくしてみたのだけどあまり効果なし(がーん)。

山登り

CutTheRootsしかりTerrainCrossingしかり座標が広い問題は最後に極端に狭い近傍で山登りというのをみなさまやってらっしゃる。のでライトを1つ周囲8dotに動かす山登りを最後にした。

高速化

100dot x 100dot(1セル)をunsigned long long[100][2]の格ビットで表現する。

f:id:hakomof:20170119224504p:plain

放射光のビットパターンと円形の光のビットパターンのandビット演算をすれば1つのライトのビットパターンが求まる。ライトとライトのorビット演算をすればライトが重なったビットパターンが求まる。あとはビットの数を数えれば(__builtin_popcountll)厳密なスコアが求まる。

f:id:hakomof:20170119224506p:plain

円形の光のビットパターンは事前に計算して持ってくる。

放射光のビットパターンは、 まず、放射光の境界線の角度が、光源から外に向かって貰うDPで求まる。 次に、境界線の角度と光源の座標から境界線の直線の式が求まる。 そして、直線の式に求めたいビット列のy座標を代入すれば何ビット目から何ビット目まで立ってるかがわかるのでビット列を求める。

他の(でも重要な)高速化

あるセルをあるライトが完全に照らしているとき、他のライトの処理の省略、代替、遅延、枝刈による高速化(これが重要だけど説明できず)。

壁による遮蔽なしライトの重なりなしなセルのスコアは2次元累積和でO(1)で求まる。

差分計算もしてます(これも重要だけど説明できず)。

Codeforces Marathon Round1 Online Exam

問題文 http://codeforces.com/contest/684/problem/A2

タイトルのマラソンで考えたことが書いてあります。過程を書いたので長いです。
暫定スコアは77261点、暫定順位は3位でした!がんばった!

69000点

2つのアイデアが必要でした。

1.ビット区間を反転してスコアが下がったら戻す

テキトーなビット列をクエリに投げてスコアを確認します。
1.そのビット列の一部を反転したものをクエリに投げます。
2.その結果、スコアが上がればビット列は反転したまま、スコアが下がればビット列を元に戻します。
1.2.をくりかえせばスコアは上がり続けます。

ではどんな一部を反転すればよいでしょうか。

1回のクエリで反転するビットの数は際限なく多いほうがよいです。
1つのビットを反転させたときのスコアの改善は高々1
2つのビット~は高々2
3つのビット~は高々3
...と反転するビットの数が多いほどスコアの改善が大きいことが期待できます。

また、スコア番目以降のビットを反転してもスコアは変わりません。つまり情報がとれない。そして初期スコアはK*2の4000前後で、クエリごとに上がるので4000ちょっとのビットから情報がとれます

また、最初のクエリは初期ビット列のスコアの確認に使いますし、最後のクエリの結果を元にさらにクエリを投げることもできません。なので使えるクエリの数は98で、めいっぱい使います。

また、同じビットを何度も調べるのは意味がない(一度調べて改善したビットを反転しても半分以上の確率でスコアが下がるため)のでクエリごとに反転するビットは重複しないほうがよさそうです。

以上より4000ちょっとのビット列を等しく98分割してクエリごとに順番に反転するという方針が立ちます。 4000 / 98 = 40.8... なので長さ41のビット区間×98あたりのスコアが一番よくなります。

f:id:hakomof:20160622203717p:plain

2.クエリの結果-1番目のビットは確実に誤答

左端から順番に採点して誤答の数がKになったら即座に終了ですから当然直前のビットは必ず誤答です。

この誤答はクエリを投げた直後に正し、以降このビットは不変としたほうがよいです。というのも正さずに放っておくと以降のクエリでこのビットが間違ってるやで~とまた言われてしまうので(間違っていることはすでにわかっているのでもったいない)。

1つのビットを正したときのスコアの上昇期待値は+2 です。1つのビットを正しているので確実に+1され、次のビットも正しければ+2、その次のビットも正しければ+3と続きます。次以降のビットが正しい確率は半分なので 1 * 0.5 + 2 * 0.25 + 3 * 0.125 + 4 * 0.0625 ... = 2 になります。+2点×99クエリ×100ケースで19800点くらい上がります。

上述のビット区間の反転と組み合わせるときにずれるので補正します。
1.あるビット列のクエリを投げて古いスコアをゲット
2.確実な誤答を正す
3.ビット区間を反転してクエリを投げて新しいスコアをゲット。新しいスコアと古いスコアを比較
このとき古いスコアは確実な誤答を正す前のスコアなのでその分ずれます。じゃあ期待値分+2すればよいかというと+1.333くらいがよいようです。たいていは+1か+2のどちらかだからだと思います。

また、上述のビット区間の反転とこれが重なってしまうのももったいないです。上述のビット区間の反転の全体の範囲が4000ちょっとが最適なのは(もっと広くてもよさげなのに)これが効いてるやも。んで、できるだけ重ならないようにするには速やかにビット列のスコアを4200くらいまで上げればよい、これはビット列をクエリごとに改善してれば十分か。あるクエリであるビット区間を反転したほうがスコアが上がることがわかったときに、あえて反転せずにためてためて最後のクエリでどばっと反転させてどばっとスコアを上げるテク(後述)を使ったときにやりすぎて(1~99クエリ目でほとんどスコアを上げなかったときに)死んだ。


この2つをやると69300点くらい出ました。

74000点

69000点の時点で75000点の人がいたのでその差を考えると1ケース60ビットの差があり、これは1クエリや2クエリの差ではないことがわかります。毎クエリやっていることが違う、毎クエリもっとたくさんの情報が得られると考えました。

そこでクエリを観察するとスコアが大きく変わるときと小さく変わるときがあります。この大きく変わるときとは正誤が偏っている(めっちゃ当たってるかめっちゃ外れてる)ということです。そして小さく変わるときは正誤が半分ずつに近いということです。

f:id:hakomof:20160622222459p:plain

このことよりスコアの変化量から正誤の偏りが推定できます正誤の偏りはずばりそのビット区間の改善の余地を意味します。偏りが小さいほど改善の余地が大きいです。たとえば長さ100のビット区間のうち90が当たっているときはあと10しか改善できませんし、90が外れているときは反転すれば90が当たっているときと同じですし、長さ100のビット区間のうち50が当たっているときは50も改善の余地があります。

そこで改善の余地が大きい偏りが小さいビット区間に優先的にクエリを投げるとよさそうということがわかります。あるビット区間にクエリを投げるべきかどうかはある区間を含むより広い区間の偏りがわかっていないといけない、つまりそのより広い区間にクエリが投げられていないといけないです。

そこでこのようなクエリが考えられます。

f:id:hakomof:20160622222501p:plain

誤答率というのは正誤の偏りの言い換えです、同じことを言っています。んでこのクエリの投げ方は以下のクエリの投げ方と同じクエリ数で同じ情報量が得られます。つまりその情報群から最適な戦略をとったきにまったく同じスコアになります(誤差を無視すれば)。

f:id:hakomof:20160622222504p:plain

この2つのクエリの投げ方からは同じ情報量が得られ、相互に入れ替えが可能です。ここで69000点解法を思い出してみます。4000ビットを98分割して等間隔にクエリを投げていましたね。

これを

f:id:hakomof:20160622222505p:plain

こうして

f:id:hakomof:20160622222508p:plain

こうして

f:id:hakomof:20160622222509p:plain

こうじゃ!

f:id:hakomof:20160622222510p:plain

なんか Binary Indexed Tree っぽいな? BIT 違いですあんまり関係ないです。これはまだ等価な置き換えをしただけなのでスコアは変わりません。ここで改善の余地が大きい偏りが小さいビット区間に優先的にクエリを投げるように変えます。

f:id:hakomof:20160622222458p:plain

投げているクエリの数(赤線の数)が変わっていないこと、ビット区間を仕切る黒縦線がばらついているのに注目してください。これで同じクエリの数で改善の余地が少ないビットへのクエリを節約して、改善の余地の大きいビットにたくさんクエリを投げれています。

これを実装すれば74000点が・・・出ません。誤差が大きくなりすぎます。このマラソンは誤差との壮絶な戦いでした。この誤差マラソン中にやってよかったことは誤差を無視したらどうなるのかを常に意識するとです。それは正解ビット列をカンニングしながら推定値を使うところをすべて真値を使うプログラムを書くことです。これをすると実装がバグってるのか誤差が大きすぎるかの切り分けができる、誤差0のときのスコアつまり誤差に対する上界がわかる、上界を元に1位に届くか判断できる、誤差でどのぐらいスコアが下がっているのかがわかるです。

でまあ以上のようなことをやって上界が78000点(1位オーバー)ですが誤差ありでは71000点くらいしかでず誤差が大きいことがわかりました。そこで誤差を小さくできれば1位に届くと思い、誤差が大きい箇所を調べました。誤差が大きい箇所は3つでした。

1.広いビット区間の反転は誤差が大きい
さっき述べましたがたくさんビットを反転するとスコアの変化量が大きいのでそれにともない誤差も大きくなります。広いビット区間のクエリは控えたいですね。

2.区間ACの誤答率と区間ABの誤答率から区間BCの誤答率を算出推定するときに誤差が累積する
クエリ値からの推定は1次ソースなので誤差は常に一定値以下ですが区間区間から区間の誤答率を求めるたびに誤差が累積します。ビット区間が狭くなるほど深くなるほど誤差が大きくなります。あまり深くしなければよさそうですね。

3.区間BCの誤答率がわかった時点で区間BCを反転した方がスコアが上がるかどうかがわかりますがこれを即時反転してしまうと誤差る
少し前に後述って言ってたやつです。わかった時点で反転してスコアを改善してしまうとスコアの上昇量を推定しないといけなくなり誤差がでます。反転したほうがスコアが上がるという情報を覚えておいて最後のクエリの直前にまとめて反転すると誤差を0にできます

1.2.より長さ88の区間46個を初期ビット区間集合として深さを3に制限する。3.をやる。パラメーター調整をする。これで74000点がでました。上界が78000点なので軽減したとはいえ結構誤差がのこってます。

77000点

誤差は限界まで小さくしたので他に何か問題がないか考えてます。反転するビット区間が広すぎると誤差が大きすぎてよくないことがわかりました。逆に狭すぎるとスコアの変化量が小さすぎるのでよくないこともわかっています。

このことから誤差が大きすぎず(長さが広すぎず)、スコアの変化量が小さすぎない(長さが小さすぎない)最適なビット区間の長さがあるのではと考えました。74000点解法は広い区間から徐々に狭い区間に狭めていくという解法でこの考察が正しいとするとよくないですね。なんとかしたい。

そこで広い区間を狭い2つの区間分割した後にもう一度統合すれば最適な区間の長さを保持できるのではと考えました。ここで統合という概念がでてきたのでここからは区間(連続している)という表現は正しくなくなったので以降ビット部分列という表現に変わります。

問題はどのビット部分列と部分列を統合するかです。これは誤答率ができるだけ近しい部分列と部分列を統合するのがよいです。理由は情報量の減少が小さいから。たとえば誤答率が10%の部分列と90%の部分列を統合してしまうと誤答率が50%になり情報がうすまってしまいます。

以上のことから偏りが小さく、かつ誤答率が近しい部分列を2つ選んで統合、分割して片方のビットを反転してクエリを投げるというのを繰り返すと改善の余地が大きいところを集中的に最適な長さのビット部分列で殴り続けられるので76000点がでました。

あとパラメーター調整とかヒューリティスとか誤差を小さくしたりあやしげな工夫をいろいろして77000点がでました。

リファクタしまくってたら100行くらいになった。

#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 考えたこと

マラソン参加3回目、がっつり参加したのは初めてだけれど楽しかったです。
暫定 72.34点 15位 Python

問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16494&pm=10967


全部Sにしたら100%になるよねーと思って上からSE以外をSにする。
38点


初期解(ランダム解)でなぜ迷路がほとんどできないのか考えてみる。

境界からスタートしてランダムに動いてもその場からあまり動かない。迷路の中心に向かう力がない。大きな迷路ができにくい。

ビジュアライザを無効なパスを表示するように変えてみる。
Uに突っ込んでる。Uを変えればよい。
くるっと回転して自分のパスに突っ込んでる。回転しなければよい。直進すればよい?やっぱりSが強い?

直進すれば迷路の中心に向かって迷路が大きくなり、回転して死ぬこともなくなる?


紙にいろいろ書いて思いつく。

f:id:hakomof:20151027204511p:plain

LとRが交互に並ぶようなライン(間にSやEはあってもよい)はどこから進入しても下から入れば上へ、上から入れば下へ抜ける。蛇行しながら直進する。

このラインを下端から上端まで積めば下端から上端、上端から下端へ抜ける迷路がたくさんできる。

このLとRが交互になるような修正をX座標が小さい順にF個とる。
64点

f:id:hakomof:20151027204509p:plain


ここでかなり迷走したので数多のソースが生まれそして死んでいった。

複数の迷路が密に重なっているのがよくないのではと思った。
複数の迷路で修正を共有しているのはメリットだけれど、マスを共有しているのはデメリットなのでトータル損してそう。もっと高効率な迷路をばらけさせたい。

LとRが交互になるような修正を全体にしたうえで有効な迷路を列挙する。
厳密に列挙すると指数時間になってしまうので、上左右の移動だけ、下左右の移動だけでできる迷路を列挙する。列挙漏れはEがからむときだけなので見なかったことにする。この制限でメモ化ができるようになってるはずなんだけど今自分の実装見るとしてない。あれ?

で、列挙した迷路をFを超えない範囲で近似スコアが最大になるように選択する組み合わせ問題になった。

最初DPしようとしたけどマスが共有されているのでできなんだ。

迷路ごとのマス数/修正数が大きい順にFを超えない範囲で選んでいく(貪欲)。
71点

f:id:hakomof:20151027204505p:plain


選択した迷路をひとつのぞいて別の迷路を選択して近似スコアが上がれば採用(山登り)。
72点

焼きなまそうと思ったけどよくわからず。

おわり


その他

方針さえあってれば Python でも探索時間減るだけやし上位狙わなければへーきへーきと思ったけど全然きつい。終わる前提の処理が終わらない終わらない。配列使いまわしたり、boolの2次元配列を整数の1次元配列に圧縮したり、なくなく迷路集合カットするなどした。

LとRを交互にするというアイデアに固執しすぎた感。マラソン終わるまで現解法の発展が上位の解法だと信じて疑わなかった。反省。

EとEを優先的につなぐように修正してみたけど微増だったのでやめた。テストケースごとのスコアは大きく上下するのがたまにある感じでWHFに特徴がみられなかった。今思うとEの割合とかもっとよく見ればよかった。平均じゃなくてFが多いとか少ないとか個々のテストケース見るの大事。

結局乱数使わなかったんだけどこれでいいのか。


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))

Laravel 5 のデバッグ出力

Laravel 5 でデバッグ出力する3つのやり方についてまとめる。

ログファイルに書きだす

2通りの書き方がある。

ヘルパー関数 logger(), info()

<?php

Route::get('/', function() {

    $message = ['a' => 1, 'b' => 2, 'c' => 3];

    logger($message);
    info($message);

    // logger()->notice($message, $context);
    // logger()->warning($message, $context);
    // logger()->error($message, $context);
    // logger()->critical($message, $context);
    // logger()->alert($message, $context);
    // logger()->emergency($message, $context);

    return 'OK';
});

storage/logs/laravel.log に書き出される。

[2015-07-31 13:40:35] local.DEBUG: array (
  'a' => 1,
  'b' => 2,
  'c' => 3,
)  
[2015-07-31 13:40:35] local.INFO: array (
  'a' => 1,
  'b' => 2,
  'c' => 3,
)  

配列ライクは var_export() で、 Jsonable なクラスインスタンスJSON 文字列に内部で見やすく整形してくれる。なので、何も考えずに引数に渡してよい。

Log ファサード

<?php

namespace App\Http\Controllers;

use Log;

// ...

class MyController extends Controller {

    public function index() {

        $message = ['a' => 1, 'b' => 2, 'c' => 3];

        Log::debug($message);
        Log::info($message);

        // Log::notice($message, $context);
        // Log::warning($message, $context);
        // Log::error($message, $context);
        // Log::critical($message, $context);
        // Log::alert($message, $context);
        // Log::emergency($message, $context);

        return 'OK';
    }
}

ヘルパー関数と Log ファサードのやってることはまったく同じ。ただ、 Log ファサードはファイルの先頭で use Log; しないといけなかったり、 use Log; できない php ファイルがある?のでヘルパー関数の logger() のほうが便利。グローバル関数は最強だな。

ブラウザに表示する var_export()

<?php

Route::get('/', function() {

    $message = ['a' => 1, 'b' => 2, 'c' => 3];

    echo '<pre>' . var_export($message, true) . '</pre>';

    return 'OK';
});

Laravel と関係ない PHP おなじみのやり方。一応説明すると var_export() で見やすく整形して pre タグで改行を可視化している。

f:id:hakomof:20150801095107p:plain

ブラウザにリッチに表示する dd()

<?php

Route::get('/', function() {

    $message = view();

    dd($message);

    return 'OK';
});

dump and die の略。上述の2つと違ってクラスインスタンスとか複雑なものも表示できる。 die と名のつく通りアプリケーションの実行を停止する( OK が表示されてないよね)。なんかすごい。

f:id:hakomof:20150801095108p:plain

まとめ

logger($message, $context);

ログファイルに書きだすので残る。

echo '<pre>' . var_export($message, true) . '</pre>';

ブラウザに表示する。

dd($message);

ブラウザにリッチに表示する。クラスインスタンスとか複雑なものも表示できる。アプリケーションの実行を停止する。

以上です。それでは Laravel のよきデバッグライフを。