ICPC2018国内予選参加記 Tech-ONC

2018年7月6日

TNP

#プログラミング#競技プログラミング

こんばんえるえる〜〜毎度ガナリヤです！部室行かなくてすいません！活動はしてるんです！集中力の問題で家でやってます･･･(お兄さん許して･･･) 今日は、ICPC国内予選に参加したので、来年のリベンジのために参加記を残しておこうとおもいます。　　

チーム Tech-ONC

チームTech-ONCはTNP部員かつ、同じ競技プログラミングバイト先の三人で構成されています。思考力・実装力担当の我らが部長！こしょう！ C++の魔法使い！サバ！手広無力おじさん！ガナリヤ！の三人です。このチームの特徴として

普段アルバイトで、競技プログラミング問題制作を行っている
得意なことがそれぞれ違い、バランスが取れている
三人共コーディングを担当できる
いい意味でも悪い意味でも、そこまで競技プログラミングコーディング力が離れていない(他チームは、一人だけ無茶苦茶強いところが多かったりする)

という点があります。僕が誘わせていただき、引き受けていただきて本当に嬉しかったです！

参加記

事前準備

統計の授業を三人で抜け出してご飯を食べる。チョコレートがおいしかった。その後、コーディング場に移動し、それぞれマクロや本の準備をしていた。その間、サバがVisualStudio設定RTAしてて面白かったです、来年は僕も設定できるようになりたい

16:10頃、監督の先生が到着(本当に引き受けていただきありがとうございます！) 雑談をしつつ、そわそわしながら開始を待つ。　　

ICPC予選開始

16:30から予選開始。サバニキが印刷をぶん回しつつ、僕がA問題の紙を読み、こしょうがB問題の紙を読み始めました。その間、サバがVisualStudioの設定やマクロの準備をしており、縁の下の力持ちでした！(またnext_combinationの実装もしてもらってしまった･･･来年までにはもっと簡単な実装にします･･･)サバありがとう！

A問題　所得格差は、N人の合計の平均を取って、平均より小さい人数を数えるだけの問題で非常に簡単でやるだけでした。年々A問題は簡単になっている気がする･･･ハラハラしつつ、doubleのガバに気をつけてAC

B問題とC問題

A問題を解いた後、こしょうがB問題へ。僕とサバでC問題に移動。

こしょうにきが解いている間、C問題を二人で話し合う。 C問題みなとハルカス

C問題は、整数bが与えられ、1~Nまでの中で連続した整数の和がbに一致する中で、最長のものを出力せよという問題でした。二人で話し合った結果、部分累積和で10^8までぶん回すか、しゃくとり法で実装するかの二択になりました。ここで壮大なミス。絶対に部分累積和じゃ通らないのに、部分累積和の案を採用。ふたりともしゃくとり法はあまりお得意なお気持ちではないため、部分累積和に逃げてしまった･･･、このミスが無ければDの実装が間に合ったかもしれない(申し訳ない)

間違った部分累積和の実装が行けそうになったとき、こしょうの実装でエラーが発生していた模様。コードを印刷してもらって、エディタを空けてもらって入れ替わりで僕が嘘解法を実装。ちなみに、今回のB問題はCよりずっと難しかったようで、さらっと解いてるこしょうやっぱやばい。

嘘解法のCを実装した僕「できた！天才か〜〜〜？」←嘘解法で喜んでいるクズの図 10^9の実装のため、テストケースだけ通して、もう一度こしょうと交代。こしょうがB問題の添字ミスと、問題文の勘違いに気づいたらしく難なくAC。こしょうにきは、問題文読み間違い以外基本的にすべて通している(すごい(すごい))

その後、こしょうに変わってもらって、投げていたテストケースを見ると、数が合っておらず、嘘解法であったことに気づく(当たり前だよなぁ？) 急いで、しゃくとり法で実装してAC。やっぱ最初からしゃくとり法にするべきでした、チキっちゃだめやね･･･　　

D問題

ここから毎回僕たちが苦戦しているD問題以降パートへ。

サバニキがD問題とE問題に目をつけていて、問題概要や、解き方のコツを教えてもらった。 D問題全チームによるプレーオフは、サッカーの試合をするとき、すべてのチームの勝敗が一致し、全員で仲良しになる総数は何個あるか？という問題だった。

僕とサバでDはやべえな･･･となり、他の問題をいろいろ見ていた。よくよく考えるとこれが悪手だった気がする。最初からずっとDのみに取り組んでいれば、時間が間に合ったかもしれない(悔しい･･･)

その後、こしょうもDに参戦し、こしょうとサバが解き方の方針を教えてくれた。(5人なら、必ず全てのチームが2勝2敗とか、普段の自分一人のコーディングなら絶対に気づけてない･･･)

その後しばらく三人でDにうなり続け、うだうだ言いながら、意見を出しつつ、next_combinationで1と0の組み合わせを求めれば計算量はあまり増えないということに気づく(正直合ってるか分からん) よくわからないまま、時間が無いため、僕が突発的に考えた多分正攻法ではない、汚いアイディアを実装することに。僕とこしょうでペアプロしつつ、サバがnext_combinationの実装をしてくれた(来年までにはもっと分かりやすいライブラリつくる許して･･･) こしょうとサバのこしょうを借りつつ、ガバガバ実装を行い、時間と戦いつつ、コーディングが完成。奇跡に祈りつつ、実行したところ、添字エラー。添字エラーを解消している中で、時間になってしまった･･･

振り返り

ICPCに参戦してみて、すんごい楽しかったです。他の人と、問題を解くためのアイディア出し合ったり、ふざけながら問題通すのって、学生のうちしかできない気がする(仕事になると、ふざけることはできない･･･) また、自分の実装の弱さに気付かされた回でもありました･･･。他の二人の実装がすごい綺麗で、僕のコーディングがかなり汚いので、デバッグしづらくて二人がかなり僕のコードを追うの辛かったと思います。もっと簡潔なコーディングできるよう目指していきたいです。

何はともあれ、すごい楽しかった来年もこの三人でTech-ONCとして出るという話をした。来年は三人共、競技プログラミングがうまくなり、僕はAtCoder年内中に青色、来年のICPCまでに黄色になっているはずなので(希望的観測)、来年のチーム名はTech-ONS(O(N^2))でしょうか･･･

何も考えず、今日あったことをそのまま書いているだけで、読みづらいと思います。すいません。それぐらい楽しかったです明日はSoundHound頑張ろうと思います！

ガナリヤでした！