Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
第6回ゆるふわオンサイト解説
Search
forcia_dev_pr
February 10, 2024
0
170
第6回ゆるふわオンサイト解説
コンテストページ
※
https://mofecoder.com/contests/yurufuwa_onsite_06
forcia_dev_pr
February 10, 2024
Tweet
Share
More Decks by forcia_dev_pr
See All by forcia_dev_pr
第7回ゆるふわオンサイト解説
forcia_dev_pr
0
130
よくわかるFORCIAのエンジニア旅行SaaSプロダクト開発編
forcia_dev_pr
0
490
よくわかるフォルシアのエンジニア 新卒採用編
forcia_dev_pr
0
2.7k
第5回ゆるふわオンサイト解説
forcia_dev_pr
0
110
よくわかるフォルシアのエンジニア 旅行プラットフォーム部編
forcia_dev_pr
0
4.7k
React hooks を気合で理解する
forcia_dev_pr
0
300
k8sマニフェストを Typescriptで管理したい― cdk8s+を導入してみました ―
forcia_dev_pr
0
300
第4回ゆるふわ競技プログラミングオンサイト解説
forcia_dev_pr
0
480
フォルシアのフレームワークとTypeScript
forcia_dev_pr
0
280
Featured
See All Featured
KATA
mclloyd
29
14k
A Modern Web Designer's Workflow
chriscoyier
693
190k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
4
370
Visualization
eitanlees
145
15k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
10
720
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
16
2.1k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
665
120k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
191
16k
The Cult of Friendly URLs
andyhume
78
6k
Product Roadmaps are Hard
iamctodd
PRO
49
11k
Happy Clients
brianwarren
98
6.7k
For a Future-Friendly Web
brad_frost
175
9.4k
Transcript
第6回ゆるふわオンサイト 解説スライド 1 writer/tester: dokin, Tallfall, ayaoni, prd_xxx, tempura0224, momohara
他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
A - Gachi Onsite 問題概要 与えられる長さ N の文字列 S に含まれる
gachi の部分を、すべて yurufuwa に 置換してください。 例 gachionsite → yurufuwaonsite gachigachionsite → yurufuwayurufuwaonsite 3
A - Gachi Onsite 解法(C++) 4
A - Gachi Onsite 解法(Python) 5
B - Yurufuwa Teaming 問題概要 ゆるふわコンテストはN人1組ででて、N問題が出題され、1人1問を担当して解 いて合計点数を競います。 問題iをときたい希望者がAi人いるので、ΣAi/Nチーム作ることにしました。 できるだけ希望が叶うようチーム分けしてください。 6
B - Yurufuwa Teaming 例 N=3, A={3,2,1} 7 問題1希望! 問題2希望!
問題3希望! 問題1 問題2 問題3 チーム1 チーム2 5人希望がかなう!
B - Yurufuwa Teaming 解法 各問題について、チーム数分担当者がいます チーム数までなら希望を叶えられます - チーム数 M=ΣAi
/N - 希望が叶う数 Σmin(M, Ai) 8
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に到達しない!
C - 153 問題の背景 ayaoni の大学時代、学祭の学科ブースにて・・・ 10 ブースに来てくれたおじさん 153 は凄い数なんだよ~
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
C - 153 解法 • 部分点解法 ◦ 循環するまで愚直にシミュレーションし続ければ良い ▪ 循環し始めたとき、M
が 153 でなければ永遠に 153 には辿り着かない • 153 は操作を加えても 153 であることに注意 ▪ 逆に M が 153 になっているときは、それまでの step 数を答えればよい • 満点解法 ◦ 愚直にやると1回目の操作に O(N) かかってしまい TLE になる ◦ 予め O(N) かけて三乗和の累積和を求めておくことで、1回目の操作を O(1) で行えるように なる ◦ 残りは部分点解法に同じ 12
C - 153 補足 • 任意の正の3の倍数は、操作を有限回繰り返すと 153 に行きつきます! ◦ 10000
以上の場合は操作後に M が減少することと、10000 未満の数が 153 に行きつくこ とから示せます • また、3の倍数以外は決して 153 には辿り着きません ◦ 操作前後で 3 で割った余りが不変であることから示せます ▪ 10^i * a ≡ a ≡ a^3 (mod 3) から分かります • 10000 未満の結果を下計算しておくと、より早く実行できます ◦ この下計算をせずとも、多くの言語で AC できる想定です 13
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
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
D - Bbubel oSrt 解法 前から決めていく 次にBに置きたい要素をXとして、XがAで最初に出てくるindexをiとすると、 • X より小さい全ての値について、
その値が最初に出てくる index が i より大きい が成立していれば OK 16
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
D - Bbubel oSrt 解法(満点) 部分点の操作のうち、判定の部分はそのままやると O(値の種類数)かかるが セグメントツリー(1点更新、区間 max)で高速に判定可能 O(N
logN) (セグメントツリーを使う判定方法なら、A そのものをセグメントツリーに載せて も解くことができるはず) 18
E - Parenthesis Candidate 問題概要 ( と * からなる文字列が与えられる。* を
( or ) にいい感じに変更して、正規 な括弧列になるものを「括弧列の候補」という。 連続部分文字列で括弧列の候補となるものを数えよ 19 (***(* ( ( ) ) ( )
E - Parenthesis Candidate 解法 20 「括弧列の候補」であるための必要十分条件 ・長さが2以上の偶数 ・(を1,*を-1に置き換えて累積和を取ったときに、末尾が最小になる 0
1 0 -1 -2 -1 -2 ( * * * ( *
E - Parenthesis Candidate 証明 偶数が必要条件に含まれるのは明らか ある位置の*を(にすることは、累積和の配列で、自身以降に+2することに同じ これを繰り返して、累積和の配列の全ての要素を0以上かつ末尾を0にできればよい 最後尾の値から、( にできる数は一意に定まり、最後尾は必ず+2されるので、最小
が必要 逆にそれさえ満たせば、手前から ( にしても破綻しない場所をひっくり返せばいい 21
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 最大長方形のアルゴリズムなどを見よう!
F - n!+(n+1)!+(n+2)! 問題概要 非負整数 N, A が与えられます。次の式を満たす整数 の個数を 998244353
で割った余りを求めてください。(T ケース) 制約 • 1 ≦ T ≦ 20 • 0 ≦ N ≦ 10^8 • 0 ≦ A ≦ 10^5 23
F - n!+(n+1)!+(n+2)! Step1: ビットに関する式に変形する となるため、与えられた式は と変形できる。ここで となるので、 となり、ビットに関する式に変形できた。 24
F - n!+(n+1)!+(n+2)! Step2: 式を変形し数え上げられる形にする n が奇数のときは比較的容易なため、以下 n が偶数とする。 とおくと
と変形できる。 25
F - n!+(n+1)!+(n+2)! Step2: 式を変形し数え上げられる形にする さらに とおき、m + 1 を次のような形で表す。
このとき m は次のような形になる。 26
F - n!+(n+1)!+(n+2)! Step2: 式を変形し数え上げられる形にする ゆえに となるので、与式はさらに次のように変形できる。 であったことを思い出すと、求める値は次の通り。 27
F - n!+(n+1)!+(n+2)! Step3: 計算量がNに比例しないようにする この式をそのまま計算しようとすると、1ケースあたり O(N + A) の計算量が必
要であり、TLE してしまう。 そこで求める値を次のように差の形で書いてみる。 28
F - n!+(n+1)!+(n+2)! Step3: 計算量がNに比例しないようにする ここで第一項に注目し、非負整数 i に対して とおくと が成立する。(フィボナッチ数列)
ゆえに第一項の値 は O(log(N + A)) の計算量で求められる。 一方第二項は O(A) で求められるため、最終的に O(log(N) + A) で求められた。 29
G - Koiwai Coffee 問題概要 32 コ イワ イ コ
ー ヒ ー コ * ワ イ * ー * * これ何通り?
G - Koiwai Coffee 解法 (簡単のため、全て-1の場合) 33 なぜこの問題は難しいのか? 区切り方を全探索して両方を回文にすればいいのでは? ⇒
以下のようなパターンでダメ ABABABAB ABABABAB 4回数える!! ABABABAB ABABABAB
G - Koiwai Coffee 重要な性質 34 ・ある文字列が周期的かつ、回文 + 回文の形で書けるとき、その 文字列の1周期も、回文
+ 回文の形で書ける ・ある文字列が周期的かつ、回文 + 回文の形で書けるとき、0文字 以上の回文 + 1文字以上の回文に分ける分け方は、文字列の最大の 周期数に等しい。特に最大周期1なら分け方は一意 ABABABAB ABABABAB ABABABAB ABABABAB ABABABABの1周期 (AB) は回文 + 回文と書ける 周期4だが、分け方は4通り
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にエンコード)
G - Koiwai Coffee 解法 (-1以外も含む) 36 本質的にやることは同じ ・Nの約数dに対して、長さdで周期的でないもので、回文 +
回文と書けるものを数え て約数包除 一方で、長さdから長さNが必ず復元できるとは限らない ・A*AB*Bが入力されたときに、長さ3の文字列を2つつなげた文字列は元の 数列と絶対に一緒にならない (元の数列が周期的ではないため) 長さdのものが回文 + 回文でかけないケースもある ・ABCA*Cが入力されたときに、長さ3の数列 (ABC) は回文 + 回文の形で書 けない。
G - Koiwai Coffee 解法 (-1以外も含む) 37 ・文字列の前d文字をN/d個つなげたものが、周期的になるように、長さd の文字列を構成する。(確定する部分とwild cardな部分が出るはず)
・この文字列に対して、(区切り方,回文 + 回文となる文字列) の組は何通 りか?を数えて約数包除をする 2番目の操作はwild card matchingなどのたたみこみで行える Nの約数dに対して、長さdの列のたたみこみを行うので、 全体の計算量はO((Nの約数の総和)logN)になる。
各問題の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はオンサイトより速かった場合のみ表記しております。
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