Programming Contest

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

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

こんにちはtatsyです。 昨日行われましたGCJ2014のRound2。まさかの2byteの違いに泣かされてTシャツを逃しました。 終了直後、悔しすぎて悔し死にするんじゃないかと思うくらい悔しかったです。 とりあえず、何言っているか分からないと思うので、そのあたりも交えながら解説をしていきます。 今回解説する範囲は A Small / Large B Small / Large C Small D Small です。 A. Data Packing (Small: 5pt, Large: 8pt) 問題 ファイルが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が互いに隣り合わない ...

こんにちはtatsyです。 GCJ2014のRound1Aの解説します。今回は普通にAとBをSmallとLarge両方通して800位台でした。去年もRound1は突破できてたし、実力は格段に伸びてるはずなので、通過できてよかったです。 一応全て解説しますが、自力で出来たのはA、Bだけなのでコードはその2問分だけのせます。Cについてはやり方のみ説明しますので、詳しくは他の方のコードを公式から見ていただけ ...

こんにちは、あいかわらず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)が同じにな ...