AOJ 1188 (300)
AOJ-ICPC 3問目
大統領候補者が2人いて、投票で大統領を一人選出する。
各階層において過半数の地区で過半数の票数を得られた者が大統領に選出されるというルールの下、大統領に選出されるための最低得票数を求めるという問題。
括弧付きの計算機を作るのと少し似てるかな、でも階層構造は単純化されてるからこの問題の方が少し簡単かも。
＊解き方
入力を文字列Sとして受け取って、[ ]に囲まれた数字を1つの要素として考える。
P階層目の必要最低得票数は、P-1階層目の必要最低得票数を昇順ソートしたときの上位半分+1地区の必要最低得票数の和となる。
したがって、Sの要素が1個になるまで、Sを最初から最後までみるループを回し、P回目のループではP階層目の必要最低得票数Vを計算する。そして計算が終わったP階層目の要素を全部削除し、代わりにP+1階層目の要素としてVをSに入れて更新していくという方針で解いた。
ただし、入力で与えられるのは1階層目の地区の有権者数なので最初のループの計算方法に注意しなければいけない。
文章だと複雑になってうまく説明できないから、実装をみたほうが早いかな。
てか、めっちゃ時間かけちゃった
AOJ 1166 (200)
AOJ-ICPC 2問目
迷路の最短経路を求める。
幅優先探索、距離はans[ ][ ]で管理。
queueにpushするときにans(pushするマスの座標)=ans(今いるマスの座標)+1で更新し、最後はans[h-1][w-1]を出力するようにした。
壁の与えられ方がちょっと複雑だった。
今いるマスの座標を(i, j)とするとき、それぞれの壁が
左：(2*i, j-1)
上：(2*i-1, j)
右：(2*i, j)
下：(2*i+1, j)
となるように壁の情報をdata[ ][ ]に入力した。
あとは、訪れたかどうかを新たに配列を作って管理するとMLEになったので、
ans[i][j]>0のときにはvisitedと判定してqueueに追加しないようにした。
＊次のマスをqueueに入れるところの処理が冗長かも
