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 になるものの個数を答える 問題文が長かったのでテキトーに読んでこう理解した。 単に、…

hos' Xmas Contest 2010夜の部に参加したので、参加記的なものを。 取り組んだ問題順がカオスだったので、最終提出の時間順で書きます。 - B. Simple Parsing Aが60%で止まってしまったので先にBへ。 偶奇だけ分かれば良いので適当な事しても良いんだろうな…

I. Operatorなんか講評よりオーダーが良かったので晒してみます。 嘘の告発は(ry 一応、二分探索＋ちょっとではありません。解法 基本はJAGの講評に準拠 オペレータの数が小さい方からシミュレーション オペレータは区別しなくて良いので各時間でヒマな人数…

F. Two-Wheel BuggyAOJに投げてみたらコードサイズがだいぶ小さかったので晒してみます。 嘘の告発は大歓迎です。解法 直進か曲がるかの2通りに場合分けして処理する 車の状態は，2個のタイヤの中点pと車の方向dirによって管理 直進(左右の回転数が一緒)はや…

信頼と実績の問題クオリティーで楽しめた回でした。 - 250. BunnyComputer 問題：n個の数字の配列から，K個間隔の2個のペアを取っていく。とれる数字の和の最大値を求める う…うさぎだと…。 とりあえずペアを取る操作で関係するのはK個離れた数字どうしなの…

2回目のCodeforces format。そして初めてのHacked…orz - A. Extra-terrestrial Intelligence 問題：与えられた01列に出現する1が等間隔に現れてるかを判定する 与えられる文字列の長さは最大100 調べるだけ。何故か面倒な実装にしてしまって少し時間がかかっ…

久々にCodeforcesに参加し、初めてのCodeforces format。 結局はHackする事もされる事もなく、順位的にも平常営業に終わりました。 - A. What is for dinner? 問題：m列に並ぶn個の歯があって各歯にはHPがある。食べ物1個を食べるには歯を1列使って、使った…

密かにバースデーSRMだったので、妙な緊張感と戦う羽目に。 - 250. TheCoffeeTimeDivOne 問題：乗客のお茶orコーヒーのオーダーを全て消化するための最短時間を求める。 貪欲に後ろから配れば良いんだろうなぁ…と思いつつ，貪欲でやる勇気が出ない。 貪欲に…