A問題
ポイント
- 1000以下の数字だけが気になるので1000で割ったあまりをまず求める
- 境界条件として1000を入れると、そのままでは1000が返ってきてしまう。しっかりテストして気が付こう
a.py
N = int(input())
tmp = N%1000
if tmp == 0:
print(0)
else:
print(1000 - tmp)
B問題
ポイント
- 簡単な条件分岐の問題は手打ちで条件を列挙すればいい
- 条件ごとのカウンタは個別に変数を用意してもよいが、コピペしにくくなるので配列で管理した方が楽
b.py
N = int(input())
res = [0]*4
for i in range(N):
s = input()
if s == "AC":
res[0] += 1
elif s == "WA":
res[1] += 1
elif s == "TLE":
res[2] += 1
elif s == "RE":
res[3] += 1
print(f"AC x {res[0]}")
print(f"WA x {res[1]}")
print(f"TLE x {res[2]}")
print(f"RE x {res[3]}")
C問題
ポイント
- まず、そもそも、AtCoderではpandasが使えない。そのためデータフレームのようなものはnumpyのarrayを用いる
- HもWも最大値が6であり、行と列について選択の有無の2パターンがあるので、(2*6) * (2*6)のパターン
- このくらいなら全探索してよさそう
- しかし、選択する組み合わせはrange(H)ではなく、range(2**6)の範囲なので注意
- ループを回した際、それを選択の有無に変換するには、2進数の01を用いればよい
- binで2進数にできる
- rjustで桁数を調整
- ところでこれはビット全探索と呼ばれており、2進数に直すよりも賢い探索方法がある様子
- 詳細は後述
- どの列や行を使うかが決まったら、これを入力のデータフレームに反映する方法を考える
- numpyのarrayは行を増やす方向にブロードキャストして掛け算してくれるので、一括でフィルタリングできる
- これが思いつかなければ、愚直にi,j!=選択行・列の場合の＃をカウントするのでもよかったみたい
- また、高速化が必要な場合はpypy、@jitなどあるみたい
- 詳細は後述
c.py
import numpy as np
H,W,K = list(map(int, input().split()))
t=[]
for i in range(H):
t.append([int(i) for i in input().replace(".","0").replace("#","1")])
cnt = 0
for i in range(2**H):
for j in range(2**W):
d = np.array(t)
i_2 = [int(k) for k in bin(i)[2:].rjust(H,"0")]
j_2 = [int(k) for k in bin(j)[2:].rjust(W,"0")]
d= ((d.T)*i_2).T
d= d*j_2
num = d.sum()
if num == K:
cnt +=1
print(cnt)
D問題
動作を再現する愚直なアルゴリズムは理解できたが、LTEだった。計算量を見積もる必要がある。
ポイント
- 円はリストとして展開した方がわかりやすい。
- a,b,c,d が円状にあるとき、[a,b,c,d,a]と、ある要素を基準に展開できる。
- 小さい値を早く登場させることでポイントが上がるようなパターンは存在しない。よって、降順にソートして円に加えることを考える
- ポイントが大きくなるように挿入を試していくと、各数値は最大2回得点として加算されることがわかる
- 最初の値は1度だけなので注意
- 手でシミュレーションしてみて、結局なにがキモなのかを理解することが重要。D問題でも解法がこんなに簡潔になることもある。
D.py
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
p = a[0]
for i in range(N-2): #-1は上記a[0]分、もう-1は最初の要素挿入は加点されないため。
p += a[(i//2)+1] #1,1,2,2,3,3...を生成
print(p)
D_LTE.py
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
p=0
ppl = [a[0]]*2
best_index = 1
best_point = a[0]
for i in a[1:]:
p += best_point
ppl = ppl[:best_index]+[i]+ppl[best_index:]
#print(ppl)
point_list = [min(ppl[i],ppl[i+1]) for i in range(0,len(ppl)-1)]
#print(point_list)
best_point = max(point_list)
for j,q in enumerate(point_list):
if q == best_point:
best_index = j+1
continue
print(p)
ビット全探索
Yes/Noがn個ある状態＝2^nの選択肢がある場合に、組み合わせの全列挙を行う方法としてビット全探索が知られているようです。
ポイントは以下です。
- i>>j はiを2進数にしてj分右に移動。出力は10進数。
- 6 (0b110) >> 1 の出力は 3 (0b11)。
- すなわち、変換後の一桁目に元の(j+1)桁目が来る。
- &は2進数の各桁同士の論理積。
- x & 1 はxを2進数にしたときの一桁目の数字(=奇数なら1)を取得することになる。
#このiを2進数に変換して、その0/1の組み合わせで探索を行う
for i in range(2**n):
#yes/noを調べる場所はn個
for j in range(n):
#iを二進数にして、一桁ずつシフト。
#それが00..01でマスクしたときに1が確認。
if((i>>j) & 1):
#このときj番目の要素はYes
pypy
提出の言語でpypyを選択するだけ。
numpyを使用できないなど、注意もある。
性能比較はこちら https://qiita.com/OKCH3COOH/items/f0c5c4681bc30dddf7f4
@jit
関数をデコレートするだけで高速化が実現できるようです。
from numba import jit
@jit
def 任意の関数:
#任意の処理
他にもnjitなどある。