Keitai Message 解説

アルゴリズムの概略

与えられた表通りに出力を行えばOKです。 何も押されていない状態で 0（確定ボタン）が入力された場合は何も出力しないことに注意。 また，確定ボタンが押されずに他の文字入力に移る，例えば '1' → '2' というような入力はありません。 典型的な状態遷移型のシミュレーション問題です。

戦略としては2通り考えられます。 一つは，現在の状態 (state) を char s という変数で持ちまわす方法です。 s の初期値は初期状態を表す 0 にでも設定しておいて（ASCIIコードで使われないため = C言語の文字列におけるNULL文字）， 最初に入力 '1' がくれば s = '.' と状態を変化させ， もう一度入力 '1' がくれば s = ',' とさらに状態を変化させていきます （ここで，数字を''で囲んだものはASCIIコードで表される文字の意味です）。 s = ' ' （スペース）のときにさらに '1' がくれば s = '.' に戻します。 入力 '0' が来た場合，現在の状態が初期状態 0 でなければ状態 s をそのまま出力すればOKです。

もう一つの戦略は，数字が何であるかだけを覚えておいて，後はその数字が何回出現したかだけをカウントします。 そして，そのカウント数を対応する種類の数で割った余りを求め（mod を求める），それに対応する文字を出力します。 例えば入力が '1' の場合は「. , ! ? （スペース）」の5種類が存在するので， カウント数が 8 なら 8 % 5 = 3 で3番目の ! を出力します（8 ≡ 3 mod 5）。 この「余りを求める」という作業は，周期性を持つ場合の操作によく使われるので覚えておきましょう（数学的には mod で表します）。

アルゴリズムの計算量

入力1文字に対して定数時間で済むので，文字数 n の1行の入力に対して O(n) で答えを求めることができますので， 計算量は全く問題となりません。

アルゴリズムの実装

入出力の対応表を二次元配列で表すとよいでしょう。 状態遷移アルゴリズムを使う場合，この程度の問題であればswitch文でひたすら場合分けしてもOKです。 ICPCではソースコードの美しさよりコーディング時間が重要になります。

ACM/ICPCではASCIIコード以外の文字列処理は（おそらく）出ません。 ですので，Cでのchar型配列やC++のstringクラスでのASCIIコードの扱いに慣れておきましょう。 stringクラスは普通にコンパイルすればchar型配列のラッパークラスになるので，基本はchar型の処理になります。 char型というのは，一般的には「文字型」であるとされますが，「8ビットint型」（一般的にint8やbyteと呼ばれる型です）と考えた方がしっくりきます。 つまり，'a' という文字列リテラルは数字 97 であると考えるというよりかは，数字 97 を表す別の方法として 'a' という表記法が用意されている，という考え方です。 そうすると，'9' - '0' といった計算（57 - 48 = 9）が納得しやすいでしょう。

なお，C言語では通常文字列の終端は NULL 文字，すなわち 0 で表されます。 これは，文字列というのは可変長の配列なので，終端を表す方法が必要とされるからです （可変長配列の終端を表すには，終端にNULL文字のような番兵を置く方法と，配列長を別に書いておく方法の2種類が一般的に使われます）。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $