AtCoderのランク別色ってのは赤色から始まって、赤、橙、黄、青、水、緑、茶、灰と８段階に分かれてて、茶色ってのは下から２番めなんだけど、なんもしらんと茶色なんてゲームでいうブロンズみたいな初心者ランク帯の様に感じる。
では茶色が時間かけて考えれば解るとされる茶diff問題がこちら。
atcoder.jp
ようは９×９のマス目があって、その複数のマス目に#で表されるコマがおいてある。
そのコマたちから４つを選んで、正方形となりえるのは何個か？という問題だ。
以下ネタバレ全開なので、問題解きたい人はここでバック。
方針としては♯の点から2点を取り、その2点から作れる正方形の残り2点を求める。
新たに求めた残り2点が、①そこにコマがあるか、②マス目に入っているか、で判定する。
このときに正方形の一意性を保つ（同じ正方形を何回もカウントしない）ために、#の2点,
としたときに
が
の"右上"（真上はOK）というふうに4重for文の設定で
、
開始と限定して、
を回転行列
で回転させて、そのベクトルと
を足して
を反時計向きに取る、という作業が必要。
んでそれから得られた,
が上に書いた①、②の条件をみたすかどうかを判定するってわけ。
これ結構難しいと思うんだけど。。。
茶色はアルゴリズム的な知識はあまり要求されないけど、この純粋な数学的能力、今回はベクトルと座標平面の回転、あたりが要求されるのはある程度高校で数学得意な方じゃないと難しくないか？
茶色にはたどり着きたいけどなー。まあ程々に頑張ろう。
