TopCoder SRM 473 (Div 1)
Result
234.31 / failed / unopened
2撃墜1ミス +75点
187位
1555->1608
500の発想はよかったが……勿体なかった。
Easy SequenceOfCommands
問題
座標平面の原点に人がいて、命令列を順番どおり実行する
- S
- 前に1進む
- L
- 90度左に回転する
- R
- 90度右に回転する
与えられた命令列を無限回繰り返したとき、有限半径の円にいるかどうかを判定せよ。
試行錯誤
ふむふむ？命令列を終えた時点で(1,0)とかに前を向いていたら円に収まらない。
(10,0)で右むいてたら正方形を描くよな。
1ループ終えたときに、向きが最初と違うか、原点に戻って来れば収まる。
書いた。サンプルも正しい。
えーこんなに簡単なのか？何か罠ない……？
なさそうなので送信。
Medium RightTriangle
問題
円周上をn等分する点に、時計回りに0,1,2,...,n-1と番号をつける。
そして、0,1,2,...,m-1のそれぞれのkに対して、
l=(a*a*k+b*k+c)%nとし、lから数えて初めて最初に赤でない点を赤にする。
この操作を終えたとき、円周上の異なる3つの赤い点を結んでできる直角三角形はいくつできるかを求めよ。
n≦1000000, 赤い点の数mはm≦100000を満たす。
試行錯誤
問題文の読解に手間取る。意味とらえにくかった！
一辺が直径なら直角三角形になる。なのでまずは点の数が偶数が必要。
それはいいとして、シミュレートでいいのだろうか。最悪ケースだと10万を線形探索することになって終わらないような気がする。
とりあえず書いてみよう。サンプル通った。
サーバ上で実行。サンプルは通るけどa=b=0で赤を適当に多くするとやっぱり実行が終わらない。
今回また撃墜祭りになりそうだなー。
うーんとどうしよう。
連続する数とかを保持しておく？いや、それを更新するのに結局O(m)かかって全体でO(m^2)になって意味がない。
……あ、そうだ平方分割の考え方使おう！！
√nごとに区間を区切って、その区間で赤の数を持っておけばO(√m)で探索できる！！
もらったぜ！実装。
サンプル通った。サーバ上でさっきのTLEケースを実行。余裕で終わる。
慎重にテストケースを5個くらい作ってテスト。おｋおｋ.送信。
残り20分弱。どうせHardは解けないのでEasyとMedium見直す。
Hard
unopened.
Challenge phase
Mediumで線形探索してる子を探す。いきなり見つけたぞ。
a=b=0で赤を10万にしてチャレンジ。お、成功。
他の人を見るとnext[]なる配列を持っている人が結構いる。というかそのやり方の人が殆どのようだ。
合ってるか良くわからないのでnextとか持ってない人探す。
線形探索二人目発見。チャレンジ成功。
javaでbitsetみたいの使ってる人がいる。これってどうなんだろ……
うーんでも工夫してないよなあ。。。
ためらいながらもチャレンジ。失敗！？なんて便利なんだこれ。
Easyも見る。怪しいのはあるが確証もてない。
怪しいのに突っ込んで盛大に自爆してきたので明らかにおかしくなけりゃ自粛しよう。
+75で部屋暫定トップ。500通れえええ
