Problem F Two-finger Programming 解答：寺島・林崎 英文：寺島・吉野 解説：寺島
解答状況 Submitted : 1 (1 teams) Solved : 1 First Accepted : 211 min (echizen.bat)
問題概要 プログラムの変数名の付け替え できるだけ短くしたい 使っていい文字は’f’,’j’のみ
プログラムの文法 重要なのは２点 字句解析は極めて簡単 構文解析はほとんど不要 ‘{‘’}’の対応と識別子だけ見れば十分
解法(1) 貪欲法 最大に割り当てられる変数集合から短い名前を割り当てていく 独立したスコープの変数には同じ名前を割り当てられる点に注意
貪欲法(step 1) スコープの最大割り当て数 = max(max{スコープに属する変数の頻度}, sum{サブスコープの最大割り当て数}) サブスコープ 6 : ga 4 : gb 3 : saa 2 : sab 6 > 3+2 {ga}にfを割り当て 2 : sba
貪欲法(step 2) スコープの最大割り当て数 = max(max{スコープに属する変数の頻度}, sum{サブスコープの最大割り当て数}) サブスコープ 6 : f 4 : gb 3 : saa 2 : sab 4 < 3+2 {saa,sba}にjを割り当て 2 : sba
貪欲法(step 3) スコープの最大割り当て数 = max(max{スコープに属する変数の頻度}, sum{サブスコープの最大割り当て数}) サブスコープ 6 : f 4 : gb 3 : j 2 : sab 4 > 2 {gb}にffを割り当て 2 : j
貪欲法(step 4) スコープの最大割り当て数 = max(max{スコープに属する変数の頻度}, sum{サブスコープの最大割り当て数}) サブスコープ 6 : f 4 : ff 3 : j 2 : sab 0 < 2 {sab}にfjを割り当て 2 : j
貪欲法(step 5) スコープの最大割り当て数 = max(max{スコープに属する変数の頻度}, sum{サブスコープの最大割り当て数}) サブスコープ 6 : f 4 : ff 3 : j 2 : fj 2 : j
解法(2) DP スコープの割り当て順序を求める 短い名前から順に割り当てる サブスコープの割り当て順序をまとめる 各サブスコープのi番目の変数集合を同じ名前を割り当てる変数集合とする そのスコープに属する変数を出現頻度でソートし，マージする 短い名前から順に割り当てる
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 サブスコープをまとめる
特殊な扱いが必要な例 IF(hoge) { VAR foo; foo = 1; } hoge = 0; VAR bar; bar = hoge; IF(j) { VAR f; f = 1; } hoge = 0; f = 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; } IF(hoge) { VAR foo; foo = 1; } hoge = 0; {VAR bar; bar = hoge;
計算量 O(n log n + m) この問題ではO(m n log n)で十分 n変数，mスコープ DP, 暗黙のスコープへの対処を2or3で 割り当て順序をまとめる処理をn回に抑える まとめる先のほうが小さければswapすることで可能 この問題ではO(m n log n)で十分