ABC149 A～Dについて - masuTomo’s blog

遅ればせながら年末にあったAtCoderのABC149のA ～D問題をやった。

A - Strings

入力された文字列を結合して出力すれば良い（順番に注意）。
各々が使用している言語の文字列結合の方法について学習すれば良い。
私は文字列自体は結合せずに，2つの文字列を出力する際に，空白無しで出力することで対応した。

S, T = input().split()
print(T,S,sep="")

sepオプションはT,Sの出力の間をどのようにするかを決定する。
指定しない場合は空白が入る。空文字列をしていすればT,Sがつづけて出力される。

B - Greedy Takahashi

まず，高橋くんが持っているクッキーのうちK枚（K>AのときはA枚まで）を食べる。
次に，青木くんが持っているクッキーのうちK-A枚（K-A>BのときはB枚まで）を食べる。

A,B,K = map(int,input().split())
if A >= K:
    A -= K
    K = 0
else:
    K -= A
    A = 0
if B >= K:
    B -= K
else:
    B = 0
print(A,B)

C - Next Prime

素数判定ついて知っていれば大丈夫そうである。　　入力Xから始めて順番に素数判定していけばよい。ちょっと変わったやり方してみた

def makePrime(n):
    i = 3
    while i*i < n:
        for p in P:
            if i%p == 0:
                i += 2
                break
        P.append(i)
        i += 2

X = int(input())
if X == 2:
    print(2)
    exit()
P = [2]
makePrime(X)
flg = 0
while 1:
    flg = 1
    for p in P:
        if X%p == 0:
            flg = 0
            X += 1
            break
    if flg:
        print(X)
        exit()

X以下の素数をあらかじめ列挙しておいて，X以上の数に対して，X以下のすべての素数で割り切れないようなもののうち最小のもの求めるものである。

D - Prediction and Restriction

じゃんけんで相手の出す手がわかっている。ただし自分はK回前と同じ手は出せない，という条件。

貪欲法で解けばよい。つまり勝てるときは勝ち，Ｋ回前の手の制限により勝てる手が出せない場合はＫ回あとで勝てなくならないように手を出す。ちなみにあいこと負けは0点でまったく同じなので，勝ち以外の手のどちらを出したかは結果の得点には関係しない。

def getPt(h):
    if h == "s":
        return R
    elif h == "p":
        return S
    elif h == "r":
        return P

N, K = map(int,input().split())
R, S, P = map(int,input().split())
T = list(input())
pt = 0
for i in range(N):
    #最初のK回は必ず勝てる
    if i < K:
        pt += getPt(T[i])
    else:
        #相手の出す手がK回前と同じときは，今回は勝てない
        if T[i] == T[i-K]:
            #i回目ではあいこor負けの手を出すので，
            #K回後では必ず勝てるので，T[i]を書き換えておく
            T[i] = "" 
        else:
            pt += getPt(T[i])
print(pt)

なぜ貪欲法で解けるのか

上記の貪欲法よりも得点が高い手があると仮定する。上記の方法でi回目のじゃんけんで勝てない（得点が入らない）のはK回前のじゃんけんで同じ手を出しているからである。　　　 i回目のじゃんけんで勝つためにはi-K回目のじゃんけんで違う手を出す必要があるが，そうするとi-K回目のじゃんけんで勝てないことになる。ここで，i回目のじゃんけんとi-K回目のじゃんけんで得られる得点は（同じ手で勝っているので）同じ得点である。
もし，i-K回目で勝たずにi回目で勝つように手を変えても得られる得点は同じ（もしくはi回目のじゃんけんがない場合は得点が減る）なので，上記の方法が最善であることがわかる。

E,Fについて

まだちょっと僕には難しいです。　　　がんばります(やってない）。