AtCoder Regular Contest 046 A,B問題 感想

シェアする

  • このエントリーをはてなブックマークに追加

12/13(日)の21:00-22:30に競技プログラミングサイトAtCoderにて、AtCoder Regular Contest(ARC)046が開催されました。

私も最初から参加したのですが、将棋叡王戦の中継と時間が被っていおり、叡王戦の終盤が非常に面白いことになったので途中から抜け出しました。

そのため、A,B問題は解けましたが、C,D問題は解けていません。(問題は部分点を貰うくらいならできたかと思いますが、叡王戦の盛り上がりに気を引かれました。)

軽く感想と自分の解き方を書いてみます。

A問題 ゾロ目数

1≦N≦50の入力に対して、小さい方からN番目の「ゾロ目数」を返す、という問題。

「ゾロ目数」とは、正の整数で、十進法で書いたときにすべての桁が同じ数字になるような整数と定義されています。

とりあえずゾロ目数を列挙してみると、

1,2,3,4,5,6,7,8,9,

11,22,33,44,55,66,77,88,99,

111,222,...

のように、「k桁のゾロ目数は必ず9個」という法則が理解できます。

高校数学っぽく考えるなら、これは「群数列」ですね。みんな大嫌い群数列(?)

Nが1~9のとき、第1群。10~18のとき、第2群。以下略。

ということで、この数列の第N項は「第[N-1を9で割った商]群」に所属することが分かります。

すなわち、N番目のゾロ目数は(N-1)/9桁となります。。(C言語などの多くのプログラミング言語で、整数型どうしの割り算は商を計算することに注意)

また、「1から9のうち、どの数字が並ぶか」を見ると、もちろん1,2,3,4,5,6,7,8,9,1,2,...となっています。これは、Nを9で割った余りですね!

……と考えてしまって、一回WA(Wrong Answer:誤答)をくらってしまいました。おいおい。

N%9(Nを9で割った余り)で考えると、Nが9の倍数のときに0を並べてしまいます。

したがって、正しい表現は「(N-1)%9+1」となります。9で割った余りは1,2,3,4,5,6,7,8,0,1,2,...と並ぶので、一つ右にずらして全部に1を足せばOK。

以上より、N番目のゾロ目数は「((N-1)%9+1)が、((N-1)/9)桁並んだ数字」となります。

それを踏まえて、

int n;
scanf("%d", &n);
int ans = 0;
while (n > 0)
{
	ans *= 10;
	ans += (n - 1) % 9 + 1;
	n -= 9;
}
printf("%d\n", ans);

とすれば完成です(一部省略しています)。私はC#で提出したのでprintf()ではなくConsole.WriteLine()でしたが。

ただし、これは微妙な解答です。この記事を書きながら、見れなかった解説生放送のタイムシフトを見ているのですが、解説スライドにはこう書いてあります。

「数字(N-1)%9+1を(N-1)/9+1回出力すればいい」

そうです。ゾロ目数を表示さえすればいいので、実際に整数の値を計算する必要は無いのです。ああ、なんと簡単なことでしょう。

つまり、「555(五百五十五)という数字を十進法で表示」するのと、「5」を3回連続で表示するのは、出力だけ見ればまったく同じことです。

AtCoderのジャッジシステムは出力の文字列のみを見るので、実際に理想的なデータ管理や計算がなされる必要は無いのです。

さらに、この問題は「1≦N≦50」という、非常に小さい範囲の入力しか扱わないので、もっと"ひどい"解法があります。

それは、「50個のゾロ目数を書き上げて、全部ソースコードに書き込む方法」です。

int zorome[] = {
	1, 2, 3, 4, 5, 6, 7, 8, 9,
	11, 22, 33, 44, 55, 66, 77, 88, 99,
	...,
	..., 333333, 444444, 555555 };
int n;
scanf("%d", &n);
printf("%d", zorome[n-1]);

とすれば、書き間違いが無い限り、確実に高速に結果を得ることができます。(50番目が555555なのは入力例3から分かります。ちなみに配列の添え字をn-1にすることに注意です。)

これを実際に行っている解答例がこちら。 http://arc046.contest.atcoder.jp/submissions/592469

色々解き方があるもんですねえ。まあ、それなりに楽に解けたので良かったです。A問題ですしね。

B問題 石取り大作戦

タイトルが桃井あずきっぽいですね。

それはさておき、「N個の石山から交互に1つ以上の石を取っていく。最後の石を取った方が勝ち」というゲームです。非常によくあるゲームで、私も必勝法を知っています。

