Google Code Jam
友人の結婚式でワインをたらふく飲んだため、 死にそうになりながらエンジョイ参加しました。 - A : Magical, Marvelous Tour i番目のデバイスが持つコンデンサ数をc[i]とする 要はmax(c[0]+...+c[a-1], c[a]+...+c[b], c[b+1]+...+c[N-1])を最小化する問題 …
巨人-オリックス戦を観戦しに行っていたのですが、 息詰まる投手戦のまま延長に突入したため泣く泣く撤退しての参加でした。 野球の方は12回までやって1-0とかアツい展開だったらしいです。ぐぬぬ…。 - A : Data Packing 最初「1個のディスクにデータは高々2…
先のARCで運を使い果たしたので震えながら参加。 - A : The Repeater アルファベットの登場順を崩すような操作はできない なので与えられた文字列で、アルファベットの登場順が違うのがあったら勝てない 勝てるんだったら文字ごとに適当に個数を揃えてやれば…
残念な結果に終わった昨年のリベンジマッチ。 - A : Ticket Swapping 問題文長い…と思って一旦飛ばしたものの、他も難しそうだったので結局Aから。 端から入退場をシミュレーションして、一番新しいチケットで退場すれば良さそう。 そのシミュレーションをど…
お酒の力を借りて本気出した(?) - A : Osmos 制約を何となくしか見てなくて、N≦10^6 と勘違いする。 DPするだけかと思いきやそれは無理そう(と思い込む)。 削除操作を途中に挟んでも無意味そう。 でかくする→マージ出来ないの削除 をシミュレーションして最…
旅行中だったので、11:00-12:30を電車移動にあてて頑張ってみました。 - A : Bullseye 電車に乗ってから30分くらい席が空かなかったのでnexusで問題文だけ見てた。 オーバーフローに気をつけて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も組み上がらず、という残念な結果でした。解けたものから記事を残して、反省しておこうと…
友人たちとノープラン温泉旅行に出かけつつの参戦。 ノープランな中でわずかな時間を見つけて頑張ってみました。 - A : カードシャッフル 30分の電車移動が発生したので、おもむろにノートPCを起動して問題を読んだ。 TopCoderで同じような問題見たなぁ…。 …
勝手に勤務先を代表して出てるつもりになってみたラウンド。 - A : Irregular Cakes 問題：前衛的な形状のケーキをG等分する問題。 Round3なのにやるだけゲーだと… Wが小さかったので、ケーキはW個の台形として管理した ケーキ全体の面積Sを求めておく i番目…
この辺からはリアル知人がだいぶ減って寂しくなるラウンド。 - A : Airport Walkways 問題：長さXの直線上にところどころ動く歩道があって、基本は速度Sで歩きつつ、全体でt秒だけ本気出して速度Rで走るとき、直線を進み切るのにかかる最短時間を求める。 こ…
この週末は地味に予定が入っていたので、 1Aで通過しておきたいなーという感じでやってみました。 問題概要がだいぶ適当なのは仕様です。 - A : FreeCell Statistics 問題：今日はNゲーム以下を遊んで勝率がちょうどPD％，過去の戦績と合わせて勝率がちょう…
今年も調子に乗ってGCJに参戦。 今回は、何となくJavaで挑戦してみました。(Round1からは通常通りC++の予定) - A : Bot Trust 問題：2台のロボットでボタンを決められた順に押すための最短時間を求める問題。 各ロボットはボタンを押したら次に押すボタンに…
ここに来るまでギリギリの展開ばかりだったのに…。というRound3。 どっちにしろ、コンテスト中は精神的にギリギリだったわけですが。 - A : De-RNG-ed 問題：桁数がD以下の素数Pと，P未満の非負整数S[0]を選び，非負整数A，Bを用いてS[i+1] = (A*S[i]+B) mod…
正直、敗退しても文句を言えない出来のRound2でありました。 - C : Bacteria 問題：簡易版ライフゲームでバクテリアが滅ぶまでの時間を求める Aが低得点な割に面倒に見えたので、とりあえずCを。 smallは初期状態のバクテリアの分布が100×100のマス内に収ま…
午前4時過ぎまで研究室で作業 帰宅して就寝，午前8時半起床 10時からGoogle Code JamのRound 1A ＼(＾o＾)／ ←今ここ - A : Rotate 問題：ボードを時計回りに90°回転したとき、一直線上にRまたはBがK個以上並ぶか判定する 眠い・・・でも英語読む・・・分か…
Google Code Jamに挑戦してみる。 開催を知ったのは，Qualification Roundの前日でしたが・・・。 - A : Snapper Chain 問題：長さNのビット列があって，初期状態では全ビットが0。1度のsnapでは，先頭から続く1が全て0となり，続く1つの0が1になる。Nビット…
