簡単な550と論理パズルな1000の組み合わせ。(1000はマイクロソフトが大好きな問題。) 250 booleanの二次元配列について、ある行ないし列を見たときにどれか一つでもtrueならtrueで、そうでなければfalseという値がすべての行と列について与えられる。このと…

500よりも簡単な1000でした。これは良問だと思う。(500で出てていいと思うけど。) 1000 文字列が三つ与えられるので、それぞれから適当に文字を除去して、全部が同じ空でない文字列になるようにするとき、最終的にできる文字列は何種類あるか答えよ、という…

深夜に更新しようとすると日付が前の日、という状況は設定いじれば解消するらしい。実際に動いているかどうかは次のSRMまで分からないけど。 250 与えられた整数がフィボナッチ数列の何番目に出てくるか答えよ、という問題。出現しないものは、直前に出現す…

昔似たような500をやったことがあるので、同じ方針でやったらTLEするという悲しい500が...。他の方針が浮かばなくなるくらい普通の方針なんだけどなぁ...。 250 N人待っている人がいて、それぞれの待っていた時間が与えられる。K人まで並列処理ができ、一人…

全然ダメなセット。こういうのが出ると手に負えないというか、必ず間違えるというか。 250 長さKのものがN個あるとき、大きさLの箱に入れる場合、箱はいくつ必要か答えよ、という問題。ただし、箱の中に13の倍数個入れてはいけない。 13の倍数という条件がな…

500に1時間かかったので、250に逃げたら15分ギリギリだった。かなり手強いセット。 250 文字列が複数与えられるので、それをPermutateして結合した文字列のうち、Rotateした時に自身に一致するインデックスの数がちょうどK個のものの数を求めよ、という問題…

250 同じ大きさのカードを使って、カードが落ちないように少しずつ外側にせり出していくようにする。1枚目は半分だけ出せて、二枚目は1/4だけ出せて、三枚目は1/6だけ出せて...、という風になる。このとき、特定の量だけ外に出るには何枚必要か答えよ、とい…

250が一番扱いに困るかも知れない。こういうのを一発で通すルーチンがちゃんと書けない...。 250 カードを半分の山に分けて、指定された山からK枚とり、その山がなくなるまで、逆の山から交互に1枚ずつとる。残ったK枚のカードをとる、というような感じでカ…

面白みの少ないセット。実装系？ 300 勝率P％の状況で、1セットNゲーム中Mゲーム勝てば勝ち、という状況で、Kセット連続で負ける確率を求めよ、という問題。 英語(日本語に訳してもかも)が分かりにくいのをどうにかすれば、doubleで適当に計算すれば何の問題…

面倒な2問と簡単な1000、ということもないけど...。 250 そろばんのようなものの形状が与えられるので、ある数を足した結果の形状を答えよ、という問題。 整数に戻してから、文字列に変形する、というだけの問題。英文が長い。 500 特定の名前の人が複数いる…

250 正方形を上下に折り、最後に斜めに折った形のうち、穴の空いている場所が与えられる。開いたときどこに穴が空いているか答えよ、という問題。 対称形になるように図形を拡張していけば良い。JavaのStringBufferにはreverseメソッドがあるので、試してみ…

1100 結局、木を定義してやるだけで良さそうなので、木を定義。後は、部分木について購入個数の可能な値を求めてマージしていく。ビットカウントを利用すればうまくいく。 木の作り方は、ビット的に完全に内包する値のうち最大のものが親になるようにすれば…

250 デジタル時計の時間を合わせることを考える。H時M分から(H+1)%24時(M+1)%60分になるボタンとH時(M+1)%60分になるボタンがあるとき、最小のボタン使用回数を答えよ、という問題。 まず時を合わせてから分を合わせるだけ。メモ付きBFSを書いてしまったが、…

IE7が一度中途半端なところで落ちて、それから頻繁に落ちるようになったのでIE8のBeta2を入れてみたら、はてなのJavaScriptにけちつけるようになった。うっとおしい。 そしてJavaのArrayListはメモリくうし遅いよ、というだけのセット。いかがなものかと。基…

やり直し。 1000 DPで解くことも、ステートの取り方も、ステート遷移の式も問題なかったのだけれど、探索の方向と初期値の設定がまずかったっぽい。最初の状態の確率を1.0として、一番確率の高い終了状態を求めようとすると、残存兵力のすべての可能性とそれ…

確率は全然分からない...。 250 3次元上にあるいくつかの点から三つ選んで、特定の条件を満たす三角形の面積の最大値を答えよ、という問題。 外積を使って面積を計算しましょう。 450 ある整数Nを、f(K)=(1からKまでの和)としてg(X)=(f(1)からf(X)までの和)…

数学のセット？ 300 xとyからなる連立方程式を解け、という問題。 行列式を計算して0なら答えがないか無限か。そうでなければ解く。前者の判定に注意が必要。2x2なら、逆行列を求めるのが簡単なのを思い出した。 450 ムーアの法則に従うとして、今からN年か…

初めて全部時間内に解けました。 250 二次元に並んだランプを列単位で反転させる操作をK回行う。最終的にすべてのランプがついている行の数の最大値を答えよ、という問題。 行単位で見て同じものじゃないと最終的に一致しないので、全部つけられる行について…

JavaのStringは遅いけど、StringBufferを使えばいいってもんじゃないよ、というセット。...違うか。 250 特定の模様を作ると点数がもらえるビンゴで、現在の状況が与えられるので、次の数字によって得られる点数の期待値を求めよ、という問題。 現在の状態か…

SRM初め。いかにしてDPの適用範囲を制限するか、という問題セットだった。(単純にDPやるとTLEするよ、という意味で。) 250 ある文字列を高々N行で表示するときに必要な幅の最小値を答えよ、という問題。空白のみ改行に変更することができる。 最後に改行にし…