2012-04-12
SRM 540
Div1 Easy (250) ImportantSequence
問題
- N+1個の数値からなる数列があり、各数値の間に+か-を書いた。
- 演算子と計算結果のN個の数値からなる数列が与えられる。
- 元の数列の組み合わせの個数を求める。
方針
- 無
- 適当に書いたら撃墜された
- cafelierさんのを写経
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_540/ImportantSequence.cpp
Div2 Easy (250) RandomColoringDiv2
問題
- フリスビーを2色で塗る。
- 上の色と、取りうる範囲が与えられる。
- 下の色は、上の色と同じでなく、かつ、違いすぎもしない色である。
- 下の色に使える組み合わせの個数を求める。
方針
- コーナーケースいまいち自信なし
- d2の範囲から、d1未満の中心範囲を引く
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_540/RandomColoringDiv2.cpp
結果
x-- 0pt 381st rating 1373 -> 1363
できなさすぎ。challengeはlong longを投げつければ良かったらしい。
2012-04-08
TCO12 Round 1B
Easy (250) FoxAndKgram
問題
- 何本かの鉛筆がある。
- 1本が長さk、または、2本でk-1の長さとなる鉛筆をk段並べたものをk-gramと呼ぶ。
- 与えられた鉛筆の組み合わせで可能な最大のk-gramを求める。
方針
- 慎重にいく
- そのままの長さのを+1していく
- k-1になるやつをフラグつけて+1していく
- https://github.com/firewood/topcoder/blob/master/tco_2012/FoxAndKgram.cpp
Medium (500) FoxAndDoraemon
問題
- のび太くんは夏休みの宿題がたまっているが、一つこなすのがやっとである。
- そんなのび太くんにドラえもんが分身ハンマーを出してくれた。
- 分身ハンマーを使うとのび太くんは二人になる。
- それぞれののび太くんは最大でも一つしか宿題をこなさないが、
- 分裂したのび太くんも分身ハンマーを使うことができる。
- 分身ハンマーの準備時間と宿題の処理時間が与えられる。
- 宿題が終わる最短時間を求める。
方針
- 分裂するか処理するかの2分木
- メモ化再帰
- タスク時間はソートしておいて、処理は長いのから使う
- バグりまくり
- 終了後書き直し
- https://github.com/firewood/topcoder/blob/master/tco_2012/FoxAndDoraemon.cpp
結果
o-- +1-1 229.07 + 50 -25 = 254.07 516th rating 1334 -> 1373
問題文が面白い!
easyしか通ってないので1チャレンジとらないとと思ってがんばってみた。
mediumは典型問題なのに全く解けなくて絶望した。さっき見たらメモ化の変数の初期化忘れだった。間抜けであるが解法自体は合っていたのでよしとする。
ratingはSRM539がunratedだったのに助けられた。運もなんとやら。
なんとかR1は通過したらしい。
2012-04-05
SRM 539
Div1 Easy (250) Over9000Rocks
問題
- 手持ちの岩がいくつかあり、9001個以上所有しているように見せかけたい。
- n個の箱があり、それぞれa個以上b個以下の岩が入っているように見せかけることができる。
- 9001以上の数値が何通り作れるかを求める。
方針
- ライブラリ問題?と思って蟻本読んだりして時間を浪費する
- std::pairに範囲を突っ込んでごり押ししてもできそう
- 間に合わず、終了後解いた
- 最も単純な解法は、その箱を範囲を使うか使わないかで2^N-1個の範囲を作る
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_539/Over9000Rocks.cpp
結果
___ 0pt
easyはいろんな解き方ができそう。system test終わってからようやくできた。
mediumは題意がまだつかめてない。なんかジャッジ解が微妙のようである。
その他
GCJ勉強会に参加してからちょうど一年経過した。記念の日に零点なのであまり成長してない感じではあるけど、一年前に比べてだいぶ楽しめるようになったのが進歩である。
解けそうで解けなかったやつは後で解こうと思っていて、結果的に毎回参加記を書くことになったので我ながらまめである。
続けられた理由としては(1)GCJ勉強会が大変よかった(2)TopCoderの制限時間が適度に短い(3)ratingが上がるのが楽しい(4)Twitterで刺激を受ける(5)コード書くのが楽しい、ということかなと思う。
アプリケーションプラネットの備前さん、講師のちょくだいさん、りんごさん、ありがとう!
2012-04-04
TCO12 Round 1A
Easy (250) EllysJuice
問題
- みかんジュースとりんごジュースが1ガロンずつある
- n人で、1ターンにみかんとりんごを交互に飲む
- 一度に残量の半分飲む
- 一番飲んだ人が勝ち
- ただし一番が複数いる場合は勝ちなし
- 勝つ可能性がある人の名前のリストを求める
方針
- 3人の場合とかで自信がないのでnext_permutationで全探索
- 解きなおし
- https://github.com/firewood/topcoder/blob/master/tco_2012/EllysJuice.cpp
Medium (500) EllysFractions
問題
- 約分できない分数A/Bを既約分数と呼ぶ。
- A×Bがnの階乗で表せるとき、それを「階乗分数」と呼ぶことにする。
- A/Bは0より大きく1未満
- 数Nが与えられるとき、A×BがN!以下の階乗分数の総数を求める。
方針
- 256未満の素数表を用意しておく
- 候補数の初期値は1
- 1からNまでループして候補数を加算
- 素数が出てきたら、候補数を2倍にする
- https://github.com/firewood/topcoder/blob/master/tco_2012/EllysFractions.cpp
結果
xo- -1 149.55*0 + 251.57 - 25 = 226.57 780th rating 1322 -> 1334
easyはnext_permutation対象の配列の扱いがバグっていて落とした。それよりも判断＆実装が遅かった。
mediumは紙に書いたら素数が増える毎に2倍になっているようだったので、なんとなく書いたら通った。まぐれだけど結果オーライ。(a)素因数毎にまとめる≒素数の数(b)どちら側に使うかどうかの2択なので2倍になっていく(c)AとBの小さいほうが分子になるので大小関係の判別は不要、というようなことを考えればよいようだ。
予選通過には400点ちょい必要だったらしい。あと二歩くらい...
2012-04-03
Codeforces 114 Div2
A. Wizards and Demonstration
問題
- ある町の人口はn人である
- そのうちx人が魔法使いである
- 魔法使いは操り人形を召還できる
- 魔法使いと操り人形がデモをする
- デモに参加する人数が人口のy%を超えるために何体の人形を召還する必要があるかを求める
方針
- (x+p)÷nがy%を超えるようにする
- 1ずつ足しても十分間に合う
B. Wizards and Minimal Spell
問題
- 先頭が#の文字列は呪文である
- それ以外の文字列は呪文ではない
- 呪文はそのまま、それ以外の文字列の空白と改行を取り除く
方針
- 特に悩むところなし
- きちんとバッファをフラッシュするようにする
- 呪文でない場合の最後に改行を忘れないようにする
C. Wizards and Trolleybuses
問題
- n台のバスが始発から終点まで運行する
- それぞれのバスの加速度は同じ
- それぞれのバスの最大速度と発車時刻が与えられる
- 途中で前のバスに追いついた場合は追い抜かず、ぴったりくっつく
- それぞれのバスの終点の時刻を求める
方針
- 最大速度まで加速
- 最大速度からは一定速度で移動
- ひとつ前のより到達が早ければ、ひとつ前の時刻にする
結果
ooo-- 398+808+972=2178pt 98th rating 1597 -> 1651
Dは題意がつかめなかった。
順位は良かったけれど、あまり解けている感はなかった。