Google Code Jam 2010 Round 1B

全問正解への道は険しい...

A. File Fix-it

今あるディレクトリのリストと、作りたいディレクトリのリストが与えられます。
何回 mkdir すればいいでしょう？
- 親が無いと子ディレクトリは作れません。
  - なにもないところに /hoge/fuga/piyo を作りたかったら
    - mkdir /hoge
    - mkdir /hoge/fuga
    - mkdir /hoge/fuga/piyo
  - 3回必要です。
----
パスをvector<string>で持つようにしてsetに叩き込む。
- あまり知られていないと思いますが、setのinsertは iterator (挿入された要素のイテレータ) と bool (その要素が既に入っていたか) のペアを返します。
- if(s.insert(v).second) というフレーズは超便利。おすすめです。
10分間クッキングでした。

B. Picking Up Chicks

N人の人たちがカイジのように電流鉄骨渡りをします。
- いやそんなシチュエーションじゃないけど
各人の位置と速度が与えられます。
前の人に追いついても追い越すことができず、前の人の速度に合わせられます。
- AさんがBさんに追いついたとき、クレーンを1回使うと、AさんはBさんを追い越すことができます。
  - 追い越しは一瞬で行われます。
  - 一ヶ所に3人以上いても、追い越しは各ペアごとに1回ずつ必要です。
時刻 T までに、少なくともK人がゴールするようにしたいです。
最低何回クレーンを使わなければならないでしょう？
----
Nがでかいと大変そうだなぁ。
- segment treeか平方分割とか使いそうな気がする。
眠くなってきた。
- A-largeが通ってれば1,000位に入りそうな気がするし、帰って寝ちゃおうかな。
...
...え？
Largeでも 1<=N<=50 だと？
...
各人について、時刻 T までにゴールするには最低何人追い越さなければならないかを求めて。
追い越す人数が少ない人から K 人を使えばよろしゅうございませんか？
書いた。
送った。
通った。

C. Your Rank is Pure

S を {2, 3, 4, ..., n} の部分集合とします。
n は S に対して pure とは、
- n は S の n' 番目に大きい元であり、
- n' は S の n'' 番目に大きい元であり、
- n'' は S の n''' 番目に大きい元であり、
- ...
- n''...' は S の一番小さな元
となっていることです。
- 例えば 5 は {2, 3, 5} に対して pure.
N が与えられます。N に対して pure となるような S はいくつあるでしょう？
- mod 100003 でおねがいします。
----
うーむ全然分からん。
sample input/output は 5 -> 5, 6 -> 8.
まずはこれを書き出してみ
...
もしかして: フィボナッチ数列
...
いやいやいやいやそんなばかな。
- でも1AのCもフィボナッチっぽかったよね。
- N = 2 .. 4 まで手計算しよう。話はそれからだ。
- ...フィボナッチになってる！
- 実！装！
Incorrect.
...
...
まぁ、当たり前ですよね。Largeで30点もくれるんだし。
じゃあ small (N <= 25) の全探索書いて得点拾いつつ規則性探そう。
- つか、全探索書いてからフィボナッチしなさいよばか。
書いた。submit.
Incorrect. あれ？
...
...
...
30分以上コードを眺めていても全然バグが見付からない...
もしかして送信ミスったのかな。ペナルティ少ないし、もう1回送ろう。
Correct. えー...
- いやとにかくLargeだ。
とりあえず何も考えずに数列検索に投げてみよう。
- 競技プログラマの嗜みですね。
ドンピシャでヒットした。これは勝てる！
- って、このページごちゃごちゃしてて分かりにくいな。これか？いや違う、この式か？これっぽいな。
できた。smallとも一致した。
Largeも実行だ！
...
...
終わらない。
- よく見たら O(N³) (N <= 500) になってる。これはマズいか？
- でも8分間ではこれ以上速くできそうにないし...
- きっともうすぐ終わると信じて待ってたけど、終わらないまま Time Expired...
やることなくなったので、参加記録書こう。

Result

書いてるうちに終わった。A, B通って498位通過。

ふと、C-largeがまだ走りっぱなしなのに気付いた。
- え？いくら何でも遅すぎないか？ 500³ だぞ？
止めて入念にテストしてみよう。
30だとちょっともっさり。40だと帰ってこない。
- そんなバカな！
...
ああああああああぁぁぁぁぁぁ！！！
メモ再帰のメモしましたよフラグを立てるの忘れてたぁぁぁぁぁぁぁ！！！
立ててみた。500も一瞬で出てきた...
- もちろんCorrect.
今夜はさめざめと泣きながら眠ります。