SRM486 Div2 500

とぷこだ 過去問

問題

1つしかレジスタがないコンピュータに命令を送って処理させる．入力sと出力tが与えられるので，sからtを作るための一番短い命令列を返す．命令は，「+」「-」「*」「/」がありそれぞれ「レジスタの値 op レジスタの値」が結果としてレジスタの新しい値となる．

考え方

「+」は値を2倍，「-」は値を0にする(使わない)，「*」は値を2乗，「/」は値を1にする，ことがわかる．
そうすると，これらの組み合わせしかないので，探索空間はそんなに大きくならないことがわかる．
なので，BFSで探索して，スタートがsの時と1の時の2つを試してより短い命令列を返すようにした．

反省

文字列比較に「<」を使ってはだめ．
これは，文字列同士をそれぞれ左端から比較していくので，

string a = "abc", b = "b";
a<b //true

BFSなら最初に見つかったものが文字列の長さの最短なモノなので(辞書順的にも)，それぞれ文字列の長さについて比較しればよかった．

a.length()<b.length() //false