Timber [Facebook Hacer Cup Qualication Round, Problem C]
問題：
www.facebook.com
概要
数直線上にN 本の木、場所Pi,高さはHi の木が立っている。
数直線上にそって任意の木をそれぞれ左右どちらかに倒すことができる。
操作後にに端点が同じ位置である木同士は１つの木とまとめることができる。
伐採後の木の長さで最大の長さを求めよ。
制約
N <= 4*10**6(テストケース全体で）
-5*10**8 <= pi <= 5*10**8
1 <=hi <= 5*10**8
同じ位置に複数の木が存在することはない。
考察
二分探索でやろうとして、p+h ,p-hでソートした時のidx を持ったりしてバグらせたので、解説の方針で実装します。
まず、答えの列に使わない木は倒していないことにすればいいので、全ての木は左右どちらかに倒すと考えて良い。
同じ位置に複数の木が存在することはないという条件、木が端点以外で重複して存在してはいけないという条件から、向きは左向きのみ、右向きのみ、右向きの列の右端に左向きの列の左端が被っている場合の３通りに絞られる。
ここで左向き、右向きのみの木の列の長さを端点の場所をkeyとして座圧して持つdp として計算すれば、最後に端点が一致するもの全てに対して、一致するi,jに対して、ans = max(ans,dp_l[i]+dp_r[j])でもとまる。
実装
import bisect import sys read = sys.stdin.buffer.read input = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines # step1:座圧して（ソートした順番で)DPを左端と右端両方から行う # dp_l[i] = max(dp_l[j] + h[i],h[i]) p+h をソートして持っておけばできる。 # dp_r[i] = max(dp_r[j] + h[i],h[i]) p-hをソートして持つ # step2:全てのi に対して、p[i]+h[i] がp[j]-h[j]となるj があるかを二分探索で探す # dict で書き換える # step3:step2で一致するi,jに対して、ans = max(ans,dp_l[i]+dp_r[j]) t = int(input()) for case in range(t): n = int(input()) p = [0] * n h = [0] * n for i in range(n): p[i], h[i] = map(int, input().split()) p, h = zip(*sorted(zip(p, h))) # p で昇順にsort 右に倒すものは昇順に、左に倒すものは降順に見る # 左から順番にみていく 左から見たものに # dp はkey がpos,value が長さ で置く dp_r_dict = {} # 右に倒れる木の列のなかでpos が末端(右端）列の中で最長の長さ dp_l_dict = {} for i in range(n): # dict[p[i]]があればそれを返し、なければ0を返す # もしp[i]で終わるものがあればそれをつなげて伸ばすことができるため tmp = dp_l_dict.get(p[i], 0) + h[i] if dp_l_dict.get(p[i] + h[i], 0) < tmp: # 同様 dp_l_dict[p[i] + h[i]] = tmp r_max = 0 for i in range(n - 1, -1, -1): tmp = dp_r_dict.get(p[i], 0) + h[i] if dp_r_dict.get(p[i] - h[i], 0) < tmp: dp_r_dict[p[i] - h[i]] = tmp r_max = max(r_max, dp_r_dict[p[i] - h[i]]) # step3:dp_l_dict に対して、全てのkey でdp_r_dictのkey と一致するのがあるかを調べmaxをとる ans = 0 for pos, l_len in dp_l_dict.items(): tmp = l_len + dp_r_dict.get(pos, 0) # 全て右向きでもOK ans = max(ans, tmp) # 全て左向きを考慮する ans = max(ans, r_max) case_str = "Case #" + str(case + 1) + ": " + str(ans) print(case_str)
頭の良い別解
友人に教えてもらったやり方でdpを１つにする方法を教えてもらったので紹介
基本的なdp の考え方は同じで、ソートした順番でDPを端から行う。
ただ、左右の切り方を区別せずdp配列を１つだけもつ。
それぞれの木を見る際にdpの更新は右に倒す方から更新する(更新を先に右に倒す方から行えば重複することはない)
import bisect import sys read = sys.stdin.buffer.read input = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines # step1:座圧して（ソートした順番で)DPを左端からのみ行う # step2: それぞれの木を見る際にdpの更新は右に倒す方から更新する(更新を先に右に倒す方から行えば重複することはない) t = int(input()) for case in range(t): n = int(input()) p = [0] * n h = [0] * n for i in range(n): p[i], h[i] = map(int, input().split()) p, h = zip(*sorted(zip(p, h))) # dp はkey がpos,value が長さ で置く dp_dict = {} # 左から更新した時に現在場所=key で終わるありうる木の列の中で最大なもの ans = 0 for i in range(n): # 木i を右向きに倒す tmp = dp_dict.get(p[i], 0) + h[i] if dp_dict.get(p[i] + h[i], 0) < tmp: # 同様 dp_dict[p[i] + h[i]] = tmp ans = max(ans, dp_dict[p[i] + h[i]]) # 左向きに倒す tmp = dp_dict.get(p[i] - h[i], 0) + h[i] if dp_dict.get(p[i], 0) < tmp: dp_dict[p[i]] = tmp ans = max(ans, dp_dict[p[i]]) case_str = "Case #" + str(case + 1) + ": " + str(ans) print(case_str)
手元で実行してみただけだと早くはならなかったが(多分dictがO(1)で重くないため）、コードが簡潔になった。
ARC050 B 花束
考察
２つの操作の共通項を考えると、一回の操作で両方とも少ない方が1減る。
そこで、解を決めうち、m セット作れるかどうか、という問題に帰着すると、できるだけ多く買おうとすると(x-1),(y-1)をできるだけ取った時になる。
数式で表すと
m <= (r - m) // (x - 1) + (b - m) // (y - 1)
ならば、mセット買うことができる。
実装
を見ながらめぐるしき二分探索で書きました。
今回はできるだけ多いmを求めたいので、ok に条件を満たす最小値0 を、ngに条件を満たさない大きな値r+bをおきました。
#!/usr/bin/env python3 r, b = map(int, input().split()) x, y = map(int, input().split()) # 解の決めうち二分探索 # k を作れるかどうかで決めうつ # 不変量: １つ花束を作ると両方1以上は減る # 不変量を意識して１変数のみ考慮すればいい状態に持っていくと # k を固定した時の最適な条件が一意に決まる ok = 0 ng = r + b def is_ok(m): if r - m >= 0 and b - m >= 0 and m <= (r - m) // (x - 1) + (b - m) // (y - 1): return True # 作れる else: return False def meguru_bisect(ng, ok): while abs(ok - ng) > 1: mid = (ok + ng) // 2 if is_ok(mid): ok = mid else: ng = mid return ok print(meguru_bisect(ng, ok))
Alchemy [Facebook Hacer Cup Qualication Round, Problem B]
読んだことはないが、鋼の錬金術師のパロディらしい。
問題文：
Problem B: Alchemy | Facebook Hacker Cup - 2020 - Qualification Round
概要
奇数個の要素を持つbit列が存在する。その中から連続する３つの要素をのぞき、選んだ３つの要素の中で多い方のbit を持つ要素を除いた箇所に挿入するという操作を繰り返す。
ただし、選ぶ３つの要素が全て同じbitであることは許されない。
その時、要素が１つになるまで操作を続けることは可能かを判定せよ。
考察
ゲーム問題なので、後ろから考えてみるが後ろから考えるのは無限にパターンが増えるので厳しい。
実験をして考えると、0,1の数の差が１であることと１つにできるかが同値っぽいので、それを証明する。
証明
必要条件
操作が行えなくなるのは、どの連続する3つの要素を選んでもそれが全て同じbitになる時である。
しかし、0,1の数の差は操作によって不変であることから、0,1の数の差が1の場合はずっと1であるので要素数が１になるまで必ず操作を行うことができる。
実装
t = int(input()) for case in range(t): n = int(input()) s = input() numA = s.count("A") numB = s.count("B") if abs(numA - numB) != 1: ans = "N" else: ans = "Y" case_str = "Case #" + str(case + 1) + ":" + ans print(case_str)
Travel_restrictions [Facebook Hacer Cup Qualication Round, Problem A]
,*概要
1列に都市が並んでおり、隣接する都市間のみ行き来することができる。ただし、いくつかの国は入国制限と出国制限を設けており、その場合は入国、出国ができない。
それぞれの都市に対して入国、出国が可能かがリストとして与えられる時、各都市からそれぞれの都市にいくことが可能かどうかをN*Nの行列の形式で出力せよ。
問題文：
Problem A: Travel Restrictions | Facebook Hacker Cup - 2020 - Qualification Round
考察
それぞれの都市から訪れることが可能な都市は数直線上に連続しているため、区間で表現できる。
また、それぞれの都市の開始点は隣接する都市との関係で求めることができる。
( もし、隣接する都市から入国が可能ならその都市の開始点と等しい、そうでなければその都市自身が開始点）
よって、左右、両方向の向きに対して、端から順番に計算すれば良い。
実装
t = int(input()) for case in range(t): n = int(input()) I = input() O = input() res = [["N"] * n for _ in range(n)] res_l = [0] * n res_u = [n - 1] * n for i in range(n - 1): # if (I[i + 1] == "N" and O[i] == "N") or (I[i + 1] == "Y" and O[i] == "Y"): if I[i + 1] == "Y" and O[i] == "Y": res_l[i + 1] = res_l[i] else: res_l[i + 1] = i + 1 for i in range(n - 1, 0, -1): if I[i - 1] == "Y" and O[i] == "Y": res_u[i - 1] = res_u[i] else: res_u[i - 1] = i - 1 # res_l では縦に見る for i in range(n): for j in range(res_l[i], i + 1): res[j][i] = "Y" for k in range(i, res_u[i] + 1): res[k][i] = "Y" case_str = "Case #" + str(case + 1) + ":" print(case_str) for i in range(n): print("".join(res[i]))
ABC173 D - Chat in a Circle 解説[python]
概要
それぞれAi の値を持つN 個の人がいる。
円に対して人を一人ずつ加えていくことを考える。
追加する場所はどこでも良い（好きな位置に割り込み可能）
新たに追加される度に左右に隣接する人の値の小さい方を心地よさとして持つ時、N人を追加し終わったときの心地よさの合計の最大値を求めよ。
考察
どこに追加することもできるので、貪欲に考えられそう。
大きくなりそうな方法を考えると、max を最初に追加し、そこから順番に大きいものをmax に隣接するように加えるのが大きそう。
証明: 降順に追加するのが最大なことの証明
swapしている箇所が1箇所のみの場合を考える。
a1 > a2 > .... >a[i] < a[i +1] > a[i+2] ...
a[i] , a[i+1] が入った場所をx,y とする。
1) x,y が隣接していない時
a[i],a[i+1]をswapしても合計は変わらない
2) x,y が隣接している時
a[i],a[i+1]をいれる順番をswap すると、a[i],a[i+1]を挿入した後の配置をa[j] a[i] a[i+1] a[k] とすると、
min(a[j],a[k]) + a[i] がmin(a[j],a[k]) + a[i+1] となり、差分はa[i] -a[i+1] で正となるのでswapした方が得
証明：max のみが一度足され、他は上から2回足されることの証明
今、先の証明から追加する順番は降順で、その時、幸福度を何回たすことができるかを考えると、最高でmax のみが一度足され、他は上から2回足すことができることがわかる。（2回足した時両側は自分より小さくなるため）
これは、max から順番に現在幸福度として加算されうる最大の要素の両端に追加していくという操作を繰り返すことで実現できるのでこれが最大。
実装
#!/usr/bin/env python3 n = int(input()) a = list(map(int, input().split())) a.sort() ans = a[-1] cnt = 1 while cnt < n - 1: ans += a[-1 * (1 + (1 + cnt) // 2)] cnt += 1 print(ans)
証明になっているか怪しくてすみません。
エイシング プログラミング コンテスト 2020 A~D解説
しょうもない実装ミス、誤読を直せずA,Bの2完でした（え？）
A - Number of Multiples
概要
L 以上 R以下の整数のうち、dの倍数であるようなものはいくつありますか？
考察
基本的にはl,r をd で割った商の差を取れば良い。ただし、l がd で割り切れる時は、+1する
#!/usr/bin/env python3 l, r, d = map(int, input().split()) print(r // d - l // d + (l % d == 0))
B - An Odd Problem
概要
1,..N の番号が書かれたマスがあり、それぞれ値A[i] を持つ。
Nこのマスのうち、番号、値が共に奇数であるマスの数を求めよ
考察
１つずつマスを見てO(N)
スライスを使うと奇数ますだけ見れて楽
#!/usr/bin/env python3 n = int(input()) a = list(map(int, input().split())) ans = 0 for i in range(0, n, 2): if a[i] % 2: ans += 1 print(ans)
C - XYZ Triplets
概要
1<=a,b,c
a ** 2 + b ** 2 + c ** 2 + a * b + b * c + c * a = n
を満たすa,b,c の組み合わせを1<=n<=N に対してそれぞれ求めよ
制約
N<=10**4
考察
1<=a,b,c より、a ** 2 + b ** 2 + c ** 2 + a * b + b * c + c * a はa**2 ,b**2,c**2よりは大きくなるから、条件を満たすa,b,c, は100未満である。
つまり1~99までa,b,cを全探索すれば良い。
ただし、n をループさせるとO(N)*100**3となってTLEするので、それぞれのn に対して個数を持つリストを用意して、a,b,cの全探索での値がN以下ならそこに対応する個数を+1すれば良い
#!/usr/bin/env python3 n = int(input()) cnt = [0] * (1 + n) for a in range(1, 100): for b in range(1, 100): for c in range(1, 100): k = a ** 2 + b ** 2 + c ** 2 + a * b + b * c + c * a if k > n: continue else: cnt[k] += 1 for i in range(1, n + 1): print(cnt[i])
D - Anything Goes to Zero
概要
D - Anything Goes to Zero
説明しにくいのでリンク
２進数をそれに含まれる1の個数で割っていったあまりに更新するという操作を繰り返す
制約
1<~N<=2*10**5
考察
桁数が2*10**5なので、まともに計算するとオーバーフローするし、時間がかかる。
オーバーフロー対策として、mod だけ取れば良いのでmod で計算する。
ただ、1回操作を行うと、1の個数以下になるので2*10**5以下になり大幅に減る。
それぞれの反転で1の数は+1 or -1 になるので、初期の1の値をcntとすると、cnt+1とcnt-1をmodにした時の値をそれぞれもち、それぞれのbit反転数に対してbit反転した後の値をそこから計算した後、それ以降の操作を行えば良い。
操作をstepごとにまとめると以下のようになる
step1; 1を数える cnt_1
step2 : 全体の計算をする cnt1 + 1 とcnt1 -1 それぞれ
step3 : それぞれの桁に対して0 なら cnt+ 1 を適用 + 2**k mod cnt + 1
1ならcnt - 1 を適用 - 2**k mod (cnt-1)
step4 : その中でf(x)を0になるまで計算
実装
#!/usr/bin/env python3 n = int(input()) x = input() cnt = x.count("1") x_cnt_plus = 0 x_cnt_minus = 0 for i in range(n): if x[i] == "1": x_cnt_plus += pow(2, n - i - 1, cnt + 1) x_cnt_plus %= cnt + 1 if cnt > 1: x_cnt_minus += pow(2, n - i - 1, cnt - 1) x_cnt_minus %= cnt - 1 for i in range(n): # 上からi 桁目に注意 if x[i] == "0": f = x_cnt_plus + pow(2, n - i - 1, cnt + 1) f %= cnt + 1 else: if cnt == 1: print(0) continue f = x_cnt_minus + cnt - 1 - pow(2, n - i - 1, cnt - 1) f %= cnt - 1 ans = 1 while f != 0: cnt_f_1 = 0 k = f while k: if k % 2: cnt_f_1 += 1 k //= 2 f = f % cnt_f_1 ans += 1 print(ans)
コドフォ Educational Contest 90 E Sum of Digits 解説[python]
ジャンル
整数問題 埋め込み問題
概要
f(x)を各位の和とする。
n,kが与えられる時
f(x)+f(x+1)+...+f(x+k) = n となるような最小の非負整数x を求めよ。
制約
0<=k<=9
1<=n<=150
考察
k が小さい(K<=9) ので1のくらいでの繰り上がりはあったとしても一度のみ
N,Kが共に小さく、150*10 通りを計算して埋め込めそうな気もする
K=0 の時、1,2,3,..9,19,29,...99,199,299....999 とn*9 を超えたら桁を増やしていく
K=1の時、奇数だったら作れそう。偶数の時、繰り上がりが必ず起こる
10 => 9,10 12 => 19,20, ..26=> 89,99 28=>189,199 で作れる
K=2の時、3の倍数なら繰り上がりがない範囲で作る。あまり1,2は繰り上がらないと無理そう
繰り上がる時、繰り上がる前の数の桁は9 でそれが繰り上がると0になってその次の桁が1増えるので結果的に3で割ったあまりは1増えるのと変わらない。したがって、繰り上がりがあっても無理。
K=3 を考えると、4の倍数ならいける。同様に考えると、繰り上がると9が減って1増えるので+- 0 になる。がここからはかなり厳しい。
K>=3 の時、取りうる値を考えると、数字が４つ連続するので、9*4*桁数-6 がその桁数の中で最も大きい値になる。(99..96,99..97,99..98,99..99 の時）
つまり、N<=150の元での上界を考えると、桁数は5桁以内に収まることがわかる。
したがって、<10**5 でループを回せば良い
実装
step1: K=0 の時の分岐を作る
step2: K=1の分岐を作る
step3: K=2の時の分岐を作る
step4: K>=3なら、10**5以内で全探索する。
計算量：K>=3の時が計算が重くて、O(t*N) N=10**5 で10**7オーダーになる
のようにK の値に応じて処理を分ける
lim を10**5固定にするとtestcase7 (K=5)でTLEしたのでlim をKに応じて変更するとAC
lim は何桁が最大化のみを見れば良くて、9*(K+1)*digit - (K+1)*K//2 >=150 になる最小のdigit が桁数になる
これで埋め込みなしで630msec
import sys import math """ step1: K=0 の時の分岐を作る step2: K=1の分岐を作る step3: K=2の時の分岐を作る step4: K>=3なら、10**5以内で全探索する。 計算量：K>=3の時が計算が重くて、O(t*N) N=10**5 で10**7オーダーになる """ read = sys.stdin.buffer.read input = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines def solve_sum_digit(n): res = 0 while n: res += n % 10 n //= 10 return res def solve_0(n): digit = math.ceil(n / 9) res = "" if n % 9: res += str(n % 9) + "9" * (digit - 1) else: res += "9" * (digit) return res def solve_1(n): # 偶奇で分ける if n % 2: # 奇数なら全て作れる if n <= 17: return n // 2 else: # 2桁以上なら、最後は8になる digit = n // 18 + 1 num_top = (n % 18) // 2 + 1 return str(num_top) + "9" * (digit - 2) + "8" else: # 偶数なら必ず繰り上がりが必要で10以上は作れる # 10 => 9,10 12 => 19,20, ..26=> 89,99 28=>189,199 で作れる if n < 10: return -1 elif n == 10: return 9 else: digit = (n + 8) // 18 + 1 num_top = ((n + 8) % 18) // 2 + 1 if digit == 2: return str(num_top - 1) + str(9) else: return str(num_top) + "9" * (digit - 3) + "89" def solve_2(n): if n % 3: return -1 else: if n <= 24: return n // 3 - 1 else: digit = n // 27 + 1 num_top = (n % 27) // 3 + 1 return str(num_top) + "9" * (digit - 2) + "7" t = int(input()) # t = 1501 for case in range(t): n, k = map(int, input().split()) # n = case // 10 + 1 # k = case % 10 if k == 0: ans = solve_0(n) elif k == 1: ans = solve_1(n) elif k == 2: ans = solve_2(n) else: pass_flag = 0 if k == 3: lim = 10 ** 5 elif k <= 5: lim = 10 ** 4 else: lim = 10 ** 3 for x in range(0, lim): sum_digit = 0 for i in range(k + 1): sum_digit += solve_sum_digit(x + i) if sum_digit == n: # print(x) ans = x pass_flag = 1 break if pass_flag == 0: # print(-1) ans = -1 print(ans)
