CTPC

お疲れ様でした。参加ありがとうございました。僕は運営してました。

404 Not Found

404 Not Found

高専枠の

  • natrium11321
  • Tan
  • HETARE

さんそれぞれ1位,2位,3位おめでとうございます。

一般枠の

  • k_yuridenamida
  • k_operafan
  • tozangezan
  • chokudai
  • Komaki
  • uwi
  • hogloid
  • semiexp

さん全完おめでとうございます。

さて、コンテストいかがでしたか。

今回writerをしたのは僕とkagamiz君です。実はテスターをtokoharuさんにお願いしたりもしていました。

まず、1月上旬にkagamiz君に「コンテストやらないか」と誘われて、ちょっとずつ問題を作って、大体出来上がったのが２月入る前くらいだったと思います。そこからお互いに試験期間重なったりなんやらで手をつけていませんでしたが。２月下旬にテストケース作成とか一気にした感じで、とこはるさんにテスターお願いしたのもそのあたりだったと思います。まあそんなこんなでコンテスト開催することが出来ました。imosさんジャッジ提供ありがとう。atcoderは本当にすごいですね。

ところでとこはるさんにはテスターとしてかなりの仕事を要求しました。彼がいなかったら問題文はもっと不明瞭に、テストケースには間違いがあったことでしょう。本当にありがとうございました。


コンテストの順位表の流れ見てて思ったこと(高専/一般)

  • tozanとかなとりうむさんのＡがめちゃくちゃ早かった。実はkomakiさんが一番速かった説があるが、彼はcppのコードをGCCでコンパイルしてCEしていて惜しかった。"Yes"を"YES"にしてＷＡしてる人数十人居た気がする。
  • 一般枠のk_yuridenamida(誰だ!!)さんがやばい速度で問題解きまくっていて、ｳﾜｱｱってなってた。ていうか一般枠基本的にやばい。
  • とりあえず高専枠にＣでとんでもないＷＡ数出してる人がいたのは印象的だった。
  • 問題ポンポン解いてるはずなのに変なclar大量に送りつけてくるt○zangezanとかいう人も印象的だった。

僕が担当した問題とその講評

  • 僕が担当したのはB,D,F,I,Jです。

B Macaron

感想
  • 問題名はsupercon2011本選の課題ナクロンをパロディしました。
  • この問題は、性格が表れたと思います。一見面倒くさくみえますが、ある座標があるスタンプの色付き部分かどうかは簡単な式で表せるので、それを使ってクエリ毎に全ての座標をループをまわす解法が出来ます。それに早く気づけた人は実装も軽くバグも少なく速く通せたはずです。
  • 気づけない場合にも実装力があれば愚直にシミュレーションすれば通るので、そうやった人も多かったと思います。

回答状況

【高専枠】

First Accepted: nikollson (39:26)

Accepted people: 16

Accepted rate: 64 %

Trying people: 16

Total submit 25

(※挑戦してくれた人は全員通したらしいです)

【一般枠】

First Accepted: tozangezan (07:47)

Accepted people: 47

Accepted rate: 63 %

Trying people: 49

Total submit 74

正答者数はCの続いて3番目に多いです。最も多いのはもちろんAです。

解法
  • 頑張ったシミュレーションで解けるはずなので、ここでは効率的な解法を説明しておきます。
  • 与えられるXi,Yi,Liと任意の座標(a,b)があったときに、x = |Xi-a| , y = |Yi-b|とすると

(x <= y && y%(Li+1)==0) or (y <= x && x%(Li+1)==0)

が成り立っていれば、その座標はスタンプに含まれるということが分かります。この式は、

(max(x,y)+1)%(Li+1) == 0

と省略して書くことも可能です。この条件式を使って全ての座標をループで回すと実装が楽です。

D Knapsack Problem

感想
  • ただのナップサック問題じゃつまんないよな～とおもって作ったのがこれです。クエリの性質をちょっと利用して計算量減らしてもらう問題です。問題文の通りナップサックを形だけでしか覚えてない人をこらしめる意図がありました。自分自身は実装がだるくてあまり楽しくないとコンテスト前くらいに思っていましたが、Dを00:12で通してるヤバイ人がいたので実装だるいとか言ったら怒られるかも。
  • 1-indexedなことが分かりにくすぎたかもしれません。告知はしましたが、本当にご迷惑おかけしました。

