TopCoderの学習のお時間

2017-01-22

■ [CodeChef]January Challenge 2017 18:13

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

■ [CodeChef]December Challenge 2016 13:40

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 になる。

次に、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

これは 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への出題について」です。お楽しみに！

2016-11-14

■ [CodeChef]November Challenge 2016 00:48

https://www.codechef.com/NOV16

最後の問題までやる時間とれないですねえ…

Task for Alexey(ALEXTASK)

最小公倍数

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

Chef and squares(CHSQR)

F(K) の上界が K/2 であることはすぐにわかって、次のように K/2 になる例が構成できるので F(K) == K/2

4 5 1 2 3
3 4 5 1 2
2 3 4 5 1
1 2 3 4 5
5 1 2 3 4

5 6 7 1 2 3 4
4 5 6 7 1 2 3
3 4 5 6 7 1 2
2 3 4 5 6 7 1
1 2 3 4 5 6 7
7 1 2 3 4 5 6
6 7 1 2 3 4 5

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

Count Permutations(CPERM)

i=k の場合が何通りか == iよりも左の(k-1)個に 1〜N-1のうち何個を割り当てるか == C(N-1,k-1)

なので、 i=1,2,...N の場合を足し上げると C(N-1, 0) + C(N-1,1) + ... + C(N-1,N-1) = (1+1)^(N-1)

なので、求める答えは i=1,N の場合を除いた 2^(N-1)-2

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

Gift and Chef(GIFTCHEF)

S上のマッチ箇所を列挙してからDP

文字列のマッチはローリングハッシュでやったら、ハッシュ衝突するテストケースが含まれてたみたいでやたら時間かかった…。せっかくSuffixArrayライブラリ持ってるのだからそっち使っとくべきだった

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

Friends Meeting(FRIEMEET)

木DPですべてのあり得る経路の合計長を求める

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

Urban Development(URBANDEV)

y軸方向のどの座標にhorizontalな辺があるかをBITで持ってx軸方向に平面走査

各辺が交差する回数を出さないといけないのでxy入れ替えて2回やる

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

Kirito in Memeland(KIRMEME)

なんか重心分解とかでできそうなんだけど、よくわからないので独自なアルゴリズムでがんばっていた。

各ノードにBITを2つ持たせて Weighted Union Heuristics で木DPをする。

2つのBITは、それぞれ次の値を持つ。

そのノードの子孫（自身含む）で始まり、そのノードで終わる経路のうち最後の移動で標高が上がっているもので、経路の中に「上がって下がる」をi箇所含むものが何個あるか
上と同じ経路のうち、最後の移動で標高が上がっていないもの

BITに先頭へのadd（既存の要素は1つずつ後ろへshiftされる）をサポートさせる必要があったので、ただのBITではなくて改造を加えた。

最初はサイズに余裕を持たせておいて配列の途中から使い、先頭へのaddのときは前側に伸ばしていって、いっぱいになったらキャパシティを2倍にしてコピーする、といった実装にした（vectorの伸長みたいな）。

O(N logN^2)

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

Bear and Shuffled Points(BIKE)

行列累乗で部分点のみ

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

Sereja and Permutations 3(SEAPERM3)

手つかず

Sereja and Ways in the Cube(SEAWCU:タイブレーク)

DFSしただけ

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

34.069点

~~上位のスコアが理論限界超えてる気しかしなくて何かがおかしい（ソースをチラ見したけどわからず…）~~

【追記】自分のコードがバグってるだけでした…

結果

764.069pts/1000pts
28位/4143人

2016-10-18

■ [CodeChef]October Challenge 2016 17:35

http://www.codechef.com/OCT16

ひさしぶりに参加した。ちょうど良い難易度だった。

Chef and Keyboard(CHEFKEY)

やる

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

Chef and Three Dogs(CHDOGS)

Three Dogs Problem でググると http://mathworld.wolfram.com/MiceProblem.html に行き着く

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

Fenwick Iterations(FENWITER)

実験するとわかる

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

Chef and Two String(CHEFTWOS)

2を使うのは次のように 2,2,1 と並んでいる形しかありえない

2 2 1 ?
 --->
  <-
   --->

2が何個連続しているかを状態としてDPする。終端でぴったり終わらないといけないので最後だけちょっとややこしい

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

Big Queries(BGQRS)

遅延更新するSegmentTree。

各ノードに次の値を持たせる

配下の範囲に含まれる2の数,5の数の和
配下の範囲すべてに共通して含まれる2の数,5の数
配下の範囲がクエリ2によってひとつの等差数列に含まれているなら、その先頭の値

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

Sereja and Stones(SEASTONE)

石の配分を固定したとき、Eが大きい箱にたくさんの石を置くようにするのが最適なので、箱はEの値でソートする。

Eが最大の箱にすべての石を入れる、またはできるだけフラットになるように石をすべての箱に分配する、という戦略が良い上限になっているようで、枝刈り探索で十分早く答えが出た。メモ化もせず0.38秒。

forumによると、DPを加速する方針の計算量が保証できる解答もあるらしい

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

Power Sums(POWSUMS)

https://ja.wikipedia.org/wiki/%E5%AF%BE%E7%A7%B0%E5%BC%8F#.E3.83.8B.E3.83.A5.E3.83.BC.E3.83.88.E3.83.B3.E5.A4.9A.E9.A0.85.E5.BC.8F

