PointsAtCoder思考過程を文章として残してみたので、公開してみようっと。問題2N*2Nのグリッド上で、どの2点間の距離もd1、d2とは異なるようなN*N要素からなる集合を作ってください。何も考えなければ全体の1/4を選べれば正解で、d=1の時は市松模様、d=2の時はストライプになる感じでd1,d2でそれぞれ1/2になりそう?(d=25とかa2+b2=c2になるときは要検証)ってことで取り敢えず(0,0)から貪欲に選択していく方式で実装してみる。最初に(0,0)から距離がd1,d2の点を列挙->O(N2)1で生成したリストの要素を(x,y)としたとき、他の点でも使えるよう(-x,y)、(x,-y)、(-x,-y)もリストに加える。各点について2で生成したリスト分ずらした点を1つも使用していなければ使える。リストの点は実際ほとんど存在しないはずなので、O(1)位に見積もっても悲惨なことにはならないはず。WAしました(だから検証しろって言ったじゃん...)a2+b2=dで分解できるとき取り敢えず20×20でd=25の時の残りマス数を見ると「139/400」。実際提出してみた結果を見ても、このケースさえ何とかなればACぽい。生成されたマス目(以下。oを使用しています)をみるとかなり不規則なので、これを規則的に直したいと思います。oooooxxxxxoooooxxxxxoooooxxxxxoooooxxxxxoooooxxxxxoooooxxxxxxoooxxxxxxxoooxxxxxoxxoxxxxxxxxxoxxxxxxoxxxxxxxxxxxxxxxxxxxoxxxxxxxxxxxxxxxxxxooxxxxxxxoxxxxxxxxxooooxxxoxoooxoxxxoxxooxooxooxxoxxooxoxxxoxxoooxoxxxoxoxoxxxxxoxxoxxxoxoxoxxxxxxxoxxxxoxxxxxxxxxoxxxoxxxxxoxxxxxxoxoxxxoxxxoxxoxxxoxoxxxoxoxoxoxxxxoxoxoxoxoxoxoxoxooxoooxxxxxoxoxoxoxoxooxoxxxoxoxoxoxoxoxooxxxoxoxoxoxoxoxoxoxxoxoxoxxxoxoxoxoxoxoところでd=25の時に限って言うと、「市松模様」で実は通ります。同じ形状のd=100では2x2単位の市松模様にする必要があります。これは分解後のa,bの偶奇に依存しそうです。こっちの方面の考察をもう少ししてみましょう。a,bの偶奇について考えます。dが奇数⇔a,bの偶奇が異なるとき1x1の市松模様でOK。市松模様の色の判定は(a+b)%2で、これが常に奇数だから。4)⇔a,bがともに奇数のときd=50が(1,7)と(5,5)で分解できるなど。d=130が結構厄介で、貪欲解はこいつに殺されます。その原因は「貪欲だから」で、少し控えめの「偶数行目のみ取る」という方針を取れば解決。4)⇔a,bともに偶数のときこれは、全体を2で割って座標を圧縮することで上のどちらかのパターンに持ち込むタイプ?縮小して上のケースに持ち込んだ後、拡大するのを忘れずに。上の考察で用いられる模様は全て「残りの個数を1/2にするけど、他の模様と独立」という点があるため、問題無く1/4取り切ることが出来るはず。超考察寄りの構築ゲーでした。...「3月中に毎日1問解いて黄色になろう!」キャンペーン11問目。...「3月中に毎日1問解いて黄色になろう!」キャンペーン8問目。徘徊迷路yukicoderはとても久しぶりに解きました。日)ネットの海に生息するらしいバーチャルグソクムシ。競プロとCTFをメインに、たまにEsolangを混ぜます。(7)月別アーカイブリンクGitHubはてなブログをはじめよう!Hyogaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。