Problem F Two-finger Programming

Presentation on theme: "Problem F Two-finger Programming"— Presentation transcript:

1 Problem F Two-finger Programming
解答：寺島・林崎 英文：寺島・吉野 解説：寺島

2 解答状況 Submitted : 1 (1 teams) Solved : 1
First Accepted : 211 min (echizen.bat)

3 問題概要 プログラムの変数名の付け替え できるだけ短くしたい 使っていい文字は’f’,’j’のみ

4 プログラムの文法 重要なのは２点 字句解析は極めて簡単 構文解析はほとんど不要 ‘{‘’}’の対応と識別子だけ見れば十分

5 解法(1) 貪欲法 最大に割り当てられる変数集合から短い名前を割り当てていく 独立したスコープの変数には同じ名前を割り当てられる点に注意

6 貪欲法(step 1) スコープの最大割り当て数 = max(max{スコープに属する変数の頻度},
sum{サブスコープの最大割り当て数}) サブスコープ 6 : ga 4 : gb 3 : saa 2 : sab 6 > 3+2 {ga}にfを割り当て 2 : sba

7 貪欲法(step 2) スコープの最大割り当て数 = max(max{スコープに属する変数の頻度},
sum{サブスコープの最大割り当て数}) サブスコープ 6 : f 4 : gb 3 : saa 2 : sab 4 < 3+2 {saa,sba}にjを割り当て 2 : sba

8 貪欲法(step 3) スコープの最大割り当て数 = max(max{スコープに属する変数の頻度},
sum{サブスコープの最大割り当て数}) サブスコープ 6 : f 4 : gb 3 : j 2 : sab 4 > 2 {gb}にffを割り当て 2 : j

9 貪欲法(step 4) スコープの最大割り当て数 = max(max{スコープに属する変数の頻度},
sum{サブスコープの最大割り当て数}) サブスコープ 6 : f 4 : ff 3 : j 2 : sab 0 < 2 {sab}にfjを割り当て 2 : j

10 貪欲法(step 5) スコープの最大割り当て数 = max(max{スコープに属する変数の頻度},
sum{サブスコープの最大割り当て数}) サブスコープ 6 : f 4 : ff 3 : j 2 : fj 2 : j

11 解法(2) DP スコープの割り当て順序を求める 短い名前から順に割り当てる サブスコープの割り当て順序をまとめる
各サブスコープのi番目の変数集合を同じ名前を割り当てる変数集合とする そのスコープに属する変数を出現頻度でソートし，マージする 短い名前から順に割り当てる

12 DP 6 : ga 4 : gb 3 : saa 2 : sab f <= 6 : ga j <= 5 : saa,sba
サブスコープ 6 : ga 4 : gb 3 : saa 2 : sab f <= 6 : ga j <= 5 : saa,sba ff <= 4 : gb fj <= 2 : sab マージ 2 : sba 5 : saa,sba 2 : sab サブスコープをまとめる

13 特殊な扱いが必要な例 IF(hoge) { VAR foo; foo = 1; } hoge = 0; VAR bar;
bar = hoge; IF(j) { VAR f; f = 1; } hoge = 0; f = hoge; 同じ変数名を 使用可能

14 暗黙のスコープ 特殊例への対処 変数宣言でスコープを作る サブスコープが閉じた直後にスコープを作る
サブスコープが閉じた後の変数宣言でスコープを作る

15 暗黙のスコープ IF(hoge) { {VAR foo; foo = 1; }} hoge = 0; {VAR bar;
bar = hoge; } IF(hoge) { VAR foo; foo = 1; }{ hoge = 0; VAR bar; bar = hoge; } IF(hoge) { VAR foo; foo = 1; } hoge = 0; {VAR bar; bar = hoge;

16 計算量 O(n log n + m) この問題ではO(m n log n)で十分 n変数，mスコープ
DP, 暗黙のスコープへの対処を2or3で 割り当て順序をまとめる処理をn回に抑える まとめる先のほうが小さければswapすることで可能 この問題ではO(m n log n)で十分