2011-05-01から1ヶ月間の記事一覧
Problem C: Towns along a Highway http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1307 問題概要 街が20個くらいある。 すべての街同士のペアの距離情報が与えられる。 考えられる全ての街の配置を求めよ。 一次元です。
問題概要 サイコロにステッカーをはる。 ステッカーの色がstringのvectorで与えられる。 隣り合う面が同じ色であってはいけない。 与えられた色のリストでそのような張り方が実現できるか答えよ。
結果 oxx 268th レートがとっても上がった。 よかったことは、250の解法がすぐ思いついたこと。 わるかったことは、書けてから提出にもたついたこと。 500に怪しげな方法で挑んだこと。 500が本当に怪しげかあってるのか未検証。 もっとすばやく行動したい。
Find the Winning Move http://uva.onlinejudge.org/external/101/10111.html 問題概要 4目並べで次どのような行動すれば勝てますか? 勝てる手を左上から順番にみて、一番最初のものを出力せよ。 引き分けまたは負ける場合は#####と出力せよ。 与えられる盤…
問題概要 4と7で終わる数字はラッキーナンバー。 数字nが与えられた時、nをラッキーナンバー何個の和で表すことができるか。 できないなら-1, できるなら最小何個の和で表すことができるか。 n
UVa 11846 Finding Seats Again http://uva.onlinejudge.org/external/118/11846.html 問題概要 最大20*20の正方形のグリッドがあたえられる。 グリッドにはところどころに、1〜9までの数字が入っている。 各数字はその数字が含まれるべき長方形の面積を表…
問題概要 n曲のリストが与えられる。 曲によって長さが違う。 聞く曲を選ぶときランダムに選ぶ。 t分きいたときに、どの曲をどのくらいの確率で聞いてるか返せ。
問題概要 ある人たちに少なくとも何人この中に嘘つきがいるか聞く。 嘘つきな人は、絶対実際より多い数をいう。 正直な人は、実際以下の人数をいう。 考えられる最低の嘘つきの人数を答えよ。 解法 考えられる人数の人数を全部試す。 嘘つきの人数を決めると…
問題概要 47人の人がいる。 あなたは10^18円くらいお金をもっている。 みんなそれぞれお金を持ってる。 一番お金が少ない人に対して、全員の平均より大きいの最小の整数円 になるようにお金をわたす。 たりない場合はありったけ渡す。 お金がある間繰り返す。…
問題概要 マスが50個のすごろくみたいなのをする。 スタートゴールは普通のマス。 その他のマスにK, もしくはCと書かれている場合がある。 それ意外は普通のマス また、K, C の二つの整数が与えられる。 すごろくをはじめてから経った時間をTとする。 T % K…
問題概要 WとBからなる文字列が与えられる。 長さがnである。 1~nまでの距離の文字の位置を入れ替えることができる。 それぞれの長さは一回しかつかえない。 最小何ステップで全てのWが全てのBの左側にできるか。
結果 oxx +1 428th 相変わらず、easyは遅かった。 まぁでも、ちゃんと1千万まで自分の仮定が正しいか試したりしたので、無駄な時間はなかったと思う。 submitしてから仮定を検証すればよかったかもしれない。 mediumは、オーバーフロー。 気をつけよう。 で…
Layout http://poj.org/problem?id=3169 問題概要 N匹の牛を飼っている。 牛は1〜N番目の牛まで順番に並んでいる。 いくつかの組み合わせについて、その牛同士の距離について、上限あるいは下限が与えられる。実現できる最後の牛と最初の牛の最大の距離を求…
問題概要 最大50個の街がある。 それぞれの人口が与えられる。 これらの街を一つに統合していく。 ある二つの街を統合するとき、人口の多い方の街の名前になる。 一つの街にしたとき、何種類の名前があり得るでしょうか。
結果 oxx easy 164.59 435th 遅すぎた。 自分の思いついた解法にあわせて、問題の制約を知らないうちに変えてて 書き出してから気づくことが多いので、ちゃんと落ち着いて問題を考えよう。
結果 撃沈。 ちゃんとそれで解けるかよく考えましょう。 サンプルを当てにするな。
Problem C: Matrix World http://uva.onlinejudge.org/external/102/10231.html 問題概要 グリッド上にロボット(複数)と壁と人(一人)とダイアモンド(複数)がある。 ロボットに捕まった時点で終了。 人はダイアモンドを拾うときコスト1かかる。 ロボッ…
問題概要 最大50*50に分割されたグリッドが与えられる。 それぞれのセルの大きさは異なっている。 いくつかのセルの面積が最初から明らかになっている。 明らかになっているセルの場所が与えられる。 あと最低いくつのセルの面積を知ることができれば、 全体…
問題概要 生焼けしたパンの数と焦げたパンの数、 それぞれ、どれだけ焼いたかの時間が与えられる。 最低何種類のパンが存在したと考えられるか。 ただし、同じ種類のパンは同じ時間を境に生焼けになったり、こげすぎたりする。 また、その境を絞り込めないよ…
502 medium 504 easy medium 504.5 easy 503 easy 505 easy 506 easy medium 507 easy 508 easy medium
問題概要 50問の問題がある。 それぞれの問題について 点数 解くためにかかる時間 1秒たつごとに減っていくその問題の点数 が与えられる。 使える時間T(最大100,000)が与えられる。 得られる点数を最大化せよ。
Problem B - Consecutive Integers http://uva.onlinejudge.org/external/112/11254.html 問題概要 ある整数を連続する正の整数の和で表せ。 n ≤ 1000000000
Tile Puzzle http://uva.onlinejudge.org/external/7/798.html 問題概要 100*100までのパズルがあたえられる。 10種類までのピースがあたえられる。 何通りでそのパズルを完成させられますか。 ある場所のピースの種類か向きが異なると、違う完成方法と数え…