こんにちは、こんぶちゃ(茶コーダー)です！
初心者視点から競プロAtCoderのABC293のA問題〜C問題の自身の解答と解答説明をしていきます。
- 競技プログラミング初心者で、問題の解き方がわからない方
- AtCoderの公式解説は読んだが、内容が理解できなかった方
- pythonでの解法を知りたい方
まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。
では早速行ってみましょう！
- bit全探索 ・・・ C問題
今回の参加コンテスト(ABC293)
A問題：Swap Odd and Even
問題(要約)
文字列が与えられ、奇数番目と偶数番目の文字数を入れ替える。
＊文字列の長さは偶数のみ。
解答
#入力をsに代入
s=input()
#入れ替えた文字列(回答）をリストに順次代入するため空の配列を作成
ans=[]
#下記説明参照
for i in range(0,len(s),2):
ans.append(s[i+1])
ans.append(s[i])
#リストにアスタリスク(*)をつけることにより中身を一覧で取り出せる(unpack)
#unpack時は要素間に空白ができるため、print分のsepオプションでスペースを除外
print(*ans,sep="")1番目文字 ⇄ 2番目文字、3番目文字 ⇄ ４番目文字、・・・を入れ替えるためにfor文とrange関数を用いて、１番目→３番目→５番目・・・を選択する。
range(0, len(s), 2)： range(スタート番号, 終了番号, 間隔) で設定。
終了番号は、len関数を用いて文字列長さに設定。
間隔は、1番目→3番目→5番目・・・を選択するために、2つおきに設定する。
for文の中身は、下記の順番で代入することにより、偶奇順番の入れ替えが可能
1. 偶数番目をans配列に代入
2. 奇数番目をans配列に代入
B問題：Call the ID Number
問題(要約)
Aiリスト順に番号を呼び、人iがまだ呼ばれていなかったら人Aiの番号を呼ぶ。
最後まで名前を呼ばれなかった全員の人数と番号を昇順に列挙する
解答
#人数の入力を受け取り、整数型に変換
n=int(input())
#スペース区切りの入力を分割し、整数型に変換する(map(int,input().split())
#分割したものをリストに格納する(list())
#入力が1スタートのため、インデックスと入力Noを揃えるため、0を先頭に追加
A=[0]+list(map(int,input().split()))
#下記参照
dp=[0 for _ in range(n+1)]
ans=set(x for x in range(1,n+1))
for i in range(1,n+1):
if dp[i]==0:
if A[i] in ans:
ans.remove(A[i])
dp[A[i]]=1
print(len(ans))
print(*ans)考え方：
・dp配列で名前が呼ばれたかを確認。0：名前呼ばれていない、1：名前呼ばれた
・ansを集合型で定義し、N人分の番号を追加
・人iの名前が呼ばれているかを確認する。
・まだ呼ばれてなければans集合からAiの番号を削除
・dp配列のAiにフラグ(1)を立てる(呼ばれた事とする）
詳細
#内包表記を用いて値0の配列を作る。インデックスを合わせるためn+1分にしている
dp=[0 for _ in range(n+1)]
# N人分の番号を集合で内包表記で作成。
# xの値が "for x in range(1,n+1)" になる。つまり、1,2,3,・・・,n の集合
ans=set(x for x in range(1,n+1))
# for文で1〜Nまで繰り返す
for i in range(1,n+1):
#既に名前が呼ばれているか確認
if dp[i]==0:
#名前が呼ばれていなかったら、配列A[i]が呼ばれているか確認
if A[i] in ans:
#呼ばれていなければ、集合から削除(集合からの削除はremoveを用いる)
ans.remove(A[I])
#A[I]が呼ばれたことをチェック
dp[A[i]]=1
# ansには名前が呼ばれていない人達の集合のため、長さを求めunpackで表示
# 昇順で登録しているため順番は気にしなくて問題なし
print(len(ans))
print(*ans)C問題：Make Takahashi Happy
問題(要約)
始点(1, 1)から終点(H, W)へ移動し、通過する経路の整数が違う経路の数を求める。
＊移動の仕方は、右方向、下方向の２通りのみ。
解答
# 入力を受け取る。
H, W = map(int, input().split())
# 2次元配列で受け取る。"list(map(int,input().split())"部分がW要素を示し、
# このW要素をH回繰り返すことにより2次元配列を形成
A=[list(map(int,input().split())) for _ in range(H)]
# 当てはまる経路をカウントするためのカウンタを用意(0で初期化)
cnt=0
# 下記参照
for i in range(2**(H-1+W-1)):
comb=[]
for j in range(H-1+W-1):
if (i>>j & 1):
comb.append(1)
else:
comb.append(0)
xpos,ypos = 0,0
ans=set()
ans.add(A[ypos][xpos])
for k in comb:
if k==0:
if xpos>=W-1:
break
else:
xpos+=1
else:
if ypos>=H-1:
break
else:
ypos+=1
ans.add(A[ypos][xpos])
if len(ans)==H-1+W-1+1:
cnt+=1
print(cnt)考え方：
・移動の仕方が右か下のみの為、ゴールまでのステップ数は H-1+W-1となる
・想定される経路はステップ数分 x (右 or 下) になる
・bit全探索にて0(右移動), 1(下移動)で全ての組み合わせを作る
・移動経路の整数を追加していく空のans集合を作成し、スタート位置(0, 0) *1 の整数値を追加
*1 配列Aを0番目から登録している為インデックス合わせをしている
・移動経路が枠からはみ出す場合、for文をぬけ次の経路を確認
・ans集合の個数と”ステップ数+スタート地点の数 (H-1+W-1+1)”と同じかを判定
・条件を満たしていれば、カウントcntに1を加算する
# bit全探索を行うために想定される通り数分forを回す
# (H-1+W-1)のステップがあり、右移動と下移動の２パターンのため、2**(H-1+W-1) (**はべき乗を表す）
for i in range(2**(H-1+W-1)):
# 経路の組み合わせを入れるための空の配列を作成
comb=[]
# bit全探索をするための桁数分jを回す
for j in range(H-1+W-1):
# iをj桁分シフトさせて1かどうかを判断
if (i>>j & 1):
comb.append(1)
else:
comb.append(0)
# ここからは上記で出来上がった今回の移動経路(例：0101)が条件に当てはまるかを確認
# スタート位置、経路の整数値を追加するための空のans集合を作成
xpos,ypos = 0,0
ans=set()
# スタート地点の整数値を集合ansに加える
ans.add(A[ypos][xpos])
# 今回の移動経路が格納されているcombを取り出し、整数値をans集合に格納していく。
for k in comb:
# 右移動(k:0)、下移動(k:1)を判断
if k==0:
# マス目外に出た時は、次の組み合わせに移行
if xpos>=W-1:
break
else:
xpos+=1
else:
# マス目外に出た時は、次の組み合わせに移行
if ypos>=H-1:
break
else:
ypos+=1
# マス目に記載してある整数値をans集合に追加
ans.add(A[ypos][xpos])
# ans集合の長さがステップ数＋スタート位置と同じかどうか判断し、同じならカウントを増やす
# 集合は同じ値を２つ持つことができないため、長さで判断が可能
if len(ans)==H-1+W-1+1:
cnt+=1
print(cnt)感想
コンテストでは、A, B問題しか解けませんでした。bit全探索を使って解けるかもと思いましたが、実装がうまくいかずに時間切れ。来週に向けて精進していこうと思います。
それでは、良い競プロライフを〜！
コメント