AOJ JOI 2006
一日ぶりです。昨日は仲間の家に泊まってたので、問題は説いてないです。
0510 Score
やるだけ。4つの合計だして比較。
0511 Who Are The Student Yet To Submit
やるだけ。提出した人のフラグを立てて、フラグの立ってない二人を出力とか。
0512 Caesar Cipher
文字に対して-3するとかmapとか配列にconvert用の表を作っとく。よく出てくる問題。
0513 Shuffle The Cards
vectorの扱いに注意。insertとかpush_backとかerase使ってけば解ける。
0514 Quality Checking
解けてないです。解説読むと、自分の方針と同じ。実装にミスが有ったのかも。通った。
0515 School Road
最短経路の数を求める。DPです。実装しやすいように向き変えて。
0516 Maximum Sum
累積和を利用する問題。kがあるおかげでO(n)で解ける。
0517 Lengest Steps
解いてないです。部分点はなんとか解けそうだけど。白いカードがないときの求め方と、バケットを使うとこまでは分かった。
0518 The Oldest Site
O(n4)の解法で部分点1、O(n3)で部分点2、O(n2)で満点かな。正方形の場合、2点が求まるとその2点を頂点とする正方形は2つしかない。残りの2点は定数時間で求められるので4点を総当りする必要はない。
0519 Worst Sportswriter
解いてないです。トポロジカルソートやDFSで解ける。トポロジカルソートは競プロでもよくでるらしい。
0520 Lightest Mobile
解いてないです。最小公倍数と再帰でなんとかなると思ったけど。やっぱりそれでなんとかなるらしい。どこから始めればいいのかわからなかったのと、実装ができない。
制限時間とかは考えずに解いたけど、とりあえず予選の通過ラインは超えていたみたいです。最終的には全問解けたのでうれしい。やっぱり本選になると数学的考察の必要な問題も増えてきて解けなかった。