Hatena::Grouptopcoder

ir5は引退した

 | 

2010-06-18

SRM473

02:42

朝のSRM.人が少ないし眠い.

DivLevelProblemNameStatus
1250SequenceOfCommandsPassed System Test
1500RightTrianglePassed System Test
11000RooksPartyCompiled

250

  • 平面上を与えられたコマンド(直進,90度直角に曲がる)どおりに無限に繰り返したとき,無限遠まで移動してしまわないか判定する問題.
  • 愚直にやって元のところに戻ってくるか見ればいいんじゃない? 書く.
  • サンプル落ちる.1回の試行で元に戻ってこなくても,4回くらいやれば元に戻ることがあるらしい.
  • なら4回くらいやればいいんじゃないの.角の回転は4周期しかないし. → 提出.ここまで8分.

500

  • 1000000個くらいの点が円状に並んでいる.そのうち100000個くらいの点に赤い色を塗っていく.
    • P[n]=(an^2+bn+c)%N みたいな式が与えられるので,点P[n]から時計回りに見ていって,初めて赤に塗られていない点を赤く塗る,というのを繰り返す.
    • で,赤色の点で構成される直角3角形の総数を求める.
  • とりあえず点の個数が奇数なら絶対に直角3角形はできないので0を返すようにする.
  • そうでない場合.直径になっているような2点を選べば,あとは任意の点と結んで直角3角形をなすようにできるから,足し上げるだけでできる.
  • とすると問題は赤い点を求めるところになる. …set<int>でupper_boundとかすればいいのでは. → 提出.ここまで20分.

1000

  • めちゃくちゃ時間余ってる… 1000でも読むか.
  • 問題文が空想的だ.
    • N*Mの盤面と,10色のルーク(将棋で言う飛車)がそれぞれC[j] (1<=j<=10)個与えられる.違う色のルークが互いに攻撃し合わないように盤面に配置するような方法は何通りあるか求めよ.
  • …あれ,1000にしては簡単じゃね,できるんじゃね?
  • ある色のルークを盤面に置いたとすると,他の色が置ける領域は長方形と見なせる → DPが使える!!
    • N*Mの盤面にルークをK個置いて盤面の大きさをn*mにするような場合の数 …とか?
    • 30^6はメモリに収まらないのでダメ.
  • よく考えるとルークをK個置いて盤面をちょうどn*mにするのは難しい.n以上*m以上とかなら簡単.(単にK個置けばよいだけだから)
  • K個置いてn*m以上にする場合の数をE(n,m)とおくと,ちょうどn*mにする場合の数はE(n,m)-E(n+1,m)-E(n,m+1)+E(n+1,m+1)なのでは. (単純な数え上げによる)
  • で,Eは単純な組み合わせ係数でできそう.あれ,メモ化いらない.単純になった.
  • 最終的な場合の数は,最初:N*M → 1種類目のルークをC[1]個置く → 2種類目のルークをC[2]個置く → … という感じなので,F[l][n][m] := l種類目のルークをC[l]個置いて盤面がn*mになるような場合の数 として計算すればできそう.書こう.
  • 書く.
  • テスト合わない.何故?
  • 良く考えてみると,これだと盤面の大きさが0*1とか0*2になる場合とかが含まれてなんだかよく分からない.
    • 上手い感じにしたいけどどうすればいいんだろう… → 結局解決せず.終了

Challenge Phase

500でlower_bound使っている人がいる.upper_boundじゃないと駄目なんじゃない? チャレンジ.失敗.

他の人見る.良くわからない.終了.


System Test

250,500が通る.


o o x 618.92 53/508 1405->1606

黄色に復帰.

codercoder2010/06/18 14:45黄色復帰おめでとうございます!
upper_boundは指定した値より「大きい」要素が最初に現れる位置を返し、
lower_boundは指定した値「以上」の要素が最初に現れる位置を返しますね。
lowerって「以下」とか「未満」っぽいから間違えそうですねw

ir5ir52010/06/18 15:12調べてみたのですが,そういう意味だったんですね.
↓のサイトを参考にしていたのですが,説明が誤っていたのか… ありがとうございます.
http://www5c.biglobe.ne.jp/~ecb/cpp/07_15.html

 |