hotpepsiの練習帳

TCO12 Round 1B

23:24

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は通過したらしい。