【AtCoder】【C#】AtCoder Beginner Contest 157 - C - Guess The Number
またしてもやらかしをしてしまったので、色々と反省して次へいかしていきたい所存です。
はじめに
本記事のテーマ
ただの反省記事です。1ケースだけ解決できなかったので、テストケースの内容がわかるまでは、自分で考えた解法は無視して、他の人の解答を見て勉強してみます。
コンテストへのリンク
本題
問題概要
整数N,Mが与えられ、ちょうどN桁になる整数が存在する場合は最小となる値を出力せよ。(Mの値は実際の問題を確認してください)
正解となる実装
static void Main(string[] args) { var input = Console.ReadLine().Split().Select(int.Parse).ToArray(); var N = input[0]; var M = input[1]; var sc = Enumerable.Repeat(0, M).Select(_ => Console.ReadLine().Split().Select(int.Parse).ToArray()).ToArray(); for (int i = 0; i < 1000; i++) { var s = i.ToString(); if (s.Length != N) continue; if (!sc.All(x => s[x[0] - 1] - '0' == x[1])) continue; Console.WriteLine(i); return; } Console.WriteLine(-1); }
考え方
- 今回の問題では、取りうる値の範囲は 0 - 999 なので全探索が可能
- ちょうどN桁になるということは、N=1のときは0-9, N=2のときは10-99, N=3のときは100-999となる
- 仮に、N=3だったときは、100-999の間で与えられた条件(sc)を満たす値が存在するかの確認をすることになる
- 今回の場合、各桁の値が条件を調べる対象となる(100のときは、"1","0","0"の各桁の値に対して、すべてのscが条件を満たしているかどうか)
このあたりを整理すると、LinqのAllメソッドを使用するといい感じにできます。すべてのscが条件を満たしているのかどうか調べるのであれば、sc.All(/条件/)でできます。
それが下の実装です。
if (!sc.All(x => s[x[0] - 1] - '0' == x[1])) continue;
最初に全探索する値を文字列sにしておきます。その文字列の各桁の値とscのcの値を比較して、すべてのscの条件を満たす最初に現れた値が解答です。
反省
今回、NGケースを先に書き出して色々と処理を書いたのですが、どうしても1ケースだけACできず終了してしまいました。
今回学んだこととしては、Allメソッドを使うことで、すべての条件を満たすか確認することができるので、いくつかクエリのようなものが与えられたときは、”すべてのクエリの条件を満たす”問題と読み替えることができないか考えていこうと思います。
今回も結果は最悪でしたが、実力だと思うのでもっとできるように頑張っていきたいですね