このあたりを使うと、与えられた情報からN変数の基本対称式の値がすべて求まる。

それを元に、a_i が満たすべきN次モニック方程式が出るので、きたまさ法を使って a_i^x の次数を落とせる。

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

Bear and Shuffled Points(GEOCHEAT)

逆向きに、すべての点がある状態から一つずつ取り除いていくと考える。

最遠点対は、凸包を作ってキャリパー法すると O(NlogN) でわかる。

取り除く点が最遠点対に一致したときのみ再計算する。点がランダムに並び替えられていることから、再計算は頻繁には起きないのでこれで間に合う。

ちなみに N=750000 のとき、再計算回数の期待値を計算してみると28くらいだった。

なおキャリパー法を蟻本を元に実装したら、停止しないケースがあって焦った。とりあえずアドホックに対応したけど、もうちょっとちゃんと対策しておかねば。

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

Tree Balancing(TREEBAL)

考える時間が無くて自明な部分点のみ。

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

Sereja and Progressions(SEAARI:タイブレーク)

まずは絶対値が大きい順にD個取り除く。

残りの値の最小値が配列の左端、最大値が右端にくるとして、それらを結んだ直線を仮の回答とする。

その直線からのずれが最も大きい位置を交換元とし、交換元の値が本来あるべき位置の周辺を探索し、入れ替えたときに最もコストが減少する位置を交換先とする。これをK回行う。

PriorityQueueを使って1回の交換あたり O(logN) で処理する。

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

83.106点

結果

893.106pts/1000pts
9位/6517人

2016-08-15

■ [ICFPC] ICFP Programming Contest 2016 12:46

例年のように会社の人たちと参加した（チーム名：fixstars）。6人で合宿。

やったこと

ソルバ作成

紙を開いていくという王道な方針のソルバは他の人がやっていたので、違う方法を考える。

入力のskeltonを最小の多角形に分解して、それらを1x1の正方形になるように敷き詰める、という方針にした。

2日目の昼くらいには何となく動いて、雑魚問は解けるようになった。

ただ指数オーダーなのでちょっと入力が複雑になると全く無理。

改善しようとしたけどたいして良くはならず、解ける問題のうち最も複雑なのはこの程度でした（problem id 285）

出題用の問題作成

2日目の夜に寝ながら考えたら、どうやら問題を解くよりも出題のほうがスコアに占めるウエイトが大きそうなことに気付いた。

その時点で自チームの出題は一応最後の分まで行われていたけど、けっこう解かれそうなので強化することにした。

Unagiの問題が強そうなので方針をパクる。折るのは90度か45度の線のみで、skeltonの線がたくさん重なっているような非凸の図形だったら良い。

このシンプル仕様でも紙を折る実装が難しくて、生成器を作るのに8時間くらいかかってしまった。

ランダムに折りまくって適当に設定した評価関数にかけて良いのを出力する、というものだけど、評価関数だけではあんまり強いのを抽出できず、何十個か生成した中から人目で強そうなのを選別していた。

（でも結局数十個しか作らないのだから、GUIを用意して人力で作るようにしたほうが良かった気もする）

なんとか最後11問は、これで作成した問題に置き換えることができた。

Unagiのものほど強くはないけど、ひとつを除いてUnagiにしか解かれていないし、サイズも1000未満なので、1問2000点以上入ることになっていてまずまずといえよう。

はじめに提出していたやつは20チーム以上に解かれていたので、置き換えたことで2万点ほど得られたことになる。良かった（ただしUnagiに対してはアシスト）。

なんか「いかにUnagi以外には解かれなくてサイズができるだけ小さい問題を作るか」という競争だった気がする。

サイズが小さいと解くうまみが少なくて、人力部隊のターゲットから外れやすくなるという効果もありますね。

ちなみに作ったのはこんなやつ（problem id 5607・5638）。

問題一覧作成

ソルバを作る過程でデバッグ用に問題を画像出力していたのを流用して、各問題がどんな見た目をしているかの一覧を作成した。

ちゃんとデプロイする環境を用意しなかったので、自分以外にはあまり活用されていない感

反省・感想

よかったこと

めっちゃでかいホワイトボードがあって活躍した
合宿先からコンビニが近いと便利
朝食がバイキングだったので時間に縛られづらく、朝食を取らない人の罪悪感も減じられた
睡眠時間は1日5時間程度で、集中も続いて削りすぎずちょうど良いくらいだった
コンテストの形式が非常に良く練られていて、本質以外の部分でのストレスが無かった
たくさんソルバの実装ができた
- 例年あまりソルバ担当にならないので…
- 次回はインフラ方面やりたい

よくなかったこと

最後ソルバにバグが残ってることが発覚して、取り切れず諦めてしまったけど、後で考えてみたらそのバグが存在したのは「解答サイズを最小にするため多角形をマージする」という部分なので、必ずしも実行しなくて良いところだった。それに気付いていればバグの影響をかなり抑えられたはずだが…
バグが残っていることに気付くのも遅かった。ソルバとしては解が出たら満点のはずなのだから、それ以外になっている時点で即アラートを上げてもらうようにしておくべきだった
コンテスト全体としての戦略に対する考察が不十分だった。出題がかなり重要であることにもっと早く気付いていたら、あと5万点くらい違っているはず
会議室の鍵がひとつしかなくて扱いづらかった（一人だけ先に寝ておいて早起きしてくる、みたいなのがやりづらい）

そのほか