Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

|

2017-10-27

[] Marathon Match 95 CirclesMix 16:10 はてなブックマーク -  Marathon Match 95 CirclesMix - TopCoderの学習のお時間

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=16959


1日目(木曜)


問題を読んだ


2日目(金曜)


テスターをカスタマイズ(いつもの)

  • マルチスレッドでのバッチテスト
  • 結果の出力を良い感じに
  • 問題パラメタを自分で指定できるようにする

3日目(土曜)


テスト画像をwikimediaからクロール

(イラストとか本のページとかの画像は弾くのだけど、基準に主観が入るので迷うのが多かった)

1000枚取ってきたけどそんなに要らなかったかな…


greedyに円を一つずつ置いていくのを実装

  • ランダムな位置・半径で円をたくさん作る
    • すでに生成したものと近すぎる円は生成されないようにする
    • 半径は徐々に小さくする
  • それぞれの円に対して、最適な色にしたときにペナルティがどれだけ減るかを評価
  • ペナルティ減少が一番大きい円を選ぶ
    • 選ばれたやつと重なるもの以外の円は保持しておいて再利用する

また、選んだ円に対して、位置と半径を動かす山登りを実装


4日目(日曜)


高速化色々、SSEも使う

円の最適な色を決めるために、円の内部のピクセルに対して中央値を取る処理が重いので、かわりに円の中心にある7*7の正方形範囲の中央値を使う、という大胆な近似を取り入れたり

最終的に、greedyフェーズでは各ターンで 10000/sqrt(N) 個の円を生成し、選ばれた円に 10000/sqrt(N) イテレーションの山登りを行った。所要時間は6,7秒くらい?


5日目(月曜)


まだまだ高速化


円を置いてしまった後に、時間いっぱい使って繰り返し山登りで改善するのを実装(高速化を頑張っていたのは、これをやる時間を作るため)

山登り対象になる円をランダムに選ぶと、評価のためにその円の上に重なっている円をすべて再描画しないといけなくなって受け入れられないほど遅そうで、そうならないよう1つめの円から順番にひとつずつ山登りした。

各ピクセルごとに、未来側に円が何枚重なっているかと色の和を覚えておけば、再描画無しで評価できる。

  • まずN枚目〜2枚目までの情報を計算して、それを使って1枚目の円を山登りする
  • 未来側の情報から2枚目の円の寄与分を取り除いて、2枚目の円を山登りする
  • 以下同様

この問題は、とにかくいかに逐次改善可能な形に持って行くかが勝負だと思ったので、ここが一番の重要ポイントだった


6日目(火曜)


調整色々


前日実装したものが山登りになっていなかった(良い解になっても状態を更新しておらず、初期状態の近傍しか調べてなかった)という致命的なバグを修正


7日目(水曜)


パラメタ調整やる、が、ほとんど変わらず

AWSで36coreマシン借りて35スレッドでテストを実行したら、めちゃくちゃ遅くなってまともにテストできなかった。16スレッドに減らすと普通だったので、コア数もったいないがそれで。

原因は追ってないけど、テスターで画像を読んでるからだろうか?


やらなかったこと


  • はじめは画像を縮小して処理することで高速化
    • やったけど良くならなかった
  • 画像から円をパターン検出
    • seed=1を見るとそういうことを考えてしまいたくなるが、実装も実行もコスト高過ぎそうでやめた

結果


1位とだいぶ差があった。

最終日にしか提出しなかったのは、戦略のつもりではなくて、単に何度も提出するのがめんどいからです

2017-07-02

[][] TCO17 Marathon Round2 20:55 はてなブックマーク -  TCO17 Marathon Round2 - TopCoderの学習のお時間

https://community.topcoder.com/longcontest/?&sc=5&sd=desc&module=ViewStandings&rd=16928


準備フェーズ


とりあえず、感覚をつかむために次の2つの自明解を作った。

  • 毎ターン一番近い敵に攻撃
  • 990人まで貯まったら一番近い敵に攻撃

これだけでもそこそこ勝てている。前者が強い場合と後者が強い場合がだいぶはっきり分かれていて、勝ちやすいケースは前者が強くて、最終的に負けてしまうケースでは後者の方が強い。

これらをうまく組み合わせていく感じかなー、と考える。

スコアが順位ベースで決まるので、何もしない解に負けてしまうと大ダメージだからそれだけは無いようにしないといけない。


敵の方がPowerが高いことから、基本的には不利なんだけど、この不利を緩和したい。端数がたくさん切り捨てられるような攻撃をするといい、とかそういうのがありそう

…と考えていたら、6人以下で攻撃すると1:1でロスなし対消滅できて最もおトクであることに気づいた。速攻で連打するとそこそこ勝てるのは最初実装したやつで分かっているので、簡単に勝てるケースはこれをどこまで最適化できるかのゲームになるんだと理解する。

