プログラミングチャレンジブックをpython3で解いてみる

初めに

　プログラミングを始めて数か月だが、atcoderを解くうえで必要な知識が圧倒的に足りないことを思い知り、プログラミングチャレンジブック（通称：蟻本）を解いてみようと思った。kaggleなどデータ分析にも興味があることもありpythonで解いていこうと思う。

1-6 三角形

n = 4
a = {4,5,10,20}
a = sorted(list(a))
ans = []

for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if a[k] < a[i]+a[j]:
                ans.append([a[i],a[j],a[k]])
if ans==[]:
    print(0)
else:
    ans2 = []
    for i in range(len(ans)):
        ans2.append(sum(ans[i]))
    print(max(ans2))

aをソートし、小さい順に並べる。同じ値は2度とれないから、i以上からjを選ぶというようにすればいい。また、iよりも大きい値を2個残しておく必要がある。

Ant (POJ No.1852)

L = 10
n = 3
x = [2,6,7]
#maxを求める時
ans = L-min(x)

#minを求める時
for i in range(n):
    x[i] = min(x[i],L-x[i])
ans2 = max(x)

print("min =",ans2)
print("max =",ans)

実は、2匹のアリはすれ違ってそのまま進んでいったと思ってしまっても何も問題ないことがわかります。…（中略）…最大の時間を求めるためには橋での距離の最大値を求めればよいことになります。

ハードルがあがった「くじ引き」

n = 3
m = 9
k= set([1,3,5])
a = set([])
for i in k:
    for j in k:
        a.add(i+j)
a = list(a)
#print(a)
n = len(a)
exist = False
for i in range(len(a)):
    for j in range(len(a)):
        l = 0 #検索範囲の左端
        r = n #検索範囲の右端
        while (r - l >= 1) and exist==False: #検索範囲がなくなったら処理を終了する
            i = (l + r) // 2 #iにデータの真ん中の位置を持たせる
            if a[i] == m-a[j]:
                exist = True
                break
            elif a[i] < m-a[j]:
                l = i + 1
            else:
                r = i
if exist== True:
    print("Yes")
else:
    print("No")

難しかった、、
四つえらぶところを、2個と2個に分けてあり得る選択肢を探した。この時の2個のとりえる値は同じ。とりえる値をリストa に入れると、a[i]==m-a[j]を探せばよいことになる。ここから二分探索をして答えを求める。

部分和問題

n = 4
a = [1,2,4,7]
k = 14
def dfs(i,s):
    if i == n:  #n個決め終わったら、今までの和sumがｋと等しいかを返す
        #print(s)
        return s == k
    if dfs(i+1,s):  #a[i]を使わない場合
        #print("not use", i)
        return True
    if dfs(i+1,s+a[i]):  #a[i]を使う場合
        #print("use", i)
        return True
    #print("f",s)
    return False  #a[i]を使う使わないにかかわらずｋでないのでfalseを返す

if dfs(0,0):
    print('Yes')
else:
    print('No')

深さ優先探索(dfs)を用いた全検索の問題。a[i]を使う時と使わないときすべてについて調べてkと等しいか調べてる。コメントになってるprint外してみるとわかりやすいかも。

Lake Counting

入力例）
N=10
M=12
w........ww.
.www.....www
....ww...ww.
.........ww.
.........w..
..w......w..
.w.w.....ww.
w.w.w.....w.
.w.w......w.
..w.......w.

def dfs(x,y):
    field[x][y] = "."
    for dx in range(-1,2):
        for dy in range(-1,2):
            nx = x+dx
            ny = y+dy
            if 0<=nx<n and 0<=ny<m and field[nx][ny]=="W":
                dfs(nx,ny)

