Atcoder - いろはちゃんコンテスト Day1 - E - 放課後
問題概要
提出コード
typedef long long ll; typedef unsigned long long ull; #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define INF 1e9 vector<ll> a; int main() { ll n, x, y; cin >> n >> x >> y; if (y == 0) { cout << 0 << endl; exit(0); } for(ll i = 0; i < y; i++) { ll k; cin >> k; a.push_back(k); } a.push_back(0); sort(a.begin(), a.end()); ll count = y; for (ll i = 0; i < y; i++) { ll k = a[i + 1] - a[i] - x; count += std::max((ll)(std::ceil((double)k / x)), (ll)0); } ll k = n - a.back(); count += std::max((ll)(std::ceil(k/x)), (ll)0); ll ans = n - count; cout << ans << endl; return 0; }
Codeforces Round #556 (Div. 2) - B. Tiling Challenge
問題概要
5つの正方形からなる十字型を
n * nからなる四角形内の空いている箇所に当てはめたとき
四角形の空きが全て埋まるとき、YES、埋まらないときはNOを出力せよ。
解法
上の段から、下に向かって十字型が埋まるか貪欲に見ればよい。
十字型である以上、最上位段、最下位段で左右連続して
空きがある際には、必ず空きができるのでNOを出力することになる。
また、一つの十字型を埋めると5個の空きが埋まるため
5の倍数ではないときは、空きがでるか、十字型を埋めることはできない。
提出コード
n = int(input()) e = [] empty = 0 for i in range(n): t = deque(list(input())) e.append(t) empty += t.count('.') if empty % 5 != 0: print("NO") else: for i in range(n): for j in range(n): if i + 2 >= n: continue if j - 1 < 0: continue if j + 1 >= n: continue if e[i][j] == '#': continue if e[i + 1][j] == '#': continue if e[i + 2][j] == '#': continue if e[i + 1][j - 1] == '#': continue if e[i + 1][j + 1] == '#': continue e[i][j] = '#' e[i + 1][j] = '#' e[i + 2][j] = '#' e[i + 1][j - 1] = '#' e[i + 1][j + 1] = '#' empty -= 5 if empty == 0: print('YES') else: print('NO')
ABC 123 D - Cake 123
問題概要
D - Cake 123
X 種類、Y 種類、Z 種類の3つの種類に重みがついている。
3種類の組み合わせで重みの合計が高い順にK個出力せよ。
解法(解説AC)
X, Y, Zをソートしておき、
Priority Queueへ最も高い重みの合計を放り込んでおく。
最も高い重みのi, j, kの状態から各種類で次点に高い重みへを1つずつずらしていき、
重みの合計をPriority Queueへ追加していく。
q.push(X(i + 1) + Y + Z)
q.push(X + Y(j + 1) + Z)
q.push(X + Y + Z(k + 1))
提出コード
x, y, z, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) c = list(map(int, input().split())) a.sort(reverse=True) b.sort(reverse=True) c.sort(reverse=True) q = [] heapq.heappush(q, (-(a[0] + b[0] + c[0]), 0, 0, 0)) kk = k ans = [] chk = defaultdict(lambda:defaultdict(lambda:defaultdict(bool))) while(k): k -= 1 v, ai, bi, ci = heapq.heappop(q) ans.append(v) if ai + 1 < x: if chk[ai + 1][bi][ci] == False: heapq.heappush(q, (-(a[ai + 1] + b[bi] + c[ci]), ai + 1, bi, ci)) chk[ai + 1][bi][ci] = True if bi + 1 < y: if chk[ai][bi + 1][ci] == False: heapq.heappush(q, (-(a[ai] + b[bi + 1] + c[ci]), ai, bi + 1, ci)) chk[ai][bi + 1][ci] = True if ci + 1 < z: if chk[ai][bi][ci + 1] == False: heapq.heappush(q, (-(a[ai] + b[bi] + c[ci + 1]), ai, bi, ci + 1)) chk[ai][bi][ci + 1] = True for i in range(kk): print(-ans[i])
Codeforces Round #555 (Div. 3) - B. Long Number
問題概要
Problem - B - Codeforces
1から9までのn桁からなる数値を1から9までの各桁に対応したMAPに置き換えることができる。
1から9までのn桁からなる数値から特定の範囲を抜き出して置き換えた際に最大となる数値を答えよ。
ただし、特定の範囲は1度しか置き換えることができない。
解法
上位の桁から置き換えるMAPの値をを比較した際に
MAPの値の方が大きい場合、MAPの値へ置き換える。
以降は、置き換えができなくなったタイミング(等しい値の場合は同じ数値で置き換える)で終了する。
What is the maximum possible number you can obtain applying this operation no more than once?
をgoogle翻訳で食わせた際には、
この操作を複数回適用して取得できる最大数はいくつですか。
と出てくるので注意が必要。
コード
n = int(input()) a = list(input()) b = list(map(str, input().split())) d = defaultdict(int) for i, s in enumerate(b): d[i + 1] = s flg = False for i, s in enumerate(a): if int(s) < int(d[int(s)]): a[i] = d[int(s)] flg = True elif flg and int(s) > int(d[int(s)]): break print(''.join(a))
ABC 125 D - Flipping Signs
解法(解説AC)
正負判定を行い、負の値が偶数個の場合全て正の値にすることが可能。
負の数が奇数個の場合、任意の値を1つだけ負の値にすることが可能。
なので、負の値が偶数個の場合、すべての値を正にした状態でsum(B)。
負の値が奇数個の場合、abs(A)の中で最も小さい値を負の値にしてsum(B)を取ればよい。
提出コード
n = int(input()) a = list(map(int, input().split())) count = 0 s = 0 b = [] for i in range(n): count += 1 if a[i] < 0 else 0 b.append(abs(a[i])) flg = False if count % 2 == 1: flg = True ans = sum(b) if flg: ans -= min(b) * 2 print(ans)
ABC 125 C - GCD on Blackboard
問題概要
C - GCD on Blackboard
N個の数列Ai, Ai+1, Ai+2...のうち、任意の1つのみの数値を0～10^9の任意の値に
置きかえた際に数列全体の最大公約数として考えられる最大値を求めよ
解法(解説AC)
けんちょんさんの記事を参考にした。
AtCoder ABC 125 C - GCD on Blackboard (300 点) - けんちょんの競プロ精進記録
Aiを置き換える際には、Aiを消したと等価になる。
また、3つ以上の数列の最大公約数の求め方がgcd(Ai, gcd(Ai+1, Ai+2))とすることができることから再帰的な求め方が可能である。
上記を利用した累積gcd(1番目からNまでのgcdとN番目からの1番目までのgcd)の結果を用意し削除するiを決めた際の最大公約数がmaxとなる値を求める。
具体例
Inputを[10, 2, 15, 20]とする。
1番目の要素からN番目までの要素のgcdを求めた場合、
①gcd(10, 2) = 2
②gcd(①の結果=2, 15) = 1
③gcd(②の結果=1, 20) = 1
となり、[2,1,1]の要素となる。
上記に0と10を付加し、[0, 10, 2, 1, 1]の要素leftとする。
N番目の要素から1番目までの要素のgcdを求めた場合、
①gcd(20, 15) = 5
②gcd(②の結果=5, 2) = 1
③gcd(②の結果=1, 10) = 1
となり、[1,1,5]の要素となる。
上記に0と20を付加し、[1, 1, 5, 20, 0]の要素rightとする。
削除するiを1番目の要素としたとき、
left[0] = 0となる。
N番目から2番目の要素まで計算した結果は
right[i + 1] = 1となり、gcd(left[0], right[1]) = 1となる。
削除するiを2番目の要素としたとき、1番目の要素の計算結果は
left[1] = 10となる。
N番目から3番目の要素まで計算した結果は
right[i + 1] = 5となり、gcd(left[1], right[2]) = 5となる。
以降、計算を繰り返すと全体の最大公約数の最大値は5となる。
提出コード
# coding: UTF-8 n = int(input()) a = list(map(int, input().split())) left = [0] * (n + 1) right = [0] * (n + 1) for i in range(n): left[i + 1] = fractions.gcd(left[i], a[i]) for i in reversed(range(n)): right[i] = fractions.gcd(right[i + 1], a[i]) mx = 0 for i in range(n): l = left[i] r = right[i + 1] mx = max(mx, fractions.gcd(l, r)) print(mx)
新年
新年あけましておめでとうございます。
目標を立てても基本達成できないことが多いのですが
去年は色々な方と出会う機会があり、今年は少し頑張ってみようと思いました。
なので、今年はブログ100記事程書けたら良いなと思っています。
(努力目標)
