AOJ1612 3D Printing (ICPC Domestic 2016 E)
オーバーラップしている面積を全組み合わせについて計算して、重なりがある場合について面積を重みとして持つ辺でグラフを作れば、次数が高々2なので全探索で最小の表面積（重みの和が最大の連結部分グラフ）を探せば良い。
幾何問題なのでバグらせないようにかなり気をつけて実装していたが、結局バグらせた。そもそもサンプルを通すまでに80分かかっているのだが、テストケースでWAが出てしまい、結局最後まで分からなかった。
バグ自体はシンプルで、グラフがサイクルになっている場合とのときの処理をミスしていた。最近バグらせてしかいないので、なんとかしたい。とりあえず丁寧に丁寧に実装していくという方針を続けてみる。
AOJ 1621 Folding a Ribbon (ICPC Domestic 2017 F)
AOJ 1603 500-yen Saving (ICPC Domestic 2015 D)
問題を見てすぐにDPっぽいということが分かる。使用した最小金額を値として持つということが自然なので、すぐに思いつく解法としては[店の数]×[500円の数]×[小銭]が考えられる。なので通るかと思い、実装した。色々とバグらせてしまい、この時点で50分くらいかかっていた。
まずMLEを受けた。dp表を更新するものに直したらTLEを受けた。AOJで制限が8秒だったが13秒くらいだった。しかし定数倍高速化できそうな要素もないので（だいぶ色々と試してから）諦めて講評を見た。講評によれば想定解の1個目が僕の解法で、2個目は状態として500円の数と使用した金額の組みを状態として持つというものだった。確かに、問題を自然によめばこの解法になる気がする。無意識のうちに見たことがあるDPの解法に落とし込もうとしてしまったかもしれない。
正直、1個目の解法ができたので満足ではあるが、1個目でもかなりバグらせてしまったので反省したい。そろそろリハビリという言い訳も効かなくなってきたので、一問一問を丁寧に解くようにしたい。
AOJ 1619 Making Lunch Boxes (ICPC Domestic 2017 D)
まず問題を見た時点でDPだということが分かる。そして、制約がなので、
が
くらいになることがわかる。
想定解法はおそらく場合分けしてDPと全探索の二通りの解法で書くんだろうなと予想していて、実際に講評の解法の1個目はそうなっていた。しかし、上の制約からDPの（実際に登場する）状態数が小さいことがわかるので、mapを使えば1つの手法で実装が済むということがわかる。これは講評の2個目の解法になっていて、考察としては完璧だった。
ただのDPなので20分くらいで実装が終わったが、制限8秒のところ14秒くらいかかっていた。細かいことは分からない（ちゃんと調べたい）がmapが結構遅いということは知っていたので、色々と定数倍高速化して頑張ってみたが間に合わなかった。結局、が小さい場合には普通のDPに書き換えることで通した。この6秒を絞り出すのに80分くらいかかってしまった。本番では通るので、この問題については悪くなかったということにしておく。
AOJ 1196 Bridge Removal (ICPC Domestic 2014 E)
島の数がnで橋の数がn-1の連結なグラフなのでサイクルが存在しないということが分かれば簡単な問題。次数が1の島には行かないで橋を撤去するだけ、次数が2以上の島にはいって帰ってきて橋を撤去する、という時間を合計してから次数が1の島を除いたグラフの二点間の最長距離を引く（この二点が始点と終点になる）。
距離が最長の二点を探すときに実装が簡単だしなのでWF法で良いと思ったのだが、AOJは全サンプルを指定時間内に終えないといけないのでTLEになった。この時点では30分台で実装できていたし、本番では間に合うくらいの速度だったので悪くなかったと思う。距離をBFSで求めるコードに書き換えてAC。
AOJ 1168 Off Balance (ICPC Domestic 2010 D)
ブロックが樹上になっていることがポイントで、一番下から再帰的にブロックの配置を表した木を作り、重心も再帰的に計算する。
このくらいの実装量になると自分がバグらせることは目に見えていたので出来るだけ書き始める前に構成を決めていって、40分程度で書きあがった。しかし、結局バグらせてしまい異常に時間を使った。こういうことを繰り返すのは良くない。方向性は良いと思うので、もっと綿密に書く前に構成を詰めていきたい。あとは、面倒臭がって冗長性のあるコードを書いていると、勘違いなどで修正をしたときに一部修正を忘れてしまいバグに繋がると言うケースが良くある。実装を速くしたいという気持ちが先立ってしまうが、綺麗なコードを書くことを心がけることがバグを減らすことに繋がると言い聞かせて急ぎすぎないようにしたい。
AOJ 1157 Roll-A-Big-Ball (ICPC Domestic 2008 E)
基礎的な幾何問題。問題文を読んで簡単そうだと思ったのだが、実装に無限に時間をかけてしまった上に凄くバグらせた。実装を始める前に構成は軽く考えていたのだが、考えていなかったコーナーケースへの対応などでどんどん酷いコードになっていった。どうも幾何問題への特別な対策が必要な気がする。
