monkukui のページ

競技プログラミングや北海道のおいしいご飯について書きます

PAST：第一回 アルゴリズム実技検定の解説　〜 エントリーを目指して 〜

はじめに

アルゴリズム実技検定，通称「PAST」とは，AtCoder 株式会社が主催するプログラミングの実技検定です．

past.atcoder.jp

検定結果に応じて，エキスパート，上級，中級，初級，エントリーの 5 段階の認定が与えられます． PAST の特徴は，選択肢回答による知識型の検定試験とは異なり，1 からアルゴリズムを考えプログラムを書かせて実行し，その結果で能力を判定する点です． つまり，実践的なコーディング力を正確に測ることができる検定だと言えるでしょう．

2019/12/14 に第一回目の検定が実施され，受験した結果「エキスパート」の認定が授与されました！ 今回は，出題された計 15 問のうち，前半 4 つの問題の解説，およびソースコードの掲載を試みます． なお，掲載されるコードは C++ です．ご了承ください．

A 問題「2 倍チェック / Is It a Number?」

A - 2 倍チェック / Is It a Number?

問題概要

長さ 3 の文字列 s が与えれれる． s の各文字が '0' 〜 '9' であるなら， s を数としてみた値に 2 倍した値を出力せよ． そうでない場合，"error" を出力せよ．

制約

s の長さは 3 である． s の各文字は数字または英小文字である．

解説

いきなり気をつけることが多い問題です． 以下のステップでコードを書くと，正解が得られます．

  • 各文字は '0' 〜 '9' であるか．
for (auto c: s) {
  if (isdigit(c)) ...

と書けます.

  • 文字列を整数に変換する．

std::stoi 関数で，std::string 型から int 型への変換ができます． 例えば "00112" という文字列も 112 という整数に変換してくれます．便利ですね．

  • 最後に 2 倍して出力

ソースコード

int main(){
    
  string s; cin >> s;
  for(int i = 0; i < 3; i++) {
    if(!isdigit(s[i])) {
      cout << "error" << endl;
      return 0;
    }
  }

  int n = stoi(s);
  cout << 2 * n << endl;

  return 0;
}

B 問題「増減管理 / Up and Down」

B - 増減管理 / Up and Down

問題概要

長さ n の数列 a_1, a_2, \ldots, a_n が与えられる． 各 i (2 \leq i \leq n) に対して， a_{i - 1} \lt a_i なら "up" と a_i - a_{i - 1} を空白区切で， a_{i - 1} \gt a_i なら "down" と a_{i - 1} - a_i を空白区切で， a_{i - 1} = a_i なら "stay" を出力せよ．

制約

2 \leq n \leq 100000

解説

for 文と if 文が書けるかを問う問題です． A 問題より，こちらの方が簡単に感じました．

ソースコード

int main(){
  
  int n; cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];

  for(int i = 1; i < n; i++) {
    if(a[i] == a[i - 1]) cout << "stay" << endl;
    else if(a[i] > a[i - 1]) cout << "up " << a[i] - a[i - 1] << endl;
    else cout << "down " << a[i - 1] - a[i] << endl;
  }
  return 0;
}

C 問題「3 番目 / The Third」

C - 3 番目 / The Third

問題概要

6 つの整数が与えられるので，小さい方から 4 番目の整数を出力せよ．

解説

std::vector や配列などで整数を受け取り，昇順ソートした後に 4 番目の値を出力します． ソートに関しては自分で実装する必要はなく，多くのプログラミング言語の標準機能で使えます． ここまで解けると「エントリー」の認定が与えられます．

ソースコード

int main(){
  vector<int> a(6);
  for(int i = 0; i < 6; i++) cin >> a[i];
  sort(a.begin(), a.end());
  cout << a[3] << endl;
  return 0;
}

D 問題「重複検査 / Duplicated?」

D - 重複検査 / Duplicated?

問題概要

長さ n の数列 a_1, a_2, \ldots, a_n が与えられる． 数列 a は，長さ n の順列の，高々 1 つの値が 1 \leq x \leq n を満たす整数 x に書き換わったものである．（一つも書き換わっていない可能性もある）

書き換わりが発生していなければ "Correct" を出力し， 書き換わりが発生していれば， 書き換わった後の整数と書き換わる前の整数を空白区切で出力せよ．

制約

1 \leq n \leq 200000

解説

各値が何回出現したかを調べます． 1 から n までの全ての値がちょうど 1 回づつ出現していれば，"Correct" を出力します． そうでない場合，書き換わる前の値の出現回数は 0 になり，書き換わった後の値の出現回数は 2 になるので，そのような二つの値を探して出力します． 計算量は O(n) です．

ソースコード

int main(){
  
  int n; cin >> n;
  // cnt[i] := 値 i が何回出現したか
  vector<int> cnt(n + 1, 0);
  for(int i = 0; i < n; i++) {
    int a; cin >> a;
    cnt[a]++;
  }
  
  bool ok = true;
  for(int i = 1; i <= n; i++) {
    // 値が書き変わらない場合，全ての値はちょうど 1 回出現している．
    if(cnt[i] != 1) ok = false;
  }

  if(ok) {
    cout << "Correct" << endl;
  } else {
    // from から to に値が書き換わる．
    int to;
    int from;
    for(int i = 1; i <= n; i++) {
      if(cnt[i] == 0) from = i;
      if(cnt[i] == 2) to = i;
    }
    cout << to << " " << from << endl;
  }
  return 0;
}

最後に

当初は全問題の解説を試みていましたが，途中で挫折しました． そのことをえびちゃん（@rsk0315）に伝えたら，たった 1 日で全問題の解説記事を書き上げてくれました． E 問題以降の解説はこちらを参照してください．