Problem F

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
6 > 3+2
{ga}にfを割り当て
サブスコープ
3 : saa
2 : sab
2 : sba
貪欲法(step 2)
スコープの最大割り当て数
= max(max{スコープに属する変数の頻度},
sum{サブスコープの最大割り当て数})
6 : f
4 : gb
4 < 3+2
{saa,sba}にjを割り当て
サブスコープ
3 : saa
2 : sab
2 : sba
貪欲法(step 3)
スコープの最大割り当て数
= max(max{スコープに属する変数の頻度},
sum{サブスコープの最大割り当て数})
6 : f
4 : gb
4>2
{gb}にffを割り当て
サブスコープ
3 : j
2 : sab
2 : j
貪欲法(step 4)
スコープの最大割り当て数
= max(max{スコープに属する変数の頻度},
sum{サブスコープの最大割り当て数})
6 : f
4 : ff
0<2
{sab}にfjを割り当て
サブスコープ
3 : j
2 : sab
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
f
j
ff
fj
<=
<=
<=
<=
6
5
4
2
:
:
:
:
ga
saa,sba
gb
sab
マージ
サブスコープ
3 : saa
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;
VAR f;
f = hoge;
同じ変数名を
使用可能
暗黙のスコープ

特殊例への対処
変数宣言でスコープを作る
2. サブスコープが閉じた直後にスコープを作る
3. サブスコープが閉じた後の変数宣言でスコープ
を作る
1.
暗黙のスコープ
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)
 n変数，mスコープ
暗黙のスコープへの対処を2or3で
 割り当て順序をまとめる処理をn回に抑える
 DP,


まとめる先のほうが小さければswapすることで可能
この問題ではO(m n log n)で十分

Download Report