第8回ゆるふわオンサイト解説スライド

第8回ゆるふわオンサイト   解説スライド   1  運営メンバー: dokin, ayaoni, prd_xxx, momohara,
siro53, ochiaigawa（他協力4名） Special Thanks: tempura0224, Tallfall, kichi2004

目次  2 • A - Progress Report Decreasing...  • B
- Edible Card Game  • C - ADD MUL MAX  • D - Range Mod Query  • E - Insert or Swap  • F - 2SAT ?  • G - Unique Factorization ?  • H - Many Count Middle Array Problem  • 各問題FA・AC数  • writer/tester 

A - Progress Report Decreasing...  3 問題概要  ゴリ太郎君の仕事の進捗は i日目に 10^(1-⌊(i-1)/9⌋)
ずつ増えます。  D日後の進捗の合計はいくらでしょう。  制約 (部分点)   • 1 ≦ D ≦ 9  制約  • 1 ≦ D ≦ 1000   

A - Progress Report Decreasing...  4 式を観察：  10^(1-⌊(i-1)/9⌋) はややこしいですが以下のようになっています  •
1 ≦ i ≦ 9 のとき、 10^(1-0) = 10^1 = 10  • 10 ≦ i ≦ 18 のとき、 10^(1-1) = 10^0 = 1  • 19 ≦ i ≦ 27 のとき、 10^(1-2) = 10^(-1) = 0.1  • 28 ≦ i ≦ 36 のとき、 10^(1-3) = 10^(-2) = 0.01  • 37 ≦ i ≦ 45 のとき、 10^(1-4) = 10^(-3) = 0.001  • …  i が 9 増えるごとに位が下がっていく！  

A - Progress Report Decreasing...  5 答えを観察：       
    …    D 1 2 3 4 5 6 7 8 9 0+ 10 20 30 40 50 60 70 80 90 9+ 91 92 93 94 95 96 97 98 99 18+ 99.1 99.2 99.3 99.4 99.5 99.6 99.7 99.8 99.9 27+ 99.91 99.92 99.93 99.94 99.95 99.96 99.97 99.98 99.99 36+ 99.991 99.992 99.993 99.994 99.995 99.996 99.997 99.998 99.999

A - Progress Report Decreasing...  6 部分点解法   • 1
≦ i ≦ 9 のとき、 10^(1-0) = 10^1 = 10  1日に 10 ずつ増えるので、10 * D が答え    D 1 2 3 4 5 6 7 8 9 0+ 10 20 30 40 50 60 70 80 90

A - Progress Report Decreasing...  7 解法  • 1 ≦
i ≦ 9 のとき、 10^(1-0) = 10^1 = 10  ◦ 10 * D   • 10 ≦ i ≦ 18 のとき、 10^(1-1) = 10^0 = 1  ◦ 90 + 1 * (D-9)  • 19 ≦ i ≦ 27 のとき、 10^(1-2) = 10^(-1) = 0.1  ◦ 99 + 0.1 * (D-18)  • 28 ≦ i ≦ 36 のとき、 10^(1-3) = 10^(-2) = 0.01  ◦ 99.9 + 0.01 * (D-27)  • …  みたいな感じで計算したいが... 

A - Progress Report Decreasing...  8 注意点  • 普通の浮動小数点数型 (float
や double等) を使うと精度が足りずWAになるので注意！  ◦ 倍精度でもせいぜい有効桁数が16桁ぐらい、本問題では112桁の精度を必要とする   ◦ (Python の Decimal を使ってもデフォルトの桁数では足りないが、112桁以上に設定すると通せる別解もあり)  • 文字列で処理しよう！ 

A - Progress Report Decreasing...  9 writer解法   • D
≦ 18 は小数点がつかないので計算で処理しておく  • D ≧ 19 のとき、(D-19) を 9で割った商をx, あまりをyとする  ◦ “99. {9をx個並べたもの} {y+1}” が答えとなる   D 1 2 3 4 5 6 7 8 9 18+ 99.1 99.2 99.3 99.4 99.5 99.6 99.7 99.8 99.9 27+ 99.91 99.92 99.93 99.94 99.95 99.96 99.97 99.98 99.99 36+ 99.991 99.992 99.993 99.994 99.995 99.996 99.997 99.998 99.999

A - Progress Report Decreasing...  10 tester解法   • 桁和がDであることを利用する！ 
• 答えの文字列 “” に、D > 9 である限り  ◦ “9”を追加する  ◦ Dから9を引く  • 最後にDを追加する  • 文字列が1桁の場合は”0”を追加する、3桁以上の場合は2桁目に”.”を挿入することを忘れずに 

