APG4bをPythonで解きたい（第2章）

はじめに

諸々の事情により、Atcoderで公開されているAPG4b問題をPythonを用いて解いてみます。
第1章は有志の方が公開してくださっているものを解いてみたので、第2章からは自分で読み解いてからEX問題にチャレンジしてみます。
Pythonについては大学で半年程度触っただけの初心者なので、もっと短く（もしくは効率よく）できる箇所がありましたらご教示頂けると幸いです。目標としては「効率的に問題が解ける」コードを目指していきます。
あと、時間的な都合により、EXテストでACが出たら模範解答をざっと読むだけで書き直しはしません。

2.01.ループの書き方と範囲for文

ループの書き方
例題

a = int(input())
data = list(map(int,input().split()))

answer = 0

for i in range(len(data)):
  if data[i] == a:
    answer += 1

print(answer)

範囲for文
例題

a = [1,3,2,5]

for i in a:
  print(i)

本家では「コンテナ型でもfor文を使用することができる」とありましたが「コンテナ型ってなんだ……？」と疑問に思ったので調べました。
listやdict等の各要素をまとめて保存している型をコンテナ型というのかな……？intやstrをデータ型と呼ぶみたいなものでしょうか。
そういうことにしておいて、ここらへんは一旦置いておきます。

細かい話
ループの使い分けについて

• 配列の要素全てに対して処理を行いたいとき → 範囲for文
• ↑の条件以外で一定回数繰り返し処理する場合　→　for文
• それ以外の場合　→　While文

まず最初に思ったのが「While文いつ使うんだ……？」でした。
私が大学で使った時は、boolean型の変数をフラグとしてWhile文を回していたのですが、実際にこの手段は使うのだろうか……？と疑問に思いながらぽちぽちしていました。

While文が適しているケース

n = int(input())

count = 0

while n > 0:
  if n % 2 > 0:
    break
  n /= 2
  count+=1

print(count)

「特定の要素が条件に満たしている間だけ」に有用。
よく考えたら大学でもそういう使い方してました（フラグ的な扱い）。

EX16 - 隣り合う同じ値を探す

data = list(map(int,input().split()))

keep=0
flag=False

for i in data:
  if keep==i:
    flag=True
    break
  keep=i

if flag==True:
  print("YES")
else:
  print("NO")

2.02.多重ループ

多重ループ
ループの中でループする。
あまり褒められたやり方ではないと聞いたことがあるのですが、すみませんソースが思い出せません。
以前、他の人が書いたコードを見る機会があったのですが、多重ループされると「これどういう意図でか書いてるんだ……？」と読み解くのに時間がかかることがありました。主に自分の能力不足が原因ですが！ね！！

for i in range(3):
  for j in range(3):
    print("i:{},j:{}".format(i,j))

例題「3要素の2つの配列A, Bに同じ要素が含まれているかどうか判定する」

A = list(map(int,input().split()))
B = list(map(int,input().split()))

answer = False

for i in range(3):
  for j in range(3):
    if A[i]==B[j]:
      answer = True

if answer == True:
  print("YES")
else:
  print("NO")

確か、多重ループしなくても配列要素の重複って確認できましたよね。
可読性的な観点からも、そっちの方法の方がわかりやすくて良いと思いつつ脳死で書いてしまう。

多重ループのbreak/continue

• 多重ループでbreak/continueを使うと一段階ループを抜けることができる。

これに尽きますよね。
例題の多重ループで言うと「『for j ~』 のところでbreak/continueすると『for i ~』に行く」ってことですよね。ちょっとわかりづらいのですが、というかわかりづらいな。
ここの部分に関しては、本家にわかりやすい例が載っています。

添字のミス
ここに関しては「変数名決めるのって大事だなぁ……」と思えたら、製作者の意図に沿えてると思います。
「i」と「j」ってぱっと見わかりにくいので駄目ですよね。でも、for文回すときに常に使ってしまいますね、いつも。
そういえば1年次に私、大学では「一文字の変数はやめろ」と教わったような気がします。
しかも提出する課題でこれ多様していたような。先生、すみませんでした……。

EX17 - 果物屋さんでお買い物

N,S = map(int,input().split())

A = list(map(int,input().split()))
P = list(map(int,input().split()))

count = 0
total = 0

for ap_price in A:
  for pin_price in P:
    total = ap_price + pin_price
    if total == S:
      count+=1
    else:
      total = 0

print(count)

2.03.多次元配列

2次元配列
すみませんC++に関して全くの無知なので、本家を読んで「なんで配列作るだけでこんなにコード書くんだろう」としか思えませんでした。
随分前にC言語(++ではない)を触った時に「メモリ確保」なる単語が出てきたので、配列の容量を確保するために色々手順を踏んでいるのだと思います。いや、やっぱりちょっとわからないですね。Pythonに戻ります。

例題

data = []
for i in range(3):
  data.append(list(map(int,input().split())))

count = 0
for i in range(3):
  for j in range(4):
    if data[i][j] == 0:
      count+=1

