Codeforces Round #627 (Div. 3) E. Sleeping Schedule (R1700)
問題概要
一日の長さはh時間である。
a_i時間起きて、h時間寝る、をi=1,2,...nと繰り返す人がいる。
起きている時間は毎回、a_iか(a_i)-1を選択できる（つまり寝るのを1時間前倒しできる）。
l時以上r時以下に寝はじめたときを、良い睡眠とする。
最大でいくつの良い睡眠を取れるか？
制約
1 ≤ n ≤ 2000
3 ≤ h ≤ 2000
0 ≤ l ≤ r < h
1 ≤ a_i < h
考察・解法
dp[i][j]を、i日目にj時に寝始める場合の良い睡眠の数の最大値（その時点までの累計）とし、-1で埋めておき、dp[0][0]=1とする。
以下、時間については (mod h) とする。
入眠を前倒ししない場合のi日目からi+1日目への推移を考えると、a[i]時間起きているので、
i日目のj-a[i]時 → i+1日目のj時という風に答えが引き継がれていくことがわかる。（こう推移できないときはdp[i][j-a[i]]==-1になっている）
このとき、i+1日目の入眠時間jがl以上r以下なら、良い睡眠だから1を足す。
（↑完成してから気づいたけど画像にした意味なかった）
答えはmax(dp[n])。
計算量はO(nh)。
# Codeforces Round #627 (Div. 3) E. Sleeping Schedule n, h, l, r = map(int,input().split()) a = list(map(int,input().split())) dp = [[-1]*(h) for k in range(n+1)] dp[0][0] = 0 for i in range(n): for j in range(h): if dp[i][(j-a[i])%h] != -1: dp[i+1][j] = max(dp[i+1][j],dp[i][(j-a[i])%h]+(l<=j<=r)) if dp[i][(j-a[i]+1)%h] != -1: dp[i+1][j] = max(dp[i+1][j],dp[i][(j-a[i]+1)%h]+(l<=j<=r)) print(max(dp[n]))
Codeforces Round #616 Div.2 C (Div.1 A) Mind Control (R1700)
codeforces.com
問題名が面白い
問題概要
長さnの配列aがある。
人がn人いて、順番に配列aの右端か左端の数を取っていく。
自分はn人のうちm番目である。
n人のうちk人まで、左右どちらを取るかを指定する事ができる。
自分が取れる数を最大化したいとき、これの最小値はいくつか？
（つまり、自分は必ずこれ以上の数が取れる、という数を求めたい）
制約
入力あたりのテストケース数t <= 1000
1 ≤ m ≤ n ≤ 3500
0 ≤ k ≤ n−1
1 <= a_j <= 10^9 (j=1,2,...n)
∑n<=3500
考察・解法
nの合計<=3500より、O(N^2)かなあとすぐ思う。
「固定できるものがないか」という定石に従い、説得できるk人を固定することを思いつく。
1. k >= mの場合（自分より前の人全員の取り方を指定できる場合）
左右の端からそれぞれm番目までの中で任意の要素を取れるので、その中の最大が答え。
（例えば左からp番目が取りたいなら、説得できるk人のうちp-1人を左から、m-(p-1)人を右から取らせればいい）
2. k < m の場合（自分より前に、取り方を指定できない人がいる場合）
指定できるk人を、
（パターン0）左から取る人が0人で右から取る人がk人
（パターン1）左から取る人が1人で右から取る人がk-1人
……
（パターンk）左から取る人がk人で右から取る人が0人
のように固定する。
左からp人、右からk-p人を説得する場合の、 残りの配列がt = a[p:n-k+p]になる。
p=0,1...kについて、説得できない人（m-k人)を動かしていき、自分が取れるもの（説得できる人&説得できない人が取り終わったあとの、左右の端うち大きいもの）をリストdに入れていき、説得できない人を動かし終わったら、dの最小値（説得できない人がどのように取ったとしても、この最小値以上の数は取れるので）をリストbに入れる。
するとリストbには、パターン0～パターンkそれぞれの、"説得できない人たちがどのように取ったとしても自分が取れる数の最小値"が入っているため、これの最大が答えとなる。
# Codeforces Round #616 Div.2 C (Div.1 A) Mind Control import sys, math def input(): return sys.stdin.readline()[:-1] def main(): q = int(input()) for _ in range(q): n, m, k = map(int,input().split()) a = list(map(int,input().split())) b = [] if k >= m: for p in range(m): b.append(max(a[p],a[n-p-1])) else: for p in range(k+1): t = a[p:n-k+p] d = [] for p in range(m-k): d.append(max(t[p],t[p+n-m])) b.append(min(d)) print(max(b)) if __name__ == '__main__': main()
Codeforces Round #606 (Div. 2) D. Let's Play the Words? (1800)
問題概要
10, 1001, 0010みたいな、0と1だけで構成される単語（同じものは無い）でしりとりをする。
10→01のように左右反転する操作が可能である。
n個の単語をすべてつなげたいが、反転する操作の回数を最小にするようにしたい。
反転の操作をしたあとでも、n個の単語全てが違うものでなければいけない。
何番目の単語を反転させればいいか（一つもしなくていいなら0、いくら反転してもしりとりが不可能なら-1）を出力せよ。
制約
入力あたりのテストケース数 <= 10^4
入力あたりのnの和 <= 2*10^5
入力あたり単語の長さの和 <= 4*10^6
解法
しりとりをしたいので、各単語の最初と最後だけ注目すればいい。
よって、最初と最後が00,11,01,10の4パターンに分け、それぞれの数をa,b,c,dとする。
さらに、反転させる意味があるのは01,10パターンのみなので、これらは単語と順番をそれぞれキーと値にして辞書C,Dに入れておく。
しりとりが不可能な場合を考えると、00,11パターンがいずれも1つ以上あり（a*b > 0）、かつそれらをつなぐ10,01パターンが1つもないこと（c == d == 0）。
そうでない場合はしりとりができる。
01,10パターンのみをつなげることを考えれば、00,11パターンは適当な場所に入れることができるので十分。
01,10,01,10...のように交互に繋げないといけないので、01パターンの個数と10パターンの個数の差が1以下でなければいけない。
（端の分だけどちらかが1多くてもよい）
従って、|c-d|=0なら0回、|c-d|=1なら0回、|c-d|=2なら1回、|c-d|=3なら2回...反転する必要がある。
つまり|c-d|//2 回だけ反転させればよい。
cとdの大小で場合分けし、例えばc > dの場合は01パターンを反転させていく。
n個の単語全てが違うものでなければいけないので、辞書Cに入っている01パターンを見ていき、それの反転が辞書Dに入っていなければ、単語をキーとしてCから値（位置）を取り出してansに追加する。
ansの長さが|c-d|//2になったらおしまい。
# Codeforces Round #606 (Div. 2) D. Let's Play the Words? import sys, math def input(): return sys.stdin.readline()[:-1] def main(): q = int(input()) for _ in range(q): n = int(input()) s = [str(input()) for k in range(n)] a, b, c, d = 0, 0, 0, 0 C = dict() D = dict() for k in range(n): e = s[k] if e[0] == "0" and e[-1] == "0": a += 1 elif e[0] == "1" and e[-1] == "1": b += 1 elif e[0] == "0" and e[-1] == "1": c += 1 C[e] = k+1 else: d += 1 D[e] = k+1 if c == d == 0 and a*b > 0: print(-1) else: diff = abs(c-d)//2 print(diff) if diff == 0: print("") else: ans = [] if c > d: for e in C: if e[::-1] not in D: ans.append(C[e]) if len(ans) == diff: break else: for e in D: if e[::-1] not in C: ans.append(D[e]) if len(ans) == diff: break print(*ans) if __name__ == '__main__': main()
Codeforcesで青になりました
ブログのタイトルにするほどの悲願だった青コーダーになれました。
ご覧の通りブランクがあるけど、再開してから実力を上げて青に到達できたというのが嬉しい！
とはいえ青を維持する自信がないので、今後は1300～1600点くらいの過去問を埋めつつ（特に苦手としているDPを中心に）、時間帯＆体調の良いときだけコンテストに出る方針に切り替えていこうと思います。
AtCoderでもレート上げていきたいなー……
AtCoder Beginner Contest 135 D - Digits Parade
atcoder.jp
典型的なdpだが解けなかった。
いかにも競プロっぽいので、こういうのが解けるようになれば楽しそう。
問題概要
数字と?で構成される文字列Sがある。
?を数字に置き換えてできる整数のうち、13で割って5あまる数は何通りあるか。
制約
len(S) <= 10^5
解法
dp[i][j]を、i文字目まで見たとき、13でわった余りがjになる数の総数とする。
i+1文字目への遷移は、i+1文字目の数字がkとすると、
dp[i+1][(j*10+k)%13] += dp[i][j]
をj = 0,1,....12としたものになる。
（例えばdp[2][7]は2文字目まで見てあまりが7の総数なので、3文字目が5ならば、70+5を13で割ったあまりのところにそれを足してやる）
i+1文字目が?のときはkを0から9まで動かす。
# ABC 135 D - Digits Parade S = input() N = len(S) dp = [[0 for i in range(13)] for j in range(N+1)] # dp[i][j] := i文字目まで見たときに13でわった余りがjになる総数 MOD = 10**9 + 7 dp[0][0] = 1 for i in range(1,N+1): if S[i-1] == "?": for j in range(13): for k in range(10): dp[i][(j*10+k)%13] += dp[i-1][j] dp[i][(j*10+k)%13] %= MOD else: t = int(S[i-1]) for j in range(13): dp[i][(j*10+t)%13] += dp[i-1][j] dp[i][(j*10+t)%13] %= MOD print(dp[N][5])
yukicoder No.852 連続部分文字列
yukicoder.me
本番では解けず。dpっぽいなと思ったし実際dpで解けるようだけど、公式解説の4番めがわかりやすかったので、こういうのを自分でも思いつけるようになりたいと思ってメモを残すことにした。
問題概要
文字列の空でない連続な部分文字列における、文字の種類数の平均を求める。
制約
Sの長さは10^6以下
解法
まず、Sの全ての空でない連続な部分文字列（以下、単に部分文字列と呼ぶ）が、アルファベット全種を含んでいると仮定して総数を計算する。
これはSの長さをnとして、(アルファベットの種類の数)*(部分文字列の選び方) = 26*n*(n+1)/2 で求まる。
（部分文字列は長さ1のものがn個、長さ2のがn-1個、…長さnのが1個で1+2+...+n = n*(n+1)/2 個）
そして、各アルファベットについて、それを含まないものを計算して、求めた総数から引いていく。
例えば文字列がabcdaだったら、aを含まないものは、bcdから選べる1+2+3=6通り。
同様にしてaとaの間がk個あるならば、1+2+...+k = k*(k+1)/2個が、aを含まないものとして選べる。
これを全てのアルファベットについて計算していけば答えが求まる。
# yukicoder 852 A = "abcdefghijklmnopqrstuvwxyz" S = input() l = len(S) def f(n): return (n*(n+1))//2 ans = 26*f(l) for e in A: t = 0 for k in range(l): if S[k] == e: ans -= f(k-t) t = k+1 ans -= f(l-t) print(ans/f(l))
AtCoder Beginner Contest 125 D - Flipping Signs
問題概要
整数の要素N個をもつ配列Aがある。
この中の隣り合う要素2つを選んで符号を反転させる操作を好きなだけ繰り返し、sum(A)を最大にしたい。
制約
2 ≤ N ≤ 10^5
- 10^9 ≤ Ai ≤ 10^9
解法
2つの要素の符号が同時に変わるので、何度操作を行っても負の要素の数を2で割ったあまりは不変である。
よって負の要素の個数の奇偶で場合分けする。
1° 偶数の場合
要素全てを正にできる。つまりAの各要素の絶対値の和を取れば答え。
2° 奇数の場合
一つの要素だけ負、残りは全部正にできる。なのでAの要素で絶対値が最小のものを負にして、残りは全部正にすればいい。
N = int(input()) A = sorted(list(map(int,input().split()))) t = 0 for e in A: if e < 0: t += 1 B = sorted([abs(e) for e in A]) if t%2 == 1: print(sum(B)-B[0]*2) else: print(sum(B))
