AtCoder Problems Hard No.71~80解説

#Hard No.71 : C - Linear Approximation
C - Linear Approximation
##発想
とりあえず$A_i$を

A_i' = A_i-i

に変換します。このとき

\sum|A_i'-b_{ \ }|

を最小にする$b$は何か考えます。この$b$は中央値になります。$b$が中央値であれば、$b$を少し移動させたときに、増加する$|A_i'-b_{ \ }|$と減少する$|A_i'-b_{ \ }|$の個数が等しくなります。つまり微分が0になるので、$b$が中央値であることがわかります。

##実装
データ数が偶数であるときは中央値はlow, highの2種類出てくるので、そのうち小さいほうを採用します。

import statistics

N = int(input())
A = list(map(int, input().split()))

Am = []
for i in range(1, N+1):
    Am.append(A[i-1]-i)

Am = sorted(Am)
mid_low = statistics.median_low(Am)
mid_high = statistics.median_high(Am)

ans_low = 0
for i in range(N):
    ans_low += abs(Am[i]-mid_low)
ans_high = 0
for i in range(N):
    ans_high += abs(Am[i]-mid_high)
    
ans = min(ans_low, ans_high)
print(ans)

#Hard No.72 : C - 4/N
C - 4/N
##発想
何も考えずに考えると、$h, n, w$の3種類の文字がそれぞれ1~3500まで動くので、$3500^3$でTLEします。条件式が与えられたらその条件式を使って文字を1つ消去できるので、例えば$h, n$を動かしたとき$w$が整数になるか判定すれば良いです。
##実装

w = \frac{Nhn}{4nh-N(h+n)}

となるので分母、分子をそれぞれ計算します。0除算に注意します。

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        w_above = N*h*n
        w_below = 4*h*n - N*(h+n)

        if w_below != 0:
            w = w_above // w_below
            if w > 0 and w_above % w_below == 0:
                print(h, n, w)
                exit()

#Hard No.73 : C - Strange Bank
C - Strange Bank
##発想
できるだけ大きい金額でお金を引き出したほうが、引き出す回数は少なくて済みます。引き出す回数は残りの金額によって刻々と変化しますので、動的計画法を使います。
##実装
引き出す金額のリストを予め作っておきます。
$dp[i]$の定義は以下のようにします。

dp[i] : 残りの金額がiの時にお金を引き出す回数の最小値

N = int(input())

Six = []
six = 6
while six < 100000:
    Six.append(six)
    six *= 6

Nine = []
nine = 9
while nine < 100000:
    Nine.append(nine)
    nine *= 9

#1回で引き出す金額のリスト
A = [1] + Six + Nine
A = sorted(A, reverse=True)

dp = [10**9+1]*(N+1)
dp[0] = 0

for i in range(1, N+1):
    #1回で引き出す金額が大きい方から調べる
    for a in A:
        if i - a >= 0:
            dp[i] = min(dp[i], dp[i-a] + 1)

print(dp[N])

#Hard No.74 : D - Harlequin
D - Harlequin
##発想
思いついたら勝ち！思いつかなかったら負け！敗者に人権はない！って感じがしてつらい気持ちになります。とりあえずリンゴの数が少ない状況で実験してみます。
（１）リンゴが2つ（色は1, 1）
1つ自分がとった後、ルンルンが最後の1個を取るので負けです。
（２）リンゴが3つ（色は1, 1, 2）
自分が2のリンゴをとった後、（１）の状況になるので私の勝ちです。
以上より奇数個のリンゴがあれば、それらを1つずつ最初に取ることで私の勝ち、すべて偶数個であればルンルンの勝ちになります。

##実装

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
    
for i in range(N):
    if A[i] % 2 == 1:
        print('first')
        exit()

print('second')

#Hard No.75 : D - Face Produces Unhappiness
D - Face Produces Unhappiness
##発想
$l,r$はどのように選べばよいか。例えば'LRRL'という並びがあったときは2つの'L'に挟まれた'RR'をまとめて回転させるように選べばよいです。「挟まれている文字列の個数」は'LR'と'RL'の個数を数えればよいです。

##実装

N, K = map(int,input().split())
S = input()
C = S.count('RL')+S.count('LR')

#幸福な人数の最大値はN-1
#操作回数が余るときはC-2*K < 0となるので、その時は0にする
print(N-1 - max(C - K*2, 0))

#Hard No.76. : C - たくさんの数式
C - たくさんの数式
##発想
$|S|$の最大値が10なので'+'を入れる箇所を全探索できそうです。
##実装
$S$の末尾を最後に追加するのを忘れそうです。出てきた数式の計算はeval()を使います。文字列をそのまま数式として計算し、結果を返してくれます。

