ABC349(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)

A問題

全員の持ち点の合計は0で不変である．
- 当然，引き分けたときは，不変である．
- 勝敗が生まれたときは，誰かが1点を得るが，誰かが1点を失う．だから，全員の合計点は不変．
入力でN-1人の点数の合計が分かっていれば，それをマイナスさせた値が答えである．
(補足)最初の標準入力のNは今回は参照しません．

A.py

"""
<方針>
- 全員の持ち点の合計は`0`で不変である．
  - 当然，引き分けたときは，不変である．
  - 勝敗が生まれたときは，誰かが`1`点を得るが，誰かが`1`点を失う．だから，全員の合計点は不変．
- 入力で`N-1`人の点数の合計が分かっていれば，それをマイナスさせた値が答えである．
- (補足)最初の標準入力の`N`は今回は参照しません．
"""

# 標準入力を受け取る．
N = int(input())
A = list(map(int, input().split()))

# N-1人の合計値にマイナスを付与したものが答え．
print(-sum(A))

B問題

それぞれの英子文字(26種類)が何回現れたかを記録する．
- アルファベット(a, b, c, ..., z)を数字(0, 1, 2, ..., 25)で表現している．
デフォルトの値が0のリストを作成する．
- それぞれのアルファベットに対して，indexをその文字が現れた回数とし，値をインクリメントする．
- この26アルファベット全てに対してインクリメントを行った後，リストの値が0または2でなければ，Noを出力する．

B.py

"""
<方針>
- それぞれの英子文字(`26`種類)が何回現れたかを記録する．
  - アルファベット(`a, b, c, ..., z`)を数字(`0, 1, 2, ..., 25`)で表現している．
- デフォルトの値が`0`のリストを作成する．
  - それぞれのアルファベットに対して，indexをその文字が現れた回数とし，値をインクリメントする．
  - この`26`アルファベット全てに対してインクリメントを行った後，リストの値が`0`または`2`でなければ，`No`を出力する．
"""

# 標準入力を受け取る．
S = input()

# それぞれの英子文字が何回現れたかを記録する．
ls = [0]*26

# 文字を一つずつみる．
for s in S:
  # 現れたアルファベットを記録する．
  ls[ord(s)-ord("a")] += 1
  
# indexを文字の現れた回数とし，そのようなアルファベットの種類の数をvalueとするリスト．
cnt = [0]*101

# それぞれの英子文字が何回現れたかを確認する．
for item in ls:
  # その現れた回数をindexとし，インクリメントする．
  cnt[item] += 1
  
# ちょうどi回現れる文字を見る．iは1以上に注意する．
for i in range(1, len(cnt)):
  # 値が0または2でないとき，
  if not (cnt[i] == 0 or cnt[i] == 2):
    # Noの出力
    print("No")
    exit() # ここでプログラムの実行を停止させる．

# i回現れるのは0または2である事が確認できたので，Yesを出力する．
print("Yes")

C問題

文字列Tを小文字列に変換させた文字列tを用意する．
文字列Sを左から見ていく．
- 文字列tの最初の文字に合致するかをみる．1度でも合致すれば真ん中，そして，最後を見ていく．
- これで，最後の文字まで合致すれば，Yesを出力する．
- ただし，tの最後の文字がxであった場合は，真ん中の文字が合致した時点でYesを出力する．

C.py

"""
<方針>
- 文字列`T`を小文字列に変換させた文字列`t`を用意する．
- 文字列`S`を左から見ていく．
  - 文字列`t`の最初の文字に合致するかをみる．1度でも合致すれば真ん中，そして，最後を見ていく．
  - これで，最後の文字まで合致すれば，`Yes`を出力する．
  - ただし，`t`の最後の文字が`x`であった場合は，真ん中の文字が合致した時点で`Yes`を出力する．
"""
S = input()
T = input()

# Tを小文字列にしたもの．
t = T.lower()

# tの何番目の文字を見る必要があるかを表すフラグ．
st = 0

# Sの文字を一つずつ見ていく．
for s in S:
  
  # tの最初の文字を見る必要があり，tの最初の文字とsが合致していたとき，
  if(st==0 and s==t[0]):
    # 真ん中の文字を見るフラグに変換する．
    st = 1
  # tの真ん中の文字を見る必要があり，tの真ん中の文字とsが合致していたとき，
  elif(st==1 and s==t[1]):
    # 最後の文字を見るフラグに変換する．
    st = 2
    # tの最後の文字がxのとき，
    if(t[2] == "x"):
      # Yesを出力して，終了する．
      print("Yes")
      exit()
  # tの最後の文字を見る必要があり，tの最後の文字とsが合致していたとき，
  elif(st==2 and s==t[2]):
    # Yesを出力して終了する．
    print("Yes")
    exit()

