AtCoder-ABC194 D - Journey【Python解答例】
AtCoder Beginner Contest194のD - JourneyについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 194 - AtCoder
AtCoder Beginner Contest194 D - Journey
問題文
頂点
1 から頂点 N までの N 頂点からなるグラフの頂点 1 に高橋君がいます。今このグラフに辺は 1 つも張られていません。
高橋君は以下の操作を繰り返します。
操作 :
(今高橋君がいる頂点も含めた) N 個の頂点の中から 1 つランダムに選ぶ。各頂点が選ばれる確率は全て 1/N であり、選択は操作毎に独立である。
今高橋君がいる頂点と選ばれた頂点の間に無向辺を張り、選ばれた頂点に移動する。
グラフが連結になるまでに行われる操作の回数の期待値を求めてください。
制約
・2≤N≤10^5
解答例
n = int(input()) res = 0 for i in range(1,n): res += n / (n - i) print(res)
解説
N個の頂点があり、すべての頂点にたどり着くまでの操作回数の期待値を答える問題です。
解説であげられている「確率 p(p≠0) で成功する試行を、成功するまで行うときの試行回数(最後の成功した回も含む) の期待値は 1/p である」という重要な事実を知らず迷走していました (^_^;)
解説の通りに計算するとあっさりACでした…
コンプガチャの期待値とかで検索すると答えに近い大ヒントがごろごろでてきました。
初めてD問題を解くチャンスでしたが逃してしまいましたね (^_^;)
ABC194の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
AtCoder-ABC194 C - Squared Error【Python解答例】
AtCoder Beginner Contest194のC - Squared ErrorについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 194 - AtCoder
AtCoder Beginner Contest194 C - Squared Error
問題文概要
長さ N の数列 A が与えられます。各要素同士の差の 2 乗の和 を求めてください。
制約
・2≤N≤3×10^5
・|Ai|≤200
・入力に含まれる値は全て整数
解答例
n = int(input()) A = list(map(int, input().split())) Sum = [0] * (n + 1) res = (n-1)*pow(A[0],2) Sum[0] = A[0] for i in reversed(range(1,n)): Sum[i] = Sum[i+1] + A[i] res += (n-1)*pow(A[i],2) -(2 * Sum[i] * A[i-1]) print(res)
解説
問題文通り長さ N の数列 A において各要素同士の差の 2 乗の和を答える問題です。
2重ループにできれば簡単ですが、時間が足りないため工夫する必要があります。
自分の解答は数学的に証明できていませんがACはとれた、という感じなのでご注意ください。
N = 3 , j = 1の場合は(A3^2 - A1^2)^2＋(A2^2 - A1^2)^2となり展開すると2A1^2 + A2^2 + A3^2 -2×A1(A2 + A3)となります。
N = 3 , j = 2の場合は(A3^2 - A2^2)^2となり、A2^2 + A3^2 -2×A2×A3です。
答えとなるその和は2(A1^2 + A2^2 + A3^2) - 2{A1(A2 + A3) + A2×A3}になります。
したがって解答は、それぞれのAの要素の2乗に( N - 1 )をかけた値の合計と、Nからj + 1までの要素の合計に-2×Ajをかけた値の和で求まると予想しました。
（Nからj + 1までの要素の合計は配列Sumとしてループにあわせて更新していきました。）
この方針でACできましたが、証明できていないので参考程度の話になります。
結果オーライではありますが、C問題まで解けてよかったです。
コンテスト中に解けなかったD問題も記事にしていきたいます。
ABC194の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
AtCoder-ABC194 A - I Scream / B - Job Assignment【Python解答例】
AtCoder Beginner Contest194のA - I ScreamとB - Job AssignmentについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 194 - AtCoder
AtCoder Beginner Contest194 A - I Scream
問題文
日本において、アイス製品は次の 4 種類に大別されます。
・乳固形分が 15 パーセント以上、乳脂肪分が 8 パーセント以上含まれるものを「アイスクリーム」とする。
・上に当てはまらず、乳固形分が 10 パーセント以上、乳脂肪分が 3 パーセント以上含まれるものを「アイスミルク」とする。
・上のいずれにも当てはまらず、乳固形分が 3 パーセント以上含まれるものを「ラクトアイス」とする。
・上のいずれにも当てはまらないものを「氷菓」とする。
ここで、乳固形分は無脂乳固形分と乳脂肪分の 2 つから成ります。
AtCoder 名物の製品「スヌケアイス」には、無脂乳固形分は A パーセント、乳脂肪分は B パーセント含まれています。
スヌケアイスに上の分類を適用したとすると、4 種類のどれに当てはまるでしょうか ?
答えは「出力」の項に従って整数で出力してください。
制約
・0≤A≤100
・0≤B≤100
・A+B≤100
・A,B は整数
解答例
a, b = map(int,input().split()) if a + b >= 15 and b >= 8: print(1) elif a + b >= 10 and b >= 3: print(2) elif a + b >= 3: print(3) else: print(4)
解説
無脂乳固形分は A パーセント、乳脂肪分は B パーセントのアイスが4種類のどれにあてはまるか答える問題です。
誤読に注意して問題文通りの条件分けを行えばOKです。
自分はラクトアイスの条件「乳固形分が 3 パーセント以上含まれるもの」はA＋Bになる点を勘違いして間違えそうでした (^_^;)
AtCoder Beginner Contest194 B - Job Assignment
問題文
あなたの会社には従業員 1 から従業員 N までの N 人の従業員がいます。
今あなたは仕事 A と仕事 B の 2 つの仕事を受注したので、これらを完了しなければなりません。
従業員 i は仕事 A を Ai 分、仕事 B を Bi 分でこなすことができます。
あなたは仕事 A と仕事 B にそれぞれ従業員を 1 人割り当てます。
同じ従業員を両方の仕事に割り当てても構いませんが、その場合 2 つの仕事が終わるのにかかる時間は、それぞれの仕事が終わるのにかかる時間の和となります。
仕事 A と仕事 B に異なる従業員を割り当てた場合、2 つの仕事が終わるのにかかる時間は、各仕事が終わるのにかかる時間の長い方となります。
2 つの仕事が終わるのにかかる時間として考えられる最小の値を求めてください。
制約
・2≤N≤1000
・1≤Ai≤10^5
・1≤Bi≤10^5
・入力に含まれる値は全て整数
解答例
n = int(input()) A = [] B = [] for i in range(n): a, b = map(int, input().split()) A.append(a) B.append(b) res = 1e9 for i in range(n): for j in range(n): if i == j: tmp = A[i] + B[j] else: tmp = max(A[i], B[j]) res = min(res,tmp) print(res)
解説
仕事AとBに割り当てる人を選んで、最短で仕事がおわる時間を答える問題です。
全探索で最短時間を求めました。
もし仕事AとBを同じ人が行う場合はAi＋Biが最短時間の候補です。
仕事Aをiさんが、Bをjさんが行う場合はAiとBjの大きいほうが候補になります。
この候補とresを比較して小さいほうをresとしていき、ループを抜ければ最短時間が求まります。
問題文を正確に理解するのに時間がかかった印象です。
続いてC問題も記事にしていきたいと思います。
ABC194の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
【AtCoder版！蟻本】ABC 007 C - 幅優先探索【幅優先探索 】
AtCoder版！蟻本の幅優先探索で類題としてあげられているABC007 CをPythonで解いていきます。
深さ優先探索と似ている部分もあり、あわせて学習すると理解しやすかったです。
リンク
AtCoder Beginner Contest 007 C - 幅優先探索
問題文
たかはし君は迷路が好きです。今、上下左右に移動できる二次元盤面上の迷路を解こうとしています。盤面は以下のような形式で与えられます。
まず、盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。
次に、それぞれのマスが通行可能な空きマス(.)か通行不可能な壁マス(#)かという情報を持った盤面が与えられる。盤面は壁マスで囲まれている。スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。具体的には、入出力例を参考にすると良い。
今、彼は上記の迷路を解くのに必要な最小移動手数を求めたいと思っています。
制約
・1 行目には、行数 R(1≦R≦50)と列数 C(1≦C≦50)がそれぞれ空白区切りで与えられる。
・2 行目には、スタート地点の座標 (sy,sx) が空白区切りで与えられる。スタート地点が sy 行 sx 列にあることを意味する。 1≦sy≦R かつ 1≦sx≦C である。
・3 行目には、ゴール地点の座標 (gy,gx) が空白区切りで与えられる。ゴール地点が gy 行 gx 列にあることを意味する。 1≦gy≦R かつ 1≦gx≦C であり、(gy,gx)≠(sy,sx)であることが保障されている。
・4 行目から R 行、長さ C の文字列が 1 行ずつ与えられる。各文字は . もしくは # のいずれかであり、i 回目 (1≦i≦R) に与えられられる文字列のうち j 文字目 (1≦j≦C) について、その文字が . なら、マス (i,j) が空きマスであり、# なら、マス (i,j) が壁マスであることをあらわす。
・盤面は壁マスで囲まれている。つまり、i=1,i=R,j=1,j=C のうちいずれか1つでも条件を満たすマス (i,j) について、c(i,j) は #である。また、スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。
解答例
from collections import deque INF = int(1e9) r, c = map(int,input().split()) sy, sx = map(int,input().split()) sy -= 1 sx -= 1 gy, gx = map(int,input().split()) gy -= 1 gx -= 1 maze = [] # 迷路の文字配列 for i in range(r): maze.append(input()) # 各座標への最短距離の配列（INFで初期化） D = [[INF] * c for _ in range(r)] # 4方向の移動ベクトル dx = [1,0,-1,0] dy = [0,1,0,-1] # スタートからゴールへの最短距離を求めるbfs def bfs(): que = deque() que.append([sy,sx]) # スタート地点をキューに入れる D[sy][sx] = 0 # スタート地点の距離を0とする # キューが空になるまで探索 while len(que) != 0: p = que.popleft() # 先入れのキューの要素を取り出す if p[0] == gy and p[1] == gx: # ゴールなら探索終了 break for i in range(4): # pから4方向に移動 移動後の点は(nx,ny) ny = p[0] + dy[i] nx = p[1] + dx[i] # 移動可能か、訪れたことがあるかの判定 if 0 <= nx < c and 0 <= ny < r and maze[ny][nx] != "#" and D[ny][nx] == INF: # 移動可能ならキューに入れて、その点の距離をpからの距離+1で確定する que.append([ny,nx]) D[ny][nx] = D[p[0]][p[1]] + 1 return D[gy][gx] print(bfs())
解説
R行C列の迷路においてスタート地点からゴール地点への最短距離を求める問題です。
以前に記事にした深さ優先探索の問題と似ています。
ebisuke33.hatenablog.com
深さ優先探索との違いはキューに入れた順番（popleft）で探索している点です。
先入れ先出しで探索し、最短距離のリストDを更新していきます。
ゴールに到着したら探索を終了し、ゴールまでの最短距離を出力すればOKです。
深さ優先探索のあとだったので理解しやすくて助かりました。
迷路探索のような問題に有効なのでしっかり覚えていきたいです。
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
【AtCoder版！蟻本】AOJ 1160 How Many Islands?【深さ優先探索】
AtCoder版！蟻本の深さ優先探索で類題としてあげられているAOJ 1160 How Many Islands?をPythonで解いていきます。
リンク
AOJ 1160 How Many Islands?
問題文
陸に対応する二つの正方形領域が，地図上で縦，横または斜め方向に隣接しているなら，一方から他方へ歩いて行くことができる． 陸に対応する二つの領域が同じ島に属するのは，一方から他方へ（一般には別の陸地を経由して）歩いて行ける時であり，またその時のみである． なお，この地図の海域は海で囲まれており，その外側へ歩いて出ることはできない．
与えられた地図を読み取り，この海域に島がいくつあるか数えるプログラムを作成して欲しい．
制約
・ w と h は地図の幅と高さを表す50以下の正の整数
・ci, j は，0 または 1 であり，空白文字1個で区切られる
・ci, j = 0 なら，地図上で左から i 番目，上か ら j 番目の正方形は海であり，ci, j = 1 なら陸である
解答例
import sys sys.setrecursionlimit(10**7) #再帰回数の上限変更 # マスy,xに隣接する陸を海に置き換え def dfs(y,x): # 現在地を0に置き換え field[y][x] = 0 # 周囲8マスをループ for dx in range(-1,2): for dy in range(-1,2): # 移動後のマスをny,nxとする ny = y + dy nx = x + dx # ny,nxがfield内で陸かどうかを判別 if 0 <= nx < w and 0 <= ny < h and field[ny][nx] == 1: dfs(ny,nx) return while True: w, h = map(int,input().split()) if w == 0 and h == 0: break field = [] for _ in range(h): array = list(map(int,input().split())) field.append(array) # 島の数 ans = 0 for i in range(h): for j in range(w): if field[i][j] == 1: dfs(i,j) ans += 1 print(ans)
解説
地図上の島の数をカウントする問題で、DFSを使って探索していきます。
これまでのDFSの問題とほとんど同じですが…
地図の各マスを全探索して島であればDFSします。
島のマスを海に置き換えて、周囲9マスに島があるか探します。
島があれば、またそのマスを海に置き換えて、という処理を繰り返して周囲に島がなくなれば島の数を1つ増やしていきました。
全探索が終わればすべて海に置き換わり、島の数がカウントできています。
最後に島の数を出力すればOKです。
このプログラムはデフォルトの再帰回数の上限を超えてしまいます。
上限を10^7に変更しないとエラーになりましたので注意してください。
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
【AtCoder版！蟻本】ARC 037 B - バウムテスト【深さ優先探索】
AtCoder版！蟻本の深さ優先探索で類題としてあげられているARC037 BをPythonで解いていきます。
DFSを使ってグラフの連結成分に閉路があるか判別していきます。
リンク
AtCoder Regular Contest 037 B - バウムテスト
問題文
バウムテストとは、被験者に「木」の絵を描かせることで被験者の心理状態を読み取る心理検査である。この検査を受けた高橋君は、 N 個の頂点と M 本の辺からなる無向グラフを描いた。
このグラフの連結成分のうち木であるようなもの、すなわち閉路を持たないものの個数を求めよ。
制約
・ N (2 ≦ N ≦ 100)
・M (1 ≦ M ≦ N×(N−1)/2)
・ i+1 行目 (1 ≦ i ≦ M) には、辺 i が結ぶ 2 頂点の番号 ui, vi (1 ≦ ui ＜ vi ≦ N) がスペース区切りで与えられる。
・どの 2 頂点についても、それらを直接結ぶ辺は高々 1 本しか存在しない。
解答例
# 深さ優先探索 from collections import deque n, m = map(int,input().split()) U = [] V = [] for i in range(m): u, v = map(int,input().split()) u -= 1 v -= 1 U.append(u) V.append(v) # 閉路を持たない木 ans = 0 # 探索済み頂点リスト Visited = [0] * n # 頂点iからdfs 探索済み頂点リストを更新していき 探索済み頂点をpopしたら閉路 def dfs(i): que = deque() que.append(i) # 探索をはじめる頂点をpush flag = True # 閉路判別フラグ Trueで閉路なし # queが空になるまで探索 while len(que) != 0: k = que.pop() # 探索する頂点kをpop if Visited[k] != 0: flag = False else: Visited[k] = 1 # 頂点kの探索済みリストを更新 for j in range(m): # 未探索の頂点ならpush if U[j] == k and Visited[V[j]] == 0: que.append(V[j]) elif V[j] == k and Visited[U[j]] == 0: que.append(U[j]) #頂点iからの探索を終えたとき閉路があるかを返す return flag # すべての頂点で未探索ならdfs for l in range(n): if Visited[l] == 0: if dfs(l): # 探索して閉路がなければans+1 ans += 1 print(ans)
解説
N個の頂点があり、2つの頂点をつなぐ辺がM本あるとき、辺でつながった連結成分のうち木である（閉路がない）ものの数を答える問題です。
0で初期化した探索済み頂点リストVisitedを作成し、DFSで探索していきます。
探索した頂点はVisitedの該当要素を+1してメモしていきました。
連結成分が木であるか閉路があるかの判断はVisitedを用います。
閉路があるときは探索済みの頂点がpopされますが、木である場合は探索済みの頂点がpopされることはないです。
これをflag管理して木である連結成分の数をカウントしていきました。
全頂点が探索済みとなればカウントしていた木の数を出力すればOKでした！
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
【AtCoder版！蟻本】ARC 031 B - 埋め立て【深さ優先探索】
AtCoder版！蟻本の深さ優先探索で類題としてあげられているARC031 BをPythonで解いていきます。
再帰関数を使用して解いています。
リンク
AtCoder Regular Contest 031 B - 埋め立て
問題文
とある所に島国がありました。島国にはいくつかの島があります。このたび、この島国で埋め立て計画が立案されたのですが、どこを埋め立てるか決まっていません。できることなら埋め立てによって島を繋いで、1 つの島にしてしまいたいのですが、たくさん埋め立てるわけにもいきません。
10 マス × 10 マスのこの島国の地図が与えられるので、1 マスを埋め立てた時に 1 つの島にできるか判定してください。ただし、地図で陸地を表すマスが上下左右につながっている領域のことを島と呼びます。
制約
・各行は 10 文字からなり、o は陸地を、x は海を表す。
・少なくとも 1 マスは陸地があることが保証される。
・少なくとも 1 マスは海があることが保証される
解答例
import copy Map = [] # 10*10マスの地図 for _ in range(10): Map.append(list(input())) # 4方向の移動ベクトル dx = [1,0,-1,0] dy = [0,1,0,-1] # 現在地に隣接する陸地を海に置き換える def dfs(x, y): # 今いるところをxに置き換える if New_map[x][y] == "o": New_map[x][y] = "x" for k in range(4): # x方向にdx y方向にdy 移動した場所を(nx, ny)とする nx = x + dx[k] ny = y + dy[k] # nxとnyがMap内で陸地か判別 if 0 <= nx < 10 and 0 <= ny < 10 and New_map[nx][ny] == "o": dfs(nx,ny) return for i in range(10): for j in range(10): if Map[i][j] == "x": New_map = copy.deepcopy(Map) dfs(i,j) else: continue flag = True for a in range(10): for b in range(10): if New_map[a][b] == "o": flag = False if flag: print("YES") exit() else: print("NO")
解説
10×10マスの島国の地図があり、海を1マスだけ陸に変えたときに1つの島になるか判定する問題です。
初期状態のマップのうち各マスを全探索し、海であればその地点をDFSに渡します。
DFSでは渡された地点から縦横4マスに陸地があれば海に置き換えていきます。
スタート地点から隣接した陸はすべて海になります。
この後に海に置き換えた地図に陸地がないか全探索します。
これで陸地がないことを確認できたらYESを出力し、ループが抜けてしまったらNOを出力すればOKです。
ループごとにdeepcopyを使ってNew_mapを初期化しないと引き継ぎたくないのに引き継がれてしまい苦労しました。
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
【AtCoder版！蟻本】ATC 001 A 深さ優先探索【深さ優先探索】
AtCoder版！蟻本の深さ優先探索で類題としてあげられているATC001 AをPythonで解いていきます。
深さ優先探索（DFS）は初めて見たとき難しく感じましたが、何問か解くとイメージがわいてきました。
理解しないと使いこなせないと思いますので頑張って取り組んでいきます。
リンク
AtCoder Typical Contest 001 A - 深さ優先探索
問題文
高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。
高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。
制約
・H(1≦H≦500)
・W(1≦W≦500)
・ci,j(0≦i≦H−1,0≦j≦W−1)
・i 行目 j 文字目の文字 ci,j はそれぞれ s, g, ., # のいずれかで与えられ、座標 (j,i) が下記のような状態であることを表す。
・s : その区画が家であることを表す。
・g : その区画が魚屋であることを表す。
・. : その区画が道であることを表す。
・# : その区画が塀であることを表す。
・高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
・与えられた街の外を通ることはできない。
・s と g はそれぞれ 1 つずつ与えられる。
解答例
# 深さ優先探索 from collections import deque INF = int(1e9) # 入力 h, w = map(int,input().split()) C = [] # 迷路の文字配列 for i in range(h): C.append(input()) # スタート、ゴールの探索 for y in range(h): for x in range(w): if C[y][x] == "s": # スタート座標はsx,sy sx = x sy = y if C[y][x] == "g": # ゴール座標はgx,gy gx = x gy = y # 各座標への最短距離の配列（INFで初期化） D = [[INF] * w for i in range(h)] # 4方向の移動ベクトル dx = [1,0,-1,0] dy = [0,1,0,-1] # スタートからゴールへの最短距離を求める def dfs(): que = deque() que.append([sy,sx]) # スタート地点をキューに入れる D[sy][sx] = 0 # スタート地点の距離を0とする # キューが空になるまで探索 while len(que) != 0: p = que.pop() # 後入れのキューの要素を取り出す if p[0] == gy and p[1] == gx: # ゴールなら探索終了 break for i in range(4): # pから4方向に移動 移動後の点は(nx,ny) ny = p[0] + dx[i] nx = p[1] + dy[i] # 移動可能か、訪れたことがあるかの判定 if 0 <= nx < w and 0 <= ny < h and C[ny][nx] != "#" and D[ny][nx] == INF: # 移動可能ならキューに入れて、その点の距離をpからの距離+1で確定する que.append([ny,nx]) D[ny][nx] = D[p[0]][p[1]] + 1 return D[gy][gx] res = dfs() if res != INF: print("Yes") else: print("No")
解説
スタート地点からゴール地点まで道を通ってたどり着けるか答える問題です。
深さ優先探索（DFS)で解いていきます。
Cに迷路の文字列を入れていき、スタート地点の座標sx,syとゴール地点の座標gx,gyを探索します。
迷路と同じ大きさの配列Dを用意しました。。
DはINFで初期化してあり、DFSでスタート地点からの最短距離を代入していきます。
DFSは最初スタート地点をキューにプッシュします。
キューからデータを取り出し、縦横4方向に移動させた座標nx,nyを求めました。
nx,nyが迷路の範囲内で その座標が道ならキューにプッシュし、最短距離も+1して更新します。
この作業をキューが空になるまで繰り返せば、通行できる道の最短距離がすべて更新されています。
ゴール地点のDが初期のINFのままなら到着できない と判断になるので、resの値にあわせて出力すればOKです。
こんな迷路問題を解けるようになりたい、っていうのが実は蟻本の購入動機のひとつでした。
意欲的に取り組んでいきます！
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