S = list(input())
N = len(S) - 1
ans = 0

#全探索
for i in range(2**N):
    #Sに'+'が追加されたS_plus
    S_plus = []
    for j in range(N):
        S_plus.append(S[j])
        if i >> j & 1 == 1:
            S_plus.append('+')
    #Sの末尾の文字を追加
    S_plus.append(S[-1])

    S_plus = ''.join(S_plus)
    ans += eval(S_plus)

print(ans)

#Hard No.77 : A - 01 Matrix
A - 01 Matrix
##発想
とりあえず小さい状況で実験します。例えば3×3の行列で$A=1,B=1$の時を考えます。$A=1$だけ意識して行列を作ると、

\begin{bmatrix}
0 & 1 & 1\\
0 & 1 & 1\\
0 & 1 & 1
\end{bmatrix}

という形になります。この形では$B=3$になってしまいます。$B=1$にするためにはどうすればよいでしょうか。例えば1行目をすべて0に変えた行列は

\begin{bmatrix}
0 & 0 & 0\\
0 & 1 & 1\\
0 & 1 & 1
\end{bmatrix}

になります。これだと2,3行目と2,3列目は$A=1,B=1$を満たしますが、1行目と1列目が満たすことができません。そこで$(1,1)$を変更すると、

\begin{bmatrix}
1 & 0 & 0\\
0 & 1 & 1\\
0 & 1 & 1
\end{bmatrix}

となり、これですべての行、列で$A=1,B=1$を満たします。このように行列を4か所に分けた形にすれば良さそうです。
それらは
(1)上から$B$個、左から$A$個は1
(2)下から$H-B$個、右から$W-A$個は1
(3)それ以外は0
とすれば良いです。
##実装

H, W, A, B = map(int, input().split())
Ans = []
for i in range(H):
    Ans.append(['0']*W)

for i in range(H):
    for j in range(W):
        if i < B and j > A-1:
            Ans[i][j] = '1'
        if i > B-1 and j < A:
            Ans[i][j] = '1'

for i in range(H):
    print(''.join(Ans[i]))

#Hard No.78 : C - K-th Substring
C - K-th Substring
##発想
$K$は5以下であり、考えるべきsubstringのうち最大の文字数は$K$以下です。substringの文字数と$S$の位置で2重ループを組めばよいです。
##実装
重複した文字は消したいのでset()を使います。

S = input()
K = int(input())
Ans = set()

# i：文字数
for i in range(1, K+1):
    # j：スタート位置
    for j in range(len(S)-i+1):
        tmp = S[j:j+i]
        Ans.add(tmp)

Ans = sorted(Ans)
print(Ans[K-1])

#Hard No.79 : D - Handstand
D - Handstand
##発想
変更を$K$回以下加えて'1'が連続で並ぶ長さの最大値を求めます。その連続部分列の左端は必ず'0'から'1'に切り替わったところの'1'です。この位置を$j$とします。次に連続部分列の右端を考えます。右端は必ず'1'から'0'に切り替わったところの'1'です。なおかつ'1'から'0'に切り替わる回数を数えて$K$回を初めて超えた場所です。この位置を$i$とします。連続部分列の長さは$i-j+1$になります。
##実装

N, K = map(int, input().split())
S = list(input())
j = 0
ans = 0
cnt = 0
for i in range(N):
    #'10'という並びを探す
    if S[i] == '0':
        if i == 0 or S[i-1] == '1':
            cnt += 1
    #'10'という並びの個数（＝逆立ちに変更する箇所）がKを超えたら
    if cnt > K:
        while S[j] == '1':
            j += 1
        while S[j] == '0':
            j += 1
        cnt -= 1
    ans = max(ans, i-j+1)

print(ans)

#Hard No.80 : D - Remainder Reminder
D - Remainder Reminder
##発想
何も考えずにすべての組み合わせをとると$O(N^2)$でTLEします。$b$を1から$N$まで動かして、その時に$a$の場合の数が$O(1)$とか$O(logN)$で求められれば勝ちです。そのための条件が「$a$を$b$で割ったあまりが$K$以上」になります。
##実装
$K=0$の場合は$N^2$通りになります。これは例外で処理しておきます。
$N$を$b$で割った商を$p$、$N$を$b$で割ったあまりを$r$とします。$b$を固定したとき、$a$の場合の数は$p×(b-K)+(r-K+1)$になりますが、$b-K<0,{ \ }r-K+1<0$になる場合があるので注意が必要です。

N, K = map(int, input().split())

if K == 0:
    print(N**2)
else:
    ans = 0
    for b in range(1, N+1):
        p = N // b
        r = N % b
        ans += p*max(0, b-K) + max(0, r-K+1)
    print(ans)