プログラミング備忘録

プログラミングに関することをつらつらと。

AtCoder Regular Contest 060 + AtCoder Beginner Contest 044

競技プログラミング

解法メモ

A問題

合計の宿泊費は、N \leq K ならば NX 円、N>K ならば KX+(N-K)Y 円。

B問題

w はたかだか100文字なので、どの文字がいくつあるか先頭から順に数えていって、奇数個の文字がひとつでもあれば"No"、ひとつもなければ"Yes"を出力する。

C問題

動的計画法で解く。
dp[i][j][k] を、x_1 から x_i までのカードから j 個とって合計を k にすることができるカードの取り方の総数とする。すると、
\begin{eqnarray} dp[i][j][k] = \begin{cases} 1 & ( i = j = k = 0 ) \\ dp[i-1][j][k] & (i \geqq 1\ \mathrm{and}\ k < x_i ) \\ dp[i-1][j][k] + dp[i][j-1][k-x_i] & (i \geqq 1\ \mathrm{and}\ j \geqq 1\ \mathrm{and}\ k \geqq x_i ) \\ 0 & (\mathrm{otherwise}) \end{cases} \end{eqnarray}
と漸化式が立てられる。カードの平均が A となるような組み合わせの数は \sum_{k=1}^N dp[i][k][kA] だから、これを出力する。

上とは別に、

D問題

s = n のときは明らかに b = n+1。0 から n までの数が各桁に使われるのは基数が n+1 以上の場合に限られるし、基数が n 以下のときに各桁の和が n になることはない。
2 \leq b \leq n について愚直に f(b,n) を計算すると時間がかかってしまうので、よい方法を考える。
\sqrt{n} < b のとき、n の b 進数表記は2桁以下になる (n = 100_{(\sqrt{n})})。つまり、b 進数表記が pq のとき、n = pb + q と表される。これより、b = (n-q)/p である。また、p+q=s だから、1+q/p=s/p より b = (n-s)/p+1 となることがわかる。すなわち、p と s の値から b が一意に定まる。こうして定められた b が f(b,n) = s を満たすかどうかを確認すればよい。

E問題

r[i][k] を、i 番目のホテルから 2^k 日以内に到達できる最も右側のホテルの番号 として、まずr[i][0] を求め、次に r[i][k+1] = r[r[i][k]][k] として順次求めることができる。こうしてできたテーブルを二分探索すればよい。

二分探索を工夫する

しかし、C言語の二分探索関数は、値が見つからないとNULLを返してくるので、いちばん近い値を求めるには工夫がいる *1。
今回は自作の二分探索関数を作ることで対応した。要素の数が奇数のときは、見ている範囲の中央にある2つの要素両方を見て判定する工夫を施した。
Submission #860171 - AtCoder Regular Contest 060 | AtCoder
また、最右端まで到達できるときは、最右端の番号ではなくてそれより大きな番号を格納しておくと、「それより少ない日数で最右端に到達できる」ことがすぐにわかる。

F問題

まだよくわかっていない。

キーワード

C問題

動的計画法

*1:このあたりの「かゆいところに手が届く」ライブラリやら関数やらがたくさん揃っているところがC++が人気な理由のひとつなのかもしれない。