無駄WAが無ければ…と思ったけど、無くても順位1個しか変わらなかった。
http://abc023.contest.atcoder.jp/assignments
A - 加算王
2桁の整数Nが与えられる。
両桁の和を答えよ。
題意の通り和を取ればよい。
N=input() print N/10+N%10
B - 手芸王
初期状態で文字列Tは"b"である。
- 3n+1手目ではTの先頭に"a"、末尾に"c"を付与する。
- 3n+2手目ではTの先頭に"c"、末尾に"a"を付与する。
- 3n手目ではTの先頭に"b"、末尾に"b"を付与する。
上記処理を何手か繰り返して入力文字列Sと一致するなら、その手数を求めよ。
Tの長さは単調増加なので、Sの長さを超えるまでシミュレーションすればよい。
以下のコードでは、先にTが100文字を超えるまでシミュレーションして配列に加え、最後にSと一致するものがあるか探索している。
import sys L=input() S=raw_input().strip() A=["b"] while len(A[-1])<=100: A.append("a"+A[-1]+"c") A.append("c"+A[-1]+"a") A.append("b"+A[-1]+"b") for i in range(len(A)): if A[i] == S: print i sys.exit(0) print -1
C - 収集王
R*Cのグリッド上の異なるN個のセル(r[i],c[i])に飴がある。
プレイヤーはあるセルを選択すると、そのセルと同じ列または同じ行のセルにある飴を回収できる。
回収する飴の数がK個になるような選択セルの数を求めよ。
まず、各行・各列に何個飴があるかをそれぞれ求める。
y行目にある飴をNR(y)個、x列目にある飴をNC(x)個と表現することにする。
セル(y,x)を選択したときの飴の数はNR(y)+NC(x) (厳密には異なる。後述)となる。
NR(y)+NC(x)==Kとなるような(y,x)の数を高速に求めたい。
飴の数pに対し、NC(x)==pとなるxの数(すなわちp個飴がある列の数)をf(p)とする。
すると(y,x)の和はとなる。
ただしまだ問題があって、(y,x)自体に飴がある場合、NR(y)+NC(x)では同じ飴を2回カウントしてしまっている。
よって飴のある各セル(r[i],c[i])について:
- NR(r[i])+NC(c[i])==Kは飴の二重カウントが無ければK-1個なので、前述のsumの処理で余分に答えに加えてしまった分を1減らす
- NR(r[i])+NC(c[i])==K+1だったら飴の二重カウントの影響を考慮するとちょうど飴がK個となるので答えを1増やす
R,C,K = map(int,raw_input().strip().split(" ")) N = input() NR = [0]*R NC = [0]*C cand = [] for i in range(N): r,c=map(int,raw_input().strip().split(" ")) cand.append((r-1,c-1)) NR[r-1] += 1 NC[c-1] += 1 CS = [0]*101000 for nc in NC: CS[nc] += 1 ret = 0 for nr in NR: left = K - nr if left >= 0: ret += CS[left] for (r,c) in cand: if NR[r] + NC[c] == K: ret -= 1 if NR[r] + NC[c] == K+1: ret += 1 print ret
D - 射撃王
N個の風船がある。
i番目の風船は、初期状態で高さH[i]にあり、1秒毎にS[i]上昇する。
プレイヤーは(0秒から初めて)1秒毎に1個風船を割ることができる。
その際、割った時点での高さの最大値がプレイヤーのスコアになる。
最適な順で風船を全て割ったとき、プレイヤーの最小スコアを求めよ。
二分探索を用いてスコアの最小値を求める。
最終的なスコアがVと仮定すると、各風船は(V-H[i])/S[i]以内に割らなければならない。
プレイヤーは当然早く風船を割った方が有利なので、0~(N-1)秒の間に1個ずつ風船を割る。
逆に0~(N-1)秒の間に1個ずつ風船を割って間に合うなら、スコアVを達成できる。
「0~(N-1)秒の間に1個ずつ風船を割る」が成り立つには、i秒目までに割らなければいけない風船がi個を超えなければ良い。
N=input() B=[] def ok(v): D=[0]*N for (h,s) in B: if v < h: return False t = (v-h)/s if t < N: D[t] += 1 x = 0 for i in range(N): if x > i: return False x += D[i] return True for i in range(N): h,s=map(int,raw_input().strip().split(" ")) B.append((h,s)) ret = (1<<51)-1 for i in range(50,-1,-1): if ok(ret - (1<<i)): ret -= 1<<i print ret
まとめ
Cの難易度が徐々に上昇している?