…で、そこではそんなに差がつかなさそうだからやっぱり難しいケースをどう賢くするかだなあ、という雰囲気になる。


モンテカルロシミュレーションやったりするのかなあと思いつつ、何やるにしても敵のパラメータ(power・attackT・locality)やTroopの行き先推定は必要なのでそいつらを実装していく。


実装フェーズ


そして実装していたら1週間経ってしまったので絶望する https://twitter.com/tomerun/status/864889052826288128

ついで、速攻ケースのシミュレーション+倒すbaseの順番での山登りを書き上げて、ある程度の高速化・パラメタ調整をやる。

この時点でまだ本丸(勝ちにくいケース)に手がついていないのに、もう2回目の週末が終わっていて絶望する https://twitter.com/tomerun/status/866298649680027648


とにかく、速攻で勝てないケースの戦略を作っていく。

とりあえず、全滅させられてしまう直前の逃避戦略を実装する。これはまあやるだけ

最序盤ですぐ倒せるところだけは速攻で倒しておくとして、基本は980まで貯めてから攻撃する。攻撃先をどこにするのかが考えるところ。

単純に一番近いところを攻撃するのは、すでに倒せるのが確定しているところに集まりすぎで損、というのはこれまでの結果から分かっている。

すでに倒せることが確定したbaseへは攻撃せず、他を狙うようにするとそれなりに良くなった。

あと、980貯まっていても、敵の攻撃が向かってきていて、攻撃で人数が半分になった状態では全滅させられてしまう場合は、攻撃せず待つようにしたり。

ここまででもう終了前日になってしまったので、全然細かい調整できてないんだけど観念して提出したら93万点とか出てびっくりした。

最後に、他の敵から攻撃されづらい位置にあるbaseを優先的に攻撃する、というのを入れようとしてみるが、良くならなくて終了


ビジュアライザ

f:id:tomerun:20170702204626p:image


カスタマイズした点は以下の通り。

  • 早送り・巻き戻し可能に
  • growRateに応じてbaseの形を変える
  • baseのindexも表示できるように(デバッグ用、普段はoff)
  • playerごとの合計人数を表示

そのほか


  • 今回は実装が難しそうで、そこまで高速化勝負にはならなさそうだったのでJavaを使った。結果的に、やっぱり実装がボトルネックだったのでこれは正解だった
  • 仲間同士で人数を1箇所に集中させて成長速度を増やすのはちょっとやってみようとしたが、あまり効果が感じられなくてやめた
  • 敵のlocalityも推定した(離散化してベイズ推定)けど結局使わなかった

結果

  • 暫定スコア 927281.55(100ケース)
  • 暫定順位 6位
  • 最終スコア 942086.41(5000ケース)
  • 最終順位 3位
  • レーティング 2491->2566 highest!

2017-06-17

[] June Challenge 2017 20:49 はてなブックマーク -  June Challenge 2017 - TopCoderの学習のお時間


https://www.codechef.com/JUNE17/


A Good Set (GOODSET)


500,499,498,... を出力する

https://www.codechef.com/viewsolution/14009670


Xenny and Coin Rankings (XENRANK)


やる

https://www.codechef.com/viewsolution/14009805


Chef and the Feast (NEO01)


大きい値のものから順に、まとめた方が得する限りまとめる。それ以外は1つずつ使う

https://www.codechef.com/viewsolution/14213083


Pairwise union of sets (UNIONSET)


K/2より大きい集合はBitSetで、小さい集合は配列で持つ

len1 + len2 + .. + lenN ≤ 10000 の制約があるのでこれで速くなる

https://www.codechef.com/viewsolution/14013196


Triplets (SUMQ)


ソートしてしゃくとりっぽく

https://www.codechef.com/viewsolution/14012356


Chef and Prime Queries (PRMQ)


永続segtreeで殴った

https://www.codechef.com/viewsolution/14213423


Cloning (CLONEME)


まともにやったら判定できる気がしないのでハッシュ的な方法を使う。

累積和・累積二乗和、kビット目だけの累積和・いろんな素数でmodの累積和 を持っておく。

二つの範囲で、すべての値が一致していたら完全一致と判定する。

そうでない場合、食い違いが1個だと仮定すると、累積和と累積二乗和の差から、ひとつめの範囲にのみ含まれる値 x とふたつめの範囲にのみ含まれる値 y がわかるので、これが他の累積和たちと矛盾しないかを確認する。

矛盾しない場合、両方の範囲の中にxとyの間の値が存在しないことが必要なので、それを永続segtreeを使って確認する。

https://www.codechef.com/viewsolution/14212683


