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

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

forcia_dev_pr
October 10, 2024
130

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

forcia_dev_pr

October 10, 2024
Tweet

Transcript

  1. 第7回ゆるふわオンサイト 
 解説スライド 
 1
 運営メンバー: dokin, Talfall, ayaoni, prd_xxx,

    momohara, siro53, ochiaigawa(他協力4名) Special Thanks: tempura0224, kiyoshi0205, kichi2004
  2. 目次
 2 • A - Subsidy
 • B - Group

    Moving
 • C - Proper Fraction Operation
 • D - Taking Sandwitches
 • E - Adjust
 • F - A Beautiful Company
 • G - Dot Product Query
 • H - EQual
 • I - FORCIAN WAY
 • 各問題FA・AC数
 • writer/tester

  3. A - Subsidy
 問題概要
 レストランで税込 A 円分の食事をした。
 キャンペーンで税抜き B 円以下の食事がタダになる。

    
 あなたは何円支払ったか?
 ただし消費税は 10 %とし、小数点以下は切り捨てて計算する。 
 制約
 • 1 ≦ A, B ≦ 10^4
 • A は 11 の倍数
 • B は 10 の倍数
 
 3
  4. A - Subsidy
 解法
 • A ≦ B * 1.1

    の時 
 ◦ 答えは 0 円
 • A > B * 1.1 の時 
 ◦ 答えは A 円
 不等式の両辺を 10 倍すると、全て整数で判定できます。 
 A 円の方を1.1で割って判定してもよいです。 
 
 4
  5. A - Subsidy
 余談
 出典:財務省「総額表示に関する主な質問」 
 「税抜価格」に上乗せする消費税相当額に1円未満の端数が生じる場合がありますが、その端数を どのように処理 (切捨て、切上げ、四捨五入など)して「税込価格」を設定するかは、それぞれの事業 者のご判断によることとなります。

    
 • 税込み価格の計算方法を問題文に明記しないと曖昧になってしまう 
 • テストケースも油断すると税込み価格としてあり得ない金額が生まれる(A=10など) 
 ◦ Aが 11 の倍数、Bが 10 の倍数という制約を課しているのはそのため 
 → 税金関連の問題を作る時は要注意...? 
 
 5
  6. B - Group Moving
 指示通り愚直に全てのゴリラを動かすとO(MQ) でTLEする。
 解法
 • Q回の移動で、色ごとにどれだけ移動すべきかの累計距離をx軸、y軸ともに計算す る


    ◦ C++ではstd::map, Pythonではdict 等、辞書型を用いる 
 • 上記の結果をM頭のゴリラに適用する
 • N*N のマス目におさめるのに注意
 ◦ 1引いて、累計移動距離を足して、Nで割ったあまりをとって、1を足す必要がある 
 • 以上の実装で O(Q+M) や O(QlogM + M) などで間に合う
 7
  7. C - Proper Fraction Operation
 問題概要
 正の整数 A,B,K,N が与えられる。有理数 A/B

    に対し、次の操作をN回行った結果を既 約分数 C/Dで答えよ。 操作:X←KX (KX<1 のとき) … (K倍)    X←1/(KX) (それ以外) … (K倍して分子分母を反転) 例
 A=1, B=7, K=3, N=2 のとき
 
 8 3/7
 1/7
 7/9
 操作 操作
  8. C - Proper Fraction Operation
 考察
 Nがとてもでかい(<=10^18) ので、法則を見つけたい →実験しよう !!
 K=2のとき


    
 
 K=1のとき
                         →ループしている !!
 9 1/10
 1/5
 2/5
 4/5
 5/8
 1/10
 K倍して分子分母を反転 K倍して分子分母を反転 ずっと1倍
  9. C - Proper Fraction Operation
 性質
 • K=1であるか、(K倍して分子分母を反転) の操作を行ったらループする ◦

    K=1 のとき周期1, それ以外のとき周期 2 • 本問題の制約では4回以内にループに入ることが示せる
 解法
 • K=1 のとき
 ◦ 周期1なのでそのまま出力... しちゃだめ! 約分しましょう 
 • それ以外のとき
 ◦ 回数を充足するか (K倍して分子分母を反転 ) の操作を行うまでは愚直に行い、残り回数が奇数の 場合に追加でもう1回操作しましょう 
 ◦ 操作しすぎに注意
 • 約分
 ◦ C/D を約分するには gcd(C,D) で分子分母をそれぞれ割りましょう 
 ◦ Python の方は fractions.Fraction を使うのが便利です 
 10
  10. D - Taking Sandwitches
 問題概要
 長さNの数列Aが与えられる。A_l = A_r (l <

    r) となるl,r を選び、A_l ,..., A_r を削除する 操作を好きなだけできる。数列Aの長さの最小値を求めよ。
 例
 
 
 11 1 2 1 1 2 2 2 2 l=1, r=2 l=1, r=4 削除 削除 長さ「0」
  11. D - Taking Sandwitches
 部分点 (A_i <= 2) 解法 


    • N <= 2 の場合を処理しておく
 ◦ A = [1] のとき答えは1 
 ◦ A = [1,1], [2,2] のとき答えは0 
 ◦ A = [1,2], [2,1] のとき答えは2 
 • 上記以外の場合は必ず答えが0か1となる
 ◦ 両端が一致している場合、答えは0 
 ◦ 両端が異なる場合、先頭を1と仮定すると [ 1, ?, ?,..., ?, 2] のようになっていて、A_i = 1 かつ A_{i+1} = 2 となる箇所は必ず存在する 
 ▪ [?, ?,..., ?] のどこかに [1,2] が存在するなら [ 1,?,...,?,1,2,?,...,?,2] のように操作できて答えは0 
 ▪ それ以外は [1,?,?,...,?,1,2] か [1,2,?,?,...,?,2] のどちらかの操作ができ答えは1 
 12
  12. D - Taking Sandwitches
 満点解法
 • 以下のDPで解ける
 • dp[i] :=

    先頭からA_i までみたときの数列の長さの最小値
 ◦ dp[N] が答え
 13 1 2 3 2 4 3 1 4 5 1 2 5 0 1 2 3 1 2 2 0 1 2 0 1 1 dp A • ただし、A_i をみてるとき、A_i = A_j (j < i) となる j を全てみるのはTLEする 
 • 別途、処理したA_i の値ごとにdp[i] の最小値を持っておけば回避できる 
 • 計算量 O(N)

  13. E - Adjust
 問題概要
 
 例
 
 14 N以下の場所と、N +

    1以上の場所が指定されているような長さ2Nの順列全てにつ いて転倒数の和を求めよ
 S=0101 のとき、ありえる順列は1番目と3番目が1 or 2, 2番目と4番目は 3 or 4
 あり得る順列は (1,3,2,4), (2,3,1,4), (1,4,2,3), (2,4,1,3) の4通り

  14. E - Adjust
 解法
 15 求めるべき値は Σ{P∈あり得る順列全体の集合}Σ{i<j} f(i,j)
 (f(i,j) はP_i>P_j なら1でそうでないなら0)


    Σの順番を入れ替えると、(いわゆる期待値の線形性/主客転倒) 
 
 Σ{i<j} Σ{P∈あり得る順列全体の集合} f(i,j)
 
 を計算する問題になり、これは、
 「ありえる順列のうち、P_i > P_j となる順列はいくつか?」という問題になる。

  15. E - Adjust
 解法
 16 S_i = S_j なら、N!*N!/2通り (P_i

    > P_j になるケースとそうでないケースがちょうど半 分ずつある。swapすれば1対1の対応が作れる) 
 S_i = 1, S_j = 0なら、N!*N!通り (問題文の制約より絶対にP_i > P_j)
 S_i = S_j となる (i,j)、 S_i = 1,S_j = 0となる (i,j)の個数が分かればよく、O(N)で解 ける。

  16. F - A Beautiful Company
 問題概要
 順列Pに対して与えられる順列Qと位置と数字共に共通する数の分だけ幸福度がもらえ る、順列を変化させるのに気合を消費する。このとき消費する気合ポイントは元の順列を $R$ 、

    変更後の順列を $R’$ としたとき、組 $(i, j)$ であって $pos(R,i) < pos(R,j) $ かつ $pos(R’,i) > pos(R’,j)$ となる組の数に等しい これをT回繰り返す。 (幸福度)- (消費した気合)を最大化せよ  例
 P:(1, 2, 3) 
 Q:(2, 3, 1) 
 17 P を (2, 3, 1) にするのが最適 

  17. F - A Beautiful Company
 解法
 18 123
 213
 312


    132
 231
 321
 愚直にdpなどを実装するとΘ(N(N!)^2T) くらい の計算量となり間に合わない。順列間の数が (N!)^2 と大きいので 
 コストの性質に注目する。
 1
 1
 1
 1
 1
 3
 3
 3
 1
 2
 2
 2
 2

  18. 解法
 組 (i, j) であってpos(R, i) < pos(R, j) かつ

    pos(R’, i) > pos(R’, j) となる組の数に等しい ※ 順列P = (P_1, P_2, … , P_N)に対して、pos(P, i) を「P_ j = i を満たす j 」と定義する →明らかに言い換えてほしそうな顔をしている。 これは、 隣接する2要素の位置を入れ替える操作を繰り返して P1をP2に一致させるための操作回数 (の最小値) に等しい F - A Beautiful Company
 19
  19. F - A Beautiful Company
 解法
 20 123
 132
 321


    123, 132, 321 の3つに注目すると
 123 → 321 への辺(遷移)は
 123 → 132 → 321 としても損しないことが分かる。
 なので
 123 → 321 への辺は必要ない!
 
 一般化すると隣接 swap 以外の辺は必要ない !!
 (転倒数はバブルソートにおける swap の回数と等しい ことから証明できる)
 3
 2
 1

  20. F - A Beautiful Company
 解法
 21 123
 213
 312


    132
 231
 321
 これを実装するとΘ(N(N!)T)となり間に合う。
 1
 1
 1
 1
 1
 1

  21. F - A Beautiful Company
 解法
 22 実装上の注意
 • 最短経路問題として実装するとやりやすい


    • 負辺が登場するが通る回数が同じなので下駄をはかせるとよい
 • dijkstra で実行時間が厳しい場合はバケットソートに置き換えるとよい、距離の 上限が低いことから高速化できる
 1日目
 2日目
 3日目
 ここのコストは - (順列Qと位置と数字 共に共通する数) となる

  22. F - A Beautiful Company
 ごめんなさい!!!!!! 
 本問題ではコンテスト中、問題文が誤っておりました。2024/10/10現在は修正されています。
 修正前の問題文では、気合ポイントの定義が「(順序付きの組) (i,

    j) (1≦i,j≦N) であって、R_i<R_j かつ R’_i>R’_j となる組の数」と なっておりました。(問題文を清書する過程で、気合ポイントの定義が変わってしまっていたことに気づきませんでした。)
 このため、コンテスト中に「サンプル2がどうしても9になる」という方が多数おられましたが、修正前の問題文ですとサンプル2は9にな るのが正しいです。
 ご迷惑おかけいたしました。
 
 23
  23. G - Dot Product Query
 問題概要
 長さNの数列A, B が与えられる。Cがクエリとして与えられるので、A・B’ =

    C となるよう Bの要素を変化させる。変化させる要素の個数の最小値は? 
 
 
 24
  24. G - Dot Product Query
 解法
 1. 初期値のA・B = S

    とすると、Aからいくつかの要素を選んで、それらの最大公約数 が|S - C| の約数になる時、A・B’ = C にできる。 2. 約数d を初めて得られるのは何回目か?は、gcd_convolution を用いて得られる。 3. 選ぶ要素の個数は、高々6つである!(2*3*5*7*11*13*17 > 2*10^5) 25 例えば、(6, 10, 15) で何が作れる?
 (6, 10) -> gcd(6, 10) = 2 -> 2の倍数
 (6, 15) -> gcd(6, 15) = 3 -> 3の倍数
 (10, 15) -> gcd(10, 15) = 5 -> 5の倍数
 (6, 10, 15) -> gcd(6, 10, 15) -> 1の倍数
 2 3 5 6 ◦ ◦ 10 ◦ ◦ 15 ◦ ◦
  25. G - Dot Product Query
 解法
 4. しかし、Sは最大で10^15程度になるから、毎回約数を計算しては間に合わない。 5. S

    - 2*10^5 <= (S - Cのとりうる値)<= S - 1 に着目する。 →区間篩の要領で、調和級数の計算量で、すべてのCに対する答えを前計算でき る! 26
  26. H - EQual
 問題概要 27 オンサイトコンテストの予選は1回目のコンテストの上位X人と、2回目のコンテストで、既 に決勝進出が決まっている人を除いた 上位X人が決勝に行く。 
 「これ問題の相性ゲーだわ~~~~、コンテストの順番が逆だったら

    (1回目の順位表と 2回目の順位表逆だったら) 決勝行ってたわ~~~」という人が出た場合、公平な予選 (equalなqual) でないとする。
 公平な予選になる問題の組 (今回は順位表の組) を数えよ
 ただし、順位表の一部は確定しているものとする。
 余談
 GCJなどがこの方式を採用していた。AtCoder主催のオンサイトなどもこのケースあり

  27. H - EQual
 例: (sample3のパターン) 
 qualAの順位表が (あ,い,う,え,お,か,き,く) 
 qualBの順位表が

    (あ,き,か,お,え,う,い,く)
 (平仮名は参加者の人名を表す)とする。3人ずつ決勝に行くとする。
 qualA→ qualB qualB→qualA
 (あ,い,う,え,お,か,き,く) (あ,き,か,お,え,う,い,く)
 (あ,き,か,お,え,う,い,く) (あ,い,う,え,お,か,き,く) 28 公平ではない 

  28. 2X < N のケース
 
 解法
 公平な予選となるケースを数える。 
 誰か一人は決勝に行けていないが、決勝に行けなかった人で、(元々の) 1回目の予選で最も順位のよかった人

    に着目する。 (この人がk + 1位とする。 k + 1 > X になることに注意) 
 このときQが満たすべき必要条件を列挙する。 
 30 }
 ・・・
 ・・・
 ・・・
 決勝進出
 ↑k + 1位
 決勝進出/予選敗退
 以降では、元々の1回目の予選を予選A,2回目の予選を予選Bと表記します。
 赤と青の丸は、予選Aでの順位の良かった人から順に左から並ぶ。

  29. 2X < N のケース (必要条件1)
 
 lem1: 予選Aでk + 1位の人の予選Bの結果はX位より大きい

    
 31 }
 ・・・
 ・・・
 ・・・
 決勝進出
 ↑k + 1位
 予選BでX位より大きい 
 決勝進出/予選敗退
 prf: もしそうでないと、予選B→予選Aで実施されたら通過してしまう。

  30. 2X < N のケース (必要条件2)
 
 lem2: 予選Aでk + 1より大きい順位を取った人のうち、2X

    - k人が決勝に進出し、そ の人たちの予選Bの順位はX以下 
 32 }
 ・・・
 ・・・
 ・・・
 決勝進出
 決勝進出/予選敗退
 ↑ 2回目でX位以下
 赤は2X - k個
 prf: 2X - k人なのは全体で2X人決勝に行くので明らか。
 公平な予選だとすると、予選B→予選Aで行っても、決勝進出する必要があるが、 予選BでX位以下でないと、予選Aで決勝に進出できない (予選Aでk + 1位が落ち るため、k + 1位より後ろは敗退) 
 ↑k + 1位 
 予選BでX位
 より大きい

  31. 2X < N のケース (必要条件3)
 
 lem3: (予選AでX + 1位からk位を取った人の予選Bの最大値)

    < (予選Aでk + 1位以 上を取った人で決勝に行かなかった人の予選Bの順位の最小値) 
 33 }
 ・・
 ・・・
 ・・・
 決勝進出
 k+1以降の青より予選Bの結果がよい 
 決勝進出/予選敗退
 prf: 予選A→予選Bで行った時に、予選AでX + 1位からk位を取った人は予選Bで 勝つしかない。この時、予選Aでk + 1位以上を取って、敗退した人 (lem2より、予 選BでX位より大きい順位)) よりは小さい順位
 ↑ 2回目でX位以下
 赤は2X - k個
 ↑k + 1位 
 予選BでX位
 より大きい
 ・・
 }
 ↓X + 1位
 決勝進出

  32. 実は十分
 
 34 }
 ・・
 ・・・
 ・・・
 決勝進出/予選敗退
 ↑ 2回目でX位以下


    赤は2X - k個
 ↑k + 1位 
 予選BでX位
 より大きい
 ・・
 }
 ↓X + 1位
 決勝進出
 k+1以降の青より予選Bの結果がよい 
 決勝進出
 これでシミュレートすると、予選A→予選Bでも、予選B→予選Aで も、赤い丸が決勝行きます。

  33. 解法
 
 35 }
 ・・
 ・・・
 ・・・
 決勝進出/予選敗退
 ↑ 2回目でX位以下


    赤は2X - k個
 ↑k + 1位 
 予選BでX位
 より大きい
 ・・
 }
 ↓X + 1位
 決勝進出
 k+1以降の青より予選Bの結果がよい 
 決勝進出
 1. 以下kについて全探索をする
 1-1. k + 1以降の赤を決める (2X - k個に1~XでQにまだ登場してない数字を埋める)
 1-2. k + 1以降の青の最小値をmとして、以下mを全探索しつつ、mについて条件を満たすものをO(1) で計算する。
 1-2-1. k + 1以降で赤になってないものについて、m ~ Xを埋める
 1-2-2. m ~ Xでまだ使ってないものを予選Aの1~X位に割り当てる (ここで割り当てきれないと0になる)
 1-2-3. 残りを予選AのX + 1~k位に割り当てる 
 1-2-1~1-2-3は二項係数や階乗などの積で O(1)になるので全体でO(N^2)

  34. I - FORCIAN WAY
 問題概要
 3*N のマス目が与えられる。各マスには高々1つの英大文字が書かれている。まだ書か れていないマスには好きな英大文字を1つ書くことができる。 (1,1) から

    (3,N) へ隣接するマスを通るマスの列であって、順に文字を読んだときに “FORCIA” の1回以上の繰り返しとなるものが存在するようにできるか?
 例
 
 36 F A F X C R X A F A F O R A F X I C R C X A F O I A “Yes”

  35. 考察
 閉路がないpathを考えると、validなpathは以下の要素からなる I - FORCIAN WAY
 38 •  右移動 •

     上下移動 •  S字移動 これで全て そして、「S字移動」以外で 左へ移動することはない
  36. 考察
 S字移動は、6文字ずつ短縮できる! I - FORCIAN WAY
 39 F O R

    C I A F F O R C I A A I C R O A I C R O F F O R C ? ? ? ? ? ? C I A A I ? ? ? ? ? ? R O F
  37. 解法 4パターンのS字を使って先に行けるか?を前計算しつつ、DPで解ける dp[i][j][f][c] := マス(i,j) に状態f (0:上に動ける/1:下に動ける)で文字cの状態がありえる か? (true/false) (fは、例えば下に動いた直後に上に動くのを防ぐため必要)

    上記テーブルを左から埋めていくことで、計算量O(kN) で解ける (kは、高さ3*文字種6*Σ(S字のパス長) = 540 ぐらいの定数とする) (i+j)の偶奇により文字種は6→3とする実装も可能 I - FORCIAN WAY
 41
  38. 各問題のFA・AC数
 43 問題 オンサイト FA 全体FA AC数 A - Subsidy

    noya2 noya2 60 B - Group Moving potato167 potato167 57 C - Proper Fraction Operation suta shiomusubi 52 D - Taking Sandwitches potato167 shiomusubi 37 E - Adjust Mitsubachi Mitsubachi 42 F - A Beautiful Company startcpp E869120 7 G - Dot Product Query potato167 potato167 6 H - Equal qual potato167 potato167 1 I - FORCIAN WAY kotamanegi 1
  39. 44 問題 writer tester A - Subsidy siro53 momohara B

    - Group Moving prd_xxx momohara C - Proper Fraction Operation prd_xxx ayaoni D - Taking Sandwitches prd_xxx ochiaigawa E - Adjust tempura0224 ochiaigawa F - A Beautiful Company Talfall ochiaigawa G - Dot Product Query ochiaigawa ayaoni H - Equal qual ###### kiyoshi0205 tempura0224 I - FORCIAN WAY prd_xxx, Talfall tempura0224 writer/tester