ABC198 参加記録 - Xenous の精進記録

4完3ペナ 56分でした

A - Div

お菓子を1つ以上分けるパターンを考えてみると、例えば $N = 4$ のときは、3個と1個、2個と2個、1個と3個という分け方の $3$ 通りがあり、他の $N$ でも試すと、結局 $N-1$ 通りあることがわかります。

B - Palindrome with leading zeros

0 をつけて回文にするということは、与えられた文字列の末尾の 0 を消したときに、残った文字列が回文になっているかどうかを考えればよさそうです。数値は $10^{9}$ までの範囲で与えられますが、桁数に注目すればよく、問題なく回文かどうかを確認することができます。

C - Compass Walking

2ペナもらいました。

まず $(X, Y)$ に到達するまでの最小の歩数を求めるには、直線で向かったときに少なくとも何歩かかるか、を考えました。大体のケースではこれで良いのですが、与えられた $(X, Y)$ が、原点を中心とした半径 $R$ の円内(円周上は含まない)にある場合は、一歩目が大きすぎて、必ず2歩必要になります。

したがって、まずは $(X, Y)$ が半径 $R$ の円内にあるかを判定して、円内なら答えは 2 です。そうでない場合は、そのままユークリッド距離を $R$ と比較すれば良いです。ただし、ルートをとると誤差が生じて正しい答えにならない場合もあるので、なるべく整数のまま扱います。以下を満たす最小の自然数 $k$ を求めることを考えます。

$\sqrt{X^{2} + Y^{2}} \leq kR$

これを両辺2乗します。

$X^{2} + Y^{2} \leq k^{2}R^{2}$

あとは $k$ について二分探索すれば、最小の $k$ を求めることができます。今回の問題では、 $k$ は $\left\lceil\sqrt{2}\times10^{5}\right\rceil$ 以下であることがわかるので、全探索することも可能です。

以下は全探索のコードです。

R, X, Y = map(int, input().split())
D2 = X**2 + Y**2; R2 = R**2
if D2 < R2:
    print(2)
else:
    for z in range(10**6):
        if D2 <= z**2 * R2:
            print(z)

D - Send More Money

バグらせてしまい、本番では AC できませんでした。スマートに書けなかったので、他の方の提出コードを参考にしつつ解きました。

方針は、文字列と0 〜 9 の数字を当てはめる全探索で良いです。計算量は長さが最大 $10$ である 3 つの文字列と、文字種が最大で $10$ 個しかなく、その順列を考えるので $O(3\times10\times10!)$ くらいです。これは $10^{8}$ より少し多いくらいの計算量になり、5sec ありますが重い処理を書いてしまうと TLE します。

まず、使われた文字種が 11 以上だと、0 〜 9 を構成したときに使われない文字が生じてしまうため、UNSOLVABLE です。
次に、どの文字にどの数字を当てはめるかを順列で実装します。0 〜 9 のうち、文字の種類数ぶん取り出して並べます。python であればitertools.permutations() があります。
そして、各文字種と、並び替えた 0 〜 9 の値を入れ替えます。str.replace() で実行可能です(str は文字列型の変数だと思ってください)。実際に足し算をして成立すればそれを答えとします。

ただ、上記の計算だと間に合わないパターン場合があります。今回実装が簡単な枝刈りとして、1桁目の計算をして、正しくなかったら replace 処理をスキップすることで少し軽くなります。

また、0 単体で使えないことと、無駄な 0 がある数字(例えば 0321)は認めないことに注意すれば、ACできます。

個人的に以下の点が反省点です。。

replace が頭から抜けており、for 文で文字列の書き換えを書いていたこと
- 基本は組み込み関数を使った方がシンプルに書けてかつ速いと思ってます。
最初の UNSOLVABLE の判定で桁数の無駄な確認などをしていたこと(OKなのに UNSOLVABLE にしてしまう可能性が生じる)

E - Unique Color

木構造の問題です。

ある頂点から DFS を行うと計算量は $O(N)$ になります。頂点 $1$ から出発したとき、DFS で探索しつつ、色の出現回数をカウントし、到達した頂点の色がまだカウントに現れていなかったら、答えのリストにその頂点番号を追加します。

DFS では、再帰関数で潜った後に戻ってくる際、色の出現回数を元に戻すことができます。具体的なコードは以下のような形です。
colordict はカウンターオブジェクト、ki は隣接リスト、ans は回答を保存するリスト、C は各頂点を保存しているリストです。

def dfs(n:int, p:int) -> None:
    global colordict, ki, ans, C
    # 深く潜っていくときに、色のカウントを行う
    if colordict[C[n]] == 0:
        ans.append(n)
    colordict[C[n]] += 1
    for to in ki[n]:
        if to != p:
            dfs(to, n)
    # 色のカウントを元に戻す
    colordict[C[n]] -= 1

この考え方はよく使うと思います。類題をご参考までに記載しておきます。

python では、再帰の上限が決まっていますが、sys.setrecursionlimit(10**6) を記載しておけば大体OKです。(忘れており1ペナ食らってしまいました）