AtCoder Beginner Contest 397
こんにちは。昨日ABC398にrated参加しました。
その記事も書こうと思うのですが、それ以前にABC397のバチャを走ったのでまずはそれをまとめます。
結果、ABCの3完（25分0ペナ）でした。
unratedですが、AC predictorによると778perfらしいです。
ただの精進不足ではあるのですが、D問題が解けないのはいただけませんね。
今回はA~Eまでの感想を述べていきます。
A - Thermometer
整数部分は入力の1,2番目、小数部分は4番目です。
それぞれ受け取り、場合分けすれば良いですね。
B - Ticket Gate Log
現在「入場中」なのか、「入場していない」のかの状態管理をして、「入場中」（未処理のiがある）なのであれば次の文字はoでなければなりません。また、「入場していない」（未処理のiがない）なのであれば次の文字はiでなければなりません。
以上を念頭に置いて、条件に合致しない文字が来てしまったらその都度文字を挿入します。
この回数が求めるべき答えです。
C - Variety Split Easy
整数列を二分する位置を左端→右端に一つずつずらしていって、左側にある整数の個数と右側にある整数の個数を差分更新する方法で解きました。これは、各整数の右端のインデックスを事前に求めておくことによって計算できます。
D - Cubes
これは、全探索＋二分探索の典型ですね。
バチャ中は、うまいこと式変形すれば$x-y$が$\sqrt[3]{N}$で上から抑えられるということに気がつきませんでした。
E - Path Decomposition of a Tree
dfs（木DP）で部分木分解っぽいことをすればいいのはすぐ見えました。
部分木の頂点数が$K$より大きいか、同じか、小さいかでそれぞれ場合分けして、別々の処理をする感じです。
しかし、どうしてもWAが取れずタイムアップしてしまいました。
部分木がパスになっていないといけない、という辺りの条件をきちんと反映できていないかもしれません。
まとめ
D,Eは水を目指すのであれば解けなければいけない問題だと思うので、しっかり復習して解けるようにしていきます。
バチャでは解けませんでしたが、考えていくうちにだんだんと競プロの勘を取り戻してきました。
色々と忙しい最近ですが、なんとか実力を維持・向上していきたいものです。