LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）に参加しました。
結果
A,B,C,Dの4問正解でした。
Dまではなんとか解けたけどE問題は全くわからなかった。 期待値を求める系の問題は解いてこなかったので解き方がわからない。確率DPとか言われる類の問題なんだろうなとは思った。
あと、今日は夕方から頭痛がして頭の回転が鈍ってる。これはたぶん気圧のせい…
A - Full House
5つの数字がフルハウスになるかどうかを判定する問題。 いろいろ解き方がありそうな問題だと思う。
私はvectorとsetを使ってゴリ押しした。
入力をvectorとsetに入れて、vectorはソートする。 setのサイズが2かつ、vectorの2番目と3番目もしくは3番目と4番目の要素が異なればフルハウスと判断して答えた。
フルハウスの条件はカードがXXYYYもしくはXXXYYの2パターンなのでsetのサイズでカードの種類を確認する。この時点でカードの種類が2じゃないならフルハウスには絶対にならないので処理を終了する。
XXYYYの場合は2番めと3番目のカードの数字が異なり、XXXYYの場合は3番めと4番目のカードの数字が異なるのでどちらかを満たしていることを確認する。
例外としてXYYYY、XXXXYのフォーカードがあり得るけどその場合は1番目と2番目もしくは4番目と5番目の数字が異なるので上記の確認でフォーカードをフルハウスと誤判定することはない。
B - Ancestor
グラフの問題っぽく見えた問題。
親の情報だけはもらえるのでNから1になるまで順番にたどるとか、人をノードとみなして親が誰かをもとに辺を繋いで1からNへの距離をもとめるとか、Union-Find木を作って距離を求めるとかいろいろ解き方が思いついた。
今回はグラフとみなして、幅優先探索で1からの距離を求めて答えた。
C - Monotonically Increasing
これもいろいろ解き方がありそうな問題だと思う。
制約を見るとで数列の項数は高々10個なのでちょっと面倒くさい解き方をしたとしても時間はそれほどかからないように思った。
後は、vectorで数列を作ってからsetに入れて重複の削除とかソートを勝手にやってもらいつつ、setの内容を順番に出力すれば良さそうなことは思いついた。
各項の値は1以上M以下なので初項は1~Mのどれかで、後は1以上づつ増えていくので 幅優先探索で項数Nの数列を作っていった。
データ構造をうまく使えればちゃんと解ける問題だと思った。
D - Left Right Operation
ぱっと問題を読んでもうまい方法が思いつかずちょっと考察していって解いた問題。
問題を読んで内容を理解すると結局、前からx個をLに置き換えて、後ろからy個をRに置き換えたときの数列の総和の最小値を求める問題だった。
制約を見ると数列の長さNがだったので
くらいで解かないとTLEになりそうだなと思った。
この時点で使えそうな処理が累積和や尺取法くらいだなあと思った。
とは言え尺取法だとlはループで1づつ増やしていけば良いとしてrをどこまで増やせば良いのかの判断は難しそうなのでちょっと違うなあと判断。
次に尺取法っぽい処理としてクイックソートの初期で数列の前と後ろから要素を見てゴニョゴニョする処理を連想して考えてみたけど尺取法と同じでどこまで要素を見ればよいのかの加減が判断できないので、尺取法っぽい解き方は無理だなあと思った。
手元の紙に色々書いて試してみて、最終的に以下の手順で解いていった。
- 各項に対してLに置き換えたとき、数列の総和がどれくらい減少するか計算する
- 先頭から1の和を求めていく。
- 各項に対してRに置き換えたとき、数列の総和がどれくらい減少するか計算する。
- 後ろから順に3の和を求めていく。
- 先頭からiまでの中で2で計算した和の最大値は何になるのかを各項に対して順番に求める。
- 後ろからiまでの中で4で計算した和の最大値は何になるのかを各項に対して順番に求める。
に対して、5で求めた値[i]+6で求めた値[i+1]を計算することでx=iとしたときに数列の総和を減少できる量の最大値が求められるので、この計算結果を使って総和がどうなるのかを計算し、最小値を求める。