回答状況

【高専枠】

First Accepted: nikollson (134:05)

Accepted people: 3

Accepted rate: 13 %

Trying people: 7

Total submit 22

【一般枠】

First Accepted: k_yuridenamida (12:49)

Accepted people: 15

Accepted rate: 25 %

Trying people: 23

Total submit 59

解法
  • クエリが与えられる毎にナップサックをやると、計算量がO(N*Wmax*Q/10)くらいでこれは高々9億くらいなので間にあわなさそうです。
  • そこで、変更されるアイテムは高々３０個なので、それを後ろに持ってきてやると、先頭のN-30個の部分は同じテーブルなので使いまわせるので事前計算して保持しておいて、変更クエリが与えられる毎にN-30個目以降のテーブルだけをループで回すようにすると、O(N*Wmax+(Q/10)^2*W_max)で、これは高々3900万なので通りそうです。
  • 説明するのは簡単ですが、実装するのは結構大変です。他の問題通してから実質4分でこれを通してくる1位の人やばげです。

F Night Museum

感想
  • 幾何は僕自身苦手なので良く分からないのですが、簡単すぎず難しすぎずという幾何を目指しました。誤差・タイムリミット的に嘘解法も含めかなり許容するつもりで出題しました。正直な話writer解が最も嘘っぽい解法というかもっとも精度の悪い解法だと思われます。

回答状況

【高専枠】

First Accepted: -

Accepted people: 0

Accepted rate: 0%

Trying people: 1

Total submit 6

寂しいですネ.

【一般枠】

First Accepted: k_yuridenamida (42:52)

Accepted people: 11

Accepted rate: 21 %

Trying people: 15

Total submit 52

解法
  • この問題は与えられる点群から最も離れた点のその距離を求める問題と言い換えれることに気づけたら、あとは頑張って思いついた実装をします。気づけなくても僕みたいな方法で強引に(この問題なら)解けます。
  • writer解は、まず円の半径を二分探索で決めるとして、

円と円の交点,長方形の辺と円の交点,長方形の頂点

の全てについてその0.00001くらいずれた周辺を0.5度刻みで360度調べるというお粗末な方法でした。それでもテストケースでは全てテスターの解と精度もほとんど一致しました。ただ撃墜できるかもしれません。

  • テスター解は調べる平面を（右上，左上，右下，左下）の４つにぶったぎっていって、今までに見つかってる最も遠い距離と、今見ている矩形の四つ角の頂点について調べて、この矩形の中に最も遠い距離を得れるような点を見つけられる見込みがないと判断したらばっさり切り捨てるという方法で解いていました。計算量は謎ですが僕のよりかはかなり速かったです。
  • 競技者の中には、ボロノイ図上の辺で山登りしてみたり、ドロネー三角形の外心とか端を使って解いた人がいたらしいですが、よく分かりません。ただ後者を使うとO(N^3)で求まるらしいし爆速でした。かなり色々な解法がありました。

I Card Game

感想

  • 予想外にJOIerからの評判が良かった問題です。
  • KUPCの時からこの問題に対する構想はあって、既出なのかなあと思いつつ出しました。
  • この問題は本選問２と酷似していると思い込んでいてボツになる予定だったのですが、冷静に問題文を読んでみるとそんなことなかった。

回答状況

【高専枠】

First Accepted: siquare (126:50)

Accepted people: 2

Accepted rate: 28 %

Trying people: 4

Total submit 7

【一般枠】

First Accepted: tomerun (16:50)

Accepted people: 20

Accepted rate: 76 %

Trying people: 21

Total submit 26

解法

  • 与えられる紙は５枚でかつ相異なる色という条件を押さえた上で解くことが重要です。
  • あと、出来るだけ先頭にある組を優先して取り除くのが最善ということに気づくのも重要です。
  • 高々５枚ということは、5!=120なの順列生成で、決め打ちしてもよさそうです。順列生成の方法としてはC++だとnext_permutationというSTLの便利な関数があります。
  • 決め打ちした上で、先頭から貪欲にカードを取っていくとかやるとO(n!*m^2)とかでヤバイ計算量になります。
  • そこで、相異なる色ということを利用するとシンプルなＤＰチックなことが出来ます。どうやるかというと、先頭からループするとして、
  • 今までに出現した色の数を足していくのですが、決め打ちしたカードの中の1個目の色については、出現したら普通に足すだけでよい。
  • 2個目以降については、

