こんにちは, 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で計算します.
| # 入力 | |
| N, X, T = [int(x) for x in input().split()] | |
| # たこ焼きを作る回数を求める | |
| kaisu = N // X | |
| if N % X != 0: | |
| kaisu += 1 | |
| # 出力 | |
| print(kaisu*T) |
B - Multiple of 9
Pythonでは文字列をリストにすると, その文字列の各文字が各要素にそのまま入ったリストが得られます. この各要素をint型に変換し, 合計を求めて
| # 入力 | |
| N = [int(x) for x in list(input())] | |
| # 9の倍数か判定・出力 | |
| if sum(N) % 9 == 0: | |
| print("Yes") | |
| else: | |
| print("No") |
C - Sum of product of pairs
前の人の高さ(踏み台含)よりその人の方が低いか否かを判断していきます. まずは, 最小の踏み台の高さのリストを作成していき, その合計を出力する例です.
| # 入力 | |
| N = int(input()) | |
| A = [int(x) for x in input().split()] | |
| # 最小の踏み台の高さのリストを作成 | |
| ANS = [0]*N | |
| for i in range(1,N): | |
| ANS[i] = max(0, A[i-1] + ANS[i-1] - A[i]) | |
| #出力 | |
| print(sum(ANS)) |
あるいは, 最小の踏み台の高さのリスト自体は必要ないので, 「最小の踏み台の高さを足していく変数」と「それまでの人の高さの最大値(踏み台含)を記録していく変数」を用意して計算することで, 実行時間を若干減らすことができます.
| # 入力 | |
| N = int(input()) | |
| A = [int(x) for x in input().split()] | |
| # 最小の踏み台の高さを足していく | |
| ans = 0 | |
| # それまでの人の高さの最大値(踏み台含)を記録していく | |
| maxheight = A[0] | |
| for height in A[1:]: | |
| # もし前の人の高さ(踏み台含)未満であれば, 踏み台が必要 | |
| # 最小の踏み台の高さの合計だけ更新する | |
| if maxheight > height: | |
| ans += maxheight - height | |
| # もし前の人の高さ(踏み台含)以上であれば, 踏み台は必要ない | |
| # 前の人の高さだけ更新する | |
| else: | |
| maxheight = height | |
| #出力 | |
| print(ans) |
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型を用いると, 計算量を減らすことができます.
| from collections import deque | |
| def main(): | |
| H, W = [int(x) for x in input().split()] | |
| C_h, C_w = [int(x) for x in input().split()] | |
| D_h, D_w = [int(x) for x in input().split()] | |
| # 迷路情報の入力(今後, これに移動"コスト"が入力されていく) | |
| # 周囲に2マス分の壁を追加 | |
| S_list = [ ["#"]*(W+4) for _ in range(2)] + [list( "##" + input().rstrip() + "##" ) for _ in range(H)] + [ ["#"]*(W+4) for _ in range(2)] | |
| # 迷路情報に合わせてCとDの値を調整 | |
| # 2マス分の壁が追加されているが, 迷路情報のIndexは0からなので1だけ足す | |
| C_h += 1 | |
| C_w += 1 | |
| D_h += 1 | |
| D_w += 1 | |
| # スタート地点はコスト0 | |
| S_list[C_h][C_w] = 0 | |
| # 移動先の地点を調査するべき地点リスト | |
| # まずはじめにスタート地点から移動Aを調べる | |
| dq_A = deque([[C_h, C_w]]) | |
| dq_B = deque() | |
| # 移動Aと移動Bで移動できる先 | |
| delta_A = [[0,1],[0,-1],[1,0],[-1,0]] | |
| delta_B = [[dh,dw] for dh in range(-2,3) for dw in range(-2,3) if (abs(dh) + abs(dw)) > 1] | |
| # 移動先の地点を調査するべき地点リストがなくなるまでループ | |
| while dq_A or dq_B: | |
| while dq_A: | |
| # 移動元=curr, 座標とコストを確認 | |
| curr_h, curr_w = dq_A.popleft() | |
| curr_cost = S_list[curr_h][curr_w] | |
| # この後移動Bに関しても調べる | |
| dq_B.append([curr_h, curr_w]) | |
| # 移動Aを全て試す | |
| for dh,dw in delta_A: | |
| next_h = curr_h + dh | |
| next_w = curr_w + dw | |
| # 移動先が移動可能かどうか(壁ではないか) | |
| if S_list[next_h][next_w] == ".": | |
| # コストは追加ではかからない | |
| S_list[next_h][next_w] = curr_cost | |
| # 再度移動Aを試す | |
| dq_A.append([next_h, next_w]) | |
| while dq_B: | |
| # 移動元=curr, 座標とコストを確認 | |
| curr_h, curr_w = dq_B.popleft() | |
| curr_cost = S_list[curr_h][curr_w] | |
| # 移動Bを全て試す | |
| for dh,dw in delta_B: | |
| next_h = curr_h + dh | |
| next_w = curr_w + dw | |
| # 移動先が移動可能かどうか(壁ではないか) | |
| if S_list[next_h][next_w] == ".": | |
| # コストは追加でかかる | |
| S_list[next_h][next_w] = curr_cost + 1 | |
| # 再度移動Aを試す | |
| dq_A.append([next_h, next_w]) | |
| # この時点でコストが入力されていないなら, それは移動不可能ということ | |
| if S_list[D_h][D_w] == ".": | |
| print(-1) | |
| # そうでなければ, 移動コストを出力 | |
| else: | |
| print(S_list[D_h][D_w]) | |
| if __name__ == '__main__': | |
| main() |
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文ですね. 「これは『おまじない』なので気にしないでください」と言って回答を終わらせてしまうのは簡単ですが, それでは悲しいので, 少し長くなりますが回答いたします. 一言…
0 件のコメント:
コメントを投稿 (Please feel free to ask me about your questions! You can use Japanese or English in the comments.)