print(count)

宣言
上の例題で言うとこの箇所ですよね。

data = []
for i in range(3):
  data.append(list(map(int,input().split())))

あらかじめ宣言しておいたlist型変数のdataに、標準入力された行をlistに変換したものをappendするだけ。
これ宣言って言っていいのでしょうか？

アクセス
上で作成した2次元配列のdataで言うと

data[上から数えて何番目か][左から数えて何番目か]

大きさの習得
本家で示されていた「大きさの習得」が（縦の長さ,横の長さ）だったので、
numpyをimportして調べる方法を書きます。わかりやすいものだとそれしかわからない…

import numpy as np

#2次元配列をつくる
data = []
for i in range(3):
  data.append(list(map(int,input().split())))

#NumPy配列にして.shapeする
data = np.array(data)
print(data.shape)

2次元配列の考え方
本家がとてもわかりやすいです。
んだけど、Pythonでは必要ないことも書いてある……気がしなくもないのですが、某大学の2年次前期でどうしても使わないといけない知識なので、やっぱり読んだ方がいいですね。
いつの日か先輩から「色々な言語を触っていると、初めて触る言語でも雰囲気でなんとなくわかってしまう」と伺ったので、Pythonで必要ないかな？と思ったことでも知識としてちゃんと読み込んで、いつの日か役に立つ日を夢見るのは大事ですね。大事ですよね！！！！！！！

多次元配列

例題
すみません書き直せませんでした……
この問題の入力は複数個の3×3形式の○×問題なのですが、その○×問題の間にある空行がどうしても多次元配列に入ってしまい、最後の行が読み込めない状況になってて詰んでいます……
私の癖として、こういうようわからん所でつまづいて無限に時間を使ってしまうので、一旦冷静になってからやり直します。
というかさっきから誰に謝っているんだ。

それ以降
上の問題が解けていないので、解けてから後日やります。

EX18 - ゲーム大会

n,m = map(int,input().split())

lists = []
for i in range(m):
  lists.append(list(map(int,input().split())))

result = []
results = []
for i in range(n):
  for j in range(n):
    result.append("-")
  results.append(result)
  result = []

for i in lists:
  win = i[0]
  lose = i[1]
  results[win-1][lose-1] = "o"
  results[lose-1][win-1] = "x"

for i in results:
  j=" ".join(i)
  print(j)

これは絶対によくない書き方です。とにかくACをもぎ取るために即興で書きました。
後日上の演習問題と一緒に修正します。

2.04.参照

参照

とある変数から別の変数を参照すること。
これPythonでもできるのかな？と思いざっと調べてみた所、「イミュータブル」と「ミュータブル」という概念を見つけました。
「イミュータブル」というのは文字列や数値などのことを言い、この概念に属するオブジェクトは本家のようにとある変数から別の変数の数値を変更することはできません。
反対に、「ミュータブル」に属する辞書やリスト等のオブジェクトは、本家のように変数から別の変数への書き換えができるそうです。ほんとかな。

a = 3
b = a
#aの数値である3が出力される
print(b)

b = 4
#本家だとaの数値が置き替わり、4が出力される
#けど数値のオブジェクトはイミュータブルなので、置き替わらずに3が出力される
print(a)


a_list=[1,2,3]
b = a_list

b[0] = 4
#本家通りになるなら、a_listの0番目の要素が書き換わって[4,2,3]になる
#listのオブジェクトはミュータブルなので、置き換わって[4,2,3]が出力される
print(a_list)

こんな仕組みがあったのか。知らなかった……
C++だと全てのオブジェクトがミュータブルなのかな、と思ったりしたのですが、確か遠い昔にC(++ではない)を触ったときに、C言語って変数をメモリ的に管理してるっていう話を聞いたような気がします。
いやでもあの時同時進行でHaskellの勉強してたからな……すみませんちょっと思い出せないに加えて記憶が混濁してるので無かったことにしてPythonに戻ります。

これ以降
本家読んだ方がわかりやすい(あとPythonと違いそう)……だがしかし、ここらへんの仕組みってPythonとC++一緒なんですか？
Pythonはインタプリタ言語でC++はコンパイル言語ですよね。
この二つの違いって実行時にコンパイルするかしないかって事しか知らないのですが、実行方法が違うだけで根本的な挙動は一緒なのでしょうか……？
これ以上はあとで自分で調べてみます。わかるかわからん。

EX19 - 九九の採点

A = []
for i in range(9):
  line = list(map(int,input().split()))
  A.append(line)

correct_count = 0
wrong_count = 0

def saiten(A,correct_count,wrong_count):
  for i in range(9):
    for j in range(9):
      if A[i][j] == (i+1)*(j+1):
        correct_count+=1
      else:
        wrong_count+=1
        A[i][j]=(i+1)*(j+1)
  return A,correct_count,wrong_count

A,correct_count,wrong_count = saiten(A,correct_count,wrong_count)

for i in range(9):
  line =[str(a) for a in A[i]]
  line=' '.join(line)
  print(line)

