翌朝も仕事だったけど構わず参加した今年最後のSRM。 - 250. Cut 問題：決められた切断回数以内で10cmのうなぎをなるべくたくさん作る 最大で長さ10mのうなぎ…ごくり。 とりあえず、長さが10の倍数のうなぎはお得 (length/10-1)回の切断で、10cmのうなぎがle…

旅路の新幹線の中から更新。たまにはこんな日も良いですよね。 - 250. MagicDiamonds 問題：与えられた自然数nを、最小何個の合成数の和で表せるか求める 合成数なら分解しなくて良いので答えは1 素数だったら、1+(n-1) あたりに分解しておけば2個で表せるの…

B : バクテリアの増殖 この問題を解くための基本アイディアとして n時間後のバクテリア数を x(n) とする ( x(n)^x(n) )%C = ( (x(n)%C)^x(n) )%C である ((x(n)%C)^p)%C = 0 となるpがなければ、x(n)%C のべき乗は値が循環する その循環の長さを y とすると …

C : ワイルドカード 以下のようなDP配列 dp[i][j] を用意する i : aにマッチし、最後の"*"を除くとi文字目までマッチするパターン j : bにマッチし、最後の"*"を除くとj文字目までマッチするパターン j = b.size()+1 のときはbにマッチしないパターンを表す …

D : クローゼットルーム smallは全探索っぽいし時間余ったらやろうと思ったまま忘れ去られた問題 1つの点から タンスの置き方4通り + 置かない1通り を試す 壁や他のタンスと重なったり、ドアが塞がったらその置き方は諦める という感じで、DFSしていけば良い

C : ワイルドカード 本戦では、なぜかlarge行ける！と思ってしばらくハマってた問題 「AにマッチするがBにマッチしない」という文面に気付くまで1時間かかった(´；ω；｀) largeを捨ててしまえば、smallは全探索で良い Aの文字を"*"で置き換えて、連続する"*"…

B : バクテリアの増殖 本戦では、smallでも多倍長がいるなぁと思って諦めたのですが…。 多倍長で計算すれば良いらしかったです。これは目からウロコでした。 勉強がてらpythonとjavaで書いてみました。 こうしてみるとpythonのお手軽感ぱない

先日行われた本戦は、Aで2WAも出したことで完全に動揺し、 Tシャツ圏内は入りそうだしと安心しきってC-Largeに挑んでいたところ、 気付いたらTシャツ圏外に、C-Largeも組み上がらず、という残念な結果でした。解けたものから記事を残して、反省しておこうと…

良いするめセットでした。(何を言ってるんだという感じですが) - 250. SRMCodingPhase 問題：SRMの3問それぞれを解くのにかかる時間と、解く時間をluck分縮める権利が与えられるので、得られる最大の点数を求める 点数高い問題から貪欲にluckを使う感じ？ 解…

友人たちとノープラン温泉旅行に出かけつつの参戦。 ノープランな中でわずかな時間を見つけて頑張ってみました。 - A : カードシャッフル 30分の電車移動が発生したので、おもむろにノートPCを起動して問題を読んだ。 TopCoderで同じような問題見たなぁ…。 …

久々に本番で解けなかったシリーズを書いてみる。Not Quick Transformation問題の概要 数列a = {1, 2, ..., N} が与えられる 数列aの奇数番目のみを並べた数列をodd, 偶数番目のみを並べた数列をevenとする F(a) = F(odd) + F(even) として新たに数列bを得る…

開催1時間前くらいに存在を知ってしまったので、修行の一環として出ることに。 解いた順に流れを追ってみます。 - A : Popularity Estimation 各時間で得られるポイントを調べてから、各キャラが得るポイントを調べるだけ 罠もなさそうだったので、さっくり…

ちょっとした辱めを受けたSRM。 - 250. YetAnotherIncredibleMachinet 問題：落下してくるボールが一個もぶつからないような板の配置は何通り? ボールの落下を全て受け止める問題だと思い込んで、しばらく悶絶した 冷静になって問題文を読み直したら簡単だっ…

