cafelier@SRM

SRM 473

SRM | 15:10 |

SRM 473 の成績・ソース (要ログイン) : AC/AC/WA : 10日放置してしまったので記憶があいまい

500開く

• 『円周をP等分します。Q箇所色を赤く塗ります。残りは青です。赤のみで作れる三角形の個数を数えてね。』
  • P≦100万
  • Q≦10万

• 100万ということはO(P)で解けと言うことだな。
• ええとまず、10万個の入力はトップコーダーではこないので、
• Q箇所塗る場所を決めるための漸化式が指定されている。
• まあ愚直に実装してQ要素のvector作るか。
  • a,b,cが与えられていて、i番目に赤く塗るのは (a*i*i + b*i + c) % P番目の点らしい
  • すでに塗ってあったら時計回りに最初に青いところを塗る
• ガリガリ
• む？
• 「すでに塗ってあったら時計回りに～」って、そのまま実装すると、常に同じ点からスタートしたら O(Q^2) 時間かかるのではないか？
• まあ疑似乱数なら同じ所に何度もぶつかることはないか。
• いやまて。
  • a*i*i + b*i + c って全然疑似乱数じゃないし。
  • a=b=0 とかできるし
• うおーこれはダメだ。高速化せねば。
• しかしこれは完璧に撃墜ポイント。まさか本題ではなさそうな入力生成フェーズに落とし穴とは

• それはそれとして、高速にQ個塗るやりかたが思いつかない
• 「この点からは何個赤が続いている」みたいな表を適宜更新していけばいいか
• 良さそうだけど最悪例が作れそうな気もする
• うーむ
• ちょっとここは後回しで本題の方を解こう

• 円周上の三点で直角三角形
• if and only if、一片が直径
• なので、0 と P/2、1 と 1+P/2、…とすべての直径について、
  • 両端が赤なら、残りの一点はどの赤にとっても直角三角形になるので、Q-2 を足す
  • どっちかが青なら、何もしない
• というループを書く終わり。あとPが奇数のときは即0。

• さて、Q点の生成に戻ろう。
• vectorじゃなくてsetで管理して、二分探索というのはどうだ。
• 「まだ青い点」の集合から、a*i*i + b*i + c 以上で最小の点をみつけてくる
• なければ時計回り一周しているので、0以上で最小の点。
• これはただのlower_boundだ。O(Q log P) これはいける。

• 書いた
• できた

250開く

• 『二次元平面に、Sで前進、Lで左90度回転、Rで右90度、というロボットが居ます。与えられたSLRの列を無限に繰り返して動いたとき、ループするか、それとも無限の彼方に飛んでいくか判定してね』

• えーと、とりあえず与えられた列を4回回れば、絶対元と同じ向きになる
• このとき、元と同じ位置にいれば、当然無限ループ
• いなければ、また4回回ると同じだけずれるので、次第に無限の彼方に飛んでいく
• というわけで実装するだけ
• できた

• これcの値は関係ないから、cを使わないでコード書いて、
• challengeの時に見る人を「バグってるんじゃね？」っと一瞬足止めする作戦…
• …そういうのはやめよう…

1000開く

• 『色んな色のルークが何個かずつたくさんありますので、違う色同士で攻撃しないように配置するやり方は何パターン？ mod 1000000009で。』
  • 最大 30x30、10色

• おー？
• DPじゃないかな。
• まず一色目のルークの置き方を全通り試す
  • すると、そのとき使った列と行には他の色は置けないから、
  • WxHの盤面からw列h行使ったとすると、残りは(W-w)x(H-h)に残りのルーク達を置くパターン数を求めればいい
  • というWxHに関するDP
• しかし「まず一色目のルークの置き方を全通り試す」
  • だけでも結構やっかいだな。
  • この部分もなんかDPでてきとうに。「i個つかってw×hを使う」みたいなパターン数をiを増やしながら

• とかやっていたらメモ化表が3個くらいあるソースができた
• 実行
• うーむ合わない
• いろいろ弄っていると、最適化のつもりでWとHをswapしている部分を外すとサンプルと合う
• しかしこれ、このswapで答えが変わるはずはないのだが…
• サンプルと合ったとしても絶対バグってる…
• けど時間内ので勢いでsubmitしちゃえ！

撃墜タイム

• 500のTLE狙いで二件撃墜
• ほかほとんど他の人に取られた。
• ううむ絨毯爆撃はしたくないのだが、そうでもしないと撃墜速度で勝てないなあ。

感想

• ロボット工学第ゼロ法則みたいなもので
  • 「個々のプレイヤのバグを見つけ出す能力が重要」
  • であるならば、その上位に「プレイヤ全体でどの程度のバグが発生するか見出す能力が重要」
  • という規則を考えることもできるのではなかろうか。
  • それで期待値を計算して絨毯爆撃してもお釣りが来ると思えばやる、
  • というのは、備えるべき能力の評価という意味で、適切な行動ということもできる。
• ううむ