Hatena::Grouptopcoder

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

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

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人

2016-12-18

[]December Challenge 2016 13:40 はてなブックマーク - December Challenge 2016 - TopCoderの学習のお時間


https://www.codechef.com/DEC16

週末1つが他の用事で埋まっていたのでつらかった


Train Partner(ANKTRAIN)


問題文が難しいので適当に推測

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


Kirito in labyrinth(KIRLAB)


dp[i][j] := i個目の部屋まで来たとき、直近でj番目の素数を持つシーケンスの最大長さ

DPする(実際にはiは明示的に持たず、配列を使い回す)。

素数の個数は10^6個くらいあるのでDP配列の長さはそれだけになるけど、1つの部屋でupdateしないといけない位置は少数なので問題ない。

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


Our Base is Under Attack(BASE)


二分探索する

オーバーフローに悩まされた

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


Kth Max Subarray(KTHMAX)


最初誤読して2周りくらい難しい問題を解こうとしていた。

説明のために値はdistinctに 1〜N として、n以上の数を含まないsubarrayの個数を C_n とする。

C_N, C_N-1, ・・・を順に求める。

C_K は、Kの直近で左にあるK以上の値の位置と、Kの直近で右にあるK以上の値の位置が分かれば、C_K+1からO(1)で計算できる。また、そのような左右の位置は、SortedSet使えばO(logN)でわかる。

あとはクエリごとに二分探索すればよい。

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


Roses for Alexey(ALEXROSE)


まず、長さごとに何個あるかを持っておく。K以上の場合はmod Kする。

個数が大きいものから貪欲に使えるかを試す。使ったときに、どの長さのものを使うかは具体的に決めずに、「長さn以上のものをK個使った」ことだけ記録する。

長さnをそれ以上の長さのものと組み合わせてK個にできることの必要条件は、以下の通り

  • n以上の長さのものがK個以上残っている
  • n以下の長さmで過去に使ったものについて、「m以上の長さのものがK個以上残っている」の条件が崩れない

これらを満たすように、貪欲に使う。

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


Bear and Three Colours(THREECOL)


非常に面白かった。


まず定式化する。

3つの色を0,1,2で表す。以下の式はすべてmod 3で考える。

色Xのセルと色Yのセルを合併したとき、合併後の両者の値は 2X+2Y になる。

また、すべてのセル上でのXの値の合計は、どのように操作した後でも X(=1*X) であり、これが不変量になる。


各セルの初期色をC_1,C_2,・・・C_N^2とすると、最終目的は、すべてのセルの値を C_1+C_2+…+C_N^2 にすること。

2(C_1+C_2+…) や 0 にならないのは、すべてのセル上でのC_iの値の合計が不変量であって C_iであることと、N % 3 != 0 より N^2 % 3 == 1 であることからわかる。

(これが、N % 3 == 0 のときに不可能であることの証明にもなっている)


例としてN=4の場合の戦略を挙げる。

次のようにセルを順序づける。

 1  2  3  4
 8  7  6  5
 9 10 11 12
16 15 14 13

4つのセル1,2,3,4に対して、次の順でマージしたら、4つのセルがどれも同じ色 C_1 + C_2 + C_3 + C_4 になる。

  • 1-2
  • 3-4
  • 2-3
  • 3-4
  • 2-3
  • 1-2
  • 3-4

次に、4,5,6,7について同様のことをすると、それら4つのセルの色は C_1 + C_2 + … + C_7 になる。

引き続き、7,8,9,10、 10,11,12,13、 13,14,15,16について順に同じことを行うと、 セル13,14,15,16の色は C_1 + … + C_16 になる。

次いで逆順に 10,11,12,13、7,8,9,10、 4,5,6,7、1,2,3,4 と戻りながら同じ操作をすると、すべてのセルの色が同じになる。


O(N^2)

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


Chef and Finding Direction(CHEFAFD)


