【AtCoder】ABC107を解いたのでメモ【Python3】
結果と最終提出コード
解答中の心境
【A】
これは肩慣らし。
【B】
え？行はif board[i] ==["."]*len(board[i])みたいに綺麗なコードで検索できるけど、列はどうするんだろ...ゴリ押すコードはプライド的に書きたくない...！あぁ...時間が...（結局、プライドなんてものは捨ててゴリ押した。笑）
【C】
計算量削減する方法全く分からない...。最も左のキャンドルと最も右のキャンドルの座標で場合分けして一通り探索する方法でもいけるんじゃね？...お。いけたいけた。
【D】
中央値を地道に求めていく方法なら書ける！でも計算量やばすぎ！中央値を1つずつ地道に求める問題なわけない.......故に、ギブアップなのじゃ！
解説やコメント
【A】
なし
【B】
《白のみの行や列を削除》ではなく、《黒がある行や列を出力》で良かった。これなら記録済みの行や列番号をスキップできるので高速化も可能になりそうだ。
問題文の『削除』につられてしまったので反省したいところ。
【C】
ゴリ押したと思った全探索が答えだった。
正直、この方法以外思いつかなかったのでホッとした。
【D】
全く何も出来なかったので、反省すべきところもない。笑
ごちゃごちゃ言い訳せずに解答だけ貼っておきます...笑
https://img.atcoder.jp/arc101/editorial.pdf
得た知識
- 問題に無意識で思考が誘導されないように注意せねば
- 《二分探索》という探索方法（《二分探索木》は知っていた）
- 数学のように問題を読み替えていく必要性がある
まとめ
- 今回のD問題をこんなに読み替えれるようになれる気がしない。笑
- 武器《二分探索》を手に入れた！
