AtCoder ABC198
ABC198参加しました。
A - Div
必ず両者に最低一個以上割り当てられるので、どちらも1~N-1個もらえます。 割り当て方は、片方に$x$個($1 \le x \le N-1$)割り当てたら、もう片方の割当は自動的に決まります($N-x$個) よって、割り当て方は$N-1$個です。
解説 - AtCoder Beginner Contest 198
B - Palindrome with leading zeros
公式解答は桁数の制約を利用して0~9個文字の頭につけて回分かどうか判定しているので、わかりやすいです。 私は0を考えたくなかったので、文字の後ろにある0を除去した文字列を作成して、それが回文になるかを考えて解きました。0は言ってしまえばいくらでも前に付け足せるので、末尾の0は抜いてしまっても回文を考えるのに支障はありません。
解説 - AtCoder Beginner Contest 198
C - Compass Walking
ちょっとおもしろかった問題。 最短距離で原点から$(X,Y)$に向かうには、その直線状をたどっていけばいいということを思い、図を書いていたらひらめきました。
原点と$(X,Y)$を結ぶ直線$l$の距離を$d$とします。赤い円の半径は$R$です。この$l$の上を$R$ずつ進んでいけば(動点$p$が点線上を進んでいきます)無駄がありません。最後に$(X,Y)$を中心とした距離$R$の円上の交点に逸れれば、その点から$(X,Y)$に1歩でたどり着けます。
よって$d / R$をした結果で以下のようになります。
- きっちり割り切れる場合は、ただただ直線$l$状を$R$ずつ刻んで行く。この場合最後の交点は2つの円とただ一点で接する場所になる。
- あまりが出る場合は、$l$の上を$R$ずつ進みつつ、最後に$(X,Y)$を中心とした距離$R$の円に逸れて$(X,Y)$に向かうことで、1手だけ多くなる
これをまとめれば、回数は$\lceil d / R \rceil$となります。
ただ、これだけではだめで、例外として$d \le 2R$の場合があります。つまり以下のような場合です。
この場合は必ず2手でたどり着けます。1手目を円と円の交点に飛び、そこから$(X,Y)$に向かえばいいです。
解説 - AtCoder Beginner Contest 198
D - Send More Money
あんまりおもしろくなかった...
覆面算です。公式解答を自分なりに解釈した結果を書いてみます。
まず大前提として、使える数は10種類なので、これを超える文字の種類があったら絶対に解けませんので、UNSOLVEDを出力します。
覆面算の例として、問題例にあったsend more moneyを使ってみます。
この筆算を以下のように分解してみます。また、筆算では見えない係数を書いてみました。
$1000s + 100e + 10n +d + 1000m + 100o + 10r + e - 10000m - 1000o - 100n - 10e - y = 0$
筆算の下(答え)の部分は、式を移行したので係数がマイナスになります。更にまとめると、
$1000s + 91e - 90n +d - 9000m - 900o + 10r + e - y= 0$
まとめてみると以下の式が成立すればいいことになります。
$$ \boldsymbol{s} \cdot \boldsymbol{c} = 0 $$ ここで2つのベクトルは以下のように定義してます。 $$ \boldsymbol{s} = \left( \begin{array}{c} s \ e \ n \ d \ m \ o \ r \ y\ \end{array} \right) $$
$$ \boldsymbol{c}^{\mathrm{T}} = \left( \begin{array}{c} 1000 \ 91 \ -90 \ 1 \ -9000 \ -900 \ 10 \ -1 \ \end{array} \right)^{\mathrm{T}} $$
あとは、この$s$の文字に数字を割り当てていき、上のベクトルの内積が0になる数の割当を探していけば答えが見つかります。注意点として、先頭文字(今回なら$(s,m)$の2つ )には0は割り当てられないので、内積0になる数の組が見つかった後、先頭文字に0が割り当てられてないかチェックする必要があります。
数の割当を探す場合、漏れをなくすためにも辞書式に探します。$(0,1,2,3, \dots, 8, 9)$をnext_permutation()のメソッドに与えてあげれば、もれなく列挙できるとのことです。
ただただ実装がめんどくさかった問題です。 実際に答え候補となる数字の組を見つけても、そこから出力のため$N1, N2, N3$を復元する手間があります。
なお計算量ですが、最大で$10!$個の組を探すだけなので間に合います。(コンテスト後に気が付きましたが、制限時間が5秒と長めになっていますね)
解説 - AtCoder Beginner Contest 198
まとめ
実装するコード量が多くなりがちなのがちょっと嫌な回でした。
