たくあんポリポリ

勉強したことを載せていきます。( 主に、C#/ Algorithm / AtCoder / Unity / 最近はKaggleとPython )

【AtCoder】【C#】AtCoder Beginner Contest 157 - C - Guess The Number

f:id:c_taquna:20200115005201p:plain

またしてもやらかしをしてしまったので、色々と反省して次へいかしていきたい所存です。

はじめに

本記事のテーマ

ただの反省記事です。1ケースだけ解決できなかったので、テストケースの内容がわかるまでは、自分で考えた解法は無視して、他の人の解答を見て勉強してみます。

コンテストへのリンク

atcoder.jp

本題

問題概要

整数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メソッドを使うことで、すべての条件を満たすか確認することができるので、いくつかクエリのようなものが与えられたときは、”すべてのクエリの条件を満たす”問題と読み替えることができないか考えていこうと思います。

今回も結果は最悪でしたが、実力だと思うのでもっとできるように頑張っていきたいですね