Problem E

Day 3 Problem E
First Experience
ACM/ICPC
Japanese Alumni Group
講評担当: 吉野
Rev 1.1
基本情報
• 野田によるオリジナル問題
問題概要
• 与えられた規則に従って動く簡易計算機を
シミュレートせよ
– レジスタが 3 つあり
– 数字が入力されたら …
– 演算子(+, -, *, =)が入力されたら …
– 途中の演算結果が負値や 10000 を超えたら
エラー表示
サブミット状況
• Total 18 submits
– 9 accepts
– First accept: 13min. (kitsune-)
• だいたい 1 発で通してくれたところが多い
– かなりハマっていたチームもありましたが…
解法
• 超易問
– 上位チームは 10 分くらいで書いてほしい
• ともかく問題の要請どおりに実装するのみ
– As you will easily see ;-)
– 他に言うこともありません
散見された間違い (1)
• 範囲外のチェック忘れ
– この問題ではチェックすべき箇所が 2 箇所ある
• 数字入力のとき、R2 の値をチェック
– 12345*0= ⇒ E
• 演算子入力のとき、R1 の値をチェック
– 100*100= ⇒ E
– 両方やってはじめて OK なのですが、片方だけ忘れる
ケースが見られました
• 演算子はつながって入力されることがあります
– 123+++++++++++++4= ⇒ 127
– 123**1= ⇒ 0
• なぜこうなるかは問題をよく読んで！
散見された間違い (2)
• 数値の解釈法に誤り
– 数値を読もうと atoi, strtol を安易に使ってはダメ
• - が数字の最初にあっても E になるとは限りません
– 123+-4= ⇒ 119 (E 出しちゃだめよ)
– 4+5+4*0+17++*7++-4= ⇒ 115 (実際のデータより)
• atoi 等は + や – を符号として解釈してしまう
• 数字まで(いくつも演算子が重なっているかもしれないのを)処理
してから使うのであれば大丈夫です
– 「キーストロークごとに」と書いてある通りやればよい
• このレベルの問題でひっかけを気にする必要はない
• またパフォーマンスを気にするようなサイズでないことは問題文
から明らか
実装のテクニック
• エラーを例外で通知すると結構便利
– 関数外からも大域脱出できる
• goto などでは同一スコープ内のみ脱出可
– 値をチェックする関数をこんな風に書ける
int check_value(const int v)
{
if(v < 0 || v > 9999) throw "Overflow.";
return v;
}
– 上の関数のつかいかた
r2 = check_value(r2 * 10 + key – ‘0’);
実装のテクニック
• C/C++ の人は関数ポインタを活用すると楽
– R3 は演算子を保持していて云々
• 単純にやると switch-case をいちいち書く必要
• もちろんマクロである程度抽出できるにせよ面倒
– 関数ポインタを使うとこれだけ
int (*r3)(const int, const int) = NULL;
#define OPERATOR(func) \
r1 = r3 ? check_value(r3(r1, r2)) : r2, r2=0, r3=func
switch(s[i]) {
case '+': OPERATOR(op_add); break;
case '-': OPERATOR(op_sub); break;
case '*': OPERATOR(op_mul); break;
case ‘=’: OPERATOR(NULL); return r1;
}
まとめ
• 簡単な問題なのでみなさん解きましょう
– 今回のように他の問題の間にまざっていることが
ありますので、問題探しは念入りに
• 必ずしも問題が難易度順に並んでいるとは限りません
– こういう実装系問題では、下手に凝るとはまる
可能性があります
• 特に atoi, strtol を使ったチーム
– 標準ライブラリを使うこと自体は悪いことではないのですが、
ちゃんと中身の挙動を把握して使うようにしましょう
• くれぐれも問題の要請に従ったプログラミングをして
ください

Download Report