今日の精進(20200102)

あけましておめでとうございます。新年最初から投稿できなかった。AtcoderのStreakも7日で止まってしまった…1週間坊主…。

Derangement

全然わからなかった。解説ACなのでざっくりまとめる。

問題


実際にスワップを行っていくのは計算量的に大丈夫かわからなかったので考察の段階で除外したのだが、1周だけなら大丈夫らしい($10^5$なので、それはそう)。
$P_i = i$である場合にスワップを行うので、これを前からやっていく。$i=N$の場合は$i$と$i-1$を、それ以外では$i$と$i+1$をスワップする。$i=1$以外なら$i-1$ともスワップできるのだが、一度見たところの変更すると面倒なのでまだ見ていないところとスワップする方が簡単だし最善。

#coding: utf-8  
N = int(input())  
P = list(map(int, input().split()))  
l = list(range(1, N+1))  
ans = 0  
for i in range(N-1):  
    if P[i] == l[i]:  
        ans += 1  
        P[i], P[i+1] = P[i+1], P[i]  
if P[-1] == l[-1]:  
    ans += 1  
print(ans)  

みんなでワイワイみかん

算数の問題。AとBの単価を比較して、Aの方がやすいならA*K、そうでない場合にはBをなるべく多く買う。ここで、Kを超えるようにするか、Kを超えないだけBを買って残りはAを買うかで安い方を出力する。

# coding: utf-8  
from math import ceil, floor  
A, B, K, L = map(int, input().split())  
b = B / L  
ans = 0  
if A < b:  
    ans += A * K  
else:  
    t1 = ceil(K / L)  
    t2 = floor(K / L)  
    if t2 < K:  
        t3 = K - t2 * L  
    else:  
        t3 = 0  
    ans += min(t1 * B, t2*B + t3 * A)  
print(ans)  

Template Matching

なんだか難しそうでABC-B問題にもかかわらずずっと放置していたが、何とか出来た。縦にマッチングしていって一番下まで行ったら1列ずらすを繰り返してどこかでマッチしたらYes、マッチしなかったらNo。

# coding: utf-8  
N, M = map(int, input().split())  
A, B = [], []  
for i in range(N):  
    tmp = input()  
    A.append(tmp[:])  
for i in range(M):  
    tmp = input()  
    B.append(tmp[:])  
for r in range(len(A[0]) - len(B[0]) + 1):  
    for i in range(N - M + 1):  
        cnt = 0  
        for j in range(i, M+i):  
            if A[j][r:r+len(B[0])] == B[j-i]:  
                cnt += 1  
        if cnt == M:  
            print("Yes")  
            exit()  
print("No")  

感想

今日も帰省などもあったのであまり時間をかけて取り組めなかった。