| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
26分、ペナなし、34位。
問題C だけいつもより難しかったかな、結構手こずってしまったｗ
問題A – αlphabet
Python ならたいていの基本的な文字列処理は標準モジュールにあります。
（https://docs.python.org/ja/3/library/stdtypes.html#string-methods）
is_upper, is_lower で大文字小文字の判別がつきます。lower, upper で大文字小文字の変換もできます。なかなかすべてのメソッド名を覚えきれないですが、どんなものがあるかだけでも把握しておくといざというとき調べて書けると思います。
chr(), ord() で文字コードと行き来する方法もあります。
問題C – One Quadrillion and One Dalmatians
問題名とか問題文とかなげー。
長さ $n$ の文字列は、$26^n$ 通りあります。このことから、まず求める名前の文字列長が分かります。例えば、$N = 2020$ であれば、$2020=26+26^2+1318$ より、長さ $3$ の文字列のうちの $1318$ 番目であると分かります。
$1318$ 番目を求める問題は、 アルファベットを $0$ ～ $25$ と見なすことで、
・$1317$ の $26$ 進法表記を求める問題
と等価になります。$1317 = 17 + 26 * 50 = 17 + 26 * 24 + 26 * 26 * 1$ といった要領で下の桁から計算していくと、[1, 24, 17] に対応する byr が 2020 番目のワンちゃんです。
$26^0$ は含まなかったり、番号を $1$ ずらしたりと、個人的に結構注意を要する実装でした。
問題F – Strivore
問題名の意味がぐぐってもわからず。
昨日の AGC と同様、自由な操作結果の完成図を数え上げる問題です。ここでも、完成図に対して一意な操作手順を対応させることを目指します。
例えば、挿入位置は左端から順番に処理するように考えます。また $S$ のある文字の左に同一の文字を挿入する操作は考える必要がありません（右側に挿入しても同じ結果になるので）。
結局サンプル 1 の oof から作られる文字列は、上の形に表せること、このような形が一意であることが確かめられます。あとは数え上げです。
いくつの数を挿入する方法が何通りあるかを、例によって多項式で表します。
左端の「o 以外」部分への挿入について。$n$ 文字挿入する方法は $25^n$ 通りありますから、$f_{25} = 1 + 25x + 25^2x^2 + 25^3x^3 + \cdots$ と表すことができます。
続く「o 以外」「f 以外」部分も同様です。「なんでも」部分は $f_{26} = 1 + 26x + 26x^2 + \cdots$ です。結局次のような問題になります。
$f_{25} = 1 + 25x + 25^2x^2 + \cdots$, $f_{26} = 1 + 26x + 26^2x^2 + \cdots$, とする（形式的べき級数）。
$S$ の文字列長を $N$ とするとき、$[x^K] (f_{25}^Nf_{26})$ を求めよ。
$f_{25} = \frac{1}{1-25x}$ です。その $K$ 乗は、$(1-25x)^{-K}$ です。
$$(1-rx)^{-K} = \sum_{n=0}^{\infty} \binom{n+K-1}{K-1}r^nx^n$$ でした（[多項式・形式的べき級数]（３）線形漸化式と形式的べき級数）から、$f_{25}^N$ は計算できます。
$f_{26}$ をかける（$1-26x$ で割る）のも簡単です（疎な多項式との積や商は計算が簡単）。形式的べき級数 $F = \sum_{n=0}^{\infty} F_nx^n$ に対して、$G = \frac{F}{1-26x} = \sum_{n=0}^{\infty} G_nx^n$ を計算したいとします。$F = (1-26x)G$ より $n\geq 1$ に対して $F_n = G_n – 26G_{n-1}$ が成り立つことから、漸化式 $G_n = F_n + 26G_{n-1}$ により順に $G_0, G_1, G_2, \ldots$ を計算することができます。
