読者です 読者をやめる 読者になる 読者になる

パソコン甲子園2010予選の思いついた解法

もうそろそろ書いていいだろう。自分の中のメモとしても。

問1:やるだけ。なんか頭が混乱する問題だった。

問2:どんな問題か忘れた。

問3:やるだけ。

問4:自分は問題文読んでないから分からない。

問5:

二進数。整数部分と小数点以下部分に分ける。

そんで、整数部分は512未満(8bitで表せられる)かチェック。小数点部分は0.5と0.25と0.125と0.0625を使って表せれるかチェック。

もっと効率的な解法あるらしい。

問6:

C++ならstringstreamなど使って整数⇔文字列する。

そんで1万までのstring型配列FizzBuzzリスト生成してチェックしてく。

問7:100(1000)万?までの素数リストを生成してからやるだけ。

問8:兄弟の座標それぞれをノードとして持った幅優先探索

問9:

問題文持ってなくて分からない。これだけは本番で真っ向から捨てる気持ちでいった。(permutation+dijkstraらしいけど)

問10:

文字の最初と最後だけを管理した配列(連想配列でも良い)を使ってバックトラック等で繋がってるか調べる。そのままやると非現実的なオーダーになるが、最初と最後の文字だけでやれば大幅枝狩り。

まあ本番で大半が誤解答で終わったんですが。(主に俺の書いたソース)