n, m = 10, 12
field = [['W', '.', '.',  '.', '.', '.', '.', '.', '.', 'W', 'W', '.'],
         ['.', 'W', 'W', 'W', '.', '.', '.', '.', '.', 'W', 'W', 'W'],
         ['.', '.', '.', '.', 'W', 'W', '.', '.', '.', 'W', 'W', '.'],
         ['.', '.', '.', '.', '.', '.', '.', '.', '.', 'W', 'W', '.'],
         ['.', '.', '.', '.', '.', '.', '.', '.', '.', 'W', '.', '.'],
         ['.', '.', 'W', '.', '.', '.', '.', '.', '.', 'W', '.', '.'],
         ['.', 'W', '.', 'W', '.', '.', '.', '.', '.', 'W', 'W', '.'],
         ['W', '.', 'W', '.', 'W', '.', '.', '.', '.', '.', 'W', '.'],
         ['.', 'W', '.', 'W', '.', '.', '.', '.', '.', '.', 'W', '.'],
         ['.', '.', 'W', '.', '.', '.', '.', '.', '.', '.', 'W', '.']]

res = 0
for i in range(n):
    for j in range(m):
        if field[i][j] == "W":
            dfs(i, j)
            res += 1
print(res)

迷路の最短路

from collections import deque
INF = float("inf")

def bfs():
    d = [[INF]*m for i in range(n)]

    dx = [1,0,-1,0]
    dy = [0,1,0,-1]

    for i in range(n):
        for j in range(m):
            if maze[i][j] == "S":
                sx=i
                sy=j
            if maze[i][j]=="G":
                gx=i
                gy=j
    que = deque([])
    que.append((sx,sy))
    d[sx][sy] = 0

    while len(que)>0:
        p = que.popleft()
        if p[0]==gx and p[1]==gy:
            break
        for i in range(4):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if 0<=nx<n and 0<=ny<m and maze[nx][ny]!="#" and d[nx][ny]==INF:
                que.append((nx,ny))
                d[nx][ny]= d[p[0]][p[1]]+1
    return d[gx][gy]

n = 10
m = 10
maze = [
    ['#', 'S', '#', '#', '#', '#', '#', '#', '.', '#'],
    ['.', '.', '.', '.', '.', '.', '#', '.', '.', '#'],
    ['.', '#', '.', '#', '#', '.', '#', '#', '.', '#'],
    ['.', '#', '.', '.', '.', '.', '.', '.', '.', '.'],
    ['#', '#', '.', '#', '#', '.', '#', '#', '#', '#'],
    ['.', '.', '.', '.', '#', '.', '.', '.', '.', '#'],
    ['.', '#', '#', '#', '#', '#', '#', '#', '.', '#'],
    ['.', '.', '.', '.', '#', '.', '.', '.', '.', '.'],
    ['.', '#', '#', '#', '#', '.', '#', '#', '#', '.'],
    ['.', '.', '.', '.', '#', '.', '.', '.', 'G', '#'],
    ]
print(bfs())

硬貨の問題

c = [3,2,1,3,0,2]
a = 620
v = [1,5,10,50,100,500]
for i in range(1,7):
    t = min(a//v[-i],c[-i])
    a = a - (t*v[-i])
    ans = ans+t
print(ans)

tは、a/500と500円の枚数の少ないほうになります。それで少ないほうかける500円をして、aから引きます。

区間スケジューリング問題

from operator import itemgetter
n = 5
s = [1,2,4,6,8]
t = [3,5,7,9,10]
st = sorted([(s[i], t[i]) for i in range(n)], key=itemgetter(1))
#print(st)
ans = 0
last = 0

for i in range(n):
    if last < st[i][0]:
        ans += 1
        last = st[i][1]

print(ans)

貪欲法では解けない問題もあるから注意

Best Cow Line

n = 6
s = "ACDBCB"
t = ""
a = 0
b = n-1
while a<=b: #文字列がなくなるまで
    left = False
    i = 0
    while a+i <= b: #意味的にはさっきのwhile と同じかな？
        if s[a+i] < s[b-i]:
            left = True
            break
        elif s[a + i] > s[b - i]:
            left = False
            break
        i = i+1
    if left:
        t = t+s[a]
        a = a+1
    else:
        t = t+s[b]
        b = b-1
print(t)

文字でも大小を比べられるのにはびっくり。

if "B">"A":
    print("yes")

これで、yesが出力されます。

Saruman's Army

n = 6
r = 10
x = [1,7,15,20,30,50]
pos = 0
cnt = 0
while True:
    if r>=x[n-1]:
        break
    for j in range(n):
        if x[j]>r:
            break
    pos = x[j-1]
    cnt += 1
    r += pos
print(cnt)