薄いブログ

技術の雑多なことを書く場所

宿題 0b1 #kagapra0715

AOJ 0569

21:31~22:24

外側からラベリングして建物のセルに到達した回数を求めれば良い。
後は6近傍の時の移動が出来ればラベリングするだけ。
外側に番兵を置く実装をすると非常に楽。
僕は6近傍の時の移動ができなかったので時間がかかりました。
53分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020674

AOJ 0033

22:26~22:33

取りうる状態が2^10個くらいなので全探索で余裕。
Aに入れるか、Bに入れるかをDFSする。
7分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020685

AOJ 0118

22:35~22:42

このようなラベリング問はUnionFindで常勝(と思っているので)
必要な部分だけUnionFind書いて終了。
4近傍で同じ文字があればmergeして、最後にgroupの数を出力するだけで良い。
実際dfsとかのほうが短く早く書けそうですが、こういう問題を見ると思考停止してしまう。
7分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020692

AOJ 0558

22:44~23:18

読んで「ダルそう」となった問題。
S -> 1 -> 2 -> 3 -> ... -> N
の最短経路長の和を求める問題だということにすぐに気がついた。
そこからは思考停止してグラフを作って、ダイクストラっぽいもので最短経路長を求めた。
34分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020743

AOJ 0121

23:19~23:35

7パズルを解く問題。
最初の時点で完成版盤面から解くことの出来る
全ての盤面の最短の解をBFSで求めて保持しておく。
盤面が7!程度しかないので問題はない。
BFSを書き慣れていなかったり、いろいろ躓いた。
16分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020767

AOJ 0529

0:37~0:45

半分全列挙を行う問題。
kagamiz先生が講義で言っていたことを素直に実装した。
0点を追加することで必ず4本ダーツを投げるようにして
N^2で2回投げるパターンを列挙しその中から一つ選び,
M-今のパターンの点数 以下の最大を2分探索で求めることで解くことが出来る。
8分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020833

とりあえずこれからも宿題で解いたものをブログに上げると思います。