ACM/ICPC模擬国内予選

ACM/ICPC模擬国内予選 6/27 14:30~17:30

ACM-ICPC OB/OGの会では，毎年ACM-ICPC 国内予選の練習会を開催しています．ということで参加してきました．

チームの詳細は以下．
・大学名
Tokyo National College of Technology(東京高専)
・チーム名
nyama
・メンバ
todo
nyama
ando(都合により模擬予選は不参加)

■Problem A 連続する整数の和
入力される数値が小さいため，単純な2重ループで通す．
ちなみに，実装担当はtodo．

■Problem B ムーンライト牧場
todoがProblem Aを解いている間，問題をnyamaに読んでもらい，収入効率の計算式を作ってもらう．計算式が間違っていたため，一度WAを食らった．計算式を直したら問題なくAC．
式が分数だったため，分数の比較にした方がいいかなと思ったが，実数の(愚直な)比較のまま通ってしまった．
本当は，整数a，b，c，dに対し，
a/b<c/d
を判定するためには，
ad<bc
と書いたほうが良い．
あるいは，実数a，bに対し，
a<b
を判定するには，
(a-b)<EPS

この時点で上位のチームは4問提出していたので焦る．

■Problem C 差分パルス符号変調
二乗誤差を最小にする問題．ここで早くも息詰まる．2人で考えたが解法が思いつかないので一旦パスして他の問題にあたった．
その後，やっと[y_i][入力信号]のDPで解けばいいことに気付きサクッと実装．ほぼ一発で通った．

■Problem D Mr. リトー郵便局
最短移動時間を求める問題．全く解法が浮かばなかった．
解法はワーシャルフロイド法とのこと．

■Problem E 不死の宝石
問題内容は簡単．しかし，棒をどのように置けば良いかさっぱり検討がつかない．解法を話し合う内，nyamaの「2つの円の接線」という言葉でPOJにあった類似問題を思い出す．まず，2つの円に対し(今回は)高々16種類の接線を考えればよい．また，n個の円から2つの円を選び出すパターンはnC2通り，つまりO(n²)．そして，ある接線について，いくつの円が条件を満たしているかを調べるのはO(n)．ということで，せいぜいO(n³)．ここまでで脳内コーディングが終了したので後は実装するだけ．一度WAを食らったが，円が1つしか無い時の例外処理が間違っていて，入力がずれていた所為だった．時間がもう残り少ないのと，計算誤差が不安だったが，修正後は一発で通った．

■Problem F 閘門式運河: 上下に動く水面
実装ゲーっぽかったけど，そこまで解く時間が無かった．

■Problem G 魔法島物語2
二分法で解けるんじゃね?と思ったが，多角形(?)の内部に集落があるかの判定が難しかったのと，すでに時間が無かったので敢え無く終了．

■結果
○○○×○××
14/158

予想以上の結果に驚き．これが東京高専の本気(ｷﾘｯ