AtCoder Grand Contest 025: D - Choosing Points
思考過程を文章として残してみたので、公開してみようっと。
問題
2N*2Nのグリッド上で、どの2点間の距離もd1、d2とは異なるようなN*N要素からなる集合を作ってください。
解説
最初の方針
特に何も考えなければ全体の1/4を選べれば正解で、d=1の時は市松模様、d=2の時はストライプになる感じでd1,d2でそれぞれ1/2になりそう?(d=25とかa2+b2=c2になるときは要検証)
ってことで取り敢えず(0,0)から貪欲に選択していく方式で実装してみる。O(N3)くらいにしなきゃいけないので、
- 最初に(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」。1/2未満です。実際提出してみた結果を見ても、このケースさえ何とかなればACぽい。
生成されたマス目(以下。oを使用しています)をみるとかなり不規則なので、これを規則的に直したいと思います。
oooooxxxxxoooooxxxxx oooooxxxxxoooooxxxxx oooooxxxxxoooooxxxxx xoooxxxxxxxoooxxxxxo xxoxxxxxxxxxoxxxxxxo xxxxxxxxxxxxxxxxxxxo xxxxxxxxxxxxxxxxxxoo xxxxxxxoxxxxxxxxxooo oxxxoxoooxoxxxoxxoox ooxooxxoxxooxoxxxoxx oooxoxxxoxoxoxxxxxox xoxxxoxoxoxxxxxxxoxx xxoxxxxxxxxxoxxxoxxx xxoxxxxxxoxoxxxoxxxo xxoxxxoxoxxxoxoxoxox xxxoxoxoxoxoxoxoxoxo oxoooxxxxxoxoxoxoxox ooxoxxxoxoxoxoxoxoxo oxxxoxoxoxoxoxoxoxox xoxoxoxxxoxoxoxoxoxo
ところでd=25の時に限って言うと、「市松模様」で実は通ります。ただ、同じ形状のd=100では2x2単位の市松模様にする必要があります。これは分解後のa,bの偶奇に依存しそうです。
こっちの方面の考察をもう少ししてみましょう。a,bの偶奇について考えます。
- dが奇数⇔a,bの偶奇が異なるとき
- d≡2(mod 4)⇔a,bがともに奇数のとき
- d=50が(1,7)と(5,5)で分解できるなど。斜めのみのパターン。d=130が結構厄介で、貪欲解はこいつに殺されます。
- でもその原因は「貪欲だから」で、少し控えめの「偶数行目のみ取る」という方針を取れば解決。(両方奇数ダカラネ!)
- d≡0(mod 4)⇔a,bともに偶数のとき
- これは、全体を2で割って座標を圧縮することで上のどちらかのパターンに持ち込むタイプ?縮小して上のケースに持ち込んだ後、拡大するのを忘れずに。
また、上の考察で用いられる模様は全て「残りの個数を1/2にするけど、他の模様と独立」という点があるため、問題無く1/4取り切ることが出来るはず。
bool use[610][610]; void fill(int d, int n) { int cnt = 0; while (d % 4 == 0) { d /= 4; cnt++; } int m = 1 << cnt; if (d % 4 == 1) { // 市松模様 rep(i, n) { rep(j, n) { if (((i>>cnt)+(j>>cnt)) % 2 == 1) { use[i][j] = false; } } } } else if (d % 4 == 2) { // ストライプ rep(i, n) { if ((i >> cnt) % 2 == 1) { rep(j, n) use[i][j] = false; } } } } int main() { int n, d1, d2; cin >> n >> d1 >> d2; int N = n << 1; rep(i, N) rep(j, N) use[i][j] = true; fill(d1, N); fill(d2, N); // 同じフィルターをかけたりすると密度が1/4にならないので、cnt必須 int cnt = 0; rep(i, N) { rep(j, N) { if (use[i][j]) { cout << i << " " << j << endl; if (++cnt == n * n) return 0; } } } return 0; }
感想
超考察寄りの構築ゲーでした。このレベルで試行していたら分かりやすいな…と思って書いてみたけど、どうなんだろ(コードの読みやすさは度外視)
SRM599(div1) Med: FindPolygons
昨日こんなことをし始めました。
ただ、今の自分は黄色手前の青。div1Easyは流石に解けていないといけない領域です。ということで、一緒にMedも解くことで精進をしよう!というのが本来の趣旨です(絶対分かるかこんなん)
続きを読むpwnablr.kr Todder's Bottle:input
なんかかなり放置していたかつ日本語解説無かった(するまでも無いかもしれないけど)ので。
続きを読むAtCoder Grand Contest 013 C - Ants on a Circle
1番ゼッケンの蟻の動きを追い続ければ絶対AC出来ると思っていましたが、無理でした。
続きを読むyukicoder No.3037 Restricted Lucas (Hard)
Easyも全く同じコードで通るのでまとめて。
続きを読む