Euler Sum (ES)


eを有理数で近似する。

A * e = B + ε (0 <= ε << 1) のとき、e = B / A と思うと1〜Aまでの floor(i * e) の和は、算数をするとO(1)で求まる。

AとしてN以下でできるだけ大きいものを取る。i > A については、 i = A + j と分解すると、N -A についての問題に帰着されるので再帰的に解く。

そのようなAはどうやって見つけるかというと、まず100くらいまで探索して、整数よりちょっと大きくなる係数Pと、整数よりちょっと小さくなる係数Sを(そこまでの範囲で)決める。

  • P * e = Q + ε (0 <= ε << 1)
  • S * e = T - δ (0 <= δ << 1)

このとき、 (P + S) * e = Q + T + (ε - δ) で、整数とのズレの部分 ε - δ は絶対値が ε, δ どちらよりも小さくなるので、ε - δの符号に応じてPとSのどちらかをP+Sに更新する。

これを繰り返せば、端数部分をどんどん小さくできる。

通してる人がみんなPythonだったのでRubyで書いてみたら、10^4000はTLEになってしまった。定数倍の範囲だとは思うのだけど…。

https://www.codechef.com/viewsolution/14231349


Persistent oak (OAK)


13点分は、永続化の実装の練習なので実装をする。

https://www.codechef.com/viewsolution/14218335


Saboteur (SBTR;タイブレーク)


残す頂点の集合を決める。

始点の頂点を1つ決めて、連結している頂点の中からコストが大きなものを使っていく、というgreedyを始点を変えつつ時間いっぱい試す

https://www.codechef.com/viewsolution/14223678

89.8点


結果


  • 852.817pts/1000pts
  • 43位/9386人
  • レーティング 2448->2422

ESの満点は取れないといけなかった感

2017-05-11

[][] TCO17 Marathon Round1 01:11 はてなブックマーク -  TCO17 Marathon Round1 - TopCoderの学習のお時間

https://community.topcoder.com/longcontest/?&sc=5&sd=desc&module=ViewStandings&rd=16903


やったこと


3段階で焼きなましをした。

  1. 35*35のグリッド上で、ランダムな頂点をランダムな位置に動かす遷移。評価値は、各辺について目的の長さと実際の長さの差の絶対値
    • 点の位置の重複は許す
    • 終わったら、各頂点をグリッド内の20*20のどこかにばらまいて700*700にする
  2. ランダムな頂点をランダムな近傍に動かす遷移。現在の辺の比の最大/最小の少し内側を目標にして、そこから外れた辺にペナルティがつく評価値
    • ペナルティは、(外れ量+0.5)^8 とか外れ具合に応じて大きく傾斜をつける
    • 頂点の移動距離は時間に伴って徐々に小さくしていく
  3. 比が最大/最小の辺に属した頂点をランダムな近傍に動かす遷移。真のスコアが評価値
    • 頂点の移動距離は時間に伴って徐々に小さくしていく
    • どの辺の比が最大/最小かを管理するのに、辺を比の値でバケットに入れて扱った
      • 各辺が自分のバケット内で何番目かを覚えておくと更新がO(1)でできる

最後の仕上げとして山登りをした。遷移は、比が最大/最小の辺に属した頂点を微少に動かして、他の辺が最大/最小を超えたら再帰的にその辺の頂点を動かす、というのを一定深さまでやる。

一応無意味ではないかな…くらいの効果はあった(結果のBestsが多かったのはこれのおかげだと思っている)


焼きなましの3フェーズの時間配分は 0.39:0.16:0.45 だった。これと別に最後の山登りに50ms使う。

焼きなましのイテレーション回数は合計6000万回くらい。SSEも使った(高速化の恩恵は1割程度)


時系列で


とりあえず真っ先に思いつくのは比が最大/最小の辺をいじることだけど、最大/最小だけ見てたら評価がハードすぎて一瞬で局所最適にハマりそう。もっとソフトな感じに評価したい。

一瞬バネ物理シミュレーションが浮かんだのだけど、その手の問題は以前ぼろ負けした(TCO13R3)のでひとまず考えないことにする。

というわけでまず焼きなましPhase2だけを作った。これが初日の48万点。


で、いろいろなケースの結果を出力して眺めていたら、長い辺がボトルネックになりがちなことが分かる。

長い辺は後から微調整が効きづらいので、最初の方でだいたい良い感じにしておかないといけない、と考える。

そこで焼きなましPhase1を作った。比で評価すると短い辺の重みが強くなってしまうので、差で評価。これで70万点超え。


ちょこちょこ調整した結果が3submit目の76万点。


ここで満を持してPhase3を追加すると4submit目の78.5万点。

