読者です 読者をやめる 読者になる 読者になる

PCK本戦2012

最後のPCKでした。結論から言うと4位/32ちーむでした。負けました。

去年の満足度を114とすると今年は514くらいなんですけど、やっぱり(3位以内)入賞できなくて悔しいという気持ちもあります。

問1

本質だけ抽出すれば有限オートマトン?と文字列が与えられて、マッチしているかを判定する問題。

ぜんぜん読めないので僕が問2を読んでいる間にrefiuteに読んでもらう。

なぜかTLEしてしまって申し訳ない気持ちになる。二回目でAC.

問2

軽い愚直なシミュレーションを行う問題。refiuteに半分くらい読んでもらった。

空白があったら詰めるの意味をなぜか勘違いしていて、サンプルがずっと合わなくて、紙デバッグしてもらう。いろいろ探した挙句、refiuteに読解ミス指摘されてそこ直して提出。

問3

refiuteが全訳してくれた。

なんか16進表現の符号付小数点数を10進数に直す問題。

まず32bitの2進数に直してそれぞれ変換してごにょる。

doubleは2で割ったりする分には誤差考えなくていいことを知っていたので、適当にやると通った。

問4

『扇形に対する点の内外判定』+『実装』をする問題。問題の条件より誤差は考えなくていいかんじ。

「とりあえず日本語やばいけどすげぇ簡単そうだゾ~」みたいなことをrefiuteが言ってきたので、実装する。

最初内外判定を、

  • 原点を基準として扇形の角度から2つの無限遠点を出し、それと原点の3点からなる三角形の中で内外判定した上で、原点から点の距離が扇形の半径rより小さければ包含している

みたいな判定しようとしていてヤバくて、refiuteが角度出すだけでよくねと言ったのでそうしました。

θが負の時、atan2の返り値が-θなのか2π-θなのか分からないので適当に2~3通り試した。

一回目の提出ではWAで、原因が分からないので紙デバッグしてもらい、変数名ミスが炙り出される。

二回目の提出でAC.

問5

最初に長さ30万以下の数列(値も30万以下)が与えられて、10万個以下の『a[i](i=1...n)をxで割った余りをmod[i]とするとき、mod[i]の最大はいくつか』という整数xからなるクエリが与えられる。それぞれのクエリに応答しなさい。

という問題。

refiuteに「こういうの得意でしょ」とか渡される。(本人数論だと思ってたらしい)

とりあえず問4のためにライブラリ写してもらってる途中に考える。

データ構造・・・?クエリ・・・?O(NQ)から落とせる気しないし、去年のスコーンより難しいと思っていたけど、5分くらい問題文とにらめっこしてたら「同じ値のクエリが与えられない」とかいう謎制約に気が引っかかって、少し考えたらO(NQ log N)だと思ってた解法がO(Q log^2 N)であることに気づき、コーディング。

これに気づいたとき、「気づいてしまった・・・」感があってテンション上がり気味でrefiuteに説明しコーディング。ACうれしい。

問6

『1~nからなる値の順列が与えられるので、それは何番目の順列かを素数で割った余りを出力しなさい。(実際は制約がこの一般化された問題より緩い)』

という問題。

これJOI合宿で見たわーやべえわーとかなってた。(あれを適当に解いたのを猛烈に後悔した)

BITやるだけだと思ったのに、書いてみたら微妙にサンプル合わなくて、自分の頭が残念と早合点して、「C言語によるアルゴリズム辞典」とかに載ってないかな~とか期待しながら、それを読む。

すると、「1~nの数からなる順列に対して、1:1対応するように番号を振る。比較ができればよい」

とか書いてあって、これは答え直結やなあとか思ってたら、写したのに答えが合わず、ライブラリが間違ってるんじゃないか・・・?(絶望)とか考えてかなり時間が過ぎる。バグっぽいところをrefiuteに探してもらう。

最後の最後になって、ライブラリが1:1対応する(=辞書順に振るとは言ってない)に気づいて軽く絶望して、自分で考えてコード書いてみたら今度はサンプルが通って、終了数分前に提出。AC.やったぁ。

問7

"わたし"と"彼女"が謎のモンスターゲームで戦う問題。

refiuteがやるだけに見えるんよ~って言ってるけど、なんか見たとき正答率が17%とかで罠があると感じて手を出すか悩んでいた。

ソートするだけじゃ駄目だと思い込み、自分が対戦してる気持ちになって以下の戦略を行ったら解けた。

  • 彼女は、わたしに勝てるか引き分けれるとき、勝てるモンスターでギリギリ強いやつを出す。
  • 彼女は、わたしにどうあがいても負けるとき、クソザコを生贄にする。

実際、こんなことしなくてもよかったかもしれないけど、直感的だったのでこれをmultisetを使って実装した。

一発でACした。

refiuteに何も言わず通してしまったので「うそん」とか言っていた。


問8

双対グラフを構築する問題。refiuteに読んでもらった。

残り1時間になったとき、問6,問8,問9,問10が解けていなくて、どれを解くか悩んでいたが、結局双対グラフの構築が無理ということになり、諦めた。

解けませんでした。

問9

問題文が長かったし、読んだ時点で時間なかったので読んでないしrefiuteにも聞いてないのでわかりません。

フローだったらしい。

解けませんでした。

問10

割と最初のほうに読んだが後回しにしていた問題。refiuteによんでもらった。

グラフがある。aからbの最短経路でc,dを通ってたどり着けるような経路は存在するか。

頂点・辺の数は馬鹿でかいけど、クエリ数が40000と少なくて、データセット1つずつだったので、20sであることをフル活用する問題なのかな?と思いつつ、解法を考えていた。

うまくDPの形に落としてCFっぽいビットパラレル(もしくは枝刈再帰でごり押し)しようとかそういうことを企んでいた。

とりあえず、DAGにならないと思っていた(アホすぎ)最短経路に使う辺だけを使うグラフが最短経路DAGだったらしく、そこに気づけなかったのでまあ解けなかったんだろう。

解けませんでした。

感想

※ここでは問題しゅうへんに関しての感想を述べます。

  • 今年のPCKはすべての問題がとても面白くて、去年とは本当に一新されていてすごいなと思いました。
  • 3位取れなかったのは悔しいですが、順当だったと思います。もう少し問6を早く解いて問10着手したかったかもなあ。
  • 解説で問8の解法を知って感動していた。
  • 本当に楽しかったです。
  • 自分が確実に解ける問題を確実に解けた点に関しては、達成できてとても満足。