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

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