EX26 - 3.06 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

説明ページに戻る

問題文

この問題は難易度が高いので、詰まったらヒントを見てみて下さい。

変数と配列を扱える電卓を作成してください。
電卓の操作は次のようにプログラムに似た命令の形式で与えられます。1行目の入力は命令の行数を表します。

入力例

4
int x = 1 + 2 ;
print_int x + 3 ;
vec a = [ 1 , 2 , x ] ;
print_vec a + [ 4 , 5 , 6 ] ;

出力例

6
[ 5 7 9 ]

命令の形式

電卓の操作は次の命令のいずれかで表されます。
それぞれの命令の終わりには必ず1つのスペースとセミコロン;があり、=の前後には必ず1つのスペースがあります。

形式 例 説明
int <変数名> = <int式> ; int x = 1 + 2 ; 整数の変数を宣言
print_int <int式> ; print_int x + 3 ; 整数の値を出力
vec <変数名> = <vec式> ; vec a = [ 1 , 2 , x ] ; 配列の変数を宣言
print_vec <vec式> ; print_vec a + [ 4 , 5 , 6 ] ; 配列の値を出力

print_vec命令は[ 値1 値2 ... 値N ]という形式で出力します。
C++プログラムで表すと次のようになります。このプログラムをそのまま回答に利用しても構いません。 

// 問題文の形式でvec値を出力
void print_vec(vector<int> vec) {
  cout << "[ ";
  for (int i = 0; i < vec.size(); i++) {
    cout << vec.at(i) << " ";
  }
  cout << "]" << endl;
}

形式の詳細

  • <変数名>は小文字のアルファベット1文字で表されます。

  • <int式>は以下の形式のいずれかで表されます。

形式 例 説明
<int項> 1, x など 1桁の正の整数
または事前にint 命令で宣言された<変数名>
<int項> <演算子> <int項> <演算子> ... <演算子> <int項> x + 3 <演算子>は+または-
  • <vec式>は以下の形式のいずれかで表されます。
形式 例 説明
<vec項> [ 1 , 2 , x ], aなど 詳細は次の表
<vec項> <演算子> <vec項> <演算子> ... <演算子> <vec項> a + [ 4 , 5 , 6 ] <演算子>は+または-
  • <vec項>は以下の形式のいずれかで表されます。
形式 例 説明
<vec値> [ 1 , 2 , x ] [ <int項> , <int項> , ... , <int項> ]の形式
<int項>と,と]はスペース1つで区切られていることに注意
<vec変数> a 事前にvec命令で宣言された<変数名>

計算の定義

式 計算 例
<int項> + <int項> 整数の加算 1 + 2 → 3
<int項> - <int項> 整数の減算 1 - 2 → -1
<vec項> + <vec項> 要素ごとの加算 [ 1 , 2 , 3 ] + [ 4 , 5 , 6 ] → [ 5 , 7 , 9 ]
<vec項> - <vec項> 要素ごとの減算 [ 1 , 2 , 3 ] - [ 3 , 2 , 1 ] → [ -2 , 0 , 2 ]

制約

  • 1 \leq N \leq 10
  • 配列の要素数は2以上5以下
  • <int式>に現れる<int項>の数は5以下
  • <vec式>に現れる<vec項>の数は5以下
  • すでに存在する変数が定義されることはない
  • 存在しない変数が式の中で使われることはない
  • 要素数の異なる配列同士の計算は存在しない
  • その他計算できない不正な命令が入力されることはない

入力

入力は次の形式で標準入力から与えられます。 

N
命令1
命令2
\vdots
命令N

出力

print_intまたはprint_vecの結果

ジャッジでは以下の入力例以外のケースに関してもテストされることに注意。

入力例1

4
int x = 1 + 2 ;
print_int x + 3 ;
vec a = [ 1 , 2 , x ] ;
print_vec a + [ 4 , 5 , 6 ] ;

出力例1

6
[ 5 7 9 ]

問題文で説明した例です。

入力例2

2
print_int 1 - 2 ;
print_vec [ 1 , 2 , 3 ] - [ 3 , 2 , 1 ] ;

出力例2

