Atcoderに取り組んだ際のメモです。
問題はこちら
#結果
Point : 600
Performance : 522
■A[完答 21:03:31] ABC Swap
■B[完答 21:19:22] Popular Vote
■C[完答 21:39:11] Replacing Integer
■D[TLE + バグ] Lunlun Number
■E[未着手] Yutori
■F[未着手] Division or Substraction
#D - Lunlun Number
■問題内容
隣り合うどの 2 つの桁の値についても、差の絶対値が 1 以下になる整数をルンルン数とする。
整数Kが与えられた時、小さい方から数えてK番目のルンルン数を求めよ。
制約：1≤K≤10^5
##コンテスト中に考えた事
- 「制約：1≤K≤10^5」だから1から順にルンルン数であるかチェックしていく全探索で単純にいけそう。
- 探索高速化のロジックが必要(であったが上手くいかない)
- なぜこの探索高速化のロジックが上手くいかないのか
「制約：1≤K≤10^5」だから1から順にルンルン数であるかチェックしていく全探索で単純にいけそう。
そんなに単純ではなかった。そのまま実装したが、テスト段階でTLEが発生した。小さい方からK番目のルンルン数なので、探索する数がKという訳ではないことに気づく必要があった。
探索高速化のロジックが必要(であったが上手くいかない)
小さい数から順に探索する場合、次のルンルン数までたどり着くのに無駄な数をチェックすることが多い。その無駄な探索回数を極力減らせないかというアプローチで探索高速化のロジックを実装した。
i桁目の数とi+1桁目の数の差が1より大きい時が異なる時、次にルンルン数となるのはi桁目に8を足した数の時でないかと推測した。例えば、11,12,…と探索すると13はルンルン数でないことが分かる。この時、13 +8→ 21 から次のルンルン数の候補に21が挙げられ、21はルンルン数なので、再び22,23,…と探索していく。別の例として、124の時、124 +8 → 132 より132となる。これはルンルン数ではないので、再度 132 +80 → 212 より次のルンルン数候補を得、そして212はルンルン数である。
public void Solve(ConsoleInput cin)
{
var K = cin.ReadInt;
long ans = 0;
long count = 0;
if (K <= 12)
{
WriteLine(K);
return;
}
ans = 20;
count = 12;
while (true)
{
ans++;
//WriteLine(ans);
var isRunrun = true;
var chars = ans.ToString().ToArray();
for (int i = 0; i < chars.Length - 1; i++)
{
var gap = chars[i] < chars[i + 1] ? chars[i+1] - chars[i] : chars[i] - chars[i + 1];
if (gap > 1)
{
isRunrun = false;
var wk = 1;
for(var l = 0; l < chars.Length - 2 - i; l++)
{
wk *= 10;
}
ans += 8 * wk - 1;
break;
}
}
if (isRunrun)
{
count++;
//WriteLine("count : {0} ans : {1}" ,count,ans);
}
if (count == K) break;
}
WriteLine(ans);
}
しかし、この方法ではルンルン数の探索は確かに早くなるが、このD問題を解く為には不十分であった。
なぜこの探索高速化のロジックが上手くいかないのか
このD問題では、小さい方から数えてK番目のルンルン数を求める必要がある。しかし、先ほどのロジックでは小さい順にルンルン数を算出することが出来なかった。
正しくない例として、124の場合があげられる。先ほどのロジックでは212が次のルンルン数として挙げられる。しかし、次に来るべきルンルン数は、210である。単純に違ってた桁に8を足すだけではうまくいかないようである。
##解答から学んだこと
####解説されていた解法
キューを使って、ルンルン数の条件を満たす数字を昇順に列挙する。
- キューに1,2,3,4,5,6,7,8,9を投入する。
- キューから数字を1つ取り出して、その数字を左にシフトして作れる数字をキューに投入する。
例えば、1を取り出し多場合は、10の位が1になり、1の位に使用可能な数字は0,1,2なので、10,11,12をキューに投入する。 - K回繰り返すと出てくる数が解答となる。
####自分の解法と解説されていた解法との差
私の解法と解説されていた解法では明らかに違う点が、ルンルン数探索へのアプローチの方法である。
解説されていたものではルンルン数のみを列挙していたことに対し、私の解法ではルンルン数への探索を減らすことを前提としていた。私の解法でもあるルンルン数と次のルンルン数への規則性を利用しようとしていた。しかし、その規則性を突き詰めぬまま、探索ありきの考えに固執していた為、上記のようなロジックとなってしまった。
#提出したコード（解説を元に実装）
キューを使用することでこんなにもシンプルに実装することが出来た。キューを使った実装は初めてだったので、新鮮で面白かった。今後はキューを使用するという発想も持てるようにしたい。
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;
namespace AtCoder
{
public class Program
{
public static void Main(string[] args)
{
new Program().Solve(new ConsoleInput(Console.In, ' '));
}
public void Solve(ConsoleInput cin)
{
var K = cin.ReadInt;
var LunLunNumber = new Queue<long>();
//キューに１～９を追加
for (int i = 1; i < 10; i++)
{
LunLunNumber.Enqueue(i);
}
var count = 0;
long ans = 0;
while (true)
{
count++;
if (count >= K)
{
ans = LunLunNumber.Dequeue();
break;
}
//次のルンルン数をキューに追加する
var num = LunLunNumber.Dequeue();
var numMod10 = num % 10;
if (numMod10 != 0) LunLunNumber.Enqueue(num * 10 + numMod10 - 1);
LunLunNumber.Enqueue(num * 10 + d);
if (numMod10 != 9) LunLunNumber.Enqueue(num * 10 + numMod10 + 1);
//WriteLine(num);
}
WriteLine(ans);
}
}
public class ConsoleInput
{
private readonly System.IO.TextReader _stream;
private char _separator = ' ';
private Queue<string> inputStream;
public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
{
this._separator = separator;
this._stream = stream;
inputStream = new Queue<string>();
}
public string Read
{
get
{
if (inputStream.Count != 0) return inputStream.Dequeue();
string[] tmp = _stream.ReadLine().Split(_separator);
for (int i = 0; i < tmp.Length; i++)
inputStream.Enqueue(tmp[i]);
return inputStream.Dequeue();
}
}
public string ReadLine { get { return _stream.ReadLine(); } }
public int ReadInt { get { return int.Parse(Read); } }
public long ReadLong { get { return long.Parse(Read); } }
public double ReadDouble { get { return double.Parse(Read); } }
public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
}
}