JOI2013 本選1 Illumination 解説

OkNCT-ICT 2013 春合宿 Day 5 (らしい) で解説したもの.

Transcript

1. JOI 2013 本選 1 Illumination 解説 @kagamiz
2. 問題の概要 • 白黒で , 長さが N の電飾があります . ◦◦••◦•◦◦◦• • ある区間を反転させて ( 反転させなくても良 い ), できるだけ長い交互列 ( 隣同士の色が 違う区間 ) を作りたい .
3. 問題例の復習 　◦◦••◦•◦◦◦•　← これを長くしたい ◦◦•◦•◦•◦◦• • こう反転させると長さが 7 の交互列になる . ◦◦••◦•◦•◦• • こうしても良い .
4. 解答に移る前に • コンピュータはぱない機械ですが , 神では無 いので 1 秒あたりに処理できる命令に限度 があります . • あるアルゴリズムで問題を解こうと考えたと きに , そのために必要な処理の回数を計算 量と言います ( 正確な定義ではない ).
5. アルゴリズムの計算量 • 計算量は , 通常「何に比例するか」で考えて , それをアルゴリズムのオーダーという . • 最初のうちはプログラム中のループの個数を 数えることが多く , たとえばループが 3 重 になっている箇所があれば O(N^3) 時間の アルゴリズムという .
6. アルゴリズムの計算量 • 計算量は , 通常「何に比例するか」で考えて , それをアルゴリズムのオーダーという . • アルゴリズムのオーダーが分かれば , O(f(N)) の N に実際に N の最大値を入れてみて , 時間制限に間に合うか考えてみる . • 1 秒制限で f(N) ≦ 10^7 位なら大体 OK.
7. O(N^3) 時間のアルゴリズム • ◦◦••◦•◦◦◦• • 実際に切る場所を , 2 重ループで 2 つ決め打 ち . ← O(N^2) • その後に , その区間を反転して , 交互列の長 さの最大値を探す .← O(N) • 3 重ループなので合計 O(N^3).
8. O(N^3) 時間のアルゴリズム • 区間の反転は？ • 前もって反転した配列を用意すると楽 .
9. ( ^o^) 区間の反転はできた
10. ( ^o^) 区間の反転はできた • ( ⊖ ) ˘ ˘ 。 o( 交互列の長さの最大値は？ )
11. ( ^o^) 区間の反転はできた • ( ⊖ ) ˘ ˘ 。 o( 交互列の長さの最大値は？ ) • |JOI2013 本選 コード [ 検索 ]| ┗(☋ ｀ )┓ 三
12. ( ^o^) 区間の反転はできた • ( ⊖ ) ˘ ˘ 。 o( 交互列の長さの最大値は？ ) • |JOI2013 本選 コード [ 検索 ]| ┗(☋ ｀ )┓ 三 • ( ) Run-Length ◠‿◠ ☛ 圧縮の応用じゃ w
13. ( ^o^) 区間の反転はできた • ( ⊖ ) ˘ ˘ 。 o( 交互列の長さの最大値は？ ) • |JOI2013 本選 コード [ 検索 ]| ┗(☋ ｀ )┓ 三 • ( ) Run-Length ◠‿◠ ☛ 圧縮の応用じゃ w • ▂▅▇█▓▒░(’ω’) █▇▅▂ ░▒▓ うわあああ
14. 交互列の長さを求める • Run-Length 圧縮では , となりと同じならま とめる , 違ったら新しく始める , といった 感じで縮約していったが , 今回はその逆 . • となりと違ったらまとめる , 同じだったら新 しく始める .
15. 交互列の長さを求める • となりと違ったらまとめる , 同じだったら新 しく始める . • 擬似コード for ( すべての電飾 ) : if ( 前の電飾と違う色 ) then 長さ = 長さ +1 else 長さを配列に格納 . 長さ = 1. 長さを配列に格納 .
16. O(N^3) 時間のアルゴリズム • 結局何点とれるの？ • 最悪 (10^5)^3 = 10^15. • 10^15?? • 10^15[msec] = 31709.7919838 年 ... • やばい (20 点が得られる )
17. O(N) 時間のアルゴリズム ◦|◦•|•◦•◦|◦|◦• • よくみてみよう
18. O(N) 時間のアルゴリズム ◦|◦•|•◦•◦|◦|◦• • 実際にひっくり返さなくても
19. O(N) 時間のアルゴリズム ◦|◦•|•◦•◦|◦|◦• • 隣り合う線に挟まる区間をひっくり返すと良 い！！ ( 隣り合わない区間をひっくり返し ても ... 死 )
20. O(N) 時間のアルゴリズム ◦|◦•|•◦•◦|◦|◦• • 隣り合う 3 つの区間を考えて , 間をひっくり 返せば交互列 . やったぜ . • 3 つも区間が無いときはうしろに 2 つ なが さ 0 の区間を入れると考えやすい .
21. O(N) 時間のアルゴリズム • まとめ for ( すべての電飾 ) : if ( 前の電飾と違う色 ) then 長さ = 長さ +1 else 長さを配列に格納 . 長さ = 1. 長さを配列に格納 . • これをする ( 長さ 0 を 2 つ足すと good) • 配列の隣り合う 3 つの和の最大値が答え .
22. O(N) 時間のアルゴリズム • O(N) 時間で働く . 実装も綺麗 . • 10^2[msec] = 100msec = 0.1s ( 実際はもっと 早いくらい ). • 文化祭もうまくいきそう . 100 点
23. ちなみに ◦◦••◦•◦◦◦• • 偶数番目をひっくり返すと ◦••◦◦◦◦•◦◦ • Run-Length して 3 つの区間和を求めるだけ