zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC157-C「Guess The Number」です。
ポイント
方針が少し迷う問題でした。さらに，文字列の操作も頭をひねらせる問題です。
まず，桁数が大きくても3桁であり，与えられる条件も大きくても5個であるため，0から999まで全てに関して全探索を行っても，計算量は$O(10^3 * 5)$であり，間に合います。
文字列の操作としては，int型からstring型に変換するto_string関数と，string型からint型に変換するstoi関数を利用すればOKです。特に，頭に0をつけた文字列が許容されない点に注意してください。
今回は，for文で各桁の数字を考えて，to_stringして調べる対象の文字列にした後に，stoiして頭の0を消して，その後またto_stringするという荒技で乗り切ってみました。
おさえるべき内容
頭の0の取り方
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
int S[10];
char C[10];
int main(){
// 入力フェーズ
int N, M;
cin >> N >> M;
rep(i, M){
cin >> S[i];
S[i]--;
cin >> C[i];
}
// 最小値としての最大値は999なので初期値は1000に設定
int ans = 1000;
// 全探索
rep(i, 10){
rep(j, 10){
rep(k, 10){
// 条件にマッチしているかどうかのフラグ
bool check = true;
// まずは文字列に変換
string a = to_string(stoi(to_string(k) + to_string(j) + to_string(i)));
// 条件全てをみていく
rep(m, M){
if (a[S[m]]!=C[m]) check = false;
}
// もしcheckフラグがtrueで，かつ「頭の0を取り除いた」文字列の長さが0であればansを更新する
if (check && to_string(stoi(a)).size()==N) ans = min(ans, stoi(a));
}
}
}
// もしansが更新されていればその値を出力する
if (ans!=1000) cout << ans << endl;
// もしansが更新されていなければ-1を出力する
else cout << -1 << endl;
}
コメント