# Yesを出力できなかったら，Noを出力する．
print("No")

D問題

L側から，2**iのiをできるだけ大きくして，Rに収まるような値lを取り，それで分割し，その値lでLを更新して，これを繰り返す．
以下に例を示す．

入力↓
3 19

出力↓
5
3 4 i→0
4 8 i→2
8 16 i→3
16 18 i→1
18 19 i→0

D.py

"""
<方針>
- L側から，`2**i`の`i`をできるだけ大きくして，Rに収まるような値`l`を取り，それで分割し，その値`l`でLを更新して，これを繰り返す．
- 以下に例を示す．
# ``` (*1)
入力↓
3 19

出力↓
5
3 4 i→0
4 8 i→2
8 16 i→3
16 18 i→1
18 19 i→0
# ``` (*1)
"""

L, R = map(int, input().split())

# 答えを格納するリスト
ans = []

# まだ分割が取れるとき，
while L<R:
  
  # lを一旦Lとする．
  l = L
  
  # iは最初0とする．
  i = 0
  
  # iの値を一つずつ増やしてみる．
  while True:
    
    # lを2で割った，商と余りを求める．
    di, mo = divmod(l, 2)
    
    # 余りが1になったとき，終了
    if(mo==1):
      break
    
    # Rの値をL+2**(i+1)が越したとき，更新せず終了
    if(L+pow(2, i+1)>R):
      break
    
    # iの値をインクリメント
    i += 1
    
    # lの値を更新
    l = di
    
  # 答えに追加．
  ans.append([L, L+pow(2, i)])
  
  # Lの値を変える．
  L += pow(2, i)
  
# 答えの出力．
print(len(ans))
for item in ans:
  print(*item)

E問題

盤面を一つずつ交代で埋めていくのを再帰的(BFS)に行う．
- 盤面を埋めていく度に，勝敗が決まっているかの判定を行い，勝敗が決まっていれば，終了する．
- 勝敗が決まっていなければ，盤面の次のターンを全て試してみる．
- 次のターンで一つでも自分が勝てる手が打てるのであれば，現在の盤面は勝ちとなる．
勝敗は連想配列にグローバルにメモする．
現在の盤面の勝敗は，盤面を進めてみないと勝敗がわからないので，盤面をキューに追加するときは，以下の2つを追加する．
- 盤面を進めた内容を追加するための要素(本コードにおけるキューの第2引数がFalseのところ)
- 盤面を進めた結果がグローバルにメモされているので，現在の盤面の勝敗判定を行う要素(本コードにおけるキューの第2引数がTrueのところ)
そもそも，再帰関数ではなく，キューのBFSで解いてる理由は，PyPyの再帰関数が遅いからです．気になる人は調べて下さい．

E.py

"""
<方針>
- 盤面を一つずつ交代で埋めていくのを再帰的(`BFS`)に行う．
  - 盤面を埋めていく度に，勝敗が決まっているかの判定を行い，勝敗が決まっていれば，終了する．
  - 勝敗が決まっていなければ，盤面の次のターンを全て試してみる．
  - 次のターンで一つでも自分が勝てる手が打てるのであれば，現在の盤面は勝ちとなる．
- 勝敗は連想配列にグローバルにメモする．
- 現在の盤面の勝敗は，盤面を進めてみないと勝敗がわからないので，盤面をキューに追加するときは，以下の2つを追加する．
  - 盤面を進めた内容を追加するための要素(本コードにおけるキューの第2引数が`False`のところ)
  - 盤面を進めた結果がグローバルにメモされているので，現在の盤面の勝敗判定を行う要素(本コードにおけるキューの第2引数が`True`のところ)
- そもそも，再帰関数ではなく，キューの`BFS`で解いてる理由は，`PyPy`の再帰関数が遅いからです．気になる人は調べて下さい．
"""

# 盤面
AA = []
for i in range(3):
  AA.extend(list(map(int, input().split())))
  
# 盤面の和
S = sum(AA)

from collections import deque

# キュー
q = deque()

# 盤面をどのように塗ったか．
TA = [0]*9

# 第一引数: 盤面をどのように塗ったか．
# 第二引数: Trueのとき，まだ塗っていないマスを実際に塗ったら，どっちが勝つかの連想配列に書かれている時に呼ばれるはず
q.append([TA, True])
q.append([TA, False])

# どっちが勝つかの連想配列
# key: 盤面
# val: 1のとき，先手が勝つ，-1のとき，後手が勝つ．
di = {}

