naoya_t@topcoder

SRM452

23:04 |

11.05.2009

cafelier先生と同じ部屋

DIV	level	問題名	競技中	後で	System Test	通過率	備考
1	250	NotTwo	o	-	passed		227.51
1	500	IOIString	間に合わず	-	-		-
1	1000	IncreasingNumber	間に合わず				-

250点問題: NotTwo

oo--
oo--
--oo
--oo

で左上から埋めて行けばよいではないか

• 最初は4x4タイルと余りとで４分割して考えたけど
• そのまんまの4x4配列作ってmod4で愚直に足し算。
• 時間余裕だからってひどい...つまらないミスで落としたくないばかりに
• sample caseがわざと模様を外してるあたりが心憎い
• 以下、愚直なコード

#define rep(var,n)  for(int var=0;var<(n);var++)
int m[4][4] = { {1,1,0,0},{1,1,0,0},{0,0,1,1},{0,0,1,1} };
class NotTwo {
 public:
  int maxStones(int width, int height) {
    int st=0;
    rep(r,height){
      rep(c,width){
        st += m[r%4][c%4];
      }
    }
    return st;
  }
};

500点問題: IOIString

• 30分ほど悩んで見えないので1000点問題を開く（が無理そうなのが分かって戻ってくる）
• 最初DPでとか考えた
• しかし何をDPしたらいいか頭の中で二転三転しててまとまらない
• 誰もsubmitしてない
• どの位置にI...O...Iが含まれるかというパターン数は最大で1250x1249かな
• inclusion-exclusion principle(日本語で包除の原理っていうのかcafelierさんちで今覚えた)でってもパターンが1250*1249ぐらいあったら無理だよね
• 上の方の人たちがちらほらsubmitしてる
• 煮詰まった

1000点問題: IncreasingNumber

• 開いた
• 11111...で始まり、そのまま ...11111で終わるやつに始まり
• 11111...で始まり途中で８段上がって ..99999で終わるのとか
• ...
• 99999...99999までのうち
• divisorで割れるやつ...(10^k mod divisor)はループするよね
• 桁数1E18とか無理ゲー？
• あきらめたので試合終了ですよ

Challenge Time

• 防衛
• 500点の人は何人か落とされてた

System Test

• 防衛
• 250でfailedしてる人がいた
• 1000点誰も取れてない

結果

• 227.51点, 185/633位（部屋6/20）
• 1428→1518 (+90) また黄色

• 1000点とかもうちょっと冷静に考えれば行けたのか？あとでまた考えてみたい。（いずれにせよ75分じゃ無理だったか）
• yeharaさんと同じあたりをうろうろ...