hotpepsiの練習帳

SRM 553

03:05

Div1 Easy (250) Suminator

問題

• Suminatorは加算だけ可能なスタックマシンである。
• プログラムとして非負の整数の配列が与えられ、順番に実行する。
• スタックへは、プログラムが0なら2値を足して格納し、0以外ならそのまま格納する。
• 最後にスタックの先頭を表示して終了する。
• 一箇所だけ書き換えて結果をwantedResultにするための最小の数値を求める。

方針

• 書き換える場所をPOSとする
• POSを0に書き換えてシミュレーションし、結果がwantedResultなら0を返す(最小ケース)
• POSを1に書き換えてシミュレーションした結果をXとする
• XがwantedResultなら1を返す
• XがwantedResultより小さくて、かつ、Xを求めるためにPOSのデータを使っているなら、可能なのでwantedResult-X+1を返す
• それ以外は不能(-1)
• あらかじめスタックにはサイズの2倍だけ0を積んでおいた
• POSを使っているかどうかは、std::pairのsecondに入れておいた
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_553/Suminator.cpp

結果

o-- 164.13pt 206th rating 1251 -> 1344 (+93)

素直に考えて普通に書いたら通った。良い感じ。

longにしてないコードがたくさんあったようで結構落ちていた。