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

第6回ゆるふわオンサイト解説

forcia_dev_pr
February 10, 2024
170

 第6回ゆるふわオンサイト解説

forcia_dev_pr

February 10, 2024
Tweet

Transcript

  1. 目次 2 • A - Gachi Onsite • B -

    Yurufuwa Teaming • C - 153 • D - Bbubel oSrt • E - Parenthesis Candidate • F - n!+(n+1)!+(n+2)! • G - Koiwai Coffee • 各問題FA・AC数 • writer/tester
  2. A - Gachi Onsite 問題概要 与えられる長さ N の文字列 S に含まれる

    gachi の部分を、すべて yurufuwa に 置換してください。 例 gachionsite → yurufuwaonsite gachigachionsite → yurufuwayurufuwaonsite 3
  3. B - Yurufuwa Teaming 例 N=3, A={3,2,1} 7 問題1希望! 問題2希望!

    問題3希望! 問題1 問題2 問題3 チーム1 チーム2 5人希望がかなう!
  4. C - 153 問題概要 1, 2, …, 9 からなる文字列の l_k

    文字目から r_k 文字目までを抜き出した数は 「十進法で表した各桁の三乗和をとる」という操作を何回繰り返せば 153 にで きるか? 例 9 24 → 2^3 + 4^3 = 72 → 7^3 + 2^3 = 351 → 3^3 + 5^3 + 1^3 = 153 3回! 2 → 2^3 = 8 → 8^3 = 512 → 5^3 + 1^3 + 2^3 = 134 →… 153に到達しない!
  5. C - 153 解法 • 2回の操作後、M は 10000 未満になる ◦

    1回の操作後、M は高々 9^3 * N ≦ 1.0935 * 10^8 になる ◦ よって2回操作すれば、M は高々 9^3 * 8 = 5832 < 10000 になる • 10000 未満の数を操作をしても 10000 以上になることはない ◦ 9^3 * 4 = 2916 < 10000 であるため 以上より、10000 未満の正の整数について調査すればよいが 実験すると高々13回で循環し始めることが分かる。 11
  6. C - 153 解法 • 部分点解法 ◦ 循環するまで愚直にシミュレーションし続ければ良い ▪ 循環し始めたとき、M

    が 153 でなければ永遠に 153 には辿り着かない • 153 は操作を加えても 153 であることに注意 ▪ 逆に M が 153 になっているときは、それまでの step 数を答えればよい • 満点解法 ◦ 愚直にやると1回目の操作に O(N) かかってしまい TLE になる ◦ 予め O(N) かけて三乗和の累積和を求めておくことで、1回目の操作を O(1) で行えるように なる ◦ 残りは部分点解法に同じ 12
  7. C - 153 補足 • 任意の正の3の倍数は、操作を有限回繰り返すと 153 に行きつきます! ◦ 10000

    以上の場合は操作後に M が減少することと、10000 未満の数が 153 に行きつくこ とから示せます • また、3の倍数以外は決して 153 には辿り着きません ◦ 操作前後で 3 で割った余りが不変であることから示せます ▪ 10^i * a ≡ a ≡ a^3 (mod 3) から分かります • 10000 未満の結果を下計算しておくと、より早く実行できます ◦ この下計算をせずとも、多くの言語で AC できる想定です 13
  8. D - Bbubel oSrt 問題概要 A[i] > A[i+1] なところを swap

    できる A を B にできるか? A = (9, 4, 3, 1, 5, 1, 2) ↓ B = (3, 1, 4, 1, 5, 9, 2) 14
  9. D - Bbubel oSrt 解法 B の先頭から順に、A から持ってくることができるか?を順次判定していく A =

    (9, 4, 3, 1, 5, 1, 2) A = (9, 4, 1, 3, 5, 1, 2) 1 を越えることができない B = (3, 1, 4, 1, 5, 9, 2) B = (3, 1, 4, 1, 5, 9, 2) 単純にシミュレーションすると O(N²) (TLE) 15
  10. D - Bbubel oSrt 解法(部分点) 1, 2, 3 が出てくる最初の index

    I[1], I[2], I[3] を管理する。 B を前から見て行って、2 を置きたい場合は • I[1] < I[2] なら無理 • そうでないなら、2を置けて、I[2] を次に2が出てくるindexに更新 のような操作を繰り返せばいい。 O(N) 17
  11. D - Bbubel oSrt 解法(満点) 部分点の操作のうち、判定の部分はそのままやると O(値の種類数)かかるが セグメントツリー(1点更新、区間 max)で高速に判定可能 O(N

    logN) (セグメントツリーを使う判定方法なら、A そのものをセグメントツリーに載せて も解くことができるはず) 18
  12. E - Parenthesis Candidate 問題概要 ( と * からなる文字列が与えられる。* を

    ( or ) にいい感じに変更して、正規 な括弧列になるものを「括弧列の候補」という。 連続部分文字列で括弧列の候補となるものを数えよ 19 (***(* ( ( ) ) ( )
  13. E - Parenthesis Candidate アルゴリズム 22 ・長さが2以上の偶数 ・(を1,*を-1に置き換えて累積和を取ったときに、末尾が最小になる 数列Aの各index iに対して、j<iで、A[i]未満となる最大のjを求められれば良い。

    の2条件を満たす部分文字列の数え上げをする。 [l,r) が条件を満たす ⇔ r - lが偶数かつ、累積和の配列で、lからrの中でrのとこで最小値 ⇒ stackなどを使って O(N) 詳細なアルゴリズムは 蟻本第2版 4-4 最大長方形のアルゴリズムなどを見よう!
  14. F - n!+(n+1)!+(n+2)! 問題概要 非負整数 N, A が与えられます。次の式を満たす整数 の個数を 998244353

    で割った余りを求めてください。(T ケース) 制約 • 1 ≦ T ≦ 20 • 0 ≦ N ≦ 10^8 • 0 ≦ A ≦ 10^5 23
  15. F - n!+(n+1)!+(n+2)! Step3: 計算量がNに比例しないようにする ここで第一項に注目し、非負整数 i に対して とおくと が成立する。(フィボナッチ数列)

    ゆえに第一項の値 は O(log(N + A)) の計算量で求められる。 一方第二項は O(A) で求められるため、最終的に O(log(N) + A) で求められた。 29
  16. G - Koiwai Coffee 問題概要 32 コ イワ イ コ

    ー ヒ ー コ * ワ イ * ー * * これ何通り?
  17. G - Koiwai Coffee 重要な性質 34 ・ある文字列が周期的かつ、回文 + 回文の形で書けるとき、その 文字列の1周期も、回文

    + 回文の形で書ける ・ある文字列が周期的かつ、回文 + 回文の形で書けるとき、0文字 以上の回文 + 1文字以上の回文に分ける分け方は、文字列の最大の 周期数に等しい。特に最大周期1なら分け方は一意 ABABABAB ABABABAB ABABABAB ABABABAB ABABABABの1周期 (AB) は回文 + 回文と書ける 周期4だが、分け方は4通り
  18. G - Koiwai Coffee 解法 (全て-1のケース) 35 Nの約数dに対して、長さdで周期的でない文字列で、回文 + 回文と表せ

    るものを数える。区切り方を全探索すればよい。(分け方が一意なので) ま たそれを、N/d倍したものが長さNのものに対応。(この対応関係は実は一 意) 約数包除をすることで、上手く周期的でないものを数える (周期的なのも のを取り除くイメージ) ・ABABABABを数えるときには、代わりに1周期分のABを数える。 ・長さ4の周期的でないものを数えるときに、ABABとかは数えたく ないが、長さ2の周期的でないものを引けばよい。 N=8, K=2のとき (1をA,2をBにエンコード)
  19. G - Koiwai Coffee 解法 (-1以外も含む) 36 本質的にやることは同じ ・Nの約数dに対して、長さdで周期的でないもので、回文 +

    回文と書けるものを数え て約数包除 一方で、長さdから長さNが必ず復元できるとは限らない ・A*AB*Bが入力されたときに、長さ3の文字列を2つつなげた文字列は元の 数列と絶対に一緒にならない (元の数列が周期的ではないため) 長さdのものが回文 + 回文でかけないケースもある ・ABCA*Cが入力されたときに、長さ3の数列 (ABC) は回文 + 回文の形で書 けない。
  20. G - Koiwai Coffee 解法 (-1以外も含む) 37 ・文字列の前d文字をN/d個つなげたものが、周期的になるように、長さd の文字列を構成する。(確定する部分とwild cardな部分が出るはず)

    ・この文字列に対して、(区切り方,回文 + 回文となる文字列) の組は何通 りか?を数えて約数包除をする 2番目の操作はwild card matchingなどのたたみこみで行える Nの約数dに対して、長さdの列のたたみこみを行うので、 全体の計算量はO((Nの約数の総和)logN)になる。
  21. 各問題のFA・AC数 38 問題 オンサイトFA オンラインFA AC数 A - Gachi Onsite

    seekworser 51 B - Yurufuwa Teaming seekworser 50 C - 153 chaemon m_99 31 D - Bbubel oSrt PCT 15 E - Parenthesis Candidate toam m_99 5 F - n!+(n+1)!+(n+2)! potato167 1 G - Koiwai Coffee 0 ※オンラインFAはオンサイトより速かった場合のみ表記しております。
  22. 39 問題 writer tester A - Gachi Onsite momohara prd_xxx

    B - Yurufuwa Teaming momohara Talfall C - 153 ayaoni prd_xxx D - Bbubel oSrt tempura0224 E - Parenthesis Candidate momohara F - n!+(n+1)!+(n+2)! ayaoni Talfall G - Koiwai Coffee tempura0224 writer/tester