一問一答八週目
AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。
四十一日目:C - 座圧
の各要素が、何番目に大きい数字なのか変換すればになる。set 型を取り、ソートして、辞書型を活用すればよい。
四十二日目:C - 総和
いもす法で解けた。部分列の和を求めるので、の各要素が何回出てくるかわかれば、「各要素 × 登場回数の和」として求められる。
正攻法は解説にも載っている通り、1からi番目までの和をすべて記録し、それらの差を取ることで部分和を計算する。
四十三日目:C - 単調増加
尺取法であることはわかった。右側を伸ばしていき、左側を追従させていく。けど、変数の名前がよろしくない気がするなぁ。。
四十四日目:C - ピアニスト高橋君
全列挙でパワープレイ。
四十五日目:C - 柱柱柱柱柱
動的計画法。解きやすいパターン。二個前か一個前のコストが小さい方からi番目に移動すればよい。漸化式解くパターン。
四十六日目:C - 背の順
身長と出席番号の二次元配列を取り扱う問題。身長でソートして、その順に出席番号を出力する。operater.itemgetter を利用すると、ソートするkeyを指定し易くなることを学んだ。
むすび
ABC-123 敗北。緑になる日はいつのことやら。