【AtCoder】ABC005を解いたのでメモ【Python3】
結果と最終提出コード
解答中の心境
【A】
- たこ焼きうまそう！
【B】
- 上手くやれば1行になりそう...（
.sort()で泣く泣く行を分けた）
【C】
【D】
- あー絶対ゴリ押し無理や...演算数がえぐいやん...でもゴリ押してみよう
- 店員は最後にまとめて評価すればOKでしょ
- ネスト深すぎて草生える（4段ネストになってる）
- TLE以外にWA出てる...速度は置いといて、正解が出る自信あったのに...
解説やコメント
【A】
- なし
【B】
- なし
【C】
- 模範解答通りの答えだった！
- 二部グラフの最大マッチングという方法もある
【D】
- 店員の部分に関しては満点レベルの思考だった
任意の長方形の中の合計値を高速に求める方法（下画像）が全く思いつかなかった...
numpy.arrayのライブラリごりごり使っちゃった。笑
高速化にはアルゴリズム以外に計算するパーツの事前計算が必要！
得た知識
- pythonは
if hoge <= huga <= piyo:みたいな条件式が記述できる！ - pythonのスライス便利。特にnumpyの方は超便利。
- 繰り返しになるが、高速化にはアルゴリズム以外に計算するパーツの事前計算が必要！
まとめ
- ゴリ押しはオーダーを計算してからにしよう！
- D問題はやっぱり難しい！1回書いたら制限時間ギリギリに...修正時間がないのがきつい。
- 間違ったテストケースを見て復習したいので、次回からは最新のコンテストから順にやっていこうと思う。