B - Edible Card Game  11 問題概要  AliceとBobがカードゲームをします。それぞれN枚の整数が書かれたカードを持っています。各ラウンドごとに1枚ずつ好きなカードを出し、数の大きい方が勝ちとなるか、数が等しければ次のラウンドに続きます。Nラウンドまで勝負がつかなければ引
き分けです。  両者が最善を尽くすとき、どちらが勝つか？引き分けか？  制約  • 1 ≦ N ≦ 1000  • 1 ≦ A_i ≦ 9 

B - Edible Card Game  12 解法  結論：常に手持ちの中で最大のカードを出し続けるのが最善   証明 
自分の手持ちのうち最大の値をx、相手の手持ちのうち最大をyとする  • x > y のとき、そのラウンドで必ず勝てるのでxを出すべき  • x = y のとき、x以外のカードを出すと負けるのでxを出すべき  • x < y のとき、何を出しても負け  → 常にxを出すのが最善！ 

B - Edible Card Game  13 解法  あとは両者手持ちのカードのうち最大のものを出し、出したら削除するシミュレーションを書けばよい  ナイーブにやって
O(N^2)、先にソートしておくと O(NlogN) で解けます 

C - ADD MUL MAX  14 問題概要  長さ N の
正整数列 A[1], A[2], ... , A[N] が与えられます。   次の 2 種類の操作をそれぞれ高々 1 回ずつ行い、A[1] + A[2] + ... + A[N] を最大化せよ   ただし操作1と操作2を両方やる場合は、必ず操作1→操作2の順で行う   操作1: [l, r] を選んで、A[l], A[l+1], ... , A[r] の各要素に + X する   操作2: [l, r] を選んで、A[l], A[l+1], ... , A[r] の各要素に × Y する   制約  • 1 ≦ N ≦ 2 × 10^5   • -10^5 ≦ X, Y, A[i] ≦ 10^5  

C - ADD MUL MAX  15 解法1: 頑張って場合分けする方針   X
の値について考えると、3 種類考えられます。   １）X = 0  ２）X > 0  ３）X < 0  それぞれについて考えていきます。    

C - ADD MUL MAX  16 １）X = 0 の場合 
操作1 をどのように施しても数列A は変わりません。そのため、数列A に対して操作2 を施した場合の増加分の最大値を求めます。  （解法★）

C - ADD MUL MAX  17 ２） X > 0
の場合  X > 0 のの時、Y ≧ 0 か Y < 0 の場合わけが必要です。  2-1) Y ≧ 0 の場合（部分点ケース含む）  A の全ての要素に対して操作1 を施すのが最適です。  そのため、(A[1] + X, A[2] + X, … , A[N] + X) とした配列に対して、（解法★）により増加分の最大値が求まります。 

C - ADD MUL MAX  18 2-2）X > 0 かつ
Y < 0 の場合、3つのパターンに分類されます  2-2-1) 操作1をしない      2-2-2) Aの要素全てに操作1をしてから、部分的に操作2をする    いずれもX=0の場合の解法で求まります。 

C - ADD MUL MAX  19 2-2）X > 0 かつ
Y < 0 の場合（入出力例２のケース）  2-2-3)    仮にA[1] … A[L+j]（L+j < R）まで操作1 を適用すると、操作2により  Y × jX だけ損してしまうので、区間を重複させる必要がありません。操作1 を適用する区間と操作2 を適用する区間は必ず隣接します。  そのため、（解法★）を配列の後ろからやり、A[i], … A[N] の間の区間に対して操作2を適用した時の増加分の最大値を各i に対して求めれば良いです。  逆のパターンもあります。 

C - ADD MUL MAX  20 ３）X < 0 の場合 
3-1) Y ≧ 0 の場合（部分点ケース含む）  X < 0, XY ≦ 0 より、操作1 をやる必要がないため、（解法★）でそのまま解けます。  3-2) Y < 0 の場合  実は操作1を適用する区間と操作2を適用する区間は完全に一致します。   

C - ADD MUL MAX  21 3-2) 仮に[1, M] に操作1,
[L, R] に操作2を適用すると...  A[i] に操作1、操作2を順に適用させたとき、(A[i] + X) × Y - A[i] だけ増加するため、（解法★）でこの場合も解くことができます。  以上、いずれの場合でもO(N)でこの問題を解けました。  

