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

spark573’s blog

こゃーん

ICPC 参加記

6/24(金)のICPCに、僕と後輩(naotti)と同級生(enbun)の三人で参加してました。

チーム名は「Freedom Life」

 

~コンテスト開始~

まずは問題文を印刷して、問題ごとに分ける。

naottiはプロだけどenbunは競プロは全然やらない人なので、enbunにいろいろやってもらった。

この作業の間にnaottiがA問題を通していた。

 

とりあえずBを読む。

イムリーな問題という感想。

i番目まで票が入ったときに、一番票を得ている人の票の数が、他の人がとりうる最大の票数を上回ればその時点が答えになると気付く。

サクッと実装しようとするが何故か手こずる 緊張のせい?

一回バグらせて交代した後に修正してACした。

 

そして僕がBを書いてる間にnaottiがCとDの解法を生やしたと言っていた。プロ。

とりあえずCとDは任せてEとFあたりを読んでみる。

enbunがFの問題についての説明をしてくれた。しかしこれは難しそう。

Eを読んで、1次元の場合について考察してみたが何も生えない。頭が弱い。

Eは投げてFの考察をしてみる。

黒と白の領域をまず数えて、領域の数が違えば明らかにnoを出力出来るということまでは分かった。

サンプル見たら、noになってるケースが全部領域の数の違いで落ちてたので、ワンチャンこの判定だけで通らないかと思って実装することにした。

通らないにしても真の解法でも領域数える部分は書く必要があるのも一つの理由。

ここまで考えたところでnaottiがCをAC。やりますねぇ!

 

交代してFを書き始める。

想像以上に実装が面倒で手こずる。どんどんバグが出る。時間も経つ。

なんとか書き終えたがサンプルが合わない。

仕方がないのでコード印刷して、D担当のnaottiにバトンパス。

印刷したコードを目で追ってデバッグ

少ししたらバグの場所が分かった。しかしnaottiがコーディングなうなので他の問題を読んでみることにした。

Gを読む。分からん。

Gわかんねーってなっていたら後輩がDをバグらせたらしく、交代してFのデバッグをした。

 

そしてまたバグった。

 

ふええええって言いながらデバッグしてたらサンプルが通った。

ダメもとで提出してみる。

 

 

 

ダメでした。

 

enbunと一緒に「ですよねー」と言う。

 

再びFの考察をしたらあっさりコーナーケースが見つかった。ていうか問題文の包含の説明に出てくる図が既にコーナーケース・・・

 

夢中になっていたらコンテスト残り30分。

 

Fの考察を続けていたら、naottiがDの嘘解法を書いていたと言っててつらそうだった。

ここでDを一緒に考えるべきだっただろうが、Fの考察を続けていた。

それでもやっぱり無理そうだったので残り時間10分くらいになってDに加勢。ブレブレである。

問題文を読んだが、「DPかな?(直感)」くらいの感想しか出なかったし、naottiもDPDP言っていたので僕が力になれることは無さそうな感じだった。ゆるして。

 

そしてコンテスト終了。

3完でした。心の中では4完以上狙っていたし、naottiも同じく4完くらいは狙っていたと思うので残念だと思うと同時に申し訳ない。

 

良かった点はスタートしてからすぐの作業、担当問題の分担。

悪かった点はそれ以外全てでしょうか・・・

僕自身コーディングに時間かけすぎだし、その上バグらせていたので目もあてられない。

反省と復習をして来年に臨みたいと思いました。

 

(6/27 追記)

E問題の誤読をしていたことに気が付きました・・・

選択するk個の立方体は「連結」しているんですね・・・

Twitterで皆が自明自明言っててふえぇ分からない>< って思っていたけど確かにこれは自明・・・

連結の状態をグラフなり何なりに表すのがO(N^2)くらい、そこからk個連続したものを取り出すパターンを全て試すのもO(NK)くらいでいけますね・・・

 

naottiとenbunに土下座してきます