今回チームとして誘われて、ちゃっく君(@chakku_000)といしづ君(@ish_774)と一緒にICPCの国内予選に出ていた。結果は3完、97位だった。
ACM-ICPC 2016 Asia Tsukuba Regional | 国際大学対抗プログラミングコンテスト2016アジア地区つくば大会
今回の方針として、ABCを2人に任せて、自分はDEあたりを解いていた。
チームが書いたソースコード(A~E): ACM-ICPC 2016 国内予選 - team: nikku (A: AC, B: AC, C: AC, D: WA, E: WA) · GitHub
以下、自分が解いていたD問題,E問題のお話
D問題 「ダルマ落とし」
ブロックが積まれてて、重さの差が1以下のもの２つずつを落とす時に、最大何個落とせるかを求める問題
とりあえず、昔解いた問題に似ていたので解法は区間DPだとすぐわかった。
(似ていたのは、Typical DP ContestのI問題だった)
この解法の記憶を元に実装 ---> サンプルケース全部通ったやったぜ ---> 提出ケースが落ちたつらい ---> †絶望†
みたいな流れを踏んでしまった。
最後には二人に見てもらったが修正できず終わってしまった。
あとで気づいたけど、悪かったのは考慮するケースが足りてなかったことで、
a[__]b, ab[__], [__]abみたいなケースは想定していたけど、[__][__]のケースは想定し忘れていて
10 9 1 3 3 1 5 7 7 5 9
みたいなケースに弱かったらしい。
この問題は昔解いた解法をきちんと生かせずに無駄にしてしまったので悔しい。
E問題 「3D プリント」
立方体がn個あって、そのうち連結したk個に絞って、表面積を最小にする問題
D問題が解けないため、解けそうだなと思ったこっちをとりあえず実装し始めた。
方針としては、立方体を頂点、重なっていることを辺とみなして、各頂点から重なる表面積が高いものを繋いでいく方法(Prim法をk個の頂点に絞ったもの)で実装したけど、ダメダメな解法だった。
こっちもサンプルケース全部通って、提出ケース落ちしたので†絶望†だった。
結局この問題では、貪欲だと厳しいケースをきちんと考えない、いい加減さを出してしまった。
あと、問題文からグラフが鎖、環であることをきちんと認識できてなかったので雑魚だった。
反省
今回の国内予選ではケースの見落としが顕著に出てしまい、自分としてはよろしくない結果になってしまった。
チーム2人はABCを通してくれたのに、自分は一つも通せなかったので非常に申し訳なかった。
今回のためにチームとして基本練習しなかったので、チームとしての良い戦略が分かってなかった。やっぱりチームで出るので、ケース見落としを防ぐためにきちんと話し合うことぐらいはしても良かったかもしれない。
問題文をきちんと読んで解法やケースを考え、正しい実装ができる人間に早くなりたい（－＿－；）
