ctyl's problem solving

競技プログラミングが主な話題です。

AGC012 C Tautonym Puzzle

問題

agc012.contest.atcoder.jp

概要

aaaを2回、bubobubobuboを2回繰り返している。このように長さ1以上の文字列を2回繰り返しているものは良い文字列と定義する。入力  N\leq 10^{12}が与えられるので、良い文字列である部分列の個数が Nである長さ200以下の文字列 sの1例を答えよ。ただし、文字の種類は最大 100種類しか使えない。

解法

まず例えば1, 2, 3, 4, 5, 1, 2, 3, 4, 5という文字列に良い部分文字列がいくつあるかを数えてみる。半分に分割すると、1, 2, 3, 4, 5から1個以上選ぶ方法存在し、それは 2^{5}-1通りであることがわかる( -1は空文字列の場合)。

ここに1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 6, 5のように6を追加すると良い部分文字列がいくつ増えるかを考える。6を含む選び方の数だけ増えるが、65を同時に選ぶことは出来ず、1, 2, 3, 4から0個以上選ぶ方法( 2^{4})通りだけ増える。 別の場合として、1, 2, 3, 4, 5, 6, 1, 2, 3, 6, 4, 5のように6を追加すると、良い部分文字列は1, 2, 3から0個以上選ぶ方法( 2^{3}通り)だけ増える。

このように、新しい文字種のペアを挿入する場所によって、増加する文字列の数を 2^{4}, 2^{3}, 2^{2}, 2^{1}, 2^{0}個増加させることができる。しかもこの挿入は独立なので、 1から 2^{5}-1個まで増加する文字列を1刻みで調節できる。

 N=60の場合を例にすると、下のように文字を追加する。 f:id:ctylim:20170403021926p:plain

 10^{12} \lt 2^{40}より、生成される文字列の長さは 40\times 2+40\times 2=160文字以下、文字の種類は 40 \times 2=80以下となる。よって制約を満たす文字列を作ることができる。

ソースコード

AGC 012 C


こういう構築系は配点がそこそこ高くても思いつき次第でACを狙える時があるので、レート上昇が滞っている今は解ける問題を時間中に貪欲に探していく戦略が大事かも。