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コーヒーのオーダーを全て消化するための最短時間を求める。 貪欲に後ろから配れば良いんだろうなぁ…と思いつつ，貪欲でやる勇気が出ない。 貪欲に…

久々にCodeforcesに参加。 しばらくレーティングが水平線でしたが、今回は良い感じの順位を取ることができました。 - A. Ring road 問題：n個のノードが有方向の枝でリング状につながっている。各ノードに方向を反転させるコストが定められてて、ノードを全…

なぜかRound3を通過してしまったので、ｶﾞｸﾌﾞﾙしながら参加してきました。 - 250. BankLottery 問題：n人がaccountBalance[i]ドルずつ銀行にお金を預けてて、週に一度、誰か1人を(預金額/全員の総預金額)の確率で選んでjackpotドル振り込む。自分が0番の人だ…

AOJで通ってしまったので、その記録を晒してみます。F. 古い記憶基本的な方針は以下の通りです。 ピースをつなぎ合わせて(深さ優先で)文字列を生成していく 改ざん文書に対し編集距離d以下のものが出来たら答えに追加 さすがにナイーブに書いたら遅すぎたの…

数時間後に演奏会を控えていますが、Round3に出ればTシャツをくれるというので参加してきました。 - 250. SieveOfEratosthenes 問題：エラトステネスのふるいで2からmaxNumまでの数を処理したときに、最後にふるわれる数は？ maxNumは4以上20億以下。素直に…

E. 最強の呪文下に書いた話で、 倍くらい調べればループを使って辞書順を小さくする文字列が見つかる ゴール以外で6*(ノード数)くらいでループなしより辞書順で小さくなったら"NO" とか言ってるので，倍くらい調べなくて良い事に気付きました。 "NO"になる判…

G. レーザー光の反射解法 レーザーが当たる鏡の順番を全列挙する 反射回数は高々5で，鏡の枚数も高々5なのでそんなに多くない 各反射順ごとに，レーザーの照射角度を求める 反射順に鏡を選び，照射地点の鏡像を取っていく 最終的に得られる照射地点の像の方…

id:kusano_progさんに先に書かれてしまいましたが…。E. 最強の呪文解法 [現在の呪文の長さ][現在地] を使った拡張ダイクストラ 文字列A, B, Cに対して、一般にmin(A+C, B+C) = min(A, B) + Cは成り立たない が，AとBの長さが同じなら成り立つので文字列長ご…

D. ぐらぐら解法 仕様どおりに実装するだけの簡単なお仕事 以下の実装では、再帰を使った深さ優先探索を行っている isStable:(_y, _x)の位置にあるピースが安定ならtrueを返す Mは関係するピースの座標値(+0.5)の合計 cntは関係するピースの個数 重心のx座標…

C. ポロック予想解法 動的計画法 Nを何個の正四面体数で表せるかは，1〜N-1の答えを使って求められる ansA[i]を「iを表すために必要な最小の正四面体数の数」とする 正四面体数1, 4, 10, 20, …に対し， ansA[N] = min(ansA[N-1], ans[N-4], ans[N-10], …) + …

B. 迷図と命ず解法 入口から幅優先探索 データが綺麗に成形してあるので、文字列のまま持っておくと楽 座標を2倍すると文字列上での現在地に対応する #include <iostream> #include <queue> using namespace std; char dx[] = {1, 0, -1, 0}; char dy[] = {0, 1, 0, -1}; int </queue></iostream>…

こっそり国内予選の問題を解いたので、記録でも書いてみます。 ちなみに、Fは自分の実力では謎。 あと、問題の概要は問題文が日本語なので省略します。A. 角角画伯，かく悩みき解法 問題文通りに各タイルの位置を計算する i番目のタイルの位置(x, y)を配列で…

研究室の生き残りが自分だけとなってしまって若干心細いRound 2。 - 250. SnowPlow 問題：N個のノードからなる有向グラフがあって，i->jの枝がK本あればj->iの枝もK本ある。ノード0からスタートしてすべての枝を通るための最小コストは？通れない枝が存在す…

研究室の後輩たちがだいぶ頑張ってるっぽいのでプレッシャーを感じつつ。 - A. World Football Cup 問題：W杯の予選リーグをnチームでやった結果が与えられるので、上位n/2チームを出力する。 順位は「勝ち点⇒得失点差⇒総得点」で決める。 これで同着になる…

GoogleCodeJamが落ち着いたところで、今度はTopCoder Open。 ちょっと眠かったので寝オチだけが心配でしたが…。 - 250. EqualizeStrings 問題：文字列s, tそれぞれに，「1文字を選びアルファベット順で1つ進める or 戻す」という操作を加え、sとtを同じ文字…

本番で解けなかったシリーズ。Balance問題の概要 文字a, b, cからなる、長さ150以下の文字列sが与えられる 文字1つを隣接するどちらかのものと同じにする操作を何回か加える s中のa, b, cそれぞれの数の差が高々1になるような文字列は何種類作れる？ 解法 あ…

ここに来るまでギリギリの展開ばかりだったのに…。というRound3。 どっちにしろ、コンテスト中は精神的にギリギリだったわけですが。 - A : De-RNG-ed 問題：桁数がD以下の素数Pと，P未満の非負整数S[0]を選び，非負整数A，Bを用いてS[i+1] = (A*S[i]+B) mod…

サーバー落ちで流れて以来のCodeforces。 最近コンテスト続きなので気合十分で挑んでみたのですが…。 - A. Noldbach problem 問題：2以上n以下の素数のうち，隣接する2つの素数の和+1で表せるものの数がk個以上かを判定する nもkも1000以下と小さいので，何…

正直、敗退しても文句を言えない出来のRound2でありました。 - C : Bacteria 問題：簡易版ライフゲームでバクテリアが滅ぶまでの時間を求める Aが低得点な割に面倒に見えたので、とりあえずCを。 smallは初期状態のバクテリアの分布が100×100のマス内に収ま…

午前4時過ぎまで研究室で作業 帰宅して就寝，午前8時半起床 10時からGoogle Code JamのRound 1A ＼(＾o＾)／ ←今ここ - A : Rotate 問題：ボードを時計回りに90°回転したとき、一直線上にRまたはBがK個以上並ぶか判定する 眠い・・・でも英語読む・・・分か…

本番で解けなかった問題シリーズ．問題 長方形の上辺と下辺にそれぞれn(≦10000)個の点が打ってある 上辺の点と下辺の点すべてを1対1でランダムで結ぶ 高々50個のペアは既に線が結んである 交差する線分のペアの数の期待値は？ 解法 上辺の2点について，そこ…

本番で解けなかった問題シリーズ．問題 部屋0から部屋nが一列に並んでて，部屋はドアで区切られてる ドアは高々16種類の色で色分けされている Johnが部屋0，Gogoが部屋nにいて，交互にドアを開けながら部屋trophyを目指すゲーム ルール：John先攻で，自分の…

これで#13との因縁を清算できる・・・。というわけで今度はE問題です。問題 1番からN番までの番号を持つ穴が一列に並んでて，各穴は正整数のpower[i]をもつ。 穴iに玉を入れると，玉は列から出るまで，穴i+power[i]への移動を続けていく このルール上で，以…

本番中に解けなかった問題シリーズ。今更ですが，前回のCodeforcesより。問題 平面上にN個の赤い点とM個の青い点があって，NもMも最大500。 赤い点からなる三角形のうち，内部に青い点を含まないものの数は？ 制約として，どの3点も同一直線上にはない 解法 …