Algorithm
250 Passed System Test 217.55 550 Compiled 950 Opened 550は無理ですって。しかもad-hocな感じの苦手な問題だし。さらに250がかなり簡単なやるだけ早解きゲー。早解きも苦手だというのに。まず250を217.55という点数でSubmitしたのが痛すぎる。217.55はど…
250 Passed System Test 179.60 500 Passed System Test 311.19 1000 Opened 初めてMedium通せた！のは嬉しいんだけど、今回のMediumは気付けばとても簡単だったのでもっと早く提出すべきだったなぁ。Mediumが初めてのせいで警戒しすぎたところはあった。撃…
F#で書いた。工夫した点？知りませんなぁ。
本番で解けなかったもの。以下考え方とソース。
今日の分。28問。 PKU 2499 Binary Tree PKU 1251 Jungle Roads
これは嘘で実際は解いていません、みたいなことはないので安心してね！ PKU 2470 Ambiguous permutations PKU 2031 Building a Space Station PKU 2524 Ubiquitous Religions PKU 2251 Dungeon Master 累計26問。
解いた報告ばっかりだとつまらないし、自分が忘れないためにも解法をメモしておこうと思う。実装ゲーについては解法も何もあったもんじゃないので書かない。とりあえず普通に解いたらTLEしたりするような、頭を使って解く問題に関してはメモする。そしてこれ…
凡ミスはもう嫌です
練習だと何故か出来る俺
timer =: 6!:2 NB. 実行時間が計れるよ！ fib =: ($:@-&2 + $:@:]) NB. ふつうにフィボナッチ数を求める fib"0 (i.18) 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 fibx =: ($:@-&2 + $:@:]) M. NB. M.をつけるだけでメモ化しちゃう fibx"0 (…
情報オリンピックに備えてC++での挑戦。
ソース長いので
TopCoderでnext_permutationゲーな問題が出ると途端にC++が有利になって、C#だとコーディング時間的に厳しいので、C#で実装しておく。パフォーマンスなんて知りません。2009/1/23 バグ修正＆TopCoder SRM 433 Div 1 Easy MagicWordsでVerified using System;…
やたーHard解けたよー
問題 いつ、どこから、どこまでエレベータを利用するかという情報が与えられるから、エレベータが最善の動きをしたときに全員を運び終えるまでにかかる時間はどれくらいですか。 解 人が全部で5人(！)しか居ないから全部試す。 using System; using System.T…
問題 マインスイーパ的ゲームで、最初の一個が爆弾なら負け、最初の一個が爆弾でなくその周囲にも爆弾が存在しないなら勝ちとする。ゲームフィールドが与えられるので勝率を求めなさい。 解 やるだけ。これは解き慣れるしかないぜ。 using System; using Sys…
問題 子、母、男のDNAっぽいのが与えられるので、男が子の父親かどうか判定してねっていう。母からのDNAを半分、男からのDNAを半分ずつそれぞれ子が引き継いでいる場合は父親だと思うよ。 解 男と子の間の一致数が半分を超えて、かつ男と母どちらでもないDNA…
問題 コンテストの結果をソートしてください。 解 めんどい。やるだけ。 using System; using System.Text; using System.Text.RegularExpressions; using System.Collections; using System.Collections.Generic; public class Data : IComparable { public…
問題 条件にマッチする文字列はどれ？っていう。 解 適当に変換して調べる。 using System; using System.Text; using System.Text.RegularExpressions; using System.Collections; using System.Collections.Generic; public class CheatCode { public int[…
問題 問題長すぎだろ・・・ｊｋ・・・ 解 問題読めれば問題はない。 using System; using System.Text; using System.Text.RegularExpressions; using System.Collections; using System.Collections.Generic; public class Inventory { public int monthlyO…
問題 ちょっと変わった言語処理系実装してね。言語仕様まで全部書くとめんどくさい。 解 ハイパーやるだけ。最初MISMATCHの意味を取り違えてて色々なんかアレ。ソース汚物。 using System; using System.Text; using System.Text.RegularExpressions; using …
問題 あんまり読めてない。Example頼りの問題解釈なので説明できない。 解 数がちっちゃいので全部やった。 using System; using System.Text; using System.Text.RegularExpressions; using System.Collections; using System.Collections.Generic; public …
問題 数列が与えられる。これをマージソートした時に比較の回数は何回になりますか。 解 テラやるだけｗｗｗｗ using System; using System.Text; using System.Text.RegularExpressions; using System.Collections; using System.Collections.Generic; publ…
問題 円に正n角形を内接させて、その正n角形の周を円周としたときの円周率の近似を求めなさい。 解 最初余弦定理がどうたらこうたらであばばばばばばってなって、結局精度が悪くてTest落ちた。その後某IRCの助けをいただいて理解。 23:07 (JAPLJ) PI = 180° …
問題 あるキャンバスに縦のストライプを塗る。ストライプの柄が与えられるので、最小で何回キャンバスに描けば模様が完成するか。 解 俺の嫁ですとも。ええ。動的計画法です。 using System; using System.Text; using System.Text.RegularExpressions; usin…
問題 ある自然数n(2 ≦ n ≦ 30)について、n進法で数を表記したとき、ある一桁の数kの倍数は全てその桁を合計するとkの倍数になるようなkを全て求めなさい。たとえば10進法において、 159 * 3 = 477, 4+7+7 = 15 = 3 * 5 なので3が該当する。 解 全部やればい…
問題 単語一覧が与えられるので、与えられた文字列の適切な位置にスペースを挟んで、もとの単語の並びを復元しなさい。ただし複数の解が存在するなら AMBIGUOUS! を、解が存在しないなら IMPOSSIBLE! を返しなさい。 解 最初に必殺総当り再帰で解いて、時間…
問題 待ち行列に人がどんどんやってきて、注文をして、食品を受け取って帰っていく。来た順に、「いつ来たか」と「注文してから食品を受け取るまで何分かかったか」の情報が渡されるので、列に入ってから注文まで一番待たされた人は何分待たされたか求めなさ…
問題 ミーティングの時間に遅れたり早く来たりするんだけど、全てのミーティングを同じ時間だけずらして待ち時間が最低になるようなずらしかたが何通りありますか。 解 全ての時間を同じだけずらすので、会議の待ち時間順で考えて真ん中にあるぶんだけずらす…
問題 8人でトーナメント形式の大会を行う。ある人が他のある人に勝利する確率が与えられるので、8人それぞれが優勝する確率を求めなさい。 解 n人目が決勝に出る確率 r[n] は、i人目がj人目に勝てる確率を p[i, j] とすると b = {2, 0, 6, 4}[n / 2] r[n] = …