社会人になって初めて平日深夜SRMへと突撃してみた、記念すべき512回目のSRM。 - 256. MysteriousRestaurant 問題：曜日ごとに特定のメニューを注文しなきゃいけないレストランで、最大で何日めまで食事できるか求める問題 i日目まで食事してみると決め打ち…

信頼と実績のLucky Numberゲーでした。 - A. Hockey 問題：文字列sのうち、禁則文字列で覆われる部分をテキトーに置換する問題 置換後も禁則文字列が残らないようにすると思ってて、無理ゲー…ってなった サンプルを見て、読み直すとレベル高めのやるだけゲー…

最近のTopCoderは鬱展開多めです。 - 250. Zoo 問題：ウサギとネコが自分より背の高い同じ動物が何匹いるか回答した状況から、答えに対するウサギ・ネコの割り当てが何通りあるか答える 同じ数字の回答が2匹づついれば、その2匹には割り当ての自由度がある 0…

勝手に勤務先を代表して出てるつもりになってみたラウンド。 - A : Irregular Cakes 問題：前衛的な形状のケーキをG等分する問題。 Round3なのにやるだけゲーだと… Wが小さかったので、ケーキはW個の台形として管理した ケーキ全体の面積Sを求めておく i番目…

前夜は夜更かししてE3の中継を見てたので、だいぶ眠い感じで参戦。 - 300. LuckyRemainder 問題：与えられた数字の空でない全ての部分列の和を9で割った余りを求める 9で割った余りとか桁ごとに使う回数の和を取るだけじゃないかｗｗｗ と思ったものの、使う…

この辺からはリアル知人がだいぶ減って寂しくなるラウンド。 - A : Airport Walkways 問題：長さXの直線上にところどころ動く歩道があって、基本は速度Sで歩きつつ、全体でt秒だけ本気出して速度Rで走るとき、直線を進み切るのにかかる最短時間を求める。 こ…

この週末は地味に予定が入っていたので、 1Aで通過しておきたいなーという感じでやってみました。 問題概要がだいぶ適当なのは仕様です。 - A : FreeCell Statistics 問題：今日はNゲーム以下を遊んで勝率がちょうどPD％，過去の戦績と合わせて勝率がちょう…

UTPC2011個人戦5時間という、久々にハードな戦いに行ってきました。 美少女セットでした。 - A. プログラミングコンテスト やるだけだったので、コンパイルもせずに投げてみて無事AC。 それでも提出は遅めで、驚愕した。 B. (iwi) やるだけだったけど、一応…

今年も調子に乗ってGCJに参戦。 今回は、何となくJavaで挑戦してみました。(Round1からは通常通りC++の予定) - A : Bot Trust 問題：2台のロボットでボタンを決められた順に押すための最短時間を求める問題。 各ロボットはボタンを押したら次に押すボタンに…

社会人としてのSRM初陣。 - 300. RectangleArea 問題：n×mに分割された長方形の各部分の面積をなるべく少ない回数聞いて、全体の面積を当てるクイズ。 300か。これ無理じゃね…。 しかし、思考停止したら終了なので何か考えてみる i番目の縦幅をR(i), j番目の…

赤い人として挑んだ最初のSRM。 - 250. FoxPlayingGame 問題：0に操作A(scoreAを足す)nA回と操作B(scoreBをかける)nB回を好きな順で行ってできる最大の数を求める。 タイトルだけ見て、日本人writerなんだろうなぁ…とか思う。 まぁ、操作Aと操作Bの残り回数…

記念&追悼SRMでした。 - 250. MafiaGame 問題：N人がいて互いに投票しあう。まず投票する人を決めているM人が投票をし、次に残りの人が得票数が最も少ない人から1人をランダムに選び投票する。最多票が同率のときは残り1人になるまで決選投票を行うとき、最…

久しぶりに参加記を書いてみたり。 - A. Irrational problem 問題：p1, p2, p3, p4, a, bが与えられたとき、[a,b]の区間の整数xのうち、x mod min(p1, p2, p3, p4) = x になるものの個数を答える 問題文が長かったのでテキトーに読んでこう理解した。 単に、…