Upgrade to Pro — share decks privately, control downloads, hide ads and more …

OUPC2024 Day 1 解説

OUPC2024 Day 1 解説

KowerKoint

March 15, 2025
Tweet

Other Decks in Programming

Transcript

  1. 統計 2025/03/15 OUPC2024 Day 1 2 問題 AC数 全体FA オンサイトFA

    A 78 C2n2pBB2y(0:00) SuginokiButtaosu(0:01) B 74 UHISHIRO(0:02) compact(0:02) C 49 compact(0:10) compact(0:10) D 12 noshi91(1:00) OUPC_Ajillo(1:38) E 0 ◦◦◦(0:00) ◦◦◦(0:00) F 9 OUPC_Ajillo(1:23) OUPC_Ajillo(1:23) G 0 ◦◦◦(0:00) ◦◦◦(0:00) H 3 compact(2:48) compact(2:48) I 0 ◦◦◦(0:00) ◦◦◦(0:00)
  2. 統計2 2025/03/15 OUPC2024 Day 1 3 問題 AC数 全体FA オンサイトFA

    J 10 sansen(0:51) OUPC_Ajillo(1:57) K 5 t_am(1:25) tree_univ_of_tree(2:44) L 55 compact(0:19) compact(0:19) M 25 sansen(0:28) tree_univ_of_tree(0:37) N 6 compact(2:22) compact(2:22) O 29 nanj_min(0:30) nanj_min(0:30) P 5 sansen(1:12) tree_univ_of_tree(1:41) Q 66 OUPC_Ajillo(0:09) OUPC_Ajillo(0:09)
  3. 想定難易度・ACチーム数 0 10 20 30 40 50 60 70 80

    A B Q C L D N O M J P F H G I E K AC者数(想定難易度順) AC者数 2025/03/15 OUPC2024 Day 1 4
  4. 解法 文字を順に見て行って頭文字と一致していたら変更しましょう 2025/03/15 OUPC2024 Day 1 12 #include <bits/stdc++.h> using

    namespace std; int main() { int N; cin >> N; string S; cin >> S; char initial = S[0]; for (auto &c : S) if (c == initial) c = toupper(c); cout << S << endl; } C++
  5. 解法 それ用の関数を用いても可 2025/03/15 OUPC2024 Day 1 13 #include <bits/stdc++.h> using

    namespace std; using ll = long long; int main() { ll N; string S; cin >> N >> S; char old_val = S[0], new_val = (char)toupper(S[0]); replace(S.begin(), S.end(), old_val, new_val); cout << S << endl; } C++ N = input() S = input() print(S.replace(S[0], S[0].upper())) Python
  6. 問題概要 OUPCは𝑁問からなる shinchanは𝐴1 , 𝐴2 , … , 𝐴𝐾 の𝐾問に正解している

    kotamanegiに𝐶𝑖 円賄賂を渡すと新たに問題𝑖に正解できる 𝑀問解くと優勝 最小いくら賄賂を渡せばよい? • 1 ≤ 𝑁 ≤ 100 • 1 ≤ 𝑀 ≤ 𝑁 • 1 ≤ 𝐶𝑖 ≤ 100 2025/03/15 OUPC2024 Day 1 15
  7. 解法 優勝のためにはあと𝑀 − 𝐾問解く必要がある 𝑀 − 𝐾 ≤ 0なら賄賂不要 𝑀

    − 𝐾 > 0なら解いてない中で必要な賄賂の小さい順に渡せばよい • 解いてない問題のコストを昇順にソートして、前から𝑀 − 𝐾個選ぶ 2025/03/15 OUPC2024 Day 1 16
  8. 問題概要 以下の2つの行動で受けるダメージの期待値の小さい方を出力 回避 • 20面ダイスを𝐾回振った最小値を𝑥 • 10面ダイスを𝑀回振った総和に𝐷を加えたものを𝑦 • 𝑥 ≤

    𝐻ならば0ダメージ、違えば𝑦ダメージ 防御 • 10面ダイスを𝑀回振った総和に𝐷を加えたものを𝑦 • max(0, 𝑦 − 𝐴)ダメージ 2025/03/15 OUPC2024 Day 1 18 • 1 ≤ 𝐻 ≤ 20 • 1 ≤ 𝑀 ≤ 6 • 1 ≤ 𝐷 ≤ 100 • 1 ≤ 𝐾 ≤ 100,000 • 1 ≤ 𝐴 ≤ 100 誤差1e-6までOK
  9. 解法 両方愚直に求められるので求めて小さい方を出力すればよい 回避 • 最小値が𝑖(1 ≤ 𝑖 ≤ 20)となる確率𝑝𝑖 を求める(上から除原理)

    • σ 𝑖=𝐻+1 20 𝑝𝑖 ⋅ 𝑦が期待値(𝑦 = 5.5𝑀 + 𝐷) 防御 • 総和が𝑖(1 ≤ 𝑖 ≤ 10𝑀)となる確率𝑞𝑖 をdpで求める • σ 𝑖=𝐴−𝐷 10𝑀 𝑞𝑖 ⋅ (𝑖 + 𝐷 − 𝐴)が期待値 2025/03/15 OUPC2024 Day 1 19
  10. 解法 𝑑𝑝 𝑖 𝐵 = max 𝑑𝑝 𝑖 − 1

    𝐵 , 𝑑𝑝 𝑖 − 1 ∗ + 1 𝑑𝑝 𝑖 𝐾𝑌𝐵 = max 𝑑𝑝 𝑖 − 1 𝐾𝑌𝐵 , 𝑑𝑝 𝑖 − 1 𝐾𝑌 + 1 𝑑𝑝 𝑖 𝐾 = max 𝑑𝑝 𝑖 − 1 𝐾 , 𝑑𝑝 𝑖 − 1 ∗ + 1 𝑑𝑝 𝑖 𝐵𝑌𝐾 = max 𝑑𝑝 𝑖 − 1 𝐵𝑌𝐾 , 𝑑𝑝 𝑖 − 1 𝐵𝑌 + 1 𝑑𝑝 𝑖 𝐵𝑌 = max(𝑑𝑝 𝑖 − 1 𝐵𝑌 , 𝑑𝑝[𝐵]) + 1 𝑑𝑝 𝑖 𝐾𝑌 = max(𝑑𝑝 𝑖 − 1 𝐾𝑌 , 𝑑𝑝[𝐾]) + 1 𝑑𝑝 𝑖 ∗ = max(𝑑𝑝 𝑖 − 1 ∗ , 𝑑𝑝 𝑖 𝐾𝑌𝐵 , 𝑑𝑝[𝑖][𝐵𝑌𝐾]) という遷移が成り立つ。 2025/03/15 OUPC2024 Day 1 24
  11. 余談 enumを使うと実装が分かりよい セグ木に乗る • 更新クエリ・区間クエリの問題だとしても解ける 2025/03/15 OUPC2024 Day 1 25

    enum State { EMPTY, // "" B, // "B" K, // "K" BY, // "BY" KY, // "KY" BYK, // "BYK" KYB, // "KYB" NUM_STATES }; if (c == 'B') { ndp[B] = max(dp[B], dp[EMPTY]) + 1; ndp[KYB] = max(dp[KYB], dp[KY]) + 1; } if (c == 'K') { ndp[K] = max(dp[K], dp[EMPTY]) + 1; ndp[BYK] = max(dp[BYK], dp[BY]) + 1; } if (c == 'Y') { ndp[BY] = max(dp[BY], dp[B]) + 1; ndp[KY] = max(dp[KY], dp[K]) + 1; } ndp[EMPTY] = max({dp[EMPTY], ndp[BYK], ndp[KYB]});
  12. 問題概要 選手𝑝1 , 𝑝2 , … , 𝑝𝑀 がコンテストAに参加する コンテストAに参加する残り2𝑁

    − 𝑀人を一様ランダムに決めるとき 選手𝐾の決勝進出確率は?998244353の有理数modで • 1 ≤ 𝑁 ≤ 50,000 2025/03/15 OUPC2024 Day 1 29
  13. 解法 実は強い2𝑁人が必ず決勝進出する • 𝐾 ≥ 2𝑁 + 1ならば1,違えば0を出力すればよい 証明 上位𝑁人はA,Bで絶対勝つし、Lでも勝つ→決勝進出

    上位𝑁 + 1~2𝑁人はRで絶対勝つし、Xでも勝つ→決勝進出 (FPSチックな制約にしたので悩んでくれてたら嬉しいらしいです) 2025/03/15 OUPC2024 Day 1 30
  14. 問題概要 𝑁枚のカードを用いて先大君と小後君の2人でゲーム 𝑖枚目のカードには𝑎𝑖 が書かれている 2025/03/15 OUPC2024 Day 1 32 先大君から以下の操作をする

    • まだ選ばれていないカードを選びどちらかに所持させる 𝑁回の操作後の2人のスコアを以下の和で定める • それぞれの所持しているカードの値の総和 • カード𝑥𝑗 とカード𝑦𝑗 を両方所持しているような𝑧𝑗 の総和 (そのような条件が𝑀個与えられる) 2人とも(自分のスコア) − (相手のスコア)を最大化するように 最適に動くときの(先大君のスコア) − (小後君のスコア)は? • 2 ≤ 𝑁 ≤ 200,000 • 1 ≤ 𝑀 ≤ 100,000 • −109 ≤ 𝑎𝑖 , 𝑧𝑖 ≤ 109
  15. 解法 𝑎 𝑥𝑗 と𝑎 𝑦𝑗 に𝑧𝑗 /2を加えることでスコアの条件の2つ目が無視できる (両方取ったら+𝑧𝑗 で、別々に取ったら±0なので) 1個目の条件だけなら明らかに貪欲に選んでよい

    • 絶対値の降順でソートして奇数番目を先大、偶数番目を小後が選ぶ • 値が正なら自分で取って、負なら相手に渡す • 絶対値を取ってそのまますべて自分で取るとしてもよい (相手に−𝑎𝑖 と自分に+𝑎𝑖 は等価なので) 実装上はすべて2倍して、最後に2で割るとよい 2025/03/15 OUPC2024 Day 1 33
  16. 問題概要 • 𝑅×𝐶の盤面上で、(𝑥1 , 𝑦1 ) にいるスーパーナイトが、ちょうど2手で、 𝑥2 , 𝑦2

    にいるお姫様を助けに行きたい • 1手目として経由する可能性のあるマスの個数を出力 • 𝑅, 𝐶 ≤ 109, 𝑄 ≤ 10000 • 𝑥1 , 𝑥2 ≤ 𝑅, 𝑦1 , 𝑦2 , ≤ 𝐶 2025/03/15 OUPC2024 Day 1 35 ただのナイト スーパーナイト
  17. 解法 同じマスでない場合 • スーパーナイト、お姫様からの方向を固定 • 正負を一緒に考えると4×4通り • それぞれ重複しないので足し合わせられる • 同じ方向

    • これも算数 • その方向で1手で行ける位置関係なら算数 • 直線上のマスの個数から 2 を引いたもの • 上記でない場合、0 2025/03/15 OUPC2024 Day 1 37
  18. 解法 同じマスでない場合 • 違う方向 • 高々1通りしかない • 連立方程式を作って解けばよい • 実装上は同じ方向の場合と合わせて、

    行列を使うと良さそう まとめ • 同じマスの場合 : 算数 • そうでない場合 : 方向を固定して行列とか • 行列式が0なら方向が同じ : 算数 • 0でないなら方向が異なる : 逆行列で一意に 2025/03/15 OUPC2024 Day 1 38
  19. 解法 左から残すビルを決めることにする(残すビルのコストを最大化する) 隣り合う2つのビルの傾きが段々大きくならないとダメ 最後2つが分かっていれば序盤はどうでもいい 以下のdpができる 𝑑𝑝 𝑖 𝑗 = として、

    𝑑𝑝 𝑗 𝑘 = max 𝑖 𝑑𝑝 𝑖 𝑗 + 𝐶𝑘 (ただし、𝑖, 𝑗間の傾きより𝑗, 𝑘間の傾きの方が大きい) 2025/03/15 OUPC2024 Day 1 41 残っているビルの右2つがビル𝑖,ビル𝑗のときの 残っているビルのコストの和の最大値
  20. 解法 𝑑𝑝 𝑗 𝑘 = max 𝑖 𝑑𝑝 𝑖 𝑗

    + 𝐶𝑘 (傾き𝑖, 𝑗 ≤傾き𝑗, 𝑘) これは以下の手順で𝑂(𝑁2 log 𝑁)で求まる 1. 𝑗を固定して傾き𝑖, 𝑗の小さい順に𝑖をソート 2. ソートした順にパレート最適な(𝑑𝑝 𝑖 𝑗 , 𝑖)を要素に持つ配列を作る (傾き𝑖1 , 𝑗 < 傾き𝑖2 , 𝑗なのに𝑑𝑝 𝑖1 𝑗 ≥ 𝑑𝑝 𝑖2 𝑗 みたいな𝑖2 は無視) 3. 𝑘を固定して、選べる中でdpの値が最大の𝑖を二分探索で見つける 全ての(𝑖, 𝑗)を傾き昇順でソートしてもいい 二分探じゃなくてセグ木でもいい (PythonのTLがかなり厳しい。(作問側未AC) 伸ばすと枝狩り3乗が通ってしまい…。ごめん) 2025/03/15 OUPC2024 Day 1 42
  21. 問題概要 「已己巳己」文字列を以下で定義 • 長さ1の文字列 • 長さの等しい相異なる「已己巳己」文字列𝑆1 , 𝑆2 , 𝑆3

    を 𝑆1 , 𝑆2 , 𝑆3 , 𝑆2 の順につなげた文字列 ex1. 𝑆 = "ABCB" ex2. 𝑆 = "ABCBBCACCABABCAC“ A,B,C,?からなる長さ4𝐾の文字列𝑆の?をA,B,Cに置き換えて得られる文字列 のうち「已己巳己」文字列はいくつ? 998244353で割った余りを出力 • 1 ≤ 𝐾 ≤ 8 2025/03/15 OUPC2024 Day 1 45
  22. 解法 𝑆を等しい長さで4つに区切って𝑆1 , 𝑆2 , 𝑆3 , 𝑆4 とする •

    𝑓(𝑆, 𝑇) 𝑆𝑖 ≠ 𝑇𝑖 のとき 片方?ならもう片方に揃える 違えば空文字を返す関数 𝑆2 = 𝑓 𝑆2 , 𝑆4 として、𝑆1 , 𝑆2 , 𝑆3 の3つで考える 𝑆1 , 𝑆2 , 𝑆3 がすべて「已己巳己」文字列かつ相異なってほしい 2025/03/15 OUPC2024 Day 1 46 string ret(len, '_’); for(int i = 0; i < len; i++) { if(S[i] == '?') ret[i] = T[i]; else if(T[i] == '?') ret[i] = S[i]; else if(S[i] == T[i]) ret[i] = S[i]; else return ""; } return ret; ex. 𝑓(A?B?,?C??) = ACB? 𝑓(A?B?,?CC?) = ""
  23. 解法 包除で数え上げ • 𝑔 𝑆 : 𝑆に対する答えを求める関数 • 𝑔 𝑆1

    , 𝑔 𝑆2 , 𝑔 𝑆3 , 𝑔 𝑓 𝑆1 , 𝑆2 , 𝑔 𝑓 𝑆1 , 𝑆3 , 𝑔 𝑓 𝑆2 , 𝑆3 , 𝑔 𝑓 𝑓 𝑆1 , 𝑆2 , 𝑆3 の7つが分かればよくてこれは再帰で求まる • 𝑂(7𝐾) (最初𝐾 ≤ 9にしてて遅い言語にだけメモ化を要求しそうだったので8になった) 2025/03/15 OUPC2024 Day 1 47 𝑔 𝑆 = 全体 − 𝑆1 = 𝑆2 ≠ 𝑆3 のとき − 𝑆1 = 𝑆3 ≠ 𝑆2 − 𝑆2 = 𝑆3 ≠ 𝑆1 − 𝑆1 = 𝑆2 = 𝑆3 = 𝑔 𝑆1 𝑔 𝑆2 𝑔 𝑆3 − 𝑔 𝑓 𝑆1 , 𝑆2 𝑔 𝑆3 − 𝑔 𝑓 𝑓 𝑆1 , 𝑆2 , 𝑆3 − ቀ ቁ 𝑔 𝑓 𝑆1 , 𝑆3 𝑔 𝑆2 − 𝑔 𝑓 𝑓 𝑆1 , 𝑆2 , 𝑆3 − 𝑔 𝑓 𝑆2 , 𝑆3 𝑔 𝑆1 − 𝑔 𝑓 𝑓 𝑆1 , 𝑆2 , 𝑆3 − 𝑔 𝑓 𝑓 𝑆1 , 𝑆2 , 𝑆3 = 𝑔 𝑆1 𝑔 𝑆2 𝑔 𝑆3 − 𝑔 𝑓 𝑆1 , 𝑆2 𝑔 𝑆3 − 𝑔 𝑓 𝑆1 , 𝑆3 𝑔 𝑆2 − 𝑔 𝑓 𝑆2 , 𝑆3 𝑔 𝑆1 + 2𝑔 𝑓 𝑓 𝑆1 , 𝑆2 , 𝑆3
  24. 問題概要・制約 正整数列 X = (X[1], X[2], …, X[Q]) が与えられる 条件を満たすようなグラフと正整数列

    K = (K[1], K[2], …, K[Q]) を見つけよ • 頂点 1 が始点の長さ K[q] のパスの個数を P で割ったあまりは X[q] • 頂点 I (2 <= I <= N) が始点の長さ K[q] のパスの個数を P で割ったあまりは X[q] でない • K は狭義単調増加 • 頂点数は 30 以下 • グラフは単純連結無向グラフ • Q: 小さい • X[i]: 正整数 • P = 998244353 2025/03/15 OUPC2024 Day 1 49
  25. 解法 簡単なグラフから考えてみる 例: 完全グラフ • 頂点 i を始点とする長さ k のパスの個数は

    (𝑁 − 1)𝑘 → 条件 1, 2 を両立できない • (𝑁 − 1)𝑥≡ 𝑁 − 1 𝑥+ 𝑃−1 (mod 𝑃) → 条件 3 は容易に達成可能 2025/03/15 OUPC2024 Day 1 50
  26. 解法 簡単なグラフから考えてみる 例: スターグラフ(ウニグラフ) • 頂点 1 を始点とする長さ k のパスの個数は

    (𝑁 − 1)ceil 𝑘 2 • 頂点 i (≠ 1)を始点とする長さ k のパスの個数は (𝑁 − 1)floor 𝑘 2 → k を奇数にすれば条件 1, 2を両立できる • (𝑁 − 1)𝑥≡ 𝑁 − 1 𝑥+ 𝑃−1 (mod 𝑃) → 条件 3 は容易に達成可能 2025/03/15 OUPC2024 Day 1 51
  27. 解法 グラフ: N-1 を mod998244353 上の原始根としたスターグラフ 正整数列 K: (𝑁 −

    1)𝑘≡ 𝑋 𝑞 (mod 𝑃) を満たすようにする • BabyStep GiantStep 法を用いればよい 2025/03/15 OUPC2024 Day 1 52
  28. 問題概要 正整数列 A がある 総積が M 以下となるような正整数列 B を考える 𝐴𝑖

    𝐵𝑖 ≤ 𝐴𝑖+1 𝐵𝑖+1 となる i の個数を最大化してください • A の各要素を何倍かして、なるべく小さい順にしたい M が複数与えられるので、それぞれについて求める • N: 10^5 • M の個数: 3*10^5 • A[i], M: 10^12 2025/03/15 OUPC2024 Day 1 54
  29. 解法 素直な dp を考える • dp[i][j][k] := • i 番目の要素までで、

    • 𝐴𝑥 𝐵𝑥 ≤ 𝐴𝑥+1 𝐵𝑥+1 となる i 未満の x の個数が j 個で、 • 𝐴𝑥 𝐵𝑥 = 𝑘であるような • prod(B) の最小値 • O(N^2 M) 時間でできました 2025/03/15 OUPC2024 Day 1 55
  30. 解法 ポイント: 240 > 1012 • 𝐵𝑥 ≥ 2 となるのは

    40 個未満 • 𝐴𝑥 > 𝐴𝑥+1 かつ 𝐴𝑥 𝐵𝑥 ≤ 𝐴𝑥+1 𝐵𝑥+1 となる x は高々 40 個 • 大小順が正される場所 → 考慮すべき j の個数は 40 個程度 • O(NM logM) 時間でできました 2025/03/15 OUPC2024 Day 1 56
  31. 問題概要・制約 • 正の整数 𝑥, 𝑦 について、𝑓 𝑥, 𝑦 を、 「

    𝑥 𝑦 を循環小数で表したときの循環節の長さ」と定義 • 1 8 = 0.1250000 … だから 𝑓 1,8 = 1 • 26 22 = 1.18181818 … だから 𝑓 26,22 = 2 • σ𝑥=𝐴 𝐵 σ𝑦=𝐶 𝐷 𝑓 𝑥, 𝑦 を求めよ • 1 ≤ 𝐴 ≤ 𝐵 ≤ 109 • 1 ≤ 𝐶 ≤ 𝐷 ≤ 109 • 0 ≤ 𝐷 − 𝐶 ≤ 105 2025/03/15 OUPC2024 Day 1 58
  32. 解法 • 𝑓 𝑥, 𝑦 は、𝑥 𝑦 10𝑡 − 1

    が有限小数であるような正の整数 𝑡 の最小値 • 例えば、x = 2, 𝑦 = 55 のとき、 2 55 = 0.03636363 … と 2 55 ⋅ 102 = 3.63636363 … の差を取ると 2 55 ⋅ 102 − 1 = 3.6 となって循環節が打ち消される • 有限小数 ⇔ 整数 𝑛 と非負整数 𝑝, 𝑞 を用いて 𝑛 2𝑝5𝑞 と表される 2025/03/15 OUPC2024 Day 1 59
  33. 解法 • 𝑥 𝑦 10𝑡 − 1 = 𝑛 2𝑝5𝑞

    と表される 𝑡 の最小値が知りたい • 𝑦 から素因数 2,5 を取り除き、さらに 𝑥 𝑦 を約分したものを 𝑥′ 𝑦′ とすると、 𝑥′ 𝑦′ 10𝑡 − 1 = 𝑛 • 𝑥′ と 𝑦′ は互いに素だから、10𝑡 ≡ 1 𝑚𝑜𝑑 𝑦′ となる • 𝑡 = 𝜙 𝑦′ なら明らかに満たし(オイラーの定理)、𝑡 の最小値(位数)は 𝜙 𝑦′ の約数 (ラグランジュの定理) • 𝑡 = 𝜙 𝑦′ から初めて、10𝑡 ≡ 1 を満たす限り 順に素因数で割っていけば最小値が得られる 2025/03/15 OUPC2024 Day 1 60
  34. 解法 • 𝑦 ごとに σ𝑥=𝐴 𝐵 𝑓 𝑥, 𝑦 を求める

    • 𝑦′ の候補は 𝑦 の約数で、𝑑 𝑦 個とする • 各 𝑦′ について、前述の方法で 𝑡 の最小値を計算する • A ≤ 𝑥 ≤ 𝐵 の各 𝑥 について、約分後分母が 𝑦′ になるものの個数を求めたい → 高速ゼータ変換により 𝑂 𝑑 𝑦 log 𝑦 時間で可能 2025/03/15 OUPC2024 Day 1 61
  35. 計算量解析 • 𝑁 = 𝐷 − 𝐶 とする • 𝐶

    ≤ 𝑦 ≤ 𝐷 の素因数分解→区間篩で 𝑂 𝑁 log 𝐷 時間 • 𝑦 の約数 𝑦′ それぞれについて 𝑥 を高速ゼータ変換で数え上げ→ 𝑂 𝑑 𝑦 log 𝑦 時間 𝐶 ≤ 𝑦 ≤ 𝐷 について足し合わせて 𝑂 𝑁 log 𝑁 + 𝐷 log 𝐷 時間 • 各 𝑦′ について、𝜙 𝑦′ を素因数分解 𝑦 の各素因数 𝑝 に対する 𝑝 − 1 の素因数分解を新たにできれば良い • 𝑝 ≤ 𝐷 の部分は前計算で 𝑂 𝐷 log 𝐷 時間 • 𝑝 > 𝐷 の部分は、y ⋅ 𝑝−1 𝑝 = 𝑦 − 𝑦 𝑝 > 𝐶 − 𝐷 なので、 𝐶 − 𝐷 から 𝐷 まで区間篩をかけておくことで 𝑝 − 1 の素因数分解が含まれる これは 𝑂 𝑁 + 𝐷 log 𝐷 時間 • 各 𝑦′ について位数を求める →工夫すれば 𝑂 𝑑 𝑦 log 𝑦 時間、 足し合わせて𝑂 𝑁 log 𝑁 + 𝐷 log 𝐷 時間 • 以上、合計で𝑂 𝑁 log 𝑁 + 𝐷 log 𝐷 時間 • もう少し愚直にやっても実際は十分間に合う 2025/03/15 OUPC2024 Day 1 62
  36. 問題概要・制約 Segment Tree みたいなグラフがある dist(i,j) = 頂点 i と頂点 j

    の距離 とする 数列 A に対し、変更クエリに対応しながら以下を求めてください • σ σ dist(𝐴 𝑖 , 𝐴 𝑗 ) • N, Q <= 250000 • A[i] <= 2^20 2025/03/15 OUPC2024 Day 1 64 0 1 2 3 4 5 6 7 8
  37. 解法 奇数頂点から始めたとき、1 足すか 1 引くかのどちらか 基本的には 4 の倍数のほうへ動くべき • 4k+1,

    4k+2, 4k+3 間、同じ頂点に存在する場合は例外で帳尻を合わせる 2025/03/15 OUPC2024 Day 1 67 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 同じ頂点に存在する場合
  38. 解法 奇数頂点から始めたとき、1 足すか 1 引くかのどちらか 基本的には 4 の倍数のほうへ動くべき • 4k+1,

    4k+2, 4k+3 間、同じ頂点に存在する場合は例外で帳尻を合わせる 全員偶数頂点に移動し、2で割ると元の問題に帰着 • 繰り返し行う= 全員頂点 0 にたどり着く 2025/03/15 OUPC2024 Day 1 68 0 1 2 3 4 5 6 7 8
  39. 解法 変更クエリに対応するためには以下の値を管理すればよい • σ dist(0, 𝐴 𝑖 ) • 「4k+1,

    4k+2, 4k+3 間、同じ頂点に存在する場合は例外で帳尻を合わせ る」をした値 • 𝑂 𝑁log𝐴 + 𝑄log𝐴 時間で解けた 2025/03/15 OUPC2024 Day 1 69
  40. 問題概要・制約 正整数 N, X が与えられます N 以下の正整数 n のうち、以下のいずれかを満たすものはいくつあります か?

    • n は X の倍数 • 文字列として見たとき、n は X を連続部分文字列として含む • 1 <= X <= N <= 10^18 2025/03/15 OUPC2024 Day 1 71
  41. 解法 条件 • n は X の倍数 • 文字列として見たとき、n は

    X を連続部分文字列として含む • X の倍数である n の個数 • これは floor(N/X) 個 • X を連続部分文字列として含む n の個数 • X を連続部分文字列として含んでかつ X の倍数である n の個数 2025/03/15 OUPC2024 Day 1 72
  42. 解法 • X を連続部分文字列として含む n の個数 • X を連続部分文字列として含んでかつ X

    の倍数である n の個数 • この2つを高速に求めたい 考えられる解法 • 桁 dp • X の倍数である n を列挙 • X を連続部分文字列として含む n を列挙 • 上記のいずれでもない斬新な解法 2025/03/15 OUPC2024 Day 1 73
  43. 解法 桁 dp • dp[i][j][k][f] := • 上から i 桁目までみたとき、

    • X で割ったあまりは j で、 • 末尾 k 文字が X の先頭 k 文字と一致 / すでに X を連続部分文字列として含み、 • N 未満であることが確定している (f = true/false) • n の個数 • 𝑂(10𝑋log𝑁 log𝑋 + 10log2𝑋) 時間 2025/03/15 OUPC2024 Day 1 74
  44. 解法 X を連続部分文字列として含む n を考える 例: X = 908, n

    = ??908???908? • 1. X と一致する場所を決め打つ • n = ????????????, ?????????908, ????????908?, …, 908908908908 2025/03/15 OUPC2024 Day 1 76
  45. 解法 X を連続部分文字列として含む n を考える 例: X = 908, n

    = 31908???9085 • 1. X と一致する場所を決め打つ • n = ????????????, ?????????908, ????????908?, …, 908908908908 • 2. ? のうち、最も長い箇所を残して全探索する • n = 00908???9080, 00908???9081, …, 99908???9089 2025/03/15 OUPC2024 Day 1 77
  46. 解法 X を連続部分文字列として含む n を考える 例: X = 908, n

    = 31908???9085 • 1. X と一致する場所を決め打つ • n = ????????????, ?????????908, ????????908?, …, 908908908908 • 2. ? のうち、最も長い箇所を残して全探索する • n = 00908???9080, 00908???9081, …, 99908???9089 • 3. 残った ? を変えたときに X の倍数になるものの個数を高速に求める 2025/03/15 OUPC2024 Day 1 78
  47. 解法 X を連続部分文字列として含む n を考える • 3. 残った ? を変えたときに

    X の倍数になるものの個数を高速に求める → k = 0,1,…, R のうち 10𝑑𝑘 ≡ 𝑥 (mod 𝑋) を満たすものの個数 → 10𝑑 gcd 10𝑑,𝑋 𝑘 ≡ 𝑥 gcd 10𝑑,𝑋 mod 𝑋 gcd 10𝑑,𝑋 を満たすものの個数 → 𝑘 ≡ ൗ 𝑥 gcd 10𝑑,𝑋 10𝑑 gcd 10𝑑,𝑋 mod 𝑋 gcd 10𝑑,𝑋 を満たすものの個数 → floor 𝑅+ 𝑋 gcd 10𝑑,𝑋 −10−𝑑𝑥 𝑋 gcd 10𝑑,𝑋 個 2025/03/15 OUPC2024 Day 1 79
  48. 解法 X を連続部分文字列として含む n を考える 例: X = 908, n

    = 31908???9085 • 1. X と一致する場所を決め打つ • 2. ? のうち、最も長い箇所を残して全探索する • 3. 残った ? を変えたときに X の倍数になるものの個数を高速に求める 最後に包除原理を用いてうまくまとめる • 高々 𝑂 1 + 10 log𝑁−log𝑋 + log𝑁 log𝑋 時間 2025/03/15 OUPC2024 Day 1 80
  49. 解法 • 桁dp 解法: 𝑂(10𝑋log𝑁 log𝑋 + 10log2𝑋)時間 • X

    < 10^5 なら充分高速 • 包除解法: 高々 𝑂 1 + 10 log𝑁−log𝑋 + log𝑁 log𝑋 時間 • X >= 10^4 なら充分高速 • 2つの解法を組み合わせればよい 2025/03/15 OUPC2024 Day 1 81
  50. 問題概要 整数 T,N および数列 𝐴 = (𝐴1 , … ,

    𝐴1000 ) がある • 1 <= T < N <= 1000 • 𝐴𝑖 = min 𝑖 − 1, 𝑁 − 1 mod 𝑇 • 𝐴1 < ⋯ < 𝐴𝑇 • 最初 T 項は狭義単調増加 • T < i <= N について、 𝐴𝑖 = 𝐴𝑖−𝑇 • 次の N-T 項は、最初の T 項が繰り返される • N < i <= 1000 について、 𝐴𝑖 = 𝐴𝑖−1 • 以降は一定 2025/03/15 OUPC2024 Day 1 89
  51. 問題概要 整数 T,N および数列 𝐴 = (𝐴1 , … ,

    𝐴1000 ) がある • 1 <= T < N <= 1000 • 𝐴𝑖 = min 𝑖 − 1, 𝑁 − 1 mod T 質問を 15 回まで行い、T を当ててください • 組 (x, y) (x<y) について、 𝐴𝑥 ≤ 𝐴𝑦 の真偽を聞く 2025/03/15 OUPC2024 Day 1 90
  52. 解法 • Step1. 𝐴𝑥 > 𝐴𝑦 となる (x, y) を得る

    • Step2. 𝐴𝑥 > 𝐴𝑥+1 となる x を得る • Step3. T を得る( 𝐴𝑥 > 𝐴𝑥+1 となる最小の x を得る) • 15 回の質問をどう割り振る? 2025/03/15 OUPC2024 Day 1 91
  53. 解法 Step1. 𝐴𝑥 > 𝐴𝑦 となる (x, y) を得る ポイント:

    𝑥 ≤ 𝑇 < 𝑦 < 2𝑥 なら𝐴𝑥 > 𝐴𝑦 • 1 ≤ 𝑦 − 𝑇 < 2𝑥 − 𝑇 ≤ 𝑥 ≤ 𝑇 より 𝐴𝑦 ≤ 𝑦 − 𝑇 − 1 < 𝑥 − 1 = 𝐴𝑥 2025/03/15 OUPC2024 Day 1 92
  54. 解法 Step1. 𝐴𝑥 > 𝐴𝑦 となる (x, y) を得る ポイント:

    𝑥 ≤ 𝑇 < 𝑦 < 2𝑥 なら𝐴𝑥 > 𝐴𝑦 • 1 ≤ 𝑦 − 𝑇 < 2𝑥 − 𝑇 ≤ 𝑥 ≤ 𝑇 より 𝐴𝑦 ≤ 𝑦 − 𝑇 − 1 < 𝑥 − 1 = 𝐴𝑥 𝑥, 𝑦 = 2𝑘 + 1, 2𝑘+1 + 1 とすると、𝐴𝑥 > 𝐴𝑦 となる (x, y) が得られる • すべて 𝐴𝑥 ≤ 𝐴𝑦 なら 𝑇 = 1 • 質問回数: 10 回 2025/03/15 OUPC2024 Day 1 93
  55. 解法 Step2. 𝐴𝑥 > 𝐴𝑥+1 となる x を得る 𝐴𝑥 >

    𝐴𝑦 となる (x, y) が 1 つ分かっているので二分探索する • 質問回数: 9 回 2025/03/15 OUPC2024 Day 1 94
  56. 解法 Step3. T を得る( 𝐴𝑥 > 𝐴𝑥+1 となる最小の x を得る)

    𝐴𝑥 > 𝐴𝑥+1 となる x が1つ分かっている ポイント: x の約数の一つが T である • x を素因数分解し、各指数を二分探索すればよい • 質問回数: 6 回 • 720 = 243251, 900 = 233353 が最大ケース 2025/03/15 OUPC2024 Day 1 95
  57. 解法 • Step1. 𝐴𝑥 > 𝐴𝑦 となる (x, y) を得る

    • 質問回数: 10 回 • Step2. 𝐴𝑥 > 𝐴𝑥+1 となる x を得る • 質問回数: 9 回 • Step3. T を得る( 𝐴𝑥 > 𝐴𝑥+1 となる最小の x を得る) • 質問回数: 6 回 • 25 回の質問で T を特定できた • 質問は 15 回しか行うことができず WA になってしまいました 2025/03/15 OUPC2024 Day 1 96
  58. 解法 Step1. 𝐴𝑥 > 𝐴𝑦 となる (x, y) を得る 𝑥,

    𝑦 = 2𝑘 + 1, 2𝑘+1 + 1 とすると、𝐴𝑥 > 𝐴𝑦 となる (x, y) が得られる • 𝑘 = 9,8, … , 0 の順に聞き、𝐴𝑥 > 𝐴𝑦 が返ってきた時点で Step2 へ Step2. 𝐴𝑥 > 𝐴𝑥+1 となる x を得る 𝐴𝑥 > 𝐴𝑦 となる (x, y) が 1 つ分かっているので二分探索する • 質問回数: 合計 10 回 2025/03/15 OUPC2024 Day 1 97
  59. 解法 Step3. T を得る( 𝐴𝑥 > 𝐴𝑥+1 となる最小の x を得る)

    𝐴𝑥 > 𝐴𝑥+1 となる x が1つ分かっている ポイント: x の約数の一つが T である • x を素因数分解し、各指数を二分探索すればよい • 質問回数: 6 回 • 720 = 243251, 900 = 233353 が最大ケース 2025/03/15 OUPC2024 Day 1 98
  60. 解法 Step3. T を得る( 𝐴𝑥 > 𝐴𝑥+1 となる最小の x を得る)

    𝐴𝑥 > 𝐴𝑥+1 となる x が1つ分かっている ポイント: x の約数の一つが T である • x を素因数分解し、各指数を二分探索すればよい • 質問回数: 5 回 • 720 = 243251, 900 = 233353 は頑張って縮める • 枝刈り・メモ化を駆使して見つける(手作業で発見するのは厳しいです) 2025/03/15 OUPC2024 Day 1 99
  61. 解法 • Step1. 𝐴𝑥 > 𝐴𝑦 となる (x, y) を得る

    • Step2. 𝐴𝑥 > 𝐴𝑥+1 となる x を得る • 質問回数: 10 回 • Step3. T を得る( 𝐴𝑥 > 𝐴𝑥+1 となる最小の x を得る) • 質問回数: 5 回 • ちょうど 15 回の質問で T を特定できた 2025/03/15 OUPC2024 Day 1 100
  62. 問題概要・制約 • 𝑁 種類のアルファベットからなるデータを 01文字列に変換するルールを構築する • ルールは 𝑇 個の01文字列で表現され、アルファベット 𝑖

    は 01文字列 𝑇𝑖 に変換される • データを変換するときは各アルファベットを01文字列に変換し、 それを連結する • データから01文字列への変換は単射でなければならない • アルファベットの出現頻度 𝐴1 , 𝐴2 , … , 𝐴𝑁 が与えられる • σ𝑖 𝐴𝑖 𝑇𝑖 の最小値を出力してください • ただし、𝑻𝟏 だけは入力 𝑺 で固定されている • 𝑁 ≤ 500000 2025/03/15 OUPC2024 Day 1 102
  63. 解法 • 𝑇1 が決まっていなければ? →ただの最適2元符号化の問題 →ハフマン符号を構築すれば終わり • 𝐴1 , …

    , 𝐴𝑛 を優先度付きキューに入れ、以下を繰り返して1つにマージ • 小さい値2つをPopし、値を足し合わせてPush • マージ過程を木とみなすと最適な語頭符号が完成 • 例: 𝐴1 , 𝐴2 , 𝐴3 , 𝐴4 = 3,1,4,1 → 01,000,1,001 2025/03/15 OUPC2024 Day 1 103 9 𝑎3 5 2 𝑎1 𝑎4 𝑎2 0 0 0 1 1 1
  64. 解法 • 𝑇1 = 𝑆 で固定されているなら? • σ𝑖 𝐴𝑖 𝑇𝑖

    の 𝐴1 𝑇1 の項は固定されているから考えても無駄 • 𝐴1 の値を変数 𝑥 として自由に書き換えてみる • 出現頻度を 𝑥, 𝐴2 , … , 𝐴𝑛 としてハフマン符号を構築したときの、 𝑇1 の最小値を 𝑦1 𝑥 、最大値を 𝑦2 𝑥 とする(広義単調減少) • 重要な事実: 𝑦2 𝑥 = 𝑦1 𝑥 + 1 (ハフマン木構築時のタイブレークを考えると 示せる) • 𝑦2 0 ≤ 𝑆 のとき → 𝑥 = 0 のときのハフマン符号で、 𝑇1 だけを長さ 𝑆 まで冗長化するのが最適 • 𝑦2 0 ≥ 𝑆 のとき、𝑦1 𝑥 ≤ 𝑆 ≤ 𝑦2 𝑥 となる 𝑥 が存在 →二分探索可能! • 計算量は 𝑂 𝑁 log 𝑁 log 𝑁 + log max 𝑖 𝐴𝑖 2025/03/15 OUPC2024 Day 1 104