第4回ゆるふわ競技プログラミングオンサイト解説

2023/2/25開催ゆるふわオンサイト解説

コンテストページ : https://www.hackerrank.com/yfkpo4
参加者募集ページ :https://forcia.connpass.com/event/271902/

Transcript

1. writer情報 番号 問題名 writer A yurufuwa string tempura0224 B Super Miraina Tower prd_xxx C 0,1,2 daifuku prd_xxx D chutti dokin E Strange Clock Tallfall F Similar Paths G1 two columns dokin G2 three columns dokin
2. A - yurufuwa string writer: tempura0224
3. 問題概要 • 8文字の文字列が与えられるので、「ゆるふわ」かどうか判定する • 以下のときに「ゆるふわ」となる ◦ 2,4,6 文字目が ‘u’ ◦ 8 文字目が ‘a’
4. 解答例 (C++) #include <bits/stdc++.h> using namespace std; int main() { string S; cin >> S; if (S[1]=='u' && S[3]=='u' && S[5]=='u' && S[7]=='a') cout << “Yes” << endl; else cout << “No” << endl; }
5. 解答例 (Python) S = input() if S[1] == S[3] == S[5] == ‘u’ and S[7] == ‘a’: print(‘Yes’) else: print(‘No’)
6. B - Super Miraina Tower writer: prd_xxx
7. 問題概要 • フィボナッチ数の階で折り返すエスカレーターがある • 1階にいるとき x=0 として、N階相当の高さに来たときの x座標を求 める
8. 想定解法 • シミュレーションしましょう！ • たとえば、下記のような解法があります ◦ まず、フィボナッチ数を求めます ▪ 1,2,3,5,8,13, … を配列に入れておきます ◦ x=0, floor=1 で初期化します ◦ 処理が終了するまで下記を行います ▪ floor の次のフィボナッチ数までの差を求め、d とします ▪ そのフィボナッチ数が偶数番目なら xからdを引きます ▪ 奇数番目なら xにdを足します ▪ floor に dを足します ▪ floor >= N となったら、行き過ぎた分を(あれば)戻し、xを出 力し、終了します
9. 本質情報 (元ネタ) • 現実のミライナタワーも5階まではフィボナッチエスカレーターです 3階 5階 2階
10. C - 0,1,2 daifuku writer: prd_xxx
11. 問題概要 • 美味しさが 0,1,2 の大福が N個並んでいる (N <= 200000) • 満足度は食べた大福の美味しさの総積 • 1 ≦ l < r ≦ N となる l,r を選び、l番目からr番目までの大福を食べ たときの満足度が 0,1,2 となるような l,r の選び方はそれぞれ何通 りか？ • 3つの値を求める
12. 想定誤解法 • 問題文の通りすべてのl,rの組み合わせを試すとTLEします ◦ l < r を満たす l,r の選び方は n*(n-1)/2 通り ▪ A_l から A_r の積をナイーブに求めたら O(N^3) ▪ 積を累積するなど工夫しても O(N^2) • 工夫して数える必要がある • 積が0,1,2 となる l,r の選び方には特徴があるので、それを利用す ると良い！
13. ans1について • ans1の値は、すべての値が1である A_l … A_r の数に一致する。 • これは次のように求められます。 ◦ 1が連続する Aの連続部分列 (のうち最長のものを列挙) 0 2 1 1 1 1 0 1 1 2 1 1 1 1 0 ◦ 取り出した連続部分列の長さをnとしたとき、下記をans1に加算していく ▪ nC2 = n*(n-1) / 2 ▪ たとえば、1,1,1,1 から (l,r) を選ぶ方法の数は 4C2 = 6 となるので6を加算し ていけば良い • 連続部分列を取り出す処理がボトルネックで O(N) 4*3/2 = 6 2*1/2 = 1 3*2/2 = 3 1*0/2 = 0
14. ▪ 求め方は ans1 の場合と同じ • 連続部分列を取り出す処理がボトルネックで O(N) • ans0の値は、0を1つ以上含む A_l … A_r の数に一致する。 • ですが、そのまま求めるのは大変なので、次のように求めます ◦ (すべての (l,r) の選び方) - (0を含まない (l,r) の選び方) • これらは次のように求められます。 ◦ (すべての (l,r) の選び方) ▪ これは、NC2 = N*(N-1)/2 です ◦ (0を含まない (l,r) の選び方) ▪ 非0 が連続する Aの連続部分列 (のうち最長のもの) を列挙 ans0について 0 2 1 1 1 1 0 1 1 2 1 1 1 1 0 5*4/2 = 10 6*5/2 = 15 1*0/2 = 0 15*14/2 = 105
15. ans2について • ans2の値は、下記の条件を満たす A_l … A_r の数に一致する。 ◦ 2 をちょうど1つ含む ◦ それ以外は、すべて 1 である • これは、一般的に次の形をしています ◦ 左右の left, right は長さが0のこともある ◦ ただし、left, right 両方の長さが0になることはない (l < r のため) 1 1 1 1 2 1 1 1 1 ・・・ left right ・・・
16. ans2について • ans2の値は、このように求まります ◦ A の中で 2が出現する箇所それぞれについて、以下を適用する ▪ 左方向へ 1が連続する限り数を数え、その数をleftとする ▪ 右方向へ 1が連続する限り数を数え、その数をrightとする ▪ ans2 に (left + 1) * (right + 1) - 1 を加算する • 最後に計算量ですが、上記は二重ループを用いる必要がありますが O(N) となります。 ◦ それぞれの 1から見て、左側の2 (のうち最も右側のもの) から走査さ れるか、右側の2 (のうち最も左側のもの) から走査されるかの高々2 回しか参照されないので O(N) 1 1 1 1 2 1 1 1 1 ・・・ left right ・・・
17. D - chutti writer: dokin
18. 問題概要 • 1～9からなる長さNの文字列Sが与えられる • 連続する1文字か2文字を選んで平方根を取る • 操作回数の最大値は？ 例: S = 4936 4936 ⇒ 2936 ⇒ 2336 ⇒ 236 ⇒ 26 答え : 4回
19. 元ネタ 設定の参考にしたもの: https://www.youtube.com/watch?v=XC40Vw4quJw
20. 解説 可能性のある文字列の置換は9通り 1 ⇒ 1 4 ⇒ 2 9 ⇒ 3 16 ⇒ 4 25 ⇒ 5 36 ⇒ 6 49 ⇒ 7 64 ⇒ 8 81 ⇒ 9
21. 解説 置換前の数字別に整理すると以下のようになる 1 ⇒ 1 16 ⇒ 4 81 ⇒ 9 25 ⇒ 5 36 ⇒ 6 4 ⇒ 2 49 ⇒ 7 64 ⇒ 8 25 ⇒ 5 16 ⇒ 4 36 ⇒ 6 64 ⇒ 8 × 81 ⇒ 9 9 ⇒ 3 49 ⇒ 7 1 4 6 2 3 5 8 9 7
22. 解説 複数の選択肢がある文字についてどれを優先して置き換えるか考える 1 ⇒ 1 16 ⇒ 4 81 ⇒ 9 25 ⇒ 5 36 ⇒ 6 4 ⇒ 2 49 ⇒ 7 64 ⇒ 8 25 ⇒ 5 16 ⇒ 4 36 ⇒ 6 64 ⇒ 8 × 81 ⇒ 9 9 ⇒ 3 49 ⇒ 7 1 4 6 2 3 5 8 9 7
23. 解説 1 は 1 ⇒ 1 で無限回操作するのが最善 1 ⇒ 1 16 ⇒ 4 81 ⇒ 9 25 ⇒ 5 36 ⇒ 6 4 ⇒ 2 49 ⇒ 7 64 ⇒ 8 25 ⇒ 5 16 ⇒ 4 36 ⇒ 6 64 ⇒ 8 × 81 ⇒ 9 9 ⇒ 3 49 ⇒ 7 1 4 6 2 3 5 8 9 7
24. 解説 16 ⇒ 4, 81 ⇒ 9 は置換の対象から除外 1 ⇒ 1 16 ⇒ 4 81 ⇒ 9 25 ⇒ 5 36 ⇒ 6 4 ⇒ 2 49 ⇒ 7 64 ⇒ 8 25 ⇒ 5 16 ⇒ 4 36 ⇒ 6 64 ⇒ 8 × 81 ⇒ 9 9 ⇒ 3 49 ⇒ 7 1 4 6 2 3 5 8 9 7 ×
25. 解説 7, 8は使い道がないので、49 ⇒ 7, 64 ⇒ 8 も除外 1 ⇒ 1 16 ⇒ 4 81 ⇒ 9 25 ⇒ 5 36 ⇒ 6 4 ⇒ 2 49 ⇒ 7 ⇒ × 64 ⇒ 8 ⇒ × 25 ⇒ 5 16 ⇒ 4 36 ⇒ 6 64 ⇒ 8 ⇒ × × 81 ⇒ 9 9 ⇒ 3 49 ⇒ 7 ⇒ × 1 4 6 2 3 5 8 9 7 ×
26. 解説 残りの文字についても選択肢が確定する 1 ⇒ 1 16 ⇒ 4 81 ⇒ 9 25 ⇒ 5 36 ⇒ 6 4 ⇒ 2 49 ⇒ 7 ⇒ × 64 ⇒ 8 ⇒ × 25 ⇒ 5 16 ⇒ 4 36 ⇒ 6 64 ⇒ 8 ⇒ × × 81 ⇒ 9 9 ⇒ 3 49 ⇒ 7 ⇒ × 1 4 6 2 3 5 8 9 7 ×
27. 解説 まとめると、下記の貪欲法が最善 1. 1 ⇒ 1 をやれるだけやる 2. 4 ⇒ 2, 9 ⇒ 3 をやれるだけやる 3. 25 ⇒ 5, 36 ⇒ 6 をやれるだけやる 　　　　　　　　　　　　⇒ あとは操作回数を気合で数えればAC！
28. E - Strange Clock writer: Tallfall
29. 問題概要 • 単位時間にA_i周する針がある • 異なる二つが重なる瞬間の数え上げ 例: A_1 = 1, A_2 = 12 答え: 11 回
30. おきもち解説 1. 3つ以上の針が重なる瞬間は考えなくてよい →2つの針が重なる瞬間を考える 2. 2つの針が重なる瞬間はその速度の差のみに依存する →速さの差をDとして1/D, 2/D, 3/D… D/D に重なる 3. 分数を重複なく数えるには既約分数を数えると良さそう 4. i/D が既約分数　<==> iとDが互いに素 →トーシェント関数が使えそう
31. 解説① 3つの以上の針が重なるときは必ず2つの針が重なっているので、 針 i, j が重なる瞬間を考える。
32. 解説② 針 i, j が重なる瞬間を考えると D = |Ai - Aj| として、時刻 1/D, 2/D, … D/D に重なることが分かる。 なのでこの問題は 以上の二つの問題に分割される。 1. 全ての i, j のペアに対して |Ai - Aj| を列挙する。 2. D = {|Ai - Aj| 1 <= i < j <= N } の要素を分母に持つ分数 を重複なく列挙する。
33. 解説③ 1. 全ての i, j のペアに対して |Ai - Aj| を列挙する。 Ai-Aj を列挙することを考える。 Bi = -Ai として、 Ai + Bj が列挙できれば良い。 これは値の制約から畳み込みで高速に計算できる。
34. 解説④ 2. D = {|Ai - Aj| 1 <= i < j <= N } の要素を分母に持つ分数を重複なく列挙する。 例) D = [2, 4] のとき 1/2 2/2 1/4 2/4 3/4 4/4 そのまま数えると重複が生じるので 既約分数を考えると Dの要素の正の約数全てに対してその数と互いに素な数を数え上げればよい これはトーシェント関数や約数包除を用いると高速に計算できる。
35. F - Similar Paths
36. 問題概要 壁1 壁2 障害物のあるグリッドが与えられます。 壁を通らずに左上から右下まで行くパスのうち、1マス 違いのものは同一視します。 このとき、何通りのパスがありますか？
37. 観察1 以下の操作をして相互に変換できるパスを同一視したとき、いくつのパスがあるか数えれば OK
38. 観察2 先ほどの操作で、パスと障害物の上下関係は変わらない 壁1 壁2 左のパスから、先ほどの操作を繰り返して、生成で きるパスに対して、壁 1は常に上側にあるし、壁 2は 常に下側にある
39. 方針 ・同一視されるパスを重複なく列挙する 列挙: 気持ち的には、同一視されるパスのうち「最も上側を通るパス」を列挙する 壁1 壁2 重複なし: 障害物の上下関係を変えることで、重複しないようにする。
40. 解法 以下の方法で生成されるパスを動的計画法で数え上げる 右か下に進むことで、障害物を通らずに、左上から右下まで到達する。 ただし、1度下に降りると、障害物の真下のマスに移動するときしか右に曲がれない Q. 列挙できてるの？ A. 最も上側を通るパスはこの方法で生成できる Q. 重複してないの？ A.上記の方法で生成されるパスで異なる⇒障害物との上下関係が異なる が成立するので観 察2より重複しない 時間空間計算量ともに O(HW) 壁 壁 OK NG
41. G1 - two columns writer: dokin
42. 問題概要 • 2列に並べられたコマに対し、操作を行う • 操作: 縦方向にリバース ⇒ 横方向にリバース • 操作回数の最大値は？
43. 解説 注目するべき性質(おきもち): 　　1列目のコマに対して操作を2回行うと、A[1] - A[2]個分下に移動する。 ⇒コマの動きがシミュレートでき、 各コマがもとにもどってくるまでの周期がわかる
44. 解説 任意のコマは途中で (1,j) (j>A[2]) を通過するので、(1,j) (j>A[2]) におかれたコマについて何回の操作でもとにもど るかを考えれば十分。 j > A[2] に対し、(1,j)におかれたコマがもとにもどってくるまでの回数は、 1. A[1]が奇数かつ j % (A[1] - A[2]) == (A[1]+1) / 2 % (A[1] - A[2]) のとき ◦ 2 × ceil(j / (A[1] - A[2]) + 1 回 2. A[2]が奇数かつ j % (A[1] - A[2]) == (A[1]+1) / 2 % (A[1] - A[2]) のとき ◦ 2 × ceil(j / (A[1] - A[2]) + 1 回 3. その他のとき ◦ 2 × (2 × ceil(j / (A[1] - A[2]) + 1) 回
45. 解説 周期の最小公倍数をとれば、次の 4通りの場合分けになる 1. A[1] - A[2] = 1 の場合 … A[1] + A[2] 2. A[1] - A[2] = 2 かつ A[1] %2 == 1の場合 … A[1] × A[2] 3. A[1] - A[2] > 1 かつ A[2] % (A[1] - A[2]) == 0 の場合 … 2×(2Q + 1) 4. 1.2.3.以外の場合 … 2×(2Q+1)×(2Q+3) 　　　　　　　　　　　　　　　　　　　　　　　　　 (ただし、 Q = floor(A[2] / (A[1] - A[2])) )
46. G2 - three columns writer: dokin
47. 問題概要 • 3列に並べられたコマに対し、操作を行う • 操作: 縦方向にリバース ⇒ 横方向にリバース • 操作回数の最大値は？
48. 解説 解き方はtwo columnsと同じ。場合分けが増えるのでがんばる。 1. 2 × A[3] >= A[1] のとき 2. A[2] + A[3] > A[1] >= 2 × A[3] のとき 3. A[1] >= A[2] + A[3] の3つの場合について各々考察すればよい。 four columns以上はO(sumA)より早く解けない気がする。
49. 統計情報 / FA (オンライン含む) 番号 問題名 AC数 FA A yurufuwa string 52/52 e869120 (0:39) B Super Miraina Tower 47/47 square1001(2:37) C 0,1,2 daifuku 39/42 square1001(8:16) D chutti 36/39 square1001(15:11) E Strange Clock 14/20 beet_aizu(13:51) F Similar Paths 20/20 square1001(31:02) G1 two columns 3/7 square1001(53:32) G2 three columns 0/2 ( heno239 (終了後) )