Hatena::Grouptopcoder

yowa の TopCoder 日記

TopCoder yowa / twitter: @yowa

2010-07-18

SRM 476 DIV2

04:48 | SRM 476 DIV2 - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク - SRM 476 DIV2 - yowa の TopCoder 日記

本番初挑戦。

事前に登録は済ませたものの、開始時間前になってアリーナを開こうと思ったら TopCoder のサイトに全然つながらない。

開始時間過ぎてもダメ。悔しいので風呂にはいる。

風呂から出て、ダメ元で Firefox のダウンロード履歴の「ContestAppletProd.jnlp」をダブルクリックしたらアリーナにつながった。やった。30分ほどの遅刻。

300 MatrixShiftings

パネルを上下左右にシフトさせる。目的の数字が左上にくるには、最低何回シフトさせるか?

パネルに同じ数字が複数出現し得るので、最小値を取るのを忘れずに。

なぜかvectorの添字を 1-origin だと勘違いしたコードを書いてて、テストを通らず焦った。

submit。

500 Badgers

事前にこれを見ていたので、問題の書き出しの "Badgers are lovely furry animals," を読んだ途端「もっふもふだよ!」と AA が去来した。"badger" はアナグマらしい。

badger は他の仲間がエサを食べてるところを見ると、自分もさらに食べてしまうそうな。

各個体ごとののhunger(本来必要な食べる量)と greed(仲間1匹あたりにつられて食べる量)、および用意できるエサの量が与えられたとき、最大何匹養えるかを答える。

どうやるんだこれ。手が止まる。

とりあえず全員養うのに必要なエサの量を求めて、そっから greedy に1匹ずつ減らしていけばいいんじゃね?

書いた。テストも通ったのでsubmit。

1000 SubAnagrams

引数の文字列が AAXAAAABX だったら A-A-XA-AAABX のように、各区間が、その1個右の区間の substring のアナグラムになるような区切り方を考えて、最大区切り数を答えよ。

「条件を満たすように2分割して、右側の文字列を再帰」がマズいのは分かる。

BBA -> B-BA はおkだけど ABBA -> A-BBA -> A-B-BA はマズいもんな。

再帰の途中でもう一度左側の条件チェックすれば無問題なんじゃね?と思い、コードを書き始めたところでTime Up。

Challenge

部屋で 1000 点を解いてるのが2人。どっちも左側の条件チェックしてないっぽく見える。

そのチェックをしなくても、用意されてるサンプルは通るもんな。

でも勇気がないからなかなか Challenge に踏み切れず、ギリギリでtest case を入力し始めるも間に合わず。

System Test

500 が通らなかった。

結果

300MatrixShiftingsAC
500BadgersWA
1000SubAnagramsOpened

Rating: (無) -> 1170

終わってから

開始時間に間に合ってれば 1000 の submit は行けたかもだけど、どっちにしろ落とされそうではある。

500 は考え方が根本から間違っていた。n 匹飼うときに必要なエサ量を個体ごとに求めて、ソートして小さい方から合計すればよいではないか。→確認したら通った。