TopCoder

今回はSRM 633の解説です。 Easy (250点) 問題 2次元の無限に広いフィールド上をジャンプしながら進む人がいる。この人のジャンプのパターンは決まっていて、例えば{2, 5}というパターンを持っていれば必ず、距離が2のジャンプ、距離が5のジャンプを繰り返しながら進んでいく。今、この人は(0, 0)から(x, 0)に向かいたい。ジャンプは特に格子点を通る必要はないものとするとき、必要なジャンプの最小数はいくつ ...

こんにちはtatsyです。 今回はTCO 2014 Round 2Bの解説です。 Easy (350点) 問題 M個のスイッチを操作するゲームがあり、ゲームは全Nステージからなる。最初スイッチはすべてオフの状態になっている。各ステージでは与えられたスイッチの状態を満たすことでクリアできる。与えられる条件は「オン」、「オフ」、「どっちでもいい」のいずれか。各ステージでプレイヤーが行える操作はオンになっているスイッチを自由に選んでオフに ...

こんにちはtatsyです。 今回はSRM622の解説です。 Easy (250点) 問題 ある国にはN個の街があり、このN個の街は完全有向グラフをなしている。この国にはアルゴリズムの日という日があり、この日には全ての街のペア(i, j)の間をバスが運行する。このバスは常に最短のパスを通ってiからjに向かうのだが、もし最短のパスが複数ある場合には運転手が任意の経路を選んでよいことになっている。この国の道路は老朽化が進 ...

こんにちはtatsyです。 今回はTCOのRound2Aを解説します。 Easy (250点) 問題 4×4のボードがある。16個のブロックが用意されていて、それぞれのブロックは底面が1×1、高さがheight[i]である。このブロックをボード上に並べるとき、外側に見えている面の面積を最大にしたい。その最大の面積を答えよ。 解法 テストケースの1が結構ヒントになる。1が8個、2が8個あるときには2が互いに隣り合わない ...

こんにちは、あいかわらずSRMの調子は低調のtatsyです。 今回はSRM617です。問題はEasyが割り算ゲー、Mediumが貪欲＋深さ優先となっております。それでは早速いきます。 Easy (250点) 問題 横幅がnのケーキがある。あなたはこれから来る友人に平等にケーキを切り分けたいが、友人が何人来るかは定かではない。友人が来る人数はnの約数のうち1とnを除いた数のどれかであることが分かっている。このとき、 ...

こんにちはtatsyです。 本日はTCO2014のAlgoRound 1Bを解説します。 Easy (200点) 問題 メールが良い行と悪い行から構成されている。良い行の場合にはG点を加算し、悪い行の場合にはB点を減算する時、メールを上から読んでいって途中で点数が負になったら、そのメールをスパムだと扱う。もし途中で一度も負にならなければ、そのメールはスパムではない。与えられたメールがスパムかどうかを判定せよ。 解法 と ...

こんにちはtatsyです。今回もSRMの解説やります。 Easy (250点) 問題 アメーバがいて、アメーバのエサとなるゼリーが列になって最大200個並んでいる。アメーバは自分と同じ大きさのゼリーと出会うと、そのゼリーを食べて大きさが2倍になる。このとき、任意の大きさのアメーバからスタートして、ゼリーの列を通過後に現れることのないアメーバの大きさの場合の数を答えよ。 解法 まず、単純なポイントとして、ゼリーの列に ...

こんにちはtatsyです。 昨日行われましたSRM611の解説をしたいと思います。今回はEasyもMediumもコンテスト中にはよく分からずでした。まだまだ練習が足りません。では、早速Easyから。 Easy (250点) 問題 自然数からなる数列A, Bが与えられる。このときLCM(A)とはAに含まれる数の部分集合のLCM(最小公倍数)を全て含むような集合になっている。このときLCM(A)とLCM(B)が同じにな ...

こんにちはtatsyです。 本日はSRM610に参加しました。結果はChallengeして、Challengeされ返され50ptどまり。Mediumは時間内に解けなかったですが、今回のMediumは下手したらEasyより簡単だったんじゃないかな？その辺も含めて解説していきたいと思います。 Easy (250点) 問題 小さなマス目で区切られた長方形のボードがある。各マス目には白か黒の色が塗られている。このボードの ...

こんにちはtatsyです。 本日はSRM609の解説をいたします。さっそく参ります。 Easy (250点) 問題 ある文字列がk個の連続する’>’で始まり、そのあとにk個の連続した’<‘が現れて終わる、というようなものを魔法の呪文と呼ぶ。たとえば”»>«<“は魔法の呪文である。ある’>’と’<‘からなる文字列が与えられたとき、適 ...