C - ADD MUL MAX  22 解法2: DPで解く方針   次のような状態を持つDP（通称「耳DP」と呼ばれるもの）をします。
  dp[i 番目まで見た][ 操作1をまだ開始していない(0) / 操作1を適用している(1) / 操作1を終えた(2) ][操作2 をまだ開始していない(0) / 操作2を適用している(1) / 操作2を終えた(2) ]:=A[1]+A[2]+...+A[i]の最大値     計算量はO(N)です。     イメージ図 

D - Range Mod Query  23 問題概要  長さ N の正整数列
A[1], A[2], … , A[N] に対して Q 個のクエリを処理する   i 番目のクエリでは l[i], r[i] (1 ≦ l[i] < r[i] ≦ N) が与えられ、以下を計算する：   • (... ((A[l[i]] % A[l[i] + 1]) % A[l[i] + 2]) ...) % A[r[i]]   制約  • 2 ≦ N ≦ 1.5 × 10^5   • 1 ≦ Q ≦ 1.5 × 10^5   • 1 ≦ A_i ≦ 10^9 

D - Range Mod Query  24 解法(TLE)   クエリごとに、以下の疑似コードのように O(N)
かけて計算する   全体の計算量は O(NQ) となり、今回の問題の制約の上では TLE となる     for i := 1,2, … ,Q do ans := A[l[i]] for j := l[i] + 1, l[i]+2, … ,r[i] do ans := ans % A[j] print(ans)    

D - Range Mod Query  25 解法(AC)   疑似コード4行目の計算において ans
< A[j] の時、計算の前後で ans の値は変化しない   → ans ≧ A[j] の時だけ ans := ans % A[j] を計算することにしても答えは変わらない     ans ≧ A[j] になる時は何回ぐらいかを見積もってみましょう！  

D - Range Mod Query  26 解法(AC)   ans ≧
A[j] となる回数は O(log max(A_i)) 回であると見積もれます（有名事実？）   (証明)   x = ans % A[j] とすると、  • A[j] > ans / 2 の時  x ≦ ans - A[j] < ans - ans / 2 = ans / 2   • A[j] ≦ ans / 2 の時  A[j] ≦ ans / 2 より x < A[j] ≦ ans / 2  → よって x ≦ ans / 2、つまり ans ≧ A[j] の時あまりを計算するたびに ans の値は 1/2 以下になる   

D - Range Mod Query  27 解法(AC)   ans <
A[j] の時は無視して ans ≧ A[j] の時だけ計算することを効率良くシミュレーションできればよい。   ans ≧ A[j] なる j を求めるのは、区間最小値を計算する segtree 上の二分探索を用いることでO(log N) で計算出来る。    よって、クエリごとに O(log N log max(A_i)) で計算出来る。   全体として O(Q log N log max(A_i)) でこの問題を解くことが出来ました。      

E - Insert or Swap  28 問題概要  N 個のボールと空の箱が1つあり、ボール i
には非負整数 A_i が書かれている   i=1,2,...,N の順に操作1 or 操作2 のいずれかを行う  ・操作1 : ボール i を箱に入れる。ボール i を箱に入れる前に箱に入っていたボールの個数が x のとき、コストは x かかる  ・操作2 : 箱に入っているボールを 1 つ選び、ボール i と swap する。ボール i を箱に入れる前に箱に入っていたボールの個数が x、ボール i と swap したボールに書かれている非負整数が y のとき、コストは x+y かかる（箱に1つ以上ボールがあるときしかこの操作は出来ない）   全ての操作を終えた後に箱に入っているボールを K 個にしたいとき、コストの合計を最小化せよ    

E - Insert or Swap  29 考察1  • 操作1 では箱の中のボールの個数は
1 個増える   • 操作2 では箱の中のボールの個数は変わらない   • 箱の個数は最終的に K 個にしなければならない   → 操作1 を行う回数は K 回、操作2 を行う回数は N-K 回で固定される      

E - Insert or Swap  30 考察2  最初すべて操作1 を行うことにして、どのボールを操作2で捨てるとよいかを考える
  全て操作1 を行うことにすると、コストの和は 0+1+...+(N-1) = (N-1)*N/2   次に、ボール i を操作2 にするときのコストの差分を考える   • 箱の中に入っているボールの個数分かかるコストをタイプx  • 捨てるボールに書かれている非負整数だけかかるコストをタイプy  とする 

E - Insert or Swap  31 考察2-x   ボール i
で操作1ではなく操作2をすることにしたときの、コストの差分を考える   • ボール i+1, i+2,..., N にかかるタイプx のコストが -1 減る  このときのコストの合計は、操作2が i=2,3,...,N でしか出来ないことに注意すると   N-(i+1)+1を小さい順にN-K個選んだ分だけ減る  

