2020年3月16日に開催されたAtCoder Beginner Contest 157に参加しました。C問題が解けず非常に悔しかったです。解説などを見てようやくACし、その中の学びをふりかえっておきます。
【結果】
順位 4126th / 6597
パフォーマンス 411
レーティング 105 → 135 (+30)
問題
問題文
以下の条件を満たす 0 以上の整数が存在すれば、それらのうち最小のものを出力してください。そのような整数が存在しなければ、 -1と出力してください。
・十進表記で丁度 N 桁である。(0 は1 桁の整数とする。その他の整数については、先頭に 0 をつけた表記は認めない。)
・左から数えて si 桁目はci である。(i=1,2,⋯,M)
制約
入力は全て整数
・1≤N≤3
・0≤M≤5
・1≤si≤N
・0≤ci≤9
解法
https://img.atcoder.jp/abc157/editorial.pdf
解法1
0以上10のN乗未満の整数を全て調べます（全探索）。
解法2
M個の条件について、矛盾が存在しないかを前から順に確かめつつ解の候補を絞り、最後にそれらの最小値を出力します。
ふりかえり
コンテスト中は問題を理解したと思って実装しましたが、WA*1が8個も出ていて皆目検討つかない状態でした。コンテスト後に、解説や他参加者の解答を見てようやく自分の理解が誤っていたことに気づきました。
大前提としてこの問題は解法1の全探索で実装した方が楽です。実装方法を考える時は常に全探索で解を制限時間*2内に求められるかを考えることはするべきと改めて思いました。
コンテスト時のアプローチは、解法2の方向でした。しかし、問題内容を理解できておらず誤った実装をしていました。WAが大量に出た時は問題理解に不足/誤りがあり、もう一度問題内容の理解を確認する必要があると思いました。１度入力された桁に再度入力を行う場合は、これまでと同じ値が入力されなければならない、という部分を理解できていなかったです。例えば、
N=2, M=2
s1=1, c1=2
s2=1, c1=1
は-1と出力すべき、10ではない。
解法2で解く場合、以下のパターンを考慮する必要があります。
| パターン | 対応 |
|---|---|
| １度入力された桁に異なる値が入力されていないか | -1を出力 |
| M=0 | Nに応じた最小値を設定(0, 10, 100) |
| N=1 | 1桁目0が許容される |
| N>2で1桁目が未入力 | 1桁目に1を設定 |
| N>2で1桁目が0 | -1を出力 |
| N>2で2桁目以降が未入力 | 未入力の桁に0を設定 |
実装方法は様々ありますが、上記考慮をしようとするとかなりややこしいことになります。しかも私はとりあえずで実装したので、出口が5箇所もあるクソコードになりました。。
実装(Rust)
解法2
use std::io::*;
use std::str::FromStr;
use std::collections::HashMap;
fn read<T: FromStr>() -> T {
let stdin = stdin();
let stdin = stdin.lock();
let token: String = stdin
.bytes()
.map(|c| c.expect("failed to read char") as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().expect("failed to parse token")
}
fn main() {
let n: u8 = read();
let m: usize = read();
let mut map = HashMap::new();
let mut flag = true;
for _i in 0..m {
let s: u8 = read();
let c: u8 = read();
let value = map.entry(s).or_insert(c);
//同じ桁で異なる値が設定された場合
if c != *value {
flag = false;
}
}
//答えを作れない場合
if flag == false {
println!("-1");
return;
}
//1桁の場合
if n == 1 && m != 0{
print!("{}", map.get(&1).unwrap());
return;
}else if n == 1 {
print!("0");
return;
}
//2桁以上の場合
//1桁目が未設定の場合
if map.get(&1) == None {
print!("1");
//1桁目が0設定の場合
} else if map.get(&1) == Some(&0) {
println!("-1");
return;
//1桁目が0以外設定の場合
} else {
print!("{}", map.get(&1).unwrap());
}
for i in 2 .. n + 1 {
if map.get(&i) == None {
print!("0");
} else {
print!("{}", map.get(&i).unwrap());
}
}
}
解法1
参考：ABC157【C問題の反省とD問題の復習】まだまだ、そこらへんもなんとなくわかる程度でごまかしている｜Takahiro Nakamori｜note
use std::io::*;
use std::str::FromStr;
fn read<T: FromStr>() -> T {
let stdin = stdin();
let stdin = stdin.lock();
let token: String = stdin
.bytes()
.map(|c| c.expect("failed to read char") as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().expect("failed to parse token")
}
//参考
//https://note.com/tak_nakamori/n/n00a17b49b69d
fn main() {
let n: usize = read();
let m: usize = read();
let mut sc: Vec<(u8,u8)> = Vec::new();
for _i in 0..m {
sc.push((read(),read()));
}
//Nごとに最小/最大+1の値を設定する
//最大+1なのはループ範囲の設定のため
let start:[usize;3] = [0, 10, 100];
let end:[usize;3] = [10, 100, 1000];
//Nに合わせて小さい数から全探索
for i in start[n - 1]..end[n - 1]{
//一文字ごとに判定するため文字列へ変換
let str:String = i.to_string();
//答えが存在するかのフラグ
let mut flg = true;
// 1桁ごと確認する。
// 見ている桁とs_iが同じだったら、
// その桁の値とc_iが同じかチェックする。
// 値とc_iが異なると答えは存在しない。
for j in 0..n {
for k in 0..m {
if (j as u8) + 1 == sc[k].0 {
if sc[k].1 != str[j..j+1].parse().unwrap() {
flg = false;
}
}
}
}
// flgがtrueのままfor文が終わった最初のiが答え。
if flg == true {
println!("{}", i);
return;
}
}
println!("-1");
}
まとめ
実装方法を考える時は常に全探索で解を制限時間内に求められるかを考える。
正しく問題内容を理解する。WAが多い場合は問題理解に誤りがある可能性が高い。
