AOJ 1627 Playoff by all the teams (ICPC Domestic 2018 D)
基礎的な内容の復習をしながら、ICPCの問題を埋めることにした。AOJ-ICPCで適当な難易度の問題から埋めていこうと思ったら、去年のD問題だった。過去問として残しておいても良かったが、目についてしまったので解いた。
初めは賢く解く方法があるのではないかと考えていたが、どうやら最悪の場合でも10^7通りくらいしかない（実際に計算したら3,230,080通りだったので概算としては良いかな）ことが分かったので、シンプルに数えることにした。
トーナメント表の上三角部分を左上から埋めていけば確定していくので、各チームが残り何回勝って良いか、負けてよいかという値をキーとして、DPみたいな感じでその時点までで何通りあるのかを足し合わせていった。かなり枝が刈られるので時間は余裕があると思っていたが、実装してみると最悪の場合は手元で数秒かかってしまった。今回は制限が8秒だったので問題なくACになったが、もうすこしまともに計算複雑度を概算できるようになりたい。
C++が分からなすぎたので色々と調べながらやっていたら実装に一時間以上かかってしまったので、本番だったら完全にダメですね。最低限の知識と実装力をつけたい。
