■ [練習][PKU]ACM/ICPC2007 Japan（東京大会） 
最近SRMの結果がへぼすぎて凹ましいので、冷静に現状の実力を測ろうと、一発勝負じゃないもので練習してみました。
http://acm.pku.edu.cn/JudgeOnline/searchproblem?field=source&key=Japan+2007
（"Domestic"が付いてない問題群）
結果
表記は「正解時のスタートからの経過時間（分）/間違えた回数」
| A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|
| 10/0 | 20/0 | 43/0 | - | - | 91/0 | 0/1 | 235/0 | - | - |
合計 5問/399min
本番での参加50チーム中13位相当。意外に良かった
問題ごとに
| ID | タイトル | 感想 |
|---|---|---|
| A | And Then There Was One | ヨセフス数。 効率の良い方法を使わなくても普通にシミュレーションしたら通った |
| B | Prime Gap | 素数+探索。やるだけ |
| C | Minimal Backgammon | 典型的DP |
| D | Lowest Pyramid | 幾何。 謎。座標が整数であることを利用してどうにかできるのか？ |
| E | Geometric Map | 実装+グラフ。 グラフができてしまえばダイクストラで終了なんだろうが、その実装がとても厄介。 手を付けたものの完全に方針が見えていない状態で書き始めたため行き詰まり |
| F | Slim Span | 最小全域木。 使用する枝のコストの最小値を変えながら最小全域木を作ってやるとよい |
| G | The Morning after Halloween | 実装がちょっとややこしいビットBFS。 状態数100万くらいだからいけるよね？ と思って書いたらMLE（たぶんTLEでもある） いつもBFS書くのに使ってる方法、効率が悪いのかなぁ |
| H | Bug Hunt | 構文解析。 やるだけなんだけど、コードが汚くなってデバッグに少し時間がかかってしまった |
| I | Most Distant Point from the Sea | 幾何。 2本の辺に接する円を他の辺に接するまでどれだけ大きくできるかを各辺ペアに対して調べるとO(N^3)でいけそう このような方針は立ったけど、実装しようとすると固まってしまう。幾何は苦手です |
| J | The Teacher’s Side of Math | Math。 係数の関係が連立一次方程式になるので線形代数的になんかやったら解けるんじゃなかろうか 学生の時にちゃんと勉強してなかった負債が重い |