E - Insert or Swap  32 考察2-y   操作2 によって捨てられるボールに書かれている整数分、コストがかかる
  捨てられるボールは i=1,2,...,(N-1) に限られることに注意すると、タイプy の合計は   i=1,2,...,N-1 の中から A_i だけ減る  

E - Insert or Swap  33 コストをまとめると、定数項を無視して   i=1,2,...,N-1について A_i
- (N - (i + 1)) をソートして、昇順にN-K個選ぶのが最適   O(NlogN) で解ける。 

F - 2SAT ?  34 問題概要  - A_i = X_i
or A_i = Y_i  - A_i ≠ A_j  以下の条件を満たす数列 A の個数を数えよ 

F - 2SAT ?  35 部分点満点の共通の考察  X = (1,2,3,4), Y
= (2,1,4,3) のケース  A_1  A_2  A_3  A_4  A_iがマッチング可能な数字の間に線を引いて二部グラフを作る  (多重辺がないように作る)  赤い頂点を被覆するようなマッチングの数え上げが答え  1  2  3  4  本問題の入力では連結成分が複数がありえるので、各連結成分で数え上げて積が答えになる。  (以後、グラフが連結とする)  赤の頂点の次数は2以下！ 

F - 2SAT ?  36 部分点と満点解法の差分  A_1  A_2  1  2 
A_1  1  2  X = (1,2), Y = (2,1)   X = (1), Y = (2)   部分点は、赤がN頂点で、青はN以下なので、 (マッチングがあるなら) 青は全て使う   満点は青は使わなくてもいい頂点がある 

F - 2SAT ?  37 部分点解法  A_1  A_2  1  2 
1. 赤も青も全て使うので、全体で次数1の点があればマッチング確定  2. マッチングした点を除く  3. 孤立点がうまれたら答えは0 。生まれなかったら1に戻る  4. 1ができなくなったら、実はcycleになっているので、マッチングは2通り  3  A_3  X = (1,2,3,4), Y = (2,3,4,3)   4  A_4  左の例だと  (A_1,1) (A_2,2)がマッチングして、長さ4の cycleがのこる 

F - 2SAT ?  38 部分点解法の正当性  次数1の点のあるグラフで、完全マッチングを作ろうとしたら、その点のマッチング先は一意  赤の頂点の次数は常に2以下で、次数1の点がないなら、赤の頂点は全て次数2  青の頂点の次数も全て2以上で、二部グラフ性より、赤の頂点の次数の総和と青の頂点の次数の総和は一致するから、青の頂点も全て次数2
(正則二部グラフになっている)  cycle内のマッチングは、時計回りに結ぶか、反時計回りに結ぶかで2通り 

F - 2SAT ?  39 観察1    (青の頂点の数) - (赤の頂点の数)
<=1 が成立  証明: 帰納法など   (気持ち的には青の頂点を追加しようとしても、赤の頂点の次数の制約があるからそんなに追加できないみたいな)  特にcycleを作ろうとすると青 - 赤が減る 

F - 2SAT ?  40 観察2    各連結成分は実は以下の4パターンに分類される。  青 -
赤 = 1で木  青 - 赤 = 0で木  青 - 赤 = 0でcycleがちょうど1つ  青 - 赤 <0   (マッチングなし)  (部分点はマッチングがあるなら、真ん中2つのみ) 

F - 2SAT ?  41 観察2の正当性 (略証)    結局のところ、ある連結成分に辺と頂点を追加して、cycleを作ろうとすると、青の頂点を追加したときに、元々その連結成分に存在する赤の頂点同士を結ぶ
必要があって、青 - 赤が減る  青 - 赤 <=1 であり、青 - 赤 = 1の場合cycleを作ることができない。 (cycleを作ろうとすると、青 - 赤が減る)  青 - 赤 = 0のとき、cycleは高々が1つしかつくれない。 (cycleを2つ以上作ろうとすると、青 - 赤 < 0になる。) 

F - 2SAT ?  42 満点解法1 (W解)     木DPでマッチングの
個数が分かる  マッチングなし  木DPでO(N)  cycleの頂点はcycle内部でマッチングさせる必要があって2通りで、あとは木DPでマッチングの個数が分かる  木DPでマッチングの個数が分かる 

F - 2SAT ?  43 満点解法2 (T解)     マッチングの個数
= 青の頂点数  実はDPしなくても分かる！  マッチングの個数 = 2   マッチングの個数 = 1   マッチングの個数 = 0  

