bootcampのeasy100をやった記録 11-20

AtCoderProblemsのTrainingをPython3でやる Easy編
↑これの11-20のやつです。

11.ABC068-B Break Number

Nが$2^i$以上か否かをi=6から0まで降順に調べるとわかります。
全列挙でもいいですが内包表記を使うとオシャレでいい感じだと思いました。

n=int(input())
a=[2**i for i in range(6,-1,-1)]
for i in a:
    if n>=i:
        print(i)
        break

12.ABC160-C Traveling Salesman around Lake

これプログラミングコンテストっていうより算数パズルじゃないのって顔になりました。
家の間の距離$A_{i+1}-A_i(1<=i<=n)$を求めて全部足した後、一番大きいのを引けば良いです。
n+1番目の家は1番目の家の位置にkを加えましょう。

k,n=map(int,input().split())
a=[int(i)for i in input().split()]
distance=[a[i+1]-a[i] for i in range(n-1)]
distance.append(a[0]+k-a[-1])
print(sum(distance)-max(distance))

13.AGC014-A Cookie Exchanges

最初AGCなのを見てうってなって、その後問題文を見てもう一度うってなりました。
無限に続く場合をどう感知するかで詰まりそうになりましたが、

一度現れたパターンをメモしておいて、操作後のパターンがメモ内にあるか確認すれば良い

と考え、それを愚直に書いたらなんとかなりました。
その後、解説を見て無限ループするのはA=B=Cのときだけであることがはっきり分かってとても深い悲しみに包まれました¹。
whileループで書きましたが、再帰関数で書けたりするのでしょうかね。

def existOdd(lst):
    for i in lst:
        if i%2==1:
            return False
    return True

cookie=list(map(int,input().split()))
seen=[]
res=0
while existOdd(cookie):
    seen.append(cookie)
    cookie=[(cookie[1]+cookie[2])/2,(cookie[0]+cookie[2])/2,(cookie[0]+cookie[1])/2]
    if cookie in seen:
        res=-1
        break
    res+=1

print(res)

#14.ABC161-C Replacing Integer
これABC175-Cでやったところだぁ！
あっちよりも場合分けが少ないので簡単ですね。
っていうかこれただのパズルじゃん

n,k=map(int,input().split())
res=min(n%k,k-n%k)
print(res)

#15.ABC132-C Divide the Problems
dをソートしたあと、$d_{n/2}$より大きくて$d_n$以下になる整数Kがいくつあるかという問題です。
それがわかれば引き算をするだけです。
C問題はパズル縛りなのか、それとも問題集の作者が意図的にパズルをこの辺に集中して配置しているのか……。

n=int(input())
d=sorted([int(i)for i in input().split()])
res=d[n//2]-d[n//2-1]
print(res)

#16.ABC142-C Go to School
j番目(1<=j<=n)に入室した生徒の出席番号はa.index(j)+1で求められますが、そのまま書くと計算量が$O^2$で、$n<=10^5$なのでTLEします。しました。

n=int(input())
a=[int(i)for i in input().split()]
res=[]
for i in range(1,n+1):
    res.append(str(a.index(i)+1))
print(" ".join(res))

しばらくのたうち回った後、$a_i$番目(1<=i<=n)に入室した生徒の出席番号はiだということに気づきました。
そっちだと通りました。

n=int(input())
a=[int(i)for i in input().split()]
res=[0 for i in range(n)]
for i in range(n):
    res[a[i]-1]=i+1
print(" ".join(map(str,res)))

こういう感じの「言い換えに気づけるか否か」みたいなのがとても苦手ということがわかりました。
なんで数学パズルしてるんだろうという気分にもなりました。

#17.ABC138-C Alchemist
x<yとするとx+y/2はyより小さいので、vをソートして前から2つ取れば良さそうだなと思いました。
高階関数reduce²を使うとわかりやすい上に格好良いですね。
あと、解説を読んだら却って混乱させられたことをここに書いておきます。
コードもないし、何を言ってるのか全く分かりませんでした。これは本当に今解いた問題の解説なのでしょうか。

from functools import reduce
n=int(input())
v=sorted([int(i)for i in input().split()])
x=lambda x,y:(x+y)/2
res=reduce(x,v)
print(res)

#18.ABC122-B ATCoder
Sの長さをNとすると、部分文字列Tは0<=i<j<=Nとなるi,jにおいて
T=S[i:j+1]で示せます。³
解説見た後だとこのコードすごくダサいですね。まあいいや。

s=input()
acgt=["A","C","G","T"]
res=0
for i in range(len(s)):
    for j in range(i,len(s)):
        t=s[i:j+1]
        tmp=False
        for j in t:
            if not j in acgt:
                tmp=True
                break
        if tmp:
            continue
        res=max(res,len(t))
print(res)

#19.ABC094-B Toll Gates
各$A_i$のうちX以上のものの数とX以下のものの数を比べて、小さいほうを出せば良い。
最初変な勘違い⁴をしてWAした。

n,m,x=map(int,input().split())
a=[int(i)for i in input().split()]
res=0
tmp=[0,0]
for i in a:
    if i<x:
        tmp[0]+=1
    else:
        tmp[1]+=1
res=min(tmp)
print(res)

#20.ABC116-B Collatz Problem

whileループで$a_i$を作って、$a_i$が数列aに入ってたらbreak、入ってなかったらappendでいけました。

s=int(input())
a=[s]
res=0
while True:
    tmp=0
    if a[res]%2==0:
        tmp=a[res]/2
    else:
        tmp=3*a[res]+1
    res+=1
    if tmp in a:
        break
    a.append(tmp)
print(res+1)

#おわりに
数学パズルにアレルギーがあると12-17あたりの問題は拒否反応が出そうですね。

1. 多分そうなんだろうなとは思ったのですが確証が持てませんでした ↩

2. ほかの言語だとfoldとか呼ぶやつ ↩

3. jではなくj+1なことに注意。私はこれで一度WAした。 ↩

4. Xがn/2以上なら正の方向、未満なら負の方向に移動させていた。 ↩