その色のカード数=min(その色のカード数+1,それより前の色のカード数のうち最小のもの)

としてやればよい。

  • 要するに、もし1個目の色が今までに1つしか出現してなくて、2個目の色が2個目出現してしまったときには、1個の組しか作れないからそれを防ぐみたいな。
  • そうやるとO(n!*nm)で間に合います。実際は直前のカードだけをmin取るときの比較対象にすればいいので、それをやるとO(n!*m)でもっと速い。
  • 分かりづらいと思うのでまた機会があれば画像で説明するかも(?)。

J Favorite Number

感想

  • 純粋な解法としては一番難しい問題として出題したつもりでした。あとコーナーケースも用意したつもりでした。
  • 一般の恐い方々はこの問題とＦで足止め出来ていたかなと思います、k_yuridenamidaさんの前では無力でしたが。
  • 想定誤解法はただのＢＦＳとか順列とかで、さすがに通せないようなケースをたくさん入れました。

回答状況

【高専枠】

First Accepted: -

Accepted people: 0

Accepted rate: 0 %

Trying people: 3

Total submit 10

【一般枠】

First Accepted: k_yuridenamida (69:24)

Accepted people: 9

Accepted rate: 21 %

Trying people: 11

Total submit 42

解法
  • 想定解法は巡回セールスマン問題のＤＰ＋Dijkstraです。前者で順列を使ってO(n!)かかったり、後者でＢＦＳを使って10^9個の状態数を作ってしまうと死にます。
  • 各点同士の移動コストをグラフに出来ればあとは巡回セールスマンのＤＰをするだけなので、主にそのコストを求めることを解説します。巡回セールスマン問題ってなんだって人は蟻本読んだりググったりしてみてください。
  • 気づくべき事実としては、ある地点にx^2への遷移を使わず、移動するコストは、xからyに直接移動するとき、

|x-y|=1のとき2 , それ以外のとき|x-y|/3を切り上げた値。

ということです。これはＤＰをしたり手計算で実験したりすると自然に得られるはずです。

  • あとは、x^2に遷移するタイミングを考えます。正直どのタイミングで掛け算使ったらいいか分かりませんよね。そこで、経路を逆算することを考えます。
  • 例えば、aからa^2に遷移してbに行く時、bからa^2に遷移してaに移動することを考えるということです。
  • その考え方で逆算すると、x^2する操作が平方数を√xする操作に変わります。
  • 直観的にb付近の平方数だけ調べてそこから遷移すればよさそうです。
  • その直観は大体あたっていて、値が大きい場合には必ず普通に移動するより必ず良い結果が得られます。
  • 値が小さい場合には、これが成り立たないことがあります。それは、

(直接移動するコスト) >= (何かの平方数を経由してそこにたどり着くコスト)

の場合です。これは小さいケースでしか成り立ちません。証明は省きます。

  • 実際にこれが元になってWAを出すケースは{3,17}のケースしかありません。

3->(二乗 コスト1)->9->(直接 コスト3)->17 (コスト4)

が最短ですが、17付近の平方数(16とか25)を経由するとコストが5になります。

  • 以上の性質を使ってダイクストラをすればコストが求めれます。
  • {3,17}ケースはケース番号3とケース番号17に入れておきましたが、さすがにこれで気づけた人いないんじゃないかなって思います。
  • このコスト求める部分の計算量は見積もっていませんが多分Ｏ（√お気に入りの数の最大）よりはかなり小さいと思います。収束めちゃくちゃ速いので。
  • 参加者の中には、40000くらいの値まで細かく調べて解いた人もいるみたいです(半分探索?)。
  • 余裕をもって付近を調べておくと{3,17}で死ぬことがないので余裕を持ちましょう。

最後に

  • 読み直してないので誤植多いと思います。あったら教えてください。質問とかあったらコメントください。

あわせてよんでね

解答例(ソース):