Hard No.71 : 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
発想
何も考えずに考えると、$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
発想
できるだけ大きい金額でお金を引き出したほうが、引き出す回数は少なくて済みます。引き出す回数は残りの金額によって刻々と変化しますので、動的計画法を使います。
実装
引き出す金額のリストを予め作っておきます。
$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
発想
思いついたら勝ち！思いつかなかったら負け！敗者に人権はない！って感じがしてつらい気持ちになります。とりあえずリンゴの数が少ない状況で実験してみます。
（１）リンゴが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
発想
$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 - たくさんの数式
発想
$|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
発想
とりあえず小さい状況で実験します。例えば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
発想
$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
発想
変更を$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
発想
何も考えずにすべての組み合わせをとると$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)