しかし、よく見る石取りゲームと違うのは、非対称性です。

先手の高橋君は一度に最大 A 個までの石を取ることが可能であり、後手の青木君は一度に最大 B 個までの石を取ることが可能です。

とあります。よく見るのは、上限が両者等しい、フェアなゲームです。(フェアと言いつつ、必勝法はあるのですが。)

両者が最善の行動をとり続けたとき、どちらが勝つかを判定せよ、という問題です。

この問題には部分点があり、

この問題には部分点が設定されている。

・A=B を満たすデータセットに正解した場合は 40 点が与えられる。
・A≠B を満たすデータセットに正解した場合は 60 点が与えられる。
・上記の 2 つのデータセット両方に正解することにより合計 100 点が得られる。

とのことです。40点分については、よくあるゲームですね。

さっきから「よくあるゲーム」と言っていますが、実際どれくらい有名なんでしょうね。(解説生放送でchokudaiさんが「非常に有名なゲーム」とおっしゃっています。)

A=Bのとき、端的に言うと「最初の石数が(A+1)の倍数なら後手の勝ち、そうでないなら先手の勝ち」です。

なぜなら、後手は常に「先手が取った数と、足してA+1になる数」つまり「A+1-[先手が取った数]」を取ることができるからです。先手が1つ取ったら後手はA個、先手がA個取ったら後手は1個取ります。

そうすると、毎回、石山の石数から(A+1)を引くことができ、もし最初に(A+1)の倍数となっていれば、(A+1)個になるまでこの操作を繰り返して、最後にもう一度同じことをすると石数を0にできます。すなわち、最後の石を取って勝てます。

一方、初期石数Nが(A+1)の倍数ではないとき、先手はNを(A+1)で割った余りだけ石を取ることで、「初期石数Nが(A+1)の倍数だったときの後手」と同じ状況になることができ、先手必勝になります。

したがって、「A=Bのとき、N%(A+1)=0なら後手、そうでなければ先手が勝つ」となります。

つぎに、A≠Bの場合を考えます。

A=4, B=3として、Nの値を1から順に増やしていって考えてみると、なんとN=8まで先手必勝になりました。(紙に書いてやりました。N>8は面倒なのでやってません)

どうやら多い方が有利みたいです。

しかし、「A≠Bなら、上限値が多い方が勝つ」としてみると、WAになりました。

「多い方が勝つ」というのは正しいのでしょうか?

結論は、正しいです。

A>Bのとき、先手が「Bまでしか取らない」という戦略を取ると、A=Bと同じ状況になり、Nが(B+1)の倍数でないときは先手必勝です。

さらに、Nが(B+1)の倍数のとき、先手は実際はBよりも多く取れるので、(B+1)個取ります。すると、後手に回った段階で石数が(B+1)の倍数。したがって、A=Bでの後手必勝理論により、こうなると先手必勝です。

B>Aのときは、最初に先手が石を取って後手に手番が回ったときに、上記の調整をすればいいのです。

ん?「手番が回ったとき」?

ここがポイントです。このゲーム、「後手に手番が回らない状況」があるのです。

それは、A>Nのとき。

いくらB>Aといっても、N=20、A=100、B=5000とかでは意味がありません、先手が最初に20個取ってゲームセットです。

私はこういうゲームを知っていた先入観から、N>A,Bを勝手に仮定していました。勘違いしていたのです。A≠Bの実験をするときにA>Bしかやらなかったのも悪かった。

ということで、「A>Nなら先手勝ち。そうでないなら、A=Bなら、Nが(A+1)の倍数なら後手勝ち、そうでないなら先手勝ち。A<NでA≠Bなら、A>Bなら先手勝ち、A<Bなら後手勝ち」という、面倒な判定になります。

いやー、単純な問題ではありますが、先入観とか勘違いは怖いもんです。色んな場合を想定して実験しないといけませんね。

ちなみに、両者最善手をとったときの結果なので、将棋プログラムの記事で名前だけ出した「ミニマックス法」が使えるかと思いきや、1≦N,A,B≦10^9なので、再帰を用いるとメモリがオーバーします。

と書きながら、解説生放送でもっと分かりやすい「N>AかつA≠Bのときは上限が多い方が勝つ」の説明がなされました。こちらのスライドをご覧ください→ http://www.slideshare.net/chokudai/arc046

以上、ARC046のA,B問題の感想でした。C問題も解いてみたいと思っているので、解いたときか諦めて解説を見たときに記事を書くかもしれません。では。

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする