ABC184バチャ
A - Determinant
概要
行列が与えられ、行列式を求める
カテゴリ
算数（四則演算）
考察
入力全て整数で、桁も小さいので特に型などは気にしなくていい
a*d-b*c
コード
#!/usr/bin/env python3 a, b = map(int, input().split()) c, d = map(int, input().split()) print(a * d - b * c)
B - Quizzes
概要
最初の持ち点がNでクイズの正解、不正解履歴が文字列で与えられる。
持ち点は正解、不正解に応じて変動し、oなら+1,xなら-1をする。（ただし、持ち点が負になることはない）
最終的な点数を答えよ
カテゴリ
ゲーム（そのままルールを実装）
考察
ループで文字列の長さ分を回す
コード
#!/usr/bin/env python3 n, x = map(int, input().split()) s = input() cur_point = x for i in s: if cur_point == 0 and i == "x": pass elif i == "x": cur_point -= 1 else: cur_point += 1 print(cur_point)
C - Super Ryuma
概要
無限に広がる二次元グリッド上の位置(r1,c1)にコマがあり、それを(r2,c2)に動かすための最小手順を答えよ。
ただし、一回の移動で(a,b)にいるコマは以下の条件のどちらかを満たす場所(c,d)に動かせる。
A:ユークリッド距離が３以下
B:対角の位置（将棋の角が移動できる場所）
カテゴリ
最短経路、グリッド
考察
可能な２つの動き（斜めと３マス以内の移動）を考えた時に、２つの動きの順番は関係ない。
つまり、A,A,B でたどり着くならばB,A,Aでも同じ場所にたどり着く。
そのため、Bの動きを行う回数を固定してk回行うとすると、Aの動きを何回行えば終了時の位置とゴール位置のユークリッド距離を3*k 以内にできるか、という問題になる。
ただし、これではk に対してO(10**9)かかるので、明らかに間に合わない。
どういう時にAの動きがBよりも優位になるかを考えると、移動後にゴールとのユークリッド距離が3よりも減っている時、ということになる。
ここで、Aの動きには向きが２つあり（右斜と左斜）、その２つを組み合わせることで一回の動きではユークリッド距離が縮まらない場合にも2回トータルすると大きく縮められることがわかる（例として、スタートとゴール位置のx座標が同じ時など）
さらに、A,Bの動きの順番が関係ないことを考えると、Aの２つの動きはそれぞれ高々一回でよくて、ゴール地点から垂線を引いてそれにぶつかるまでAの動きをすればAの動きだけで最も近づくことができる。
それを行った時の距離は1か0なので手数は3,2,1,0のいずれかになる
実装
手数が0,1,2,3になる条件を羅列していって、手数を確定させる（簡単な少ない手数の条件から記述して3はその余事象とする）
移動A二回でゴールにつく条件は必ずどちらの動作もa-c,b-dの差が偶数変化するので、abs(a-c) + abs(b-d) % 2 == 0 で、
A一回、B一回でゴールにつけるかの判定は、abs(abs(a - c) - abs(b - d)) <= 3 で行える（気づくのにだいぶ時間がかかった）
#!/usr/bin/env python3 a, b = map(int, input().split()) c, d = map(int, input().split()) if a == c and b == d: print(0) elif abs(a - c) == abs(b - d) or abs(a - c) + abs(b - d) <= 3: print(1) else: if ( abs(a - c) + abs(b - d) <= 6 or (abs(a - c) + abs(b - d)) % 2 == 0 or abs(abs(a - c) - abs(b - d)) <= 3 ): print(2) else: print(3)
D - increment of coins
概要
ゲームの期待値を求める
カテゴリ
ゲーム、期待値
考察
ゲームが終了するまでの手数の期待値を求める問題
余事象で考えられるか考えたが、無理なので、全状態を列挙する必要があると考える。
ただし、全てのpath(どれかが100枚になるまで）を考えると状態数が多くなりすぎるので、DPのように状態をまとめることを考える。(それぞれがx,y,z になる確率はx-1,y,z,とx,y-1,z , x,y,z-1から移動する確率の全ての和で計算できる）
計算量はO(10**6)(DPが10**6マスあって、それぞれの遷移がO(1)*3パス）なので、これで間に合う。
実装
期待値DPなのでゴールから埋めていく。
DP[ある状態] = (そこからゴールまでの期待値) という形で漸化式を形成する
#!/usr/bin/env python3 # input a, b, c = map(int, input().split()) dp = [[[0] * 103 for i in range(103)] for j in range(103)] dp[a][b][c] = 1 # initialization for i in range(1, 300 - a - b - c + 1): # スタートからの距離 for a_d in range(i + 1): # aに割り当てる距離 for b_d in range(i + 1 - a_d): c_d = i - a_d - b_d if (((a + a_d) == 100) + ((b + b_d) == 100) + ((c + c_d) == 100)) > 1: continue elif a + a_d > 100 or b + b_d > 100 or c + c_d > 100: continue else: if a + a_d > 0 and b + b_d < 100 and c + c_d < 100: dp[a + a_d][b + b_d][c + c_d] += dp[a + a_d - 1][b + b_d][ c + c_d ] * ((a + a_d - 1) / (a + b + c + i - 1)) if b + b_d > 0 and a + a_d < 100 and c + c_d < 100: dp[a + a_d][b + b_d][c + c_d] += dp[a + a_d][b + b_d - 1][ c + c_d ] * ((b + b_d - 1) / (a + b + c + i - 1)) if c + c_d > 0 and b + b_d < 100 and a + a_d < 100: dp[a + a_d][b + b_d][c + c_d] += dp[a + a_d][b + b_d][ c + c_d - 1 ] * ((c + c_d - 1) / (a + b + c + i - 1)) # print(dp[99][99][99:], dp[100][99][98:], dp[99][100][98:]) ans = 0 for i in range(101): for j in range(101): for k in range(101): if i == 100 or j == 100 or k == 100: ans += dp[i][j][k] * (i + j + k - a - b - c) print(ans)
Codeforces Round #662 (Div. 2)A~C [Python]
A
ジャンル
マンハッタン距離 ギャグ
概要
n*n gird の色分け
外側の境界から違い違いになるように順番に埋めていく。前回のターンで置かれた場所に隣接している箇所にしかおけないとき、最小のターン数を求めよ。
制約
1 <= n <= 10**9
考察
n*n grid で最も内側がどこに位置するかを考える。
右上を0,0とすると、(n//2,n//2)が最も内側のマス（の１つ）になる上下左右対象なのでこれを何回目にアクセスできるかを考える。
１ターンで隣接している箇所にしか進めないので最も近傍のgridの辺上のマスからのマンハッタン距離を求めれば良い。
実装
import sys import math read = sys.stdin.buffer.read # input = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines t = int(input()) for case in range(t): n = int(input()) print(n // 2 + 1)
ポイント
隣接しか進めないという条件をマンハッタン距離に帰着する。
B
ジャンル
クエリ 更新があるクエリでの最大、最小
概要
あらかじめn 本の数列がある。qこのクエリが与えられ、(- k or + k の形式）、値k が削除、挿入される。
各クエリ終了時に長方形、正方形が作れるか判定せよ。
制約
1<=n<=10**5
1<=ai<=10**5
1<=q<=10**5
考察
挿入、削除時の最適な操作（どの値を挿入して削除するのがベストか？）を考えたい。
ナイーブに考えると、各操作ごとにそれぞれの長さがいくつあるかを保持して、上からソートしたときに(4,2,2) (6,2) 以上あればOKだが、O(NQ log N )が通らない
全体で個数が6,4,2以上になる値がいくつあるかを変数としてもち、クエリでの操作によって6,4,2 を跨いだらを更新する。
O(Q) でできる。
実装
import sys import math ii = lambda: int(sys.stdin.buffer.readline().rstrip()) il = lambda: list(map(int, sys.stdin.buffer.readline().split())) fl = lambda: list(map(float, sys.stdin.buffer.readline().split())) iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] iss = lambda: sys.stdin.buffer.readline().decode().rstrip() sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split())) isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] n = ii() a = il() q = ii() cnt = [0] * (10 ** 5 + 1) cnt_246 = [0, 0, 0, 0] lis = [2, 4, 6, 8] for i in range(n): cnt[a[i]] += 1 if cnt[a[i]] in lis: cnt_246[lis.index(cnt[a[i]])] += 1 # print(i, cnt_246) for qu in range(q): s = iss().split() # print(len(s), s) if s[0] == "+": cnt[int(s[-1])] += 1 if cnt[int(s[-1])] in lis: cnt_246[lis.index(cnt[int(s[-1])])] += 1 else: cnt[int(s[-1])] -= 1 if cnt[int(s[-1])] + 1 in lis: cnt_246[lis.index(cnt[int(s[-1])] + 1)] -= 1 # print(cnt_246, cnt[:3]) if ( cnt_246[3] >= 1 or cnt_246[2] >= 2 or (cnt_246[2] >= 1 and sum(cnt_246[:3]) >= 4) or (cnt_246[1] >= 2) or (cnt_246[1] == 1 and cnt_246[0] >= 3) ): print("YES") else: print("NO")
学び
跨いだ箇所だけ変更しているので、累積の形現在の値以下のポイントにbitが立っている実装になっている(少しわかりにくい）
クエリ問題の入力の受け取りはTLEすることがあるのでsys.stdin.buffer.readline() であらかじめ一括で受け取る
sys.stdin.buffer.readline()で文字列を受け取る時は8bitのバイト列として受け取られるので、decode() で文字列に直す処理が必要になる。
Unicode 文字列はコードポイントの列であり、コードポイントとは 0 から 0x10FFFF (10 進表記で 1,114,111) までの数値です。このコードポイント列はメモリ上では コードユニット 列として表され、その コードユニット 列は 8-bit のバイト列にマップされます。Unicode 文字列をバイト列として翻訳する規則を 文字エンコーディング または単に エンコーディング と呼びます。
C
ジャンル
ギャグ 整数配列
概要
整数列が与えられ、同じ数ができるだけ遠くなるように並び替えるとき、最も近くになるペアの距離を答えよ。
制約
2 <= n<= 10**5
1 <= ai <= n
考察
同じ整数の個数がmax の数のみを考えれば良い。
max の個数 K を持つ整数が m 個あるとき、(n-m) // (K-1) -1 が答え
実装
import sys import math read = sys.stdin.buffer.read # input = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines t = int(input()) for case in range(t): n = int(input()) a = list(map(int, input().split())) cnt = [0] * (10 ** 5 + 1) for i in range(n): cnt[a[i]] += 1 k = max(cnt) m = cnt.count(k) print((n - m) // (k - 1) - 1)
学び
文字列や整数配列で出現頻度を持つのは頻出
ABC124 D - Handstand 解説[python]
制約
N<=10**5
K<=10*5
考察
bit列の区間の操作の問題は他でもみる気がする（コドフォで頻出？）
ポイントはbitが同じ連続している箇所の間で区間を反転させることはメリットがないということ。(同じにならないので）
つまり、必ずbitが異なっている箇所に区間の両端がくるようにする。
bitが同じ連続列を1つのブロックとすると、一回操作を行うたびにブロックに隣接するブロックをつなげることができる。
k回操作を行うと2*k+1個の連続したブロックをつなげることができる。(ただし、1のブロックが端点）
尺取で2*k+1の連続したブロックの長さの和のmaxをとると良い
実装
#!/usr/bin/env python3 # input import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines n, k = map(int, input().split()) s = input() range_len = 2 * k + 1 ans = 0 block_len = [] block_len.append(0) now = "1" for i in s: if now == i: block_len[-1] += 1 else: block_len.append(1) now = i if now == "0": block_len.append(0) l_block = len(block_len) # print(block_len) if l_block <= range_len: print(n) else: # 尺取 tmp = sum(block_len[:range_len]) ans = tmp for idx in range(l_block - range_len): tmp += block_len[idx + range_len] - block_len[idx] # print(tmp, idx) if idx % 2 == 1: # print(ans, tmp) ans = max(ans, tmp) print(ans) # けつにも0 をいれる。
バグらせず実装するポイント
文字列全体を舐めるより、先にブロックの長さを計算しておいた方がよかった。
また、先頭と末端が1ではない時に0 を挿入する。
コドフォ Educational Contest 92 E Calendar Ambiguity 解説[python]
概要
全ての月がd 日であり、一年にm 日ある暦がある。
1週がw 日とすると、同じ年のx月y 日の曜日がy日x日の曜日と等しいようなx,y のpair( xはyより小さい )が何個あるかを数えよ。
制約
1 <= m,d,w <= 10**9
考察
x月y日は年始から数えて(x-1)*d + y日目なので、((x-1)*d + y) %w曜日となる
そのため、条件を定式化すると
(d* (y-x)+ x-y ) %w == 0
でまとめると、
(x-y)(d-1) % w == 0 になるx,yを見つければいい。
この時、2種類に場合分けできて、
d == 1 の時
x,y は任意
m*(m-1)//2が答え
それ以外
y-x が w/gcd(d-1,w)で割り切れれば良い
m-1 >= w/gcd(d-1,w) * k を満たす任意の正の整数k に対して、ans += m - w/gcd(d-1,w) * k となるので、
m* k -w/gcd(d-1,w)*k*(k+1)//2
実装
import sys import math def gcd(a, b): if a > b: a, b = b, a if b % a == 0: return a return gcd(b % a, a) read = sys.stdin.buffer.read # input = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines t = int(input()) for case in range(t): m, d, w = map(int, input().split()) if d == 1: print(min(d, m) * (min(d, m) - 1) // 2) elif m == 1: print(0) else: div = w // gcd(w, d - 1) k = (min(m, d) - 1) // div # print(div, k, m, d, w) print(min(m, d) * k - div * k * (k + 1) // 2)
コドフォ Educational Contest 92 B Array Walk 解説[python]
概要
正の整数列aが左から順番に並んでおり、現在先頭の要素に存在する。
各stepで現在の位置から左右の要素に移動することができ、移動した場所の要素の値だけ得点が入る。
動き方の制約として、連続して左の要素にいくことはできない、左にいくのは最大でz 回まで、という条件がある時、k回移動した時の得点の最大値を求めよ
制約
n <= 10**5
a <= 10**4
k <= n-1
z <=min(5,k)
考察
動き方が2種類しかないので最初全列挙を考えたが流石にTLE。
現在位置と今何回左に進んだか、が同じ時、今までの動き方によらず、後の理想的な動き方は同じになるので、状態をまとめることができる。
状態といて、現在位置 i と今何回左に進んだか j を持つと、現在いる位置（要素）は i - 2* j で計算できる。
後持つべき状態としては、連続して左にいけないという制約から、前回左に進んだかどうかをもてば良い。
実装
3要素を持つdpを作るか、前回左に進んだかどうかでdpを分けるとかける。
import sys import math read = sys.stdin.buffer.read # input = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines t = int(input()) for case in range(t): n, k, z = map(int, input().split()) a = list(map(int, input().split())) # dp[i][j]= 現在 i 回移動して、その中でk 回左に移動した時の最大値 INF = 10 ** 4 dp_left_ok = [[-INF] * (1 + z) for _ in range(1 + k)] dp_left_ng = [[-INF] * (1 + z) for _ in range(1 + k)] dp_left_ng[0][0] = a[0] dp_left_ok[0][0] = -INF # 最初はだめ # pos = i - 2*j for j in range(z + 1): for i in range(1, k + 1): if j > 0 and (i - 1) - 2 * (j - 1) >= 0: # 現在地が0以上の時のみ使用 dp_left_ng[i][j] = dp_left_ok[i - 1][j - 1] + a[i - 2 * j] if (i - 1) - 2 * j >= 0: dp_left_ok[i][j] = ( max(dp_left_ok[i - 1][j], dp_left_ng[i - 1][j]) + a[i - 2 * j] ) print(max(max(dp_left_ng[k]), max(dp_left_ok[k]))) """print(dp_left_ng) print(dp_left_ok)"""
コドフォ Educational Contest 92 C Good String 解説[python]
概要
長さN の数字のみからなる文字列がある。
文字列を左回転、右回転した文字列が一致する時それは良い文字列とする時、与えられた文字列から最小で何文字削除すれば良い文字列になるかを求めよ。
ただし削除する場所は任意
考察
実験すると、長さが奇数なら全ての文字が同じ時、良い文字列。
長さが偶数なら偶数番目と奇数番目が同じなら良い文字列になることがわかる。
長さ偶数を考えると、互い違いに現れる文字列で最大の長さのものをもとめたい。
文字種が高々10種類なので、偶数番目、奇数番目の文字を固定して全探索をすると実装が楽にもとまる。
実装
import sys import math read = sys.stdin.buffer.read # input = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines t = int(input()) for case in range(t): s = input() ans = 0 for i in range(10): for j in range(10): i_bit = 0 # 0ならi かどうかを判定する ij_len = 0 i_len = 0 for k in s: if i_bit == 0: if i == int(k): i_bit = 1 ij_len += 1 else: if j == int(k): i_bit = 0 ij_len += 1 if i == int(k): i_len += 1 # print(i, j, ij_len, i_len, ans) ans = max(ans, i_len, (ij_len // 2) * 2) print(min(len(s) - 2, len(s) - ans))
コドフォ Educational Contest 92 D Segment Intersections 解説[python]
概要
区間[l1,r1],[l2,r2] のがそれぞれN 本ある。
i 番目の[l1,r1]区間はi 番目の[l2,r2]区間と対応する。
任意の区間の距離を長さ１伸ばすのにstepが1かかる。（左右両方向に伸ばせる）
それぞれの対応する区間同士が重なっている長さの合計をk以上にするのにかかる最低のstep数を答えよ。
制約
n <= 2*10**5
1<= l,r,k <=10**9
考察
性質として、現在重なっていて、対応する区間同士にまだ重なっていない部分があるなら、そこを使い切るまでコスト1で長さを1伸ばせる。
使い切っているならば、現在重なっていない区間をgapを埋めて使い切るか(選択1)
、現在重なっている区間に関して、両方の端を伸ばして、コスト2で長さを1伸ばすか(選択2)
の２つの選択肢がある。
選択2の時、gap分だけコストがかかるので、解を決めうつと条件分岐が少なく実装が楽になる。
場合わけとして
実装
import sys import math read = sys.stdin.buffer.read # input = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines t = int(input()) for case in range(t): n, k = map(int, input().split()) l1, r1 = map(int, input().split()) l2, r2 = map(int, input().split()) origin_inter = max(0, min(r1, r2) - max(l1, l2)) ans = 0 k -= origin_inter * n if k <= 0: ans = 0 elif origin_inter > 0: # まず伸ばせるまで伸ばす。その後、2ターンで1伸ばす if k <= n * ((r1 - l1) + (r2 - l2) - origin_inter * 2): ans += k else: ans = 2 * k - n * ((r1 - l1) + (r2 - l2) - origin_inter * 2) else: margin = max(l1, l2) - min(r1, r2) len_inter = max(r1, r2) - min(l1, l2) # 何本を使うかを決め打つ ans = 10 ** 10 for i in range(1, n + 1): tmp_i = margin * i if k > len_inter * i: tmp_i += len_inter * i + (k - len_inter * i) * 2 else: tmp_i += k # print(i, tmp_i, margin, len_inter) ans = min(tmp_i, ans) print(ans)
