AtCoder Beginner Contest 363 C,F問題メモ

AtCoder Beginner Contest 363

わりと全般的に難しかったでござる。

C - Avoid K Palindrome 2

• 英小文字のみからなる長さ $N$ の文字列 $S$ が与えられます。
• $S$ の文字を並び替えて得られる文字列（$S$ 自身を含む）であって、長さ $K$ の回文を部分文字列として含まないものの個数を求めてください。
• ただし、長さ $N$ の文字列 $T$ が「長さ $K$ の回文を部分文字列として含む」とは、以下であることをいいます。
  • ある $(N-K)$ 以下の非負整数 $i$ が存在して、$1$ 以上 $K$ 以下の任意の整数 $j$ について $T_{i+j}=T_{i+K+1-j}$ が成り立つ

• $2 \leq K \leq N \leq 10$
• $S$ は英小文字のみからなる長さ $N$ の文字列

解法は、ABCの序盤問題なこともあり全探索と容易に想像できるが、計算量がやや厳しく $O(N!NK)$ となる。
$NK$ の部分は正確には $\frac{K(N-K+1)}{2}$ なので、最大となる $N=10,K=6$ などとして見積もると $5 \times 10^7$ となり、遅い言語ではやや厳しい。
せめて実行時間制約を3秒にしてクレメンス。

Pythonの itertools.permutations では、例えば 'aab' だと 'a' の位置を入れ替えただけのものが複数回、返されてしまう。
実質的に同じ並びに関しては2回以上判定処理を行わないようにすると、1/2、1/6、1/24などの定数倍がかかり、間に合う。（同じかどうかの判定に追加の計算が必要となるが）

しかし、最初から全て別の文字の場合はこれが効かない。
ただしその場合、制約上、回文になるものはないので、$N!$ そのものを出力すればよい。
このような場合分けをすれば、なんとかギリギリで通る。

提出一覧では、Pythonでも1秒未満で通してる方々も居るので、どういうことをしているのか確認してみる。

• 文字列は ord() で数値リストにする
  • PyPyの場合、そちらの方が速い
• 回文判定の時に素朴なindexループを回した書き方にする
  • PyPyでは素朴な書き方の方が速くなることが多い。
  • 特に以下のようなことをしない。
    • 文字列を切り出して比較
    • リストをスライスして比較
    • all()などのリスト内包表記を用いて判定
  • 提出 #55776424 - AtCoder Beginner Contest 363 - 313ms
• indexループでチェックする箇所は $K$ でなくて $K/2$ 個でよい
  • 'abcde'が回文かチェックするのに、aとe、bとdを比較すれば十分であり、cとc、dとb、eとaを比較する必要は無い
  • 定数倍高速化
• C++ の next_premutation のように、同じものを返さない順列生成を自分で実装する
  • 1つの配列を使い回してswapで生成すると、メモリ確保の面でも速くなる。
  • 提出 #55822676 - AtCoder Beginner Contest 363 - 294ms
• ひとまず全ての permutations についてチェックした上で、同じ文字の個数をカウントして最後に除算する
  • 同一判定にもそこそこかかるため、permutations を使う場合、結果的にそっちの方が速いっぽい。
• more_itertools.distinct_permutations を使う
  • こんなんあるんだ。
  • 提出 #55816666 - AtCoder Beginner Contest 363
  • ただし、通常のpermutationsよりは遅い。

まぁ、いろいろ書いたが、結局、数値リストにし、forループでチェックするという「PyPyフレンドリーな書き方」にするのが一番大事そう。

Python3

from itertools import permutations


def hash(p):
    h = 0
    for c in p:
        h = h * 26 + c
    return h


n, k = map(int, input().split())
s = input()

if len(s) == len(set(s)):
    ans = 1
    for i in range(2, n + 1):
        ans *= i
    print(ans)
    exit()

s = [ord(c) - 97 for c in s]

ans = set()
for p1 in permutations(s):
    h = hash(p1)
    if h in ans:
        continue
    ok = True
    for i in range(n - k + 1):
        if all(p1[i + j] == p1[i + k - 1 - j] for j in range(k)):
            ok = False
            break
    if ok:
        ans.add(h)
ans = len(ans)
print(ans)

F - Palindromic Expression

• 整数 $N$ が与えられます。
• 次の条件を全て満たす文字列 $S$ としてあり得るものを $1$ 個出力してください。
• そのような文字列が存在しなければ -1 を出力してください。
  • $S$ は 123456789 および *(乗算記号) からなる長さ $1$ 以上 $1000$ 以下の文字列である。
  • $S$ は回文である。
  • $S$ の先頭の文字は数字である。
  • $S$ を式として評価した値が $N$ と一致する。

• $1 \leq N \leq 10^{12}$

まず以下を調べる。
rev(a)は、aを文字列として逆から読んだ数を表すとする。
また、いずれの数も'0'は含まないもののみに限るとする。

• ①単独で回文数になっている $N$ の約数
• ② $a \times \mathrm{rev}(a)$ が $N$ の約数であるような $(a,\mathrm{rev}(a))$ のペア

$i=1～\sqrt{N}$ の範囲で、①は $i$ と $\frac{N}{i}$ を、②は $a=i$ の場合を調べればよい。
回文判定に桁数分の計算量がかかるので、$O(\sqrt{N} \log{N})$ で列挙できる。

②を使ったり使わなかったりして（同じものを複数使う場合も含め）再帰的に試していき、最終的に①に含まれるものが残れば成功。

Python3

import sys

sys.setrecursionlimit(10000)


def solve(n, i):
    if n in palindrome_divisor:
        return str(n)
    if i >= m:
        return None
    a, b, c = palindrome_pair[i]
    if n % c == 0:
        res = solve(n // c, i)
        if res is not None:
            return a + '*' + res + '*' + b
    return solve(n, i + 1)


n = int(input())

s = str(n)
if s == s[::-1] and '0' not in s:
    print(n)
    exit()

palindrome_divisor = {1}
palindrome_pair = []
for i in range(2, 1_000_001):
    if n % i != 0:
        continue
    s = str(i)
    n2 = n // i
    s2 = str(n2)
    if '0' not in s:
        t = s[::-1]
        j = int(t)
        if s == t:
            palindrome_divisor.add(i)
        if s <= t and n2 % j == 0:
            palindrome_pair.append((s, t, i * j))
    if '0' not in s2 and s2 == s2[::-1]:
        palindrome_divisor.add(n2)

m = len(palindrome_pair)
# print(palindrome_divisor)
# print(palindrome_pair)

result = solve(n, 0)
if result is None:
    print(-1)
else:
    print(result)