コドフォ Educational Contst 89 D. Two Divisors 解説[python]
ジャンル
パズル、整数問題、構築
概要
整数nが与えられ、それの1以上の約数の組のうち、gcd(a+b, n) = 1となる組を１つ出力せよ。
ない場合は-1を出せ
制約
1<=n<=5*10**5 クエリの個数
2<=ai<=10**7 整数nの大きさ
考察
約数の個数は10**7なら高々200個程度なので全探索でもいける?
(ただ、クエリの個数が大きいのでそれに200C2 を重ねると無理そう)
探索する範囲を絞ることを考えると、明らかに、a,b が同じ公約数を持っていた場合は無理でa,bは互いに素である
n を素因数分解して、良さげな性質を見つけたい
nの一番小さい素数と、nのそれ以外の素数の積を考えると、nの一番小さい素数 とnのそれ以外の素数の積は互いに素だから この和はnの一番小さい素数 では割り切れず、かつ、nのそれ以外の素数よりも足された数は小さいからそれでも割り切れない。
よってこれが条件を満たす。
-1になるケースは素数を1種類しか持たない時
実装
TLE解2
事前計算して素因数の列挙することを高速化することを考える。
10**7までの値の素因数は10**7以下になるので、10**7以下の素数をエラトステネスで全列挙した後にそれらで割っていくことを考える。
C++ だとこれで通るらしいが、Python(Pypy)だとTLE(test case 23)
import sys import math N = 10 ** 7 def eratosthenes(N): prime = [] table = [0] * (N + 1) for i in range(2, N + 1): if table[i]: continue prime.append(i) for j in range(i, N + 1, i): table[j] = 1 # print(prime) return prime read = sys.stdin.buffer.read input = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines n = int(input()) a = list(map(int, input().split())) ans_u = [0] * n ans_b = [0] * n prime = eratosthenes(N) # print(len(prime) / 10 ** 7 * 100) 6.6%が素数 cnt = 0 for i in a: ng = 1 for j in prime: if j ** 2 > i: break if i % j == 0: while i % j == 0: i = i // j if i == 1: break ans_b[cnt] = i ans_u[cnt] = j ng = 0 break if ng: ans_b[cnt] = -1 ans_u[cnt] = -1 cnt += 1 print(*ans_u) print(*ans_b)
さらに高速化することを考える。
現在の計算量は
エラトステネスの篩 でO(NlogN) N=10**7
各要素に関して最小の素因数で割っていく
O(NKlogA)
K: root(A)以下の素数の数(root(10**7) 以下の素数は400 個くらい。
N : クエリの個数 5*10**5
logA : 最小の素数で何回われるか？log 10**7 で底が2でも高々25以下
よって、計算量が10**8 オーダーになって落ちる。
AC解
Kを最小の素数を見つける箇所を無くしたい。事前計算時に効率化することを考える。
事前計算（エラトステネスの篩の時に）10**7までの値のテーブルを作っているので、それぞれの値に対して、約数としてもつ素数を1ついれておくことを考える。
計算量はO(NlogA) で10**7 オーダー
実行時間は1341msec なのでギリギリ。
定数倍高速化を狙うと、最小の素数でなくて、できるだけ大きい素数にするとlogAの底が大きくなるので早くなりそう。
import sys import math N = 10 ** 7 table = [0] * (N + 1) def eratosthenes(N): prime = [] table[0] = 0 table[1] = 1 for i in range(2, N + 1): if table[i]: continue prime.append(i) for j in range(i, N + 1, i): table[j] = i # print(prime) return prime read = sys.stdin.buffer.read input = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines n = int(input()) a = list(map(int, input().split())) ans_u = [0] * n ans_b = [0] * n prime = eratosthenes(N) # print(len(prime)) # 6.6%が素数 cnt = 0 for i in a: # talbe[i] がi が持つ最小の素数 # table[i]でi を割り切れるまでわる min_prime = table[i] # print(i, min_prime) while i % min_prime == 0: i = i // min_prime if i != 1: # 素数を2種類以上持つ ans_b[cnt] = i ans_u[cnt] = min_prime else: ans_b[cnt] = -1 ans_u[cnt] = -1 cnt += 1 print(*ans_u) print(*ans_b)
コドフォ Educational Contst 89 A~C 解説[python]
A~Cの3完。後半集中が切れてDが解けなかった。pythonにとっては不利な問題だったけどもう少し数学的な考察を加えてあげれば間に合ったので実力不足
A. Shovels and Swords
考察
Atcoderの昔のARCの問題を簡単にしたような問題(
atcoder.jp)
２つの操作があるので両方に共通するものが何か考える
両方の操作で、必ずa,bは1つ以上は減る、かつ合計で3減るという２つの共通点が見つかる。
合計で3減ることから上界は(a+b)/3となる。
また、aが律速になるケースとbが律速になるケースがあり、それぞれa,bが上界となる
実装
min((a+b)//3, a,b)を実装する
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): a, b = map(int, input().split()) print(min(a, b, (a + b) // 3))
B. Shuffle
ジャンル
整数列、操作、貪欲
概要
0,0.. 1,0,0..0 という整数列(`a[x] = 1`で他0) があり、それをm 回swapをすることでak = 1 にできるかを判定
ただし、それぞれの操作でswapに選べる２つのindex の範囲が ` l[i]<=c,d<=r[i]`と決まっている
考察
swapのindex c,d は同じところを選んでもいいので変えないこともできる。
つまり、一度a[k] = 1にできたらそれで終了にできる。
また、xを含みえない範囲でswapしても何も変わらないので、1が取りうる範囲l,r を更新すれば良い
範囲に含むなら更新する
実装
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, x, m = map(int, input().split()) l_x, r_x = x, x for i in range(m): l, r = map(int, input().split()) if l_x <= r: l_x = min(l_x, l) if r_x >= l: r_x = max(r_x, r) print(r_x - l_x + 1)
C. Palindromic Paths
回文、構築
概要
n*m のgrid があり、それぞれのマスは0か1である
左上から右下にいく最短パスが全て回文になるようにgridを変更する時、最小の操作回数を求めよ
考察
2<=n,m<=30なので、全てを考えるとTLEしそう。いい性質を見つける
全ての最短パスが回文になるので、同じマスが回文として対応するマスを考えてみると、始点、終点からの距離がk であるマスは全て同じ値になる
それらは0,1どちらをとってもいいので、最小の操作回数にするためには、距離k の中でmajorityに合わせる。つまり0,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, m = map(int, input().split()) # 始点、終点からの距離がk であるマスで0 の個数を数える # 全体の個数は cnt = [0] * ((n + m) // 2) cnt_zero = [0] * ((n + m) // 2) for i in range(n): a = list(map(int, input().split())) for j in range(m): k = min(i + j, n - 1 - i + m - 1 - j) cnt[k] += 1 if a[j] == 1 and (k * 2 != n - 1 + m - 1): cnt_zero[k] += 1 ans = 0 # print(cnt, cnt_zero) for i in range(len(cnt)): ans += min(cnt_zero[i], cnt[i] - cnt_zero[i]) print(ans)
実装で真ん中処理を考えてなかったのと、軽く
バグった
全体で20min
コドフォEducational 90 A~D解説[python]
結果：A~Dの4完遅解きでぎり青パフォくらい
A - Donut Shops
算数、パズル
概要
２つの店A,Bがある。
Aではドーナツを１つa ドルでうり、Bではb 個単位でc ドルでうる。
考察
式に落とすとb*k < c*ceil(k/b) だが、この中で、１つでも条件を満たすものを考えれば良い(コドフォでよくある）
この中で、１つでも条件を満たすものを考えれば良い(コドフォでよくある）は、閾値を考える
B が安くなるのは、ちょうど単位セットで変えた時で最小はb の時
Aが安くなるのはB が最も余分が多い時で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): a, b, c = map(int, input().split()) if a >= c: print(-1, end=" ") else: print(1, end=" ") if a * b <= c: print(-1) else: print(b)
全体で10min
if a*b <= c : else の箇所で出力を1 にしてて1WA出した。（ちゃんと解けたと思っても確認しようね）
B - 01 Game
ゲーム
考察：
動けなくなる時とは？：隣接した文字が全て同じ文字なら（１種類の文字だけになれば動けない）
必ず1回の操作で0,1が１つずつ減る
場所や順番は関係ないので 1,0の少ない方の個数が奇数なら先行が勝つ
文字列で/b を除きたい時ってどうやるんだっけ？
実装
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() zero_num = s.count("0") # 小さい方が奇数なら勝ち ただし0の場合は数えない if min(len(s) - zero_num, zero_num) == 0: print("NET") elif min(len(s) - zero_num, zero_num) % 2: print("DA") else: print("NET")
C - Pluses and Minuses
コードの理解、累積和（事前計算）、定式化
二重ループ
考察
内側をみるとbreakされないならlen(s) -1 になる
先頭から見てcur より- の数が+より大きくなったら終了
外側はok だったらberakする
最後まで行ってもcur がずっと0以上なら続ける
定式化すると、累積わ*-1を持っておいて、1,2,3...と回してそこまでの分を足せば良い
O(N)
実装
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() n = len(s) ans = 0 cnt = [0] * (1 + n) cum = 0 for i in range(n): if s[i] == "-": cum += 1 else: cum -= 1 if cum > 0 and cnt[cum] == 0: ans += i + 1 cnt[cum] = i + 1 # 最後まで行ったケースを考える。 ans += i + 1 print(ans)
D - Maximum Sum on Even Positions
数列の操作、反転、累積和、実装ゲー
考察
偶数番目にくる数がどのように変わるだけを見れば良い。
l,r の偶奇で場合わけする
even,even => 変わらない
even , odd => 範囲内の選択が逆転
odd, even => 同様
odd,odd => 変わらない
任意の地点に対して、そこまでの偶数、奇数それぞれの累積和を持って差分の差分を計算してmax を取れば良さそう
どうやってmaxを計算するか？
まとめたい。偶数の時は+ 奇数は- の累積和をとる
累積わの区間の最大はどうやって求める？
現在のmax, minを持ってそれぞれ更新する感じ
実装
step1 : 現在の偶数番目の和を計算
step2: 累積和を計算する
step3: 偶数番目、奇数番目それぞれ累積和の列に対して、現在の最大、最小をそれぞれ更新して差分のmaxを計算
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())) """step1 : 現在の偶数番目の和を計算 step2: 累積和を計算する step3: 偶数番目、奇数番目それぞれ累積和の列に対して、現在の最大、最小をそれぞれ更新して差分のmaxを計算 """ origin = sum([a[i] for i in range(n) if i % 2 == 0]) acc = [0] * (1 + n) for i in range(n): if i % 2: acc[i + 1] = acc[i] + a[i] else: acc[i + 1] = acc[i] - a[i] # 偶数に対して現在のmax,minを更新=> min のみの管理 ans_dif = 0 # print(origin, acc) even_min = acc[0] for i in range(n // 2 + 1): even_min = min(even_min, acc[i * 2]) ans_dif = max(ans_dif, acc[i * 2] - even_min) odd_min = acc[1] for i in range((1 + n) // 2): odd_min = min(odd_min, acc[i * 2 + 1]) ans_dif = max(ans_dif, acc[i * 2 + 1] - odd_min) print(ans_dif + origin)
こういう問題は遷移を頭の中でイメージできなくて難しい。典型的な問題みたいなので慣れかな。
Tenka1_2018 C - Align 解説[python]
概要
正の整数がN個与えられた時、それを並び替えて、隣あう要素との差の合計が最大になるようにした時の値を求めよ
制約
2<=N<=10**5
1<=A<=10**9
考察
Naiveな方法だと全ての並び方を全列挙して毎回差を計算することができるが、当然TLE
貪欲に考えると、大きい、小さいが交互に並んだ時が最小に見える。また両端は一度しか計算されないので、差分が小さくなる真ん中の大きさの文字を持ってくれば良さそう。
証明の図
あとは、並び順と大小の準で並べるか、小大の順で並べるかを決める必要がある。
並び順
並び順に関しては、大小を交互で並べた時、それぞれの要素a[i]に対して|a[i]-a[j] | がa[i]-a[j] になるか、a[j]-a[i]になるかは大、小どちらの区分に入るかで決まるので、2*(sum(a[i])-sum(a[j])) -(+)両端の要素(iは大区分に入る要素、j は小区分に入る要素）
という形になる。
大小か小大かに関しては両方計算して大きい方をとる
実装
#!/usr/bin/env python3 n = int(input()) a = [int(input()) for _ in range(n)] a.sort() if n % 2 == 0: print(2 * (sum(a[n // 2 :]) - sum(a[: n // 2])) - a[n // 2] + a[n // 2 - 1]) else: daishou = 2 * (sum(a[n // 2 :]) - sum(a[: n // 2])) - a[n // 2] - a[n // 2 + 1] shoudai = ( 2 * (sum(a[1 + n // 2 :]) - sum(a[: 1 + n // 2])) + a[n // 2] + a[n // 2 - 1] ) print(max(daishou, shoudai))
反省
Naiveな解から貪欲な解を考えて証明するという流れは考えやすくよかった。
40min くらいかかったが、大部分は証明を考えていた時間。
証明に慣れることが必要かも。
ただ、証明を行ってきちんと立式していたおかげ実装に手間取らなかったので、このくらいの解像度を実装前に用意することは必要そう。
AGC031 A - Colorful Subsequence 解説[python]
概要
長さNの文字列Sが与えられ、Sの部分列で全て異なる文字列からなるものの個数を10**9+7で割ったあまりを出力
ただし、異なる位置から出力されたものは違うものとする
制約
1<=N<=10**5
考察
Sが全て異なる文字列からなる場合を考えると、どの部分列も条件を満たす。
個数は、文字列の長さ(=文字数）に対してそれぞれ選ぶかどうか2択なので2**N -1 となる。
次に、問題を考えると、同じ文字がK 箇所ある文字に関しては、どの位置のその文字を選ぶか、または１つも選ばないかのK+1択になる。
よってそれぞれの文字の個数をcnt[26] とすると、(cnt[i]+1) の総乗をとって空文字列として-1 をすれば良い
実装
n = int(input()) s = input() mod = 10 ** 9 + 7 cnt = [0] * 26 # それぞれの文字に対してfreqを数える for i in s: cnt[ord(i) - 97] += 1 ans = 1 for i in cnt: ans *= i + 1 ans %= mod print(ans - 1)
反省
10min 程度で解けたのでなし。
