一問一答十三週目 - 競プロ引退しました。

AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。

　自力AC。 $N=A \times B$ という条件から、 $1 ～ \sqrt{N}$ までAを全探索し、 $F(A,B)$ の最小値を求める。

　自力AC。与えられる $s_i$ のいずれかを基準として、使用できるアルファベットを絞り込んでいくイメージ。候補となるアルファベットが、各 $s_i$ にどれだけ含まれてるか調べ、最小個数がそのアルファベットの個数となる。

　写経AC。操作後の配列の符号が、「 $+-+-+-...$ 」となる場合と「 $-+-+-+...$ 」となる場合があり、そのうち手数が少ない方を答える問題。符号を変更する必要があるときだけ操作すればよい。累積和が0になる場合を漏れなく条件に入れること。

　自力AC。シャワーボタンを押す間隔 $t_(i+1) - t_i$ が、シャワーが出続ける時間 $T$ より長ければ $T$ を足す。短ければ $t_(i+1) - t_i$ を足す。if文でもいいけど、min関数使った方がすっきり書ける。

　解説読みAC。"K個目の小さい数"を、"K番目の数"と勝手に解釈していた。

　 $(a_i, b_i)$ を $a_i$ で昇順ソートした配列を作り、 $\sum b_i \geqq K$ となるときの $a_i$ が答え。

　このほかに、バケツソートというアルゴリズムを使用する解法もある。大きい一次元配列を準備して、 $a_i$ 番目に $b_i$ を足していく。その配列に対して、 $\sum b_i \geqq K$ となるときの $a_i$ が答え。

　解説読みAC。「二の字」に分割線を引くか、「T字」に分割線を引くかで場合分けする。最初の区切り線でループを回し、残った部分はなるべく面積が等しくなるように分割すればよい。

　一回上記探索を行ったら、チョコを90度回転させて再度ループを回す（ループ対象の辺を縦横変更する）。一回目と二回目で求めた差分のうち、より小さい方が答え。

　自力AC。合計成績が10で割り切れるか否かで場合分けすれば素直に解ける問題。

　ただ、この問題はメモ化再帰に因るDPで部分和をすべて列挙できる。DP解法については、写経ACだったが、考え方はなんとなく理解できた。

　分割した小さな問題は、「ある時点で、与えられる要素を足す場合と足さない場合のポイントを求める」で、それをメモ化再帰してベースケースに辿り着くようにすればよい。

　扁桃炎に罹って苦しみました。健康第一。また、体調崩して以降、一意専心の気持ちがやや弱くなってきているので、目の前の問題に集中するよう心掛けたいです。