セルを市松模様で左右に分けて完全二部マッチングが存在するかどうか。

…をやったらTLEしたので高速化を頑張った(もっと速い方法あるんだろうか)

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


Sereja and Increasing subsequence(SEAINCR)


制約がちょっと珍しい。

平方分割っぽくやればいけそうな気がしていたけど、わからず


Advanced Cooking Machine(BOUNCE)


手つかず


Edit Distance Revisited(EDIT:タイブレーク)


SWAP使ってない自明解のみ。

普通の編集距離DPを、SとTの長さが同じくらいになるような範囲の周辺だけ保持する。

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

60.283点


結果


  • 760.283pts/1000pts
  • 51位/5041人?

2016-12-01

[] AtCoderの昔の問題を難易度推定する 00:09 はてなブックマーク -  AtCoderの昔の問題を難易度推定する - TopCoderの学習のお時間


これは Competitive Programming (その2) Advent Calender 2016 1日目の記事です。


先日、Twitterでこのような発言を見かけました。

AtCoderの過去問が今の基準だと何点になるのか知りたい

https://twitter.com/hogeover30/status/785894012716654593

やってみました。


一応、背景を書いておきます。

以前のAtCoder Regular Contest(以下ARC)・AtCoder Beginner Contest(以下ABC)では、基本的にそれぞれの問題は100点満点でした。

2016年7月にAtCoderがリニューアルされた際、難しい問題は高い点数となるよう、難易度に応じた配点がされるように変わりました。

そこで、以前の問題が最近の基準では何点くらいになるのかを、ユーザーの回答状況を元に推定しました。


AtCoderリニューアル後のコンテストの問題に対する、各ユーザーの正解/不正解の結果と配点を教師データとして機械学習し、過去の問題に対する正解/不正解の結果をテストデータとしています。


結果はこちらにあります。

https://tomerun.github.io/atcoder_statistics/estimated_scores.html


  • どうしても古いコンテストほどデータが少なくて推定しづらい様子。ABCのA問題が250点くらいといった高すぎる数値が出ている
    • 逆に、新しめのものはそこそこよさげに見える
    • こういった状況は他の機械学習案件でもありそうなんだけれど、うまく扱う方法あるんだろうか
  • ABCのD問題にもけっこう難しいのが紛れている
    • あまり出てないので知らなかった
  • 難易度順が逆転してしまっているところはあんまりない
  • これくらいの推定なら正解者数や正解率だけの分析でも出せるんではないかという気もしますが…
  • 解ける人が数人しかいない最高難易度帯の問題は、そのコンテストに誰が参加していたかによって結果がかなり影響されてしまうので、信頼性低そう
    • おおまかには、強い人がコンテストに出ていて解けなかった場合に推定スコアが高くなるという仕組みなので、あまり強い人が出ていなかった場合、推定スコアが高くなりようがない


実装に関しては、だいたいはscikit-learnのSVMに放り込んだだけですが、細々とした話としては次のようなことがあります。

  • 全ユーザー使ってしまうとデータがすごくスパースになって精度下がってしまうので、過去のコンテストに100問以上参加しているユーザーのみを計算に使いました
    • 対象ユーザーは236人でした
  • 過去に一部、満点が101点という問題がありましたが、100点以上を正解として扱っています
  • 「後ろのほうの問題だけ解いて他は無視」という参加をする人もいるので、コンテストの後半の問題は提出しているのに前半の問題は未提出の場合、前半の問題は不正解ではなく不参加という扱いにしています
    • 逆に前半だけ提出していて後半は未提出の場合、後半の問題は手が出なかったとみなして不正解扱い


せっかく今回いろいろデータを集めてきたので、他にもなにか面白い分析をやりたいですね。アイディアがある人はぜひ教えてください。


Advent Calendar2日目は、tubo28さんの「未定」と、snuke_さんの「IOIへの出題について」です。お楽しみに!