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

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

forcia_dev_pr
June 28, 2023
100

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

forcia_dev_pr

June 28, 2023
Tweet

More Decks by forcia_dev_pr

Transcript

  1. 目次
 2 • A - Yurufuwa Times
 • B -

    RGB Equation
 • C - Not Divide Factorial
 • D - ×2÷2%22
 • E - A's ugly behavior in the elevator
 • F - Range Sum GCD
 • G - Exponential Banana Game
 • H - Oriented to DAG
 • I - A's ugly behavior in the elevator (general)
 • J - Yurufuwa Topology
 • 各問題FA・AC数
 • writer/tester

  2. A - Yurufuwa Times
 問題概要
 1以上N以下の整数が与えられるので、第N回のゆるふわオンサイトが西暦何年に開催 されたかを解答してください。
 
 
 3

    開催年(西暦) 開催タイトル 2019 第1回ゆるふわオンサイト 2019 第2回ゆるふわオンサイト 2020 第3回ゆるふわオンサイト 2023 第4回ゆるふわオンサイト 2023 第5回ゆるふわオンサイト
  3. B - RGB Equation
 問題概要
 以下の4つのうち3つ の等式が与えられます。R,G,Bを求めてください。
 ① G +

    B = C
 ② R + B = M
 ③ R + G = Y
 ④ R + G + B = W
 解法
 具体的な手順はいくつかありますが、連立方程式として解けます。式変形と場合分けを がんばります。
 5
  4. B - RGB Equation
 ・Cがない場合
 ① G + B =

    C
 ② R + B = M
 ③ R + G = Y
 ④ R + G + B = W
 ④*2: 2R + 2G + 2B = 2W
 -② : - R - B = -M
 -③ : - R - G = -Y
 C = G + B = 2W - M - Y
 6 ・Mがない場合
 ① G + B = C
 ② R + B = M
 ③ R + G = Y
 ④ R + G + B = W
 ④*2: 2R + 2G + 2B = 2W
 -① : - G - B = -C
 -③ : - R - G = -Y
 M = R + B = 2W - C - Y

  5. B - RGB Equation
 ・Yがない場合
 ① G + B =

    C
 ② R + B = M
 ③ R + G = Y
 ④ R + G + B = W
 ④*2: 2R + 2G + 2B = 2W
 -① : - G - B = -C
 -② : - R - B = -M
 Y = R + G = 2W - C - M
 7 ・Wがない場合
 ① G + B = C
 ② R + B = M
 ③ R + G = Y
 ④ R + G + B = W
 ① : G + B = C
 +② : R + + B = M
 +③ : R + G = Y
 (R+G+B)*2 = C + M + Y
 W = (C+M+Y) / 2

  6. B - RGB Equation
 C,M,Y,W がすべて求められれば
 R = W -

    C
 G = W - M
 B = W - Y
 のように解が求まります
 余談
 Python には numpy や sympyに食わせると連立一次方程式を解いてくれるモジュール があるのですが、HackerRank には対応してなくて残念でした (><)
 8
  7. C - Not Divide Factorial
 問題概要
 正の整数 N が与えられるので、N! を割り切らない最小の正の整数を答えてください。


    方針
 • 1, 2, …, N は明らかに N! を割り切るので、N + 1 以上の整数を1つ1つ検証していき ます。
 • N + 1 以上の整数に対して素因数分解を行い、各素因数 p に対して p の指数と p が N! を割り切る回数を比較します。
 ◦ p が N! を割り切る回数は、[N / p] + [N / p^2] + … と求められます 
 9
  8. C - Not Divide Factorial
 具体例(N = 19 のとき)
 •

    20 = 2^2 × 5^1
 ◦ 19! が 2 で割り切れる回数は、[19/2] + [19/2^2] + [19/2^3] + [19/2^4] = 16 となり、2(2の指数) 以上。
 ◦ 19! が 5 で割り切れる回数は、[19/5] = 3 となり、1(5の指数) 以上。 
 ◦ 故に 20 は 19! を割り切る。 
 • 21 = 3^1 * 7^1
 ◦ 19! が 3 で割り切れる回数は、[19/3] + [19/3^2] = 8 となり、2(3の指数)以上。 
 ◦ 19! が 7 で割り切れる回数は、[19/7] = 2 となり、1(7の指数)以上。 
 ◦ 故に 21 は 19! を割り切る。 
 10
  9. C - Not Divide Factorial
 具体例(N = 19 のとき)
 •

    22 = 2^1 × 11^1
 ◦ 19! が 2 で割り切れる回数は、[19/2] + [19/2^2] + [19/2^3] + [19/2^4] = 16 となり、2(2の指数) 以上。
 ◦ 19! が 11 で割り切れる回数は、[19/11] = 1 となり、1(11の指数) 以上。 
 ◦ 故に 22 は 19! を割り切る。 
 • 23 = 23^1
 ◦ 19! が 23 で割り切れる回数は、0となり、1(23の指数)以上。 
 ◦ 故に 23 は 19! を割り切らない。 
 • ゆえに解は「23」!!!
 11
  10. C - Not Divide Factorial
 この計算、高速なの?
 少なくとも答えは N より大きい最小の素数で上から抑えられますが、10^9 以下で最も長

    く合成数が連続する区間は 436273010 から 436273290 までの長さ 281 の区間なの で、高々 282 個の数に対して検証を行えば良いです。
 実は・・・
 N ≠ 3 のとき、N より大きい最小の素数が答えになります!
 (「ベルトランの仮説」を用いると証明できます)
 12
  11. D - x2÷2/22
 問題概要
 X = 1 から次の操作を繰り返して 整数N を作ってください。


    • A … X に 2 をかける
 • B … X を 2 でわる
 • C … X を 22でわった余りで置き換える
 作り方が複数ある場合は、最短かつ辞書式順序最小のものを出力してください。
 方針
 解き方はいろいろ。各 N について地道に調べていけば解けるはず。
 13
  12. D - x2÷2/22
 解法1 地道に調べて答えを出力
 2 ≡ N または 2 ≡

    N × 2 (mod22) をみたす最小の x を K とおく。
 FACT : Nを作るために操作Aは最小でも K 回必要
 • N = 2, 4, 8, 16 … AをK個並べる
 • N = 6, 10, 12, 14, 18, 20 … AをK個並べたあとにCを並べる
 • N = 3, 5, 7, 9 … AをK個並べたあとにCBを並べる
 • N = 11, 13, 15, 17, 19, 22 … Kが存在しないので、-1 を出力する
 
 14 x
 x

  13. E - A's ugly behavior in the elevator
 問題概要
 •

    A君は1階からエレベーターに乗り込み、目的階はN階
 • 2階, 3階, …, N - 1 階を目的階とする N - 2 人が乗り込んできた
 • A君はいくつか目的階を解除して、できるだけ停車回数を少なくしたい
 • ただし x 階が目的階の人が y 階で降りることになった場合、A君に対して
 y - x のヘイトが向けられる
 • このヘイトの総量が H を超えるとアウト
 • 途中停車の回数の最小値は?
 16
  14. E - A's ugly behavior in the elevator
 方針
 •

    f(i) := (i 回途中停車したときのA君に向けられるヘイトの総和の最小値) とおくと、f は i に関して単調減少関数
 • ゆえに f(i) <= H なる i の最大値を二分探索で求めてやれば良い
 • あとは f(i) を高速に計算する方法を考えれば良い
 17
  15. E - A's ugly behavior in the elevator
 f(i) の求め方


    N = 12, i = 2 のときで考えてみます。
 
 
 18 1
 12
 3
 7
 1
 4
 7
 12
 差2
 差4
 差5
 差3
 差3
 差5
 ヘイト
 1
 ヘイト
 1+2+3
 ヘイト
 1+2+3+4
 ヘイト
 1+2
 ヘイト
 1+2
 ヘイト
 1+2+3+4
 ヘイト減少! 差が2以上

  16. E - A's ugly behavior in the elevator
 f(i) の求め方


    • このように隣り合う停車階の差をとり、それが 2 以上離れている所は差を少なくす るようにスライドさせるとヘイトの総和が減少します。
 ◦ (…, a, b, …, c, d, …) => (…, a, b + 1, …, c + 1, d, …) 
 • このような操作を繰り返していくと、できるだけ均等に停車階を設定した時にヘイト が最小になることが分かります。
 ◦ 先程の例だと、(1, 4, 8, 12) の時がヘイトが最小になる一例 
 • ゆえに N - 1 = q * (i + 1) + r と割り算して、q を i +1 - r 個と q + 1 を r 個に分ける のが最適です。
 • f(i) = (i + 1 - r) * (1 + … + (q - 1)) + r * (1 + … + q) となり、これは高速に求めら れます。
 19
  17. F - Range Sum GCD
 問題概要
 数列 A1, A2, …,

    AN がある。
 区間和をいくつか選んでそのGCD(最大公約数)を G にすることができますか?
 例
 A = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3}, G = 7
 gcd(5+9, 4+1+5+9+2) = gcd(14, 21) = 7 なので Yes
 20
  18. F - Range Sum GCD
 考察②
 Aの累積和配列 S (S0=0, Si

    = A1+A2+...+Ai) を考えると
 区間和は Sr -Sl と表せる。
 また、Sr - Sl が G の倍数 ⇔ Sr ≡ Sl (mod G) なので、
 S を G でわったあまりごとにグループ分けして、
 グループごとに差のGCDをすべて取ったものが G になればよい。
 22
  19. F - Range Sum GCD
 考察②例
 A = {3, 1,

    4, 1, 5, 9, 2, 6, 5, 3}, G = 7
 S = {0, 3, 4, 8, 9, 14, 23, 25, 31, 36, 39}
 7 で割った余りごとに分けると
 (0, 14), (8, 36), (9, 23), (3), (4, 25, 39), (31)
 gcd(14-0, 36-8, 23-9, 25-4, 39-4, 39-25) = 7
 23
  20. F - Range Sum GCD
 考察③
 このままだとペアは O(N^2) 組ありえるので N=200000

    では間に合わない
 ここで、gcd(x, y) = gcd(x, y - x) なので(ユークリッドの互除法)、
 gcd(Sm-Sl, Sr-Sl) = gcd(Sm-Sl, (Sr-Sl)-(Sm-Sl)) = gcd(Sm-Sl, Sr-Sm)
 つまり、
 Sr-Sl と Sm-Sl の gcd を取れば Sr-Sm のことは考えなくてよい!
 24
  21. F - Range Sum GCD
 考察③
 したがってグループ(S1, S2, …,Sk) ごとに、


    gcd(S2-S1, S3-S1, …, Sk-S1) のみを考えれば十分。
 これで調べるべきペアを O(N) 組に減らすことができた。
 25
  22. F - Range Sum GCD
 まとめ
 結局この問題は以下のステップで解ける
 1. 累積和配列Sを作り、SをGで割ったあまりごとにグループ分けする
 2.

    各グループごとに、(各項-先頭) の GCD を取る
 3. それらの GCD を取る
 4. G になれば Yes を出力、ならなければ No を出力
 計算量は実装方針にもよりますが O(NlogN+logA) など。
 26
  23. G - Exponential Banana Game
 問題概要
 与えられた条件で以下の交互進行ゲームを行う
 ・部屋i には A_i

    本のバナナがあり、B_i が設定されている
 ・手番では i,j を選び、部屋i のバナナを B_i^j 本、食べる
 ・操作ができなくなったほうが負け
 先手がゲーム開始前に各部屋あたりM本以下のバナナをこっそり食べるような細工がで きるとき、先手が必勝となるような食べ方は何通りあるか?
 27
  24. G - Exponential Banana Game
 解法 
 ◆ B_i が偶数の場合


    (0, 1, 0, 1, ... , 0, 1, 2), (0, 1, 0, 1, ... , 0, 1, 2) , ...
 のように B_i + 1 周期で繰り返すことがわかります!
 
 例: B_i = 4の場合
 (0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, ... ) 
 30 B_i + 1 周期

  25. G - Exponential Banana Game
 解法 
 Grundy数の法則から重要な観察ができ、このゲームのGrundy数は高々2までの値しか 取らないことがわかります。
 さらに、各部屋のGrundy数のxorを取ったときの途中結果は0~3の整数

    (2ビット) で表 せることがわかります 
 このことを用いて、元の問題を考えると、次のようなdpが可能です。
 dp[i][j] = 部屋iまで求めた途中結果で、
    Grundy数がjとなるようにバナナを食べる場合の数
 31
  26. G - Exponential Banana Game
 解法
 部屋i でバナナをM本まで食べる方法のうち、Grundy数が xとなる食べ方の場合の数は 適切に計算することで

    O(1)で求まります。
 これを利用して適切なdpを書くことで、全体の計算量は O(N) で求められます。(定数倍 は 4*4 = 16 程度で、十分間に合います)
 
 類題
 H - 8^kゲーム
 32
  27. (彩色数) -1 ≧ 最長パスの長さの最小値
 35 無向グラフを彩色する。 (左図では、赤,青,緑,ピンクの4彩色) 
 色に序列を付ける。
 例えば、赤

    > 青 > 緑 > ピンク とする。
 序列の大きい方から小さいほうに辺の向きを付けると、DAGが構 成できる (同じ色同士に辺がないことに注意) が、 
 そのDAGの最長パスの長さは (彩色数 - 1) 以下になる。 
 証明: 同じ色は二回通ることはないため。 

  28. (彩色数) -1 ≦ 最長パスの長さの最小値
 36 3 1 2 0 1

    1 辺に向き付けしてDAGを作る。 
 DAGの各頂点に、「この頂点から始まる最長パスの長さ」を書 いていく。
 全体で一番大きい数字が最長パスの長さ + 1 になるが、数字 が同じ頂点を同じ色で塗れば、 (最長パスの長さ + 1) 色での彩 色が可能
 証明: dp[v] := 「頂点vから始まる最長パスの長さ」とすると、 
 dp[v] = max_{vからuへ向かう有向辺が存在} dp[u] + 1 なので、隣接す る頂点に書かれた番号は異なる。 

  29. 計算量/余談など
 37 彩色数を求める計算量は、アルゴリズムによるが、O(3^N) とか、O(2^NN^2) とか、場合によってはもっ と早い
 詳細はmathnachiaさんのブログを参照: https://www.mathenachia.blog/chromatic-fast/ 
 余談ですが、


    dp[S]:= 集合Sに入ってくる辺の向きを全てつけたときの、最長パスの長さの最小値 
 でbitDPすると
 dp[S] = max_{T⊂S} (dp[T] + 1) 
 という遷移になるが、これが彩色数のdpと同じになることに気づいても解法にたどり着けるかも しれない。

  30. I - A's ugly behavior in the elevator (general)
 


    
 問題概要
 • A君は1階からエレベーターに乗り込み、目的階はN階
 • A1 階, A2 階, …, AM 階を目的階とする M 人が乗り込んできた
 • A君はいくつか目的階の解除して、できるだけ停車回数を少なくしたい
 • ただし x 階が目的階の人が y 階で降りることになった場合、A君に対して
 y - x のヘイトが向けられる
 • このヘイトの総量が H を超えるとアウト
 • 途中停車の回数の最小値は?
 
 38
  31. I - A's ugly behavior in the elevator (general)
 


    
 考察
 • dp[i][j] := 人 i から 人 M までを考えたとき、Ai 階に停まり j 階 skip する場合のヘイ トの最小値、としたdpを解くと正しい答えが求まる。
 • 勿論この解法では制限実行時間に間に合わない
 • 何か良い性質はないだろうか??
 
 39
  32. I - A's ugly behavior in the elevator (general)
 


    
 考察
 g(x) を x 階 skipする場合のヘイトの合計の最小値とすると、
 g は下凸になります (直感的には負の効用逓減が効きます) → Alien’s trick が使えます。 
 40
  33. I - A's ugly behavior in the elevator (general)
 


    
 解法
 dp[i][j] := 人 i から 人 M までを考えたとき、Ai 階に停まり j 回 skip する場合のヘイト の最小値 を考える代わりに、1 階 skip するあたり C (この問題では C < 0) のコストがかかると考 えて、 dp[i; C] := 人 i から 人 M までを考えたとき、Ai 階に停まるときの ヘイト + コスト の最小 値 という dp を考えます。 
 41
  34. I - A's ugly behavior in the elevator (general)
 


    
 解法
 dp[i; C] := 人 i から 人 M までを考えたとき、Ai 階に停まるときの ヘイト + コスト の最小 値 とすると、 dp[i]=min(j<i) (dp[j]+Σj<k<i(Ak−Aj)+(i−j−1)C) です。 整理するためにSi=Σk≧i Akとおくと dp[i]=Si−1+iC+ minj<i (dp[j]−Sj−(j+1)(C−Aj)−i⋅Aj) となり、これは Convex Hull Trick で高速に計算できます 42
  35. I - A's ugly behavior in the elevator (general)
 


    
 解法
 ヘイト+コストの最小値と、それを実現する skip 階数を CHT を用いて求めることができ ました。C に対して skip 階数がどう変化するのかを考えます。 
 43
  36. I - A's ugly behavior in the elevator (general)
 


    
 
 44 C = 0, H = 20
 skip する階数
 最小値
 最小値は 0 階skip のとき

  37. I - A's ugly behavior in the elevator (general)
 


    
 
 45 C = -10, H = 20
 skip する階数
 最小値
 最小値は 1, 2, 3 階skip のとき

  38. I - A's ugly behavior in the elevator (general)
 


    
 
 46 C = -20, H = 20
 skip する階数
 最小値
 最小値は 3, 4 階 skip のとき

  39. I - A's ugly behavior in the elevator (general)
 


    
 
 47 I - A's ugly behavior in the elevator (general)
 
 
 解法
 g(x) は単調なので、C の値を二分探索すると、ヘイトが H を超えない skip 階数が求ま ります。 計算量は O(M log(NM-sum(A)) です。 (他にも monge グラフ上の最短路問題とみなして解く解法などもあります) 47
  40. J - Yurufuwa Topology
 
 
 
 48 問題概要
 閉曲線とN個の頂点が与えられる。

    頂点の部分集合で、閉曲線が”ほどける”頂点数の最大値を求めよ。 48 右側の頂点のみを選ぶと、ほどける 

  41. J - Yurufuwa Topology
 
 
 
 49 49 本質

    頂点集合 S に対し、閉曲線 C がほどける ⇔ 任意の2頂点以下のSの部分集合Tに対し、閉曲線Cがほどける
  42. J - Yurufuwa Topology
 
 
 
 50 50 方針

    頂点1 … N からなるグラフを用意する。 集合 {i, j} が “ほどける” とき i と j の間に辺を貼る (自己ループも含む)。 最大クリーク問題を解く。 1ケースあたりの計算量 : O(N × 2^N + N × L)
  43. 各問題のFA・AC数
 51 問題 オンサイトFA オンラインFA AC数 A - Yurufuwa Times

    hamath(00:43) sayakaamemiyag(00:40) 59 B - RGB Equation noko_(02:44) 59 C - Not Divide Factorial n_fuppy(03:23) 53 D - ×2÷2%22 KKT89(18:04) heno239(17:25) 54 E - A's ugly behavior in the elevator noko_(18:16) 37 F - Range Sum GCD primenumberzz(12:52) 30 G - Exponential Banana Game ytqm3(31:54) 17 H - Oriented to DAG noko_(1:08:06) sayakaamemiyag(1:06:04) 7 I - A's ugly behavior in the elevator (general) heno239(1:36:11) 2 J - Yurufuwa Topology heno239(2:16:00) 1 ※オンラインFAはオンサイトより速かった場合のみ表記しております。

  44. writer/tester
 52 問題 writer tester A - Yurufuwa Times momohara

    prd_xxx B - RGB Equation prd_xxx dokin C - Not Divide Factorial ayaoni tempura0224 D - ×2÷2%22 dokin momohara E - A's ugly behavior in the elevator ayaoni prd_xxx F - Range Sum GCD tempura0224 G - Exponential Banana Game prd_xxx dokin H - Oriented to DAG ayaoni I - A's ugly behavior in the elevator (general) Tallfall(原案: ayaoni) ayaoni J - Yurufuwa Topology dokin ayaoni