パナソニックプログラミングコンテスト2020　参加メモ

atcoder.jp
あ゛あ゛あ゛あ゛あ゛あ゛あ゛あぁあああぁあ(悲嘆)
846th, Perf=1542, 1905 -> 1873(-32)
ABCDの4完でした E埋めをしたので5完出来ると思ってました(それは幻想)

A - Kth Term

問題文からコピペをして配列の添字を参照するだけです

B - Bishop

基本的には市松模様になっているが、 $H=1$ , または $W=1$ のとき、移動できないので反例となる。
30分溶かしました

C - Sqrt Inequality

doubleだと精度の問題からうまくいかないらしい(たしかにlong long くらいの精度は持ってないね(いくらか指数に使ってるから))
long double を使うか、式変形をする
$\sqrt a + \sqrt b < \sqrt c$
$\Leftrightarrow a + 2 \sqrt{ab} + b < c$ ( $a > 0, b > 0, c > 0$ より)
$\Leftrightarrow 2 \sqrt{ab} < c-b-a$
$\Leftrightarrow c-b-a \gt 0 \land 4ab < (c-b-a)^2$

これで整数で扱えるようになったので、書くとACする

D - String Equivalence

現在 $n$ 文字の標準系の文字列 $s_n$ を形成しているとして、 $s_n$ に文字 $c$ を末尾に追加した文字列 $s_{n+1}$ を作るとしたとき、それが標準形になるような文字 $c$ は、

$s_n$ 内で使われている文字
$s_n$ 内で使われている最大の文字より一つ大きい文字

しかないので、これらを全通り試す。たかだか $n!$ くらいしか無いので解ける。

この条件を満たしていないと、書き換えた時に辞書順で小さいものを形成できてしまう。
難易度 D < C < B だと思う(個人の感想です)

E - Three Substrings

$b$ が $a$ に対して $i$ 文字右にずれていて、 $c$ が $a$ に対して $j$ 文字右にずれているとき、　 $c$ が $b$ に対して $j-i$ だけずれている。

そのため、 $a$ を基準にして $i,j$ を決めてやる。
このとき、 $a, b$ が $i$ 文字ずらして大丈夫か, $a, c$ が $j$ 文字ずらして大丈夫か , $b, c$ が $j-i$ 文字ずらして大丈夫かわかれば、文字列 $s$ を作れることがわかる。
ところで $2$ つの文字列が条件を満たしているかは $\mathrm{O}(文字列の長さ^2)$ で前計算しておけば $\mathrm{O}(1)$ で呼び出せるので、 $i, j$ を決める事で $\mathrm{O}(M^2)$ ( $M$ は $a$ からずらして答えが見つかる可能性のあるものの数(たかだか8000程度))
くらいで解ける。
ずらす方向は右だけじゃなくて左もあるので、うまくoffsetとか使ってマイナスを対応しなければならない。

F - Fractal Shortest Path

まず、一番大きいフラクタルの構造について見ていく( $3^{29}$ の正方形をマスとした $9$ マス)。
このとき、図のように $7$ 通りの座標パターンがある(対称性を保つように適切に変換を行うとこれしかない)。
f:id:tinumukiti631:20200317184204j:plain