-1
[ -2 0 2 ]

計算結果が負になることもあります。

入力例3

1
print_int 5 ;

出力例3

5

入力例4

1
print_vec [ 1 , 2 ] ;

出力例4

[ 1 2 ]

入力例5

2
int x = 1 ;
print_int x ;

出力例5

1

入力例6

2
vec a = [ 3 , 4 ] ;
print_vec a ;

出力例6

[ 3 4 ]

入力例7

4
int x = 1 ;
int y = 2 ;
int z = 3 ;
print_int x + y + z ;

出力例7

6

入力例8

4
vec a = [ 1 , 2 , 3 ] ;
vec b = [ 4 , 5 , 6 ] ;
vec c = [ 7 , 8 , 9 ] ;
print_vec a + b + c ;

出力例8

[ 12 15 18 ]

入力例9

6
vec a = [ 1 , 2 ] ;
vec b = a + [ 3 , 4 ] ;
vec c = a - [ 5 , 6 ] ;
print_vec a ;
print_vec b ;
print_vec c ;

出力例9

[ 1 2 ]
[ 4 6 ]
[ -4 -4 ]

ヒント1

ヒント1はちょっとしたアドバイスでしかないので、気軽に開いて良いです。

クリックでヒントを開く 今回の問題は少し長いプログラムを書く必要があります。
機能を一つずつ作っていき、正しく動いているかをコードテストで確認しましょう。

入力3から入力6は特にプログラムのテストに有用です。
まずはこれらの入力に対して正しく出力できるプログラムを作ると良いでしょう。

上記の入出力例だけでは原因が分かりにくいバグが発生した場合は、手動で入出力例を作ってみてテストするのも一つの手です。

ヒント2

ヒント2ではこの問題を解く際に使えるSTLの関数を示します。

クリックでヒントを開く

  • stoi関数：文字列を数値に変換（3.01で解説）
使用例
stoi("123") == 123 // true
  • isdigit関数：文字が数値かどうか判定（3.06で紹介）
使用例
char c;
cin >> c;
// isdigit関数はchar型を引数に取ることに注意
if (isdigit(c)) {
  cout << "cは数字" << endl;
}
else {
  cout << "cは数字でない" << endl;
}

なお、これらの関数を使わずに解くことも可能です。 入力には1桁の正の整数しか出てこないため、それだけに対応するstoiやisdigit相当の関数は数行程度で書くことができます。

ヒント3

ヒント3では解答例で実装した関数の概要とmain関数を示します。実装方針の参考にしてください。

クリックでヒントを開く

// 問題文の形式でvec値を出力
void print_vec(vector<int> vec)

// 変数名を読み取りイコールを読み飛ばす
string read_name()

// int式の項を1つ読み取る。
// 数字ならその値を返し、そうでないなら変数として解釈し変数の値を返す
// var_int : intの変数を保持するmap
int read_int(map<string, int> &var_int)

// int式全体を読み取って計算する
// var_int : intの変数を保持するmap
int calc_int(map<string, int> &var_int)

// vec値を読み取る
// 最初の"["は読み取ってある前提であることに注意
// var_int : intの変数を保持するmap
vector<int> read_vec_val(map<string, int> &var_int)

// vec式の項を1つ読み取る
// vec値ならその値を返し、そうでないなら変数として解釈し変数の値を返す
// var_int : intの変数を保持するmap
// var_vec : vecの変数を保持するmap
vector<int> read_vec(map<string, int> &var_int, map<string, vector<int>> &var_vec)

// vec式全体を読み取って計算する
// var_int : intの変数を保持するmap
// var_vec : vecの変数を保持するmap
vector<int> calc_vec(map<string, int> &var_int, map<string, vector<int>> &var_vec)


