最後の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の解法を知って感動していた。
- 本当に楽しかったです。
- 自分が確実に解ける問題を確実に解けた点に関しては、達成できてとても満足。