https://twitter.com/tomerun/status/855468636860891136 ここで言っていた「伸びしろ」はこれのこと)


このあとはほとんど焼きなましの調整と高速化だけだったと言ってよい。

最終日の1日前の段階でアルゴリズム的な改善は打ち止めにして、ここで有給休暇を取って細かい高速化をまとめてやり、最終日に会社行っている間にクラウド使ってパラメタ調整、というのが最近の試合運びのトレンドになっている。

EC2のc4.8xlargeを24時間ほど動かして$17くらい使った。35スレッドだと1000ケースのテストが3分で終わるので良い。


もうちょっと探っておくべきだったかなーというところは、

  • 多スタート
    • 難しいケースでスコアが0.1くらいぶれることがあるので、その安定性のため
  • 辺の目標長を最初から短めに設定しておく
    • ちょっとやってみたら良くならなかったので捨てたのだけど、実際最終状態が短い方に寄るケースが多いし、Psyhoさんはこれ入れるとめっちゃ伸びる(余裕で1位超えるくらい)らしいし、もっと時間をかけて見ておくべきだったかも
  • 頂点の移動先はランダムじゃなくて辺の向きを考えて選ぶ
    • 1位2位はそれをやっているみたいなので

結果

  • 暫定スコア 790914.54(100ケース平均)
  • 暫定順位 6位
  • 最終スコア 797343.97(1000ケース平均)
  • 最終順位 3位
  • レーティング 2410->2491

2017-01-22

[]January Challenge 2017 18:13 はてなブックマーク - January Challenge 2017 - TopCoderの学習のお時間


https://www.codechef.com/JAN17


Cats and Dogs(CATSDOGS)


やる

https://www.codechef.com/viewsolution/12432868


Reservior(RESERVOI)


やるだけだけど問題文で網羅されていない仕様があって1WAした

https://www.codechef.com/viewsolution/12534258


Capital Movement(CAPIMOVE)


首都の隣かどうかで場合分け

https://www.codechef.com/viewsolution/12452430


Tourists in Mancunia(TOURISTS)


DFSして閉路を作る→グラフの残っている部分について閉路を作って最初の閉路に挿入する を繰り返す

https://www.codechef.com/viewsolution/12456303


Digits Cannot Separate(DIGITSEP)


普通に桁DPするだけ、にしては正解者数少ない

https://www.codechef.com/viewsolution/12457791


Chef and Circle(CHEFCIRC)


N点中3点を通る円を全列挙したい。

まず2点A,Bを決める。残り1点Cを決めたときに外接円の中心がABの垂直二等分線上のどこに来るかが分かる。

この垂直二等分線上で外接円の中心となる点の位置をソートしてスイープすると、A,Bを通って点がK個以上含まれるような円の中心となる範囲が分かる

これがO(N^3 logN)だけど、遅くてダメだった。

制限時間が来たらその時点での最善の解を出力するようにしたら通ってしまった

https://www.codechef.com/viewsolution/12562803

想定解は、半径Rについての二分探索。

円が通る点Aをまず1つ決めて、Aを中心とする半径Rの円周上を円の中心の候補として、ほかの各点について円に含まれるような円の中心の存在範囲を求めて偏角ソートしてスイープ


Fantastic Four(FOURSQ)


前半パートの積を求めるところはごく普通のsegtree(ただしオーバーフローに気をつける必要あり)。

後半パートの、4つの平方数に分解するところがわからず、定数倍高速化を頑張って通してしまった

https://www.codechef.com/viewsolution/12491784


想定解は、積を求めてしまってから平方数に分解するのではなくて、各要素を平方数に分解してから掛けていく方法だった

https://discuss.codechef.com/questions/90269/foursq-editorial

参照 : オイラーの四平方恒等式


Sereja and BOX(SEABOX)


最小化は木DP、最大化はGreedy

スコアは必ず 7*N+1 の形になるので、これを利用して状態を1/7に圧縮すると考えやすい。

一見変な問題かと思いきや普通だった。の割に正解者数少ない

https://www.codechef.com/viewsolution/12535146


Coprime 6-tuples(TUPLES)


包除原理やって部分点だけ

https://www.codechef.com/viewsolution/12563810

想定解はFFTを巧妙に使う方法 https://discuss.codechef.com/questions/90271/tuples-editorial


Sereja and Circles(SEACIR:タイブレーク)


候補の半径をある程度保守的に選んで、互いの距離が遠くなるように焼きなましで候補円の位置を調整

入力の円それぞれについて、半径が自分以上の候補円のうち最も半径が小さいものを選んでそこに置く

https://www.codechef.com/viewsolution/12587441

75.063点

type=2の結果が不安定すぎて まだ改善の余地はあった


結果


  • 922.063pts/1000pts
  • 17位/6866人
|