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

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

今日の競プロ(2015/04/05)

Python 競技プログラミング AtCoderABC

ちょっと疲れたので,今日は予約投稿しておきます.

ABCのC問題を少しずつやってます.

ABC 007 C

abc007.contest.atcoder.jp

もう問題文に答え書いてありますけど,幅優先探索を実装する問題.
幅優先探索自体は大体使いこなせるようになってきたかな.
別のところで読んだ文字列のテーブル作るところで,ミスを多発してしまい,幅優先探索実装よりもそっちの方が大変でしたorz
地図の探索みたいな問題に関しては,今後こんなかんじの読み取り方にしよう….

maptable = [list(str(input())) for x in range(R)]

これでこんなん読んで

5 5
2 2
4 4
#####
#...#
#.#.#
#...#
#####

printしてみると,こんなかんじに.

[['#', '#', '#', '#', '#'], ['#', '.', '.', '.', '#'], ['#', '.', '#', '.', '#'], ['#', '.', '.', '.', '#'], ['#', '#', '#', '#', '#']]

""と''で囲まれた要素の違いがいまいちわからないのですが,

maptable[0][0] = '{0}'.format(count)

この違いについては,時間があれば調査したい.

ABC 007 C

先に99点バージョン.

abc008.contest.atcoder.jp

とりあえず総当りでやればいいのは分かったのもの,方法がよくわからなかったので,解説スライドを本に実装.
next_permutationなるものがあることを知った.リスト使って総当りでやるときには重宝しそう.
計算時間の問題から使えそうな場面は限られるだろうけど….

参考にしたサイトのリンク↓
Tech Tips: Pythonでnext_permutation


100点バージョン.

abc008.contest.atcoder.jp

実は最初解説スライドを見てもわからなかったのだが,実際に紙に書きながら整理していくと理解できた.
確かに約数となるコインだけ見ていれば良いね….
偶数,奇数のときどうしてその確率になるのか,わからなかったわけだけど下のような図を書いたら納得.


で,確かに計算してみたらそのとおりだろうなと.

本番でこれくらいの問題が解けるようになったら気持ちいいんだろうなあと思う.

ABC 016 C

abc016.contest.atcoder.jp


大昔に似たような問題をやったことあるような気がするが….(議員の問題が近い?)
setを使って,友達の友達の集合と自分の友だちの集合の差を取って更新すれば良さそうだなあと思って,その通りに実装….
集合に関してはまだ使いこなせていない部分も多いので,うん,練習あるのみかなあと思う.



さて,このブログが予約投稿される頃にはARC終わってると思います.
どんな結果になっているんだろうか….

明日は解けなかったARCの問題に挑戦しようかな.

毎日頑張るぞい!