【競プロ精進日記】AtCoder パナソニックプログラミングコンテスト2020

2020.03.17
競プロ

1. はじめに
2. A
3. B
4. C
5. D
6. E
7. F

はじめに

当ブログは問題の解説がメインではなく、筆者の解法やアイデアの保存がメインです。
したがって、読者の期待に沿えないことがあると思いますがご了承ください。

A

A – Kth Term
配列にコピペしてK番目を出力
https://atcoder.jp/contests/panasonic2020/submissions/10951321

B

B – Bishop
コーナーケースに気付けるかがポイント。その名の通りコーナーです。
縦もしくは横の長さが1の場合は身動き取れないため1マス。
2以上あるときはジグザグ移動できるので面積の半分の切り上げが答え。
https://atcoder.jp/contests/panasonic2020/submissions/10951390

C

C – Sqrt Inequality
私はリアルタイムに出場できなかったのですがタイムラインで見かけました。
浮動小数の精度でWAが出るようです。
公式解説にもある通り式変形するのがよいでしょう。
√の項を片方の辺に集めて両辺を2乗していけば√が消せます。
両辺を2乗するわけですが、負の数をかけると不等号が反転することを考えないといけません。
したがって、2乗する文字式の正負を考えますが、今回は負の場合に不等式が成り立たないのでNoです。
$$\sqrt{a} + \sqrt{b} < \sqrt{c} $$ $$ \left( \sqrt{a} + \sqrt{b} \right) \left( \sqrt{a} + \sqrt{b} \right) < \sqrt{c} \left( \sqrt{a} + \sqrt{b} \right) < \sqrt{c} \sqrt{c} = c $$ $$ a + 2\sqrt{ab} + b < c $$ $$ 2\sqrt{ab} < c - a - b $$ ここで、右辺$$ c - a - b $$の正負で場合分け、負の場合不等式が成り立たないのでNo $$ 4ab < (c - a - b)^2 $$ この不等式が成り立つ場合Yesで成り立たない場合No
https://atcoder.jp/contests/panasonic2020/submissions/10951421

D

D – String Equivalence
読解が難しいですね。とても苦手です。
N < 10なので最初はiとjの辺をつなぐつながないの全通り試すのかと思いましたが$2^{10!}$通りですかね？無理です。
題意について考えると、標準形を構成する文字種はa,b,cやa,b,c,d,e,やaなど必ずaから順番になります。
a,cやb,c,dなどの文字種で構成される文字列は標準形ではありません。
さらに、標準形は同型のうち辞書順で最小でなければなりません。
つまり、ある同型な関係（任意の$i,j$に対して$s_i=s_j$かつ$t_i=t_j$もしくは$s_i\neq s_j$かつ$t_i\neq t_j$）を持つ文字列で辞書順が最小なものは、先頭から初めて登場する文字がアルファベット順でなければなりません。

したがって、acbなどは標準形ではありません（bの前にcが登場しているので）。
これらを整理すると、先頭の文字はaで、次に続く文字を既出な文字種＋１から構成していけば標準形になります。
これをdfsで定義すればACです。
https://atcoder.jp/contests/panasonic2020/submissions/10962535