int main() {

  // 命令の行数を取得
  int N;
  cin >> N;

  map<string, int> var_int; // intの変数を管理するmap
  map<string, vector<int>> var_vec; // vectorの変数を管理するmap

  // 行数分の処理
  for (int i = 0; i < N; i++) {

    // 命令を受け取る
    string s;
    cin >> s;

    // int命令の処理
    if (s == "int") {
      // 変数名を読み取る
      string name = read_name();
      // 右辺の式を計算して変数に代入
      var_int[name] = calc_int(var_int);
    }

    // vec命令の処理
    if (s == "vec") {
      // 変数名を読み取る
      string name = read_name();
      // 右辺の式を計算して変数に代入
      var_vec[name] = calc_vec(var_int, var_vec);
    }

    // print_int命令の処理
    if (s == "print_int") {
      // 式を計算して出力
      cout << calc_int(var_int) << endl;
    }

    // print_vec命令の処理
    if (s == "print_vec") {
      // 式を計算して出力
      print_vec(calc_vec(var_int, var_vec));
    }
  }
}

テスト入出力

書いたプログラムがACにならず、原因がどうしてもわからないときだけ見てください。

クリックでテスト入出力を見る

テスト入力1
10
int d = 9 + 1 + 2 - 3 + 1 ;
int x = d - 3 - 2 + 1 + d ;
int k = x - d + d + x - x ;
vec c = [ d , x , k , 1 , x ] ;
vec u = [ 8 , 9 ] ;
vec n = [ 1 , 2 , 3 , 4 , 5 ] ;
vec s = [ 6 , 7 ] ;
print_vec u + s + u + s - u ;
print_vec n - c - c - c + n ;
print_int x + k + k - d + x ;
テスト出力1
[ 20 23 ]
[ -28 -44 -42 5 -38 ]
54
テスト入力2
10
int l = 7 - 6 - 5 - 4 + 8 ;
vec q = [ l , l , l , l ] ;
int e = 9 + 9 + 9 + 9 + 9 ;
print_vec [ 9 , 5 , 3 ] + [ 2 , 4 , 6 ] - [ 8 , 8 , 8 ] - [ 2 , 2 , 2 ] ;
print_int 8 + 8 + 8 ;
int z = e + e + e + e + e ;
int b = z + z + z + z + z ;
print_vec q + [ e , z , z , z ] ;
int r = b + b + b + b + b ;
print_int r + z + b + e + l ;
テスト出力2
[ 1 -1 -1 ]
24
[ 45 225 225 225 ]
7020
テスト入力3
10
vec j = [ 3 , 3 , 4 ] ;
vec a = [ 2 , 8 ] ;
vec s = [ 5 , 2 , 6 , 3 ] ;
vec t = [ 1 , 1 , 1 , 1 ] - s - s - s - s ;
vec o = [ 2 , 2 , 2 , 2 ] - s - s - s - s ;
print_vec s ;
print_vec a + a + [ 9 , 9 ] - a ;
print_int 7 ;
print_vec [ 2 , 5 , 2 , 5 ] ;
print_vec s - o - o - o + s ;
テスト出力3
[ 5 2 6 3 ]
[ 11 17 ]
7
[ 2 5 2 5 ]
[ 64 22 78 36 ]

解答例

必ず自分で問題に挑戦してみてから見てください。

クリックで解答例を見る

細かく関数分けされたプログラムなので、main関数から処理の流れを追うように読むと良いです。 

#include <bits/stdc++.h>
using namespace std;

// 問題文の形式でvec値を出力
void print_vec(vector<int> vec) {
  cout << "[ ";
  for (int i = 0; i < vec.size(); i++) {
    cout << vec.at(i) << " ";
  }
  cout << "]" << endl;
}

// 変数名を読み取りイコールを読み飛ばす
string read_name() {
  string name, equal;
  cin >> name >> equal;
  return name;
}

// int式の項を1つ読み取る。
// 数字ならその値を返し、そうでないなら変数として解釈し変数の値を返す
// var_int : intの変数を保持するmap
int read_int(map<string, int> &var_int) {
  string val;
  cin >> val;

  // 最初の文字が数字かどうかで数字か変数かを判定（3.06で紹介した条件演算子を使用。if文で書いても良い。）
  return isdigit(val.at(0))
    ? stoi(val) // 数値の場合
    : var_int.at(val); // 変数の場合

  // isdigit関数は3.06で、stoi関数は3.01で紹介している
  // これらを使わず自分で変換する処理を書いても良い
}

