hotpepsiの練習帳

SRM 532 Div2

00:48

Easy (250) DengklekTryingToSleep

問題

• アヒルにAからBまでの番号がついている。
• 呼んだ番号が配列で与えられる。
• 呼んでいないアヒルが何匹かを求める。

方針

• とりあえず足せばいいか
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_532/DengklekTryingToSleep.cpp

Medium (600) DengklekMakingChains

問題

• 布切れの状態を表す3文字が与えられる。
• 文字はドットか数字である。
• 数字の部分だけをつなげることができる。
• 連続する数字の和の最大値を求める。

方針

• ドットがないやつと、左と右に分離
• 「数値ドット数値」は1回しか使わないようにする
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_532/DengklekMakingChains.cpp

Hard (950) DengklekPaintingSquares

問題

• N×Mのタイルがある。
• あるタイルに隣接するタイルの数が偶数になるように置く。
• 置き方の総数を求める。

方針

• 典型的なDPではある
• しめじたんのを読むが、自力では書けなさそう
• ありえる置き方を泥臭くテーブルで持ってみる
• なんとか書けた
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_532/DengklekPaintingSquares.cpp

結果

ox- 240.0+0=240.0 436th rating 1152 -> 1123

easyはソートして先頭と末尾から一発で求めればよいだけだった。

mediumは見直したのだけど落ちてしまった。submitしてからテストケースを作ればよかった。