print(correct_count)

print(wrong_count)

正答数と誤答数を示す「correct_count」「wrong_count」はイミュータブルなオブジェクトなので、採点を行う「saiten()」関数内で数値の置き換えができません。なのでreturnで結果を返しています。
計算結果を格納している二次元配列の「A」はミュータブルなオブジェクトなので関数内での置き換えができます。なのでreturnさせていません。

これまでイミュータブルやらミュータブルやら専門用語らしい言葉を使っていますが、これ全部間違ってたらかなり滑稽なことになっていそう。
古文に出てくる「わろし」の意味を「とてもおもしろいさま」だと勘違いして国語の先生の前で多用していたら顔をしかめられる、みたいな。人生で一度はやる。

2.05.再帰関数

• ある関数の中で同じ関数を呼び出すことを「再帰呼び出し」という
• 再帰を行う関数を「再帰関数」という

これ1年次のときに学んだんですけど、あれ以来再帰を使った記憶がありません。
本家ではこれ難しい部類に入るそうで、「説明を読んでわからなかったら飛ばしても構わない」と書かれていました。え？これやっぱりあまり使わないやつなの？

私もほんやりとしか覚えていないので、演習のコードを書いて思い出してみます。

def sum(n):
  if n == 0:
    return 0

  s = sum(n - 1)
  return s + n

print(sum(2))　# 0 + 1 + 2 = 3
print(sum(3))　# 0 + 1 + 2 + 3 = 6
print(sum(10)) # 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55

どう言葉にすればいいのかわからねぇ。

sum(n)はif n == 0のときにreturn 0、つまり0を返すようになっていて、
次のs = sum(n - 1)で再帰動作を行なっている。
nから1を引いた数を再帰呼び出しに突っ込んで、nが0になった時に再帰を終了させて計算を行なっている……？

この関数の気持ちは分かるのですが、文章にするとなると難しいなこれ。
箇条書きにしてみよう。

sum(2)の場合

【1ループ目】n=2なのでif文はパス。s = sum(n - 1)はs = sum(1)になる。ここで再帰。
　　　⬇︎
【2ループ目】n=1なのでif分はパス。s = sum(n - 1)はs = sum(0)になる。ここで再帰。
　　　⬇︎
【3ループ目】n=0でif文にgo。returnで0が返す。
　　　⬇︎
【2ループ目】s = sum(n - 1)が3ループ目に返された値であるs = 0になる。n=1なのでreturn s + nをして1を返す。
　　　⬇︎
【1ループ目】s = sum(n - 1)が2ループ目に返された値であるs = 1になる。n=2なのでreturn s + nをして3を返す。終わり。

こういうことだわ。これが私の気持ちだわ。いや、これ初見難しいな。
こういう問題を解く分には楽しそうなのですが、実戦で使うとなると可読性とか大丈夫なのでしょうか。
私のレベルだと箇条書きにしないと難しいのですが、熟練した方となるとやはりぱっと見でわかってしまうのでしょうか。精進しないと……

これ以降
本家を読もう。わかった(わけではない)。私はちょっと難しかった。けど内容的には2年次前期のアルゴリズムの授業でちょっとやった。
いや正直、本家の内容って実戦云々ではなく教科書的に読んだ方がいいのかもしれない。
「こういうやり方があるんやよ〜」って雰囲気で読んだ方がよろしいのかもしれない。
けど私だったらif文とかフラグとかをばりばり立ててやっちゃうだろうな…ぱっと思いつけない。

EX20 - 報告書の枚数

n = int(input())
read_line = list(map(int,input().split()))

p = []
for i in range(n):
  if i == 0:
    p.append(-1)
    continue
  p.append(read_line[i-1])

key = list(dict.fromkeys(p))
children={}

for i in key:
  value_list = []
  for j in range(n):
    if i == p[j]:
      value_list.append(j)
  children[i]=[]
  for k in value_list:
    children[i].append(k)

def count_report_num(chlidren,x):

  if children.get(x)==None:
    return 1

  sum = 0
  for i in children[x]:
    sum += count_report_num(chlidren,i)
  sum+=1
  return sum


for i in range(n):
  print(count_report_num(children,i))

再帰の動作がどうしてもわからなかったので、模範回答を参考にしました…
あと、c++だと配列に子要素を追加できるそうなのですが、Pythonでのやり方がわからなかったのでdict型で実行する形にしました。難しかったです。

2.06.計算量

• プログラムの計算量を見積もる「オーダー法」について

本家の説明をじっくり読む。とてもわかりやすかったです。
これも某大学2年次前期にやる内容なので、ためになる内容だと思いました。

• for文1重だとN、2重だとN^2
• 「特定の数字Nが2で何回割れるか？」とかの場合はlogが使える
• 速さ(遅い順)　 [O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N)]

EX21 - 計算量の見積もり

これは本家に答えもあるし、書き換えもしなくて良いので(コメントアウトだけ)、書かなくて良いのだろうか。