AtCoder Beginner Contest 176をPythonで解く

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 176を, Pythonで解いてみた結果を書き連ねていこうと思います.

AtCoder Beginner Contest 176 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - Takoyaki

割り算の商をA // Bで, 剰余をA % Bで計算します.

B - Multiple of 9

Pythonでは文字列をリストにすると, その文字列の各文字が各要素にそのまま入ったリストが得られます. この各要素をint型に変換し, 合計を求めて$9$で割った剰余を調べます.

C - Sum of product of pairs

前の人の高さ(踏み台含)よりその人の方が低いか否かを判断していきます. まずは, 最小の踏み台の高さのリストを作成していき, その合計を出力する例です.

あるいは, 最小の踏み台の高さのリスト自体は必要ないので, 「最小の踏み台の高さを足していく変数」と「それまでの人の高さの最大値(踏み台含)を記録していく変数」を用意して計算することで, 実行時間を若干減らすことができます.

D - Wizard in Maze

AtCoder Beginner Contest 177の「D - Friends」と同様に, 幅優先探索(breadth first search; BFS)と呼ばれる方法を用います. スタート地点から移動A・Bで移動できるマスをまず調べ上げ, 次にそれらのマス全てから移動A・Bで移動できるマスを調べます. これを繰り返していくことで, 移動できるマス全てにおける移動「コスト」(移動Bをしなければならない回数)が分かります.

AtCoder Beginner Contest 177をPythonで解く

こんにちは, Shinoryoです. 今回は AtCoder Beginner Contest 177 を, Pythonで解いてみた結果を書き連ねていこうと思います. AtCoder Beginner Contest 177 - AtCoder AtCoder is...

注意点としては, 「他にももっと簡単に移動できる方法があったのに！」という可能性です. 以下のコードでは, 「移動Aで移動できるマス→それらから移動Bで移動できるマス→それらから移動Aで移動できるマス→それらから移動Bで移動できるマス→……」というように調べています(移動履歴がすでに存在するマスから移動A・Bで移動できるかどうかは調べません). このようにすることで移動Bが最も少ない移動パターンを先に調べられるので, 「他にももっと簡単に移動できる方法があったのに！」という可能性はなくなります.

なお, 「移動先の地点を調査するべき地点リスト」には, AtCoder Beginner Contest 177の「D - Friends」と同様にdeque型を用いると, 計算量を減らすことができます.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

• 「解説 - AtCoder Beginner Contest 176」
  Editorial - AtCoder Beginner Contest 176

  AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

• hirokiky様の「Pythonのif __name__ == "__main__" とは何ですか？への回答」(オンラインPython学習プラットフォームPyQ)
  Pythonのif __name__ == "__main__" とは何ですか？への回答

  こんにちは. id:hirokiky です. 今日も皆さまからPyQメールサポートにご質問いただいた内容で多かった質問と回答をご紹介します. この質問はとくに疑問になりやすい点なのではないでしょうか. pyq.jp 質問と回答. Pythonの if __name__ == '__main__': は何のためにあるものですか？ はい. こちらはよくPythonプログラムに書かれていますね. 書かれることは多い割には, 不思議の多いif文ですね. 「これは『おまじない』なので気にしないでください」と言って回答を終わらせてしまうのは簡単ですが, それでは悲しいので, 少し長くなりますが回答いたします. 一言…