2016-12-18

■ [CodeChef]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人?