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

私が歌川です

@utgwkk が書いている

ICPC2016 国内予選に参加しました

チーム YoukaiGirl として、サークルの人たちと参加しました。結果は3完で116位でした。

ぼくは基本的に実装をしていて、ほかの2人に先に解法を考えてもらっていました。

A (1WA)

異なる i≠j に対して abs(a[i] - a[j]) の最小値を取る。 これだけなんだけど、提出ミスってもったいないペナルティが付いた。

B (2WA?)

前から順に、得票数を map<string, int> とかに記録していく。ダミーデータを用意しておくと場合分けが少なくなるというのにしばらくしてから気付いた。

i票目まで見た段階で、 (1位の得票数) > (2位の得票数) + (n - i) だったら当確。そうならなかったらTIE。

最初は雑に書いてて、バグらせてしまって苦労した。よく考えるとそんなに複雑な解法ではなかった。

C

B がバグってたのでこっちを先に解いた。チームメンバーが解法を用意してくれていたので実装するだけだった。

区間 [m, m * 2] の整数を素数と見立てるエラトステネスのふるいをしておく(以下ではm素数と呼ぶ)。最大値が問題文に与えられていたのでそこまでやっておく。

カウント変数をcntとかで持っておいて、iをmから初めて、m素数だったらcnt++して、cntがnを越えた時点でのiを出力する。

審判団講評の解法より低速に見えるけど大丈夫かな……(本番は時間内に終われば大丈夫だし)。

D (TLE)

最初は全探索をしようとしたけど、まあオーダー的に無理だったし、うまい枝刈りも思いつかない。

チームメンバーに聞いた解法を実装したけど、なかなかうまくいなかくて、そのまま大会が終わってしまった。

まず0 < i < n - 1 に対して abs(a[i + 1] - a[i]) なら tb[i] = tb[i + 1] = true みたいな感じで、最初の段階で落とせるブロックを記録する。

それから tb[i] == false な i に対して、それよりも左側と右側に落とせるブロックがあるならそこも true にしていくみたいな解法だったと思うけど、うまくいかなかった。

DP で解けるということをあとで知って、あーーーという気持ちです。

E, F, G, H

難しそうなのでパス。

総評

とりあえずC問題までは解けたのでよかったけど、どうせならD問題まで解きたかった……。

だいたい実装しかしていないので、今度は自分でちゃんと解法を練ってからコードを書けるようになりたい。

あと、入力データはちゃんとダウンロードできたか確認しましょう。