ABC290の振り返り(A, B, C, D, E)

振り返りです。

def test_all(f): for i, data in enumerate(eval(f'test_data{f.__name__[0]}')): exp = data["out"] ans = f(*data["in"]) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}: expected: {exp}, output: {ans}")

A - Contest Result

B - Qual B

略

C - Max MEX

やってみよう！

C関数を完成させて「Run」ボタンをクリックしよう！

test_dataC = [ { "in":[7, 3, [2, 0, 2, 3, 2, 1, 9]], "out": 3 } ] def C(N, K, A): pass test_all(C)

自由欄

try

振り返りよりコンテスト中の方がいい感じだったので置いときます。
こんな感じ。

def C(N, K, A): A = sorted(set(A)) ans = 0 for i in range(min(K, len(A))): if A[i] == i: ans += 1 else: break return ans test_all(C)

結果：#39024386

自由欄

D - Marking

やってみよう！

D関数を完成させて「Run」ボタンをクリックしよう！

test_dataD = [ { "in":[9, [[4, 2, 1], [4, 2, 2], [4, 2, 3], [4, 2, 4], [5, 8, 1], [5, 8, 2], [5, 8, 3], [5, 8, 4], [5, 8, 5],]], "out": """0 2 1 3 0 3 1 4 2""" }, ] def D(T, NDK): pass test_all(D)

自由欄

try

コンテスト中の終了間際提出が変数名間違えるという凡ミスしてたので修正したのが以下。
でも結局RE x 4...

import numpy as np def D(T, NDK): for n, D, k in NDK: D = D % n if n % D == 0: cycle = n // D else: cycle = np.lcm(D, n) // D if cycle == 0: d = 0 m = k else: d, m = divmod(k - 1, cycle) m += 1 # print(k, m, cycle) print((d + (D * (m - 1))) % n) return test_all(D)

結果：#39313452

振り返り

上のコードを見返しても、何がしたかったのかよく分かりません😇
まぁ、頑張って考えたんだろうな、俺。そして頭の中ごちゃごちゃになったんだろうな。お疲れ…

という訳で改めて考えてみると、以下のようなことがしたかったんでしょう。

import numpy as np def D(T, NDK): for N, D, K in NDK: if D % N == 0: cycle = 1 else: D = D % N cycle = np.lcm(D, N) // D K -= 1 print(D * K % N + K // cycle) return test_all(D)

結果：#39313452

無事AC😁

解説を見る

実は上の振り返りの前に解説を見てみたのですが、一旦理解することを諦めました。
それが以下。

import numpy as np def D(T, NDK): for N, D, K in NDK: K -= 1 a = N // np.gcd(N, D) print(D * K % N + K // a) test_all(D)

結果：#39313982

んで、振り返りの後にまた見てみると、ほとんど一緒やん！！(まぁところどころ影響を受けたのは否めない…)
自力で考えたのは、「何回目に元の場所に戻るか」ということで、それなら最小公倍数だろうとなったのですが、最大公約数でも同じ数が出せるというなんですね。

確認します。
今回「何回目に元の場所に戻るか」を知るために$\frac{lcm}{D}$で計算しました。
ここで$D = gcd \times d$、$N = gcd \times n$と置くと、$lcm = gcd \times d \times n$と表せます。
という訳で、結局
$\frac{lcm}{D} = \frac{gcd \times d \times n}{gcd \times d} = n = \frac{N}{gcd}$
という解説の想定解の式になるわけですね。勉強になった。(中高で習った…？)

自由欄

E - Make it Palindrome

やってみよう！

E関数を完成させて「Run」ボタンをクリックしよう！

test_dataE = [ { "in":[5, [5, 2, 1, 2, 2]], "out": 9 } ] def E(N, A): pass test_all(E)

自由欄

解説を見る

回文を作れって、稀によく見る気がしますね。
まぁそんな気がするだけで解法の見当は全くつかないので解説を見ます。

斜め読みして「主客転倒完全に理解した！」ってことで提出したのが以下。

from itertools import combinations from collections import defaultdict def E(N, A): ans = 0 for i, j in combinations(range(N), 2): if A[i] == A[j]: continue ans += min(i + 1, N - j) return ans test_all(E)

結果：#39333959

TLE × 56...
そりゃすべての組み合わせを見ると$O(N ^ 2)$になって今回の制約下だと無理だわな。

ちゃんと解説を見る

「悪い線の合計、簡単に出せるじゃん」と考えて書いたのが上のコードでした。
もちろん処理自体は簡単なのですが、計算量の壁が立ちはだかります。

解説でわざわざ(悪い線の合計) = ( 線の合計 - 良い線の合計 )としているのは、工夫すれば良い線の合計を$O(N)$で出せるからなんですね。
詳細は解説を見ていただくとして、以下のコードでは9行目からのfor文がそれにあたります。
考え方を理解するのになかなかの時間を要しました😇

def E(N, A): p = defaultdict(list) for i, a in enumerate(A, 1): p[a].append(i) res = 0 for i in range(1, N + 1): res += (N + 1 - i) * (i // 2) for v in p.values(): l = 0; r = len(v) - 1 while l < r: if v[l] < (N + 1 - v[r]): res -= (r - l) * v[l] l += 1 else: res -= (r - l) * (N + 1 - v[r]) r -= 1 return res test_all(E)

結果：#39335826

自由欄