// int式全体を読み取って計算する
// var_int : intの変数を保持するmap
int calc_int(map<string, int> &var_int) {

  string symbol = ""; // 演算子を受け取る変数
  int result = 0; // 結果を保持する変数

  // 式の終わりである";"が出てくるまで読み取る
  while (symbol != ";") {
    // 項を1つ読み取る
    int val = read_int(var_int);

    // 記号が入力されてない場合（式の最初の項）は結果にそのまま代入
    if (symbol == "") {
      result = val;
    }
    // 足し算の場合
    if (symbol == "+") {
      result += val;
    }
    // 引き算の場合
    if (symbol == "-") {
      result -= val;
    }

    // symbolには"+", "-", ";"のいずれかが入力される
    cin >> symbol;
  }

  return result;
}

// vec値を読み取る
// 最初の"["は読み取ってある前提であることに注意
// var_int : intの変数を保持するmap
vector<int> read_vec_val(map<string, int> &var_int) {

  vector<int> result; // 結果を保持する変数
  string symbol = ""; // vec値中の記号を受け取る変数

  // vec値の終わりである"]"が出てくるまで読み取る
  while (symbol != "]") {
    // 数値を1つ読み取ってvecに追加
    int val = read_int(var_int);
    result.push_back(val);

    // symbolには","か"]"が入力される
    cin >> symbol;
  }

  return result;
}

// vec式の項を1つ読み取る
// vec値ならその値を返し、そうでないなら変数として解釈し変数の値を返す
// var_int : intの変数を保持するmap
// var_vec : vecの変数を保持するmap
vector<int> read_vec(map<string, int> &var_int, map<string, vector<int>> &var_vec) {

  string val;
  cin >> val;

  // "["かどうかでvec値か変数かを判定（3.06で紹介した条件演算子を使用。if文で書いても良い。）
  return val == "["
    ? read_vec_val(var_int) // vec値の場合
    : var_vec.at(val); // 変数の場合
}

// vec式全体を読み取って計算する
// var_int : intの変数を保持するmap
// var_vec : vecの変数を保持するmap
vector<int> calc_vec(map<string, int> &var_int, map<string, vector<int>> &var_vec) {

  string symbol; // 演算子を受け取る変数
  vector<int> result; // 結果を保持する変数

  // 式の終わりである";"が出てくるまで読み取る
  while (symbol != ";") {

    // 項を1つ読み取る
    vector<int> vec = read_vec(var_int, var_vec);

    // 記号が入力されてない場合（式の最初の項）は結果にそのまま代入
    if (symbol == "") {
      result = vec;
    }
    // 足し算の場合
    if (symbol == "+") {
      for (int i = 0; i < result.size(); i++) {
        result.at(i) += vec.at(i);
      }
    }
    // 引き算の場合
    if (symbol == "-") {
      for (int i = 0; i < result.size(); i++) {
        result.at(i) -= vec.at(i);
      }
    }

    // symbolには"+", "-", ";"のいずれかが入力される
    cin >> symbol;
  }

  return result;
}

int main() {

  // 命令の行数を取得
  int N;
  cin >> N;

  map<string, int> var_int; // intの変数を管理するmap
  map<string, vector<int>> var_vec; // vectorの変数を管理するmap

  // 行数分の処理
  for (int i = 0; i < N; i++) {

    // 命令を受け取る
    string s;
    cin >> s;

    // int命令の処理
    if (s == "int") {
      // 変数名を読み取る
      string name = read_name();
      // 右辺の式を計算して変数に代入
      var_int[name] = calc_int(var_int);
    }

    // vec命令の処理
    if (s == "vec") {
      // 変数名を読み取る
      string name = read_name();
      // 右辺の式を計算して変数に代入
      var_vec[name] = calc_vec(var_int, var_vec);
    }

    // print_int命令の処理
    if (s == "print_int") {
      // 式を計算して出力
      cout << calc_int(var_int) << endl;
    }

    // print_vec命令の処理
    if (s == "print_vec") {
      // 式を計算して出力
      print_vec(calc_vec(var_int, var_vec));
    }
  }
}