ACPC 2018 Day3 F: 01 文字列と窓 (Binary String with Slit)
0 likes320 views
2018/9/21 会津大学プログラミング合宿 Day3 (北大セット) F 問題 ※文字が見えない場合、ダウンロードするかフルスクリーンにしてご覧ください。(フルスクリーンにすると文字が消える問題に対処できるようです)
![[DL輪読会]Clebsch–Gordan Nets: a Fully Fourier Space Spherical Convolutional Neu...](https://cdn.slidesharecdn.com/ss_thumbnails/20181214clebschgordanmizuta-181214051939-thumbnail.jpg?width=560&fit=bounds)
More Related Content
What's hot (16)
More from HCPC: 北海道大学競技プログラミングサークル (20)
Recently uploaded (11)
ACPC 2018 Day3 F: 01 文字列と窓 (Binary String with Slit)
- 1. 会津合宿 2018 Day3 F 問題 01 文字列と窓 (Binary String with Slit) 原案: tsutaj 問題文: TAB 解答: tsutaj?rsk0315?tsukasa_diary 解説: tsutaj 2018 年 9 月 21 日 tsutaj ACPC 2018 Day3 F 2018/9/21 1 / 12
- 2. 問題 01 文字列と窓 (Binary String with Slit) 01 文字列 S に対する操作 1 回分を以下で定義 S を 2 進数として見た時の LSB を含むように幅 2 のスリットを置く スリット内の数値を +1 するか -1 する ただし、1 ≤ 変更後のスリット内の数値 ≤ 3 01 文字列 Si を Ti に変えるための操作回数の最小値を求める このようなクエリが Q 回来るので処理する 制約 1 ≤ Q ≤ 105 2 ≤ |Si| = |Ti| ≤ 50 Si, Ti は 0 と 1 のみからなる Si, Ti はともに 1 を少なくとも 1 つ含む tsutaj ACPC 2018 Day3 F 2018/9/21 2 / 12
- 3. 想定誤解法 以下、N は文字列の長さとする BFS などで毎回求める クエリ 1 回につきオーダーが O(2N ) だし、それを 105 回やることが要 求されているし、まず無理 全点対最短経路問題 グラフの頂点数を M とすると O(M3 ) かかり、この問題において頂点 は 2N 個存在するのだから、この問題においては O(2N3 ) かかる。まず 無理 tsutaj ACPC 2018 Day3 F 2018/9/21 3 / 12
- 4. アプローチ この問題は気づけば一瞬です スリット内の数値の Before / After を考えよう パターンはかなり少ない (たった 4 通り) 10 → 01 10 → 11 ! 11 → 10 01 → 10 各 01 文字列を頂点と見なし、1 回の操作で到達できるもの同士に辺を 張ってグラフを作ってみよう tsutaj ACPC 2018 Day3 F 2018/9/21 4 / 12
- 5. アプローチ こんな感じになるが???もう少し綺麗に書いてみよう tsutaj ACPC 2018 Day3 F 2018/9/21 5 / 12
- 6. アプローチ 整形すると、このように完全二分木 (それぞれの辺は相互に移動可能) に なる tsutaj ACPC 2018 Day3 F 2018/9/21 6 / 12
- 7. 遷移 遷移 (1) tsutaj ACPC 2018 Day3 F 2018/9/21 7 / 12
- 8. 遷移 遷移 (2) tsutaj ACPC 2018 Day3 F 2018/9/21 8 / 12
- 9. 遷移 遷移 (3) tsutaj ACPC 2018 Day3 F 2018/9/21 9 / 12
- 10. 遷移 遷移 (4) tsutaj ACPC 2018 Day3 F 2018/9/21 10 / 12
- 11. 遷移 クエリに答えるときは、以下のように Si と Ti の LCA を求め、パス の長さを求めれば良い 木が大きすぎてダブリングで LCA を求めることはできないが、木が平 衡なので高さは高々 50 程度 つまりパスの長さは高々 100 程度なので愚直に求めても間に合う Q = 105 でもこれなら余裕 tsutaj ACPC 2018 Day3 F 2018/9/21 11 / 12
- 12. Writer 解?統計 Writer 解 tsutaj (C++?43 行?954 bytes) rsk0315 (C++?29 行?513 bytes) tsukasa_diary (C++?37 行?687 bytes) 統計 AC / tried: 14 / 36 (38.9 %) First AC On-site: acpc_Fixstars (69 min) On-line: LLma (93 min) tsutaj ACPC 2018 Day3 F 2018/9/21 12 / 12