# 連想配列のキーを一意にしてる
def ke(TA):
  return sum(map(lambda x: TA[x]*pow(10, x) ,range(9)))

# 横並びにflaの値が揃っているかの判定
def isHor(ls, fla):
  # 最上行が揃っているかの判定
  if(ls[:3].count(fla)==3):return True
  # 真ん中の行が揃っているかの判定
  if(ls[3:6].count(fla)==3):return True
  # 最下行が揃っているかの判定
  if(ls[6:9].count(fla)==3):
    return True
  
  return False
  
# flaの値が縦横斜めに揃っていればTrueを返す．
def isLine(rawLs, fla):
  ls = rawLs
  
  # 左上から右下が揃っているかの判定
  if(ls[:9:4].count(fla)==3):return True
  
  # 左下から右上が揃っているかの判定
  if(ls[2:7:2].count(fla)==3):return True
  
  # 横並びがあるかの判定
  if(isHor(ls, fla)):return True

  # 縦並びがあるかの判定．
  ls = ls[0:9:3] + ls[1:9:3] + ls[2:9:3]
  if(isHor(ls, fla)):return True
    
  return False


# 縦横斜めに揃っているか判定する．
# 揃っていなくて，盤面が全て塗られていれば，どっちが勝ちかを判定する．
# 勝敗が決まっていればTrueを返す．
def judge(TA):
  # 先手が揃えたか．
  if isLine(TA, 1):
    # 先手のかち
    di[ke(TA)] = 1
    return True
    
  # 後手が揃えたか．
  if isLine(TA, -1):
    # 後手のかち
    di[ke(TA)] = -1
    return True
    
  # 全て塗られている時
  if(TA.count(0)==0):
    # 1で塗られた盤面の合計値
    pts1 = sum(map(lambda x: AA[x], filter(lambda x: TA[x]==1, range(9))))
    
    # 先手の方が点数が高い時
    if(pts1>S-pts1):
      di[ke(TA)] = 1
    # 後手の方が点数が高い時
    else:
      di[ke(TA)] = -1
    return True
    
  # 勝敗が決まっていないので，Falseを返す．
  return False
  
while q:
  # BFS
  rawTA, fla = q.pop()
  
  # 現在の盤面で勝敗が決まっているかを判定する．
  if(judge(rawTA)):
    continue
  
  # 塗られてないところを実際に塗ってみる．
  if(not fla):
    for i in range(9):
      it = rawTA[i]
      # まだ塗られてない時，
      if(it==0):
        TA = rawTA[:]
        # 塗ってみる．
        TA[i] = 1 if rawTA.count(0)%2==1 else -1
        # キューに追加
        q.append([TA, True])
        q.append([TA, False])
  # 現在の盤面から到達できる塗るパターンは全て連想配列に入っている（はず）なので，
  else:
    # 先手が勝つパターンある時
    isT = False
    # 後手が勝つパターンがある時
    isA = False
    
    # 到達できるパターンを確認する．
    for i in range(9):
      it = rawTA[i]
      # 塗っていない面を実際に塗ってみる
      if(it==0):
        TA = rawTA[:]
        # 塗る
        TA[i] = 1 if rawTA.count(0)%2==1 else -1
        
        # 塗ってみたパターンが先手の勝ちの時
        if(di[ke(TA)]==1):
          isT = True
        # 塗ってみたパターンが後手のかちの時，
        else:
          isA = True
          
    # 先手のターンのとき
    if(rawTA.count(0)%2==1):
      # 先手が勝つ手がある時
      if(isT):
        # この盤面では先手が勝つとする．
        di[ke(rawTA)] = 1
      else:
        # 後手のかち
        di[ke(rawTA)] = -1
        
    # 後手のターンの時
    else:
      # 後手が勝つてがある時
      if(isA):
        # 後手のかち
        di[ke(rawTA)] = -1
        
      else:
        # 先手のかち
        di[ke(rawTA)] = 1
    
# 空の盤面はどっちの勝ちか
if(di[ke([0]*9)] == 1):
  print("Takahashi")
else:
  print("Aoki")

補足

関係するリンク(参考文献など)

筆者について

その他

間違いを含んでいる可能性があります．
方針と言いつつ，方針ではない感想などを書いている可能性があります．
A問題から解説がだんだん省略されます．

最後に一言

Eの解説読んだ時，「これコンテスト中解けたかも〜」って思ってましたが，いざ実装してみると，無限にバグらせて，コンテスト中絶対解けんかった事が，わからされました．
F問題の復習はサボってます...(*2)

修正

D問題の提出コードにおいて，冒頭の方針部分で提示したサンプルの表示を，一部修正しました．(*1)
最後に一言を追記しました．(*2)