F - 2SAT ?  44 満点解法2の正当性    青 - 赤
= 0で木のケースでマッチングが一意に存在することを示す  二部グラフなので、赤の頂点の次数の総和 = 辺の総数で、偶数頂点なので、辺の総数は奇数になる。赤の頂点で次数が奇数のものが存在するが、赤の頂点の次数は2以下なので、次数1のものが存在する (これは葉)   葉を一意にマッチングして、マッチングした頂点を消すと、青 - 赤 = 0の頂点数の少ない木の問題に帰着できるので帰納的にわかる。    青 - 赤 = 0かつcycleがある場合、cycle内部で2通り +周辺が木となる。  青 - 赤 = 1の場合は、使わない青の頂点を決めるとマッチングが一意に存在する。 

F - 2SAT ?  45 余談    2SATという問題がある  (x ∨
y) ∧ (¬x ∨ z) ∧ (¬y ∨ ¬z)　   全体でx,y,zに真理値を割り当てして、全体を真にする。  第一節は x = true or y = trueということ  充足解の存在判定をするのは線形時間でできる。  ACL参照:https://zer0-star.github.io/Nim-ACL/document_ja/twosat.html  充足解の数え上げは #P完全と呼ばれており、P≠NPのもとでは、多項式時間で解けない   参照: https://en.wikipedia.org/wiki/2-satisfiability   (途中二部グラフの完全マッチングの数え上げに帰着していたが、これも#P完全)     本問題では、特殊な制約があるので解ける  

G - Unique Factorization ?  46

問題概要数列 X, Y の全ての並び替えに対する↓の答えの和 mod 998244353 Count Middle Array
Problem 全ての i について X[i] <= A[i] <= Y[i] をみたす数列の個数 H - Many Count Middle Array Problem  55

言い換え① Count Middle Array Problem の答えは ∏ (Y[i] - X[i]
+ 1) if すべての i で Y[i] >= X[i] else 0 Y にあらかじめ 1 を足しておくことで、以下では ∏ (Y[i] - X[i]) if すべての i で Y[i] > X[i] else 0 として考える。すると、問題は以下のように言い換えられるすべての i で Y[i] > X[i] となるような並び替えに対する ∏ (Y[i] - X[i]) の和   H - Many Count Middle Array Problem  56

言い換え② ∏ (Y[i] - X[i]) をそのまま扱うのは大変。展開して、以下のように考える各項から Y[i] or -X[i]
のどちらかを選んで積を取る。選び方全て(2^N通り)に対するこの積の総和この考えを使うと、問題はさらに言い換えられるすべての i で Y[i] > X[i] となるように並び替えたあと、Xをすべて -1 倍し、各 i ごとに X[i] とY[i] のどちらかに丸をつける。丸をつけた要素の積の総和 H - Many Count Middle Array Problem  57

そしてDPへ X, Y をそれぞれ昇順に並べて小さいものから取り出していく。 X: 残りの場所に自由に選べる Y: すでにXがある場所に置ける dp[X,Yから取り出した合計個数][まだペアが決まっていなくて丸のついている
Xの数] を考えることで、いい感じに遷移できる。よって O(N^2) で解くことができた。 H - Many Count Middle Array Problem  58 3 2 5 1 4 7 4 X = {1, 2, 3, 4, 5, …}  Y = {4, 7, 10, …}  X  Y 

各問題のFA・AC数  59 問題オンサイト FA 全体FA AC数 A - Progress
Report Decreasing… potato167 potato167 53/53 B - Edible Card Game uruzunyaa uruzunyaa 55/55 C - ADD MUL MAX potato167 potato167 30/36 D - Range Mod Query potato167 potato167 40/42 E - Insert or Swap potato167 potato167 29/33 F - 2SAT ? potato167 wasureta 23/24 G - Unique Factorization ? potato167 tute7627 3/4 H - Many Count Middle Array Problem potato167 potato167 4/5

60 問題 writer tester A - Progress Report Decreasing… prd_xxx
momohara B - Edible Card Game prd_xxx momohara C - ADD MUL MAX ###, tempura0224 ochiaigawa D - Range Mod Query siro53 ayaoni E - Insert or Swap siro53 ochiaigawa F - 2SAT ? ### siro53 G - Unique Factorization ? ayaoni ochiaigawa H - Many Count Middle Array Problem tempura0224 ### writer/tester 

第8回ゆるふわオンサイト 解説スライド

第8回ゆるふわオンサイト 解説スライド

More Decks by forcia_dev_pr

Featured

Transcript

第8回ゆるふわオンサイト解説スライド

第8回ゆるふわオンサイト解説スライド