Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

September 2011 Cook-Off 4問目 - Target Practice (この記事を編集する[管理者用])

Source

codechef September 2011 Cook-Off 4問目
Problem Statement

問題概要

N個の的が一直線上に並んでいる. (Nは18以下)
1回の射撃で,的がある場所,もしくは,もう倒れたけど的があった場所を狙うことができる.
その際に,狙った的の左の的,狙った的,狙った的の右の的,に当たる確率が与えられる.(2つ以上離れた場所に当たる確率は0)
すべての的を倒すための必要な射撃数の最小値の期待値を求める問題.

解法

ビットDP.ただし,O(N*2^N)ではTLEで通らない.
2つ以上連続して的が倒れてる場所があると2つの部分問題に別れることを利用するとO(fib[N])になる.fibはフィボナッチ数.
他にも,対称性なども利用して状態数を減らす.
今ある最も右の的の,さらに右を狙うことが可能かどうか,などを新しく状態に加えた.

C言語のスパゲッティなコード

続きを読む

September 2011 Cook-Off 3問目 - Last Digit Sum (この記事を編集する[管理者用])

Source

codechef September 2011 Cook-Off 3問目
Problem Statement

問題概要

S(N)をNを10進数表記したときに出てくる奇数+出てくる偶数*2の和とする.例は問題文を参照.
D(N)はS(N) mod 10とする.
 D(A) + D(A+1) + … + D(B)
を求める問題.
A, Bは400000000以下.

解法

D(1) + D(2) + … + D(n)を高速に求めれられれば良い.
D(k)が0になるものの数,1になるものの数,…,9になるものの数をDPで求める.

C言語のスパゲッティなコード

続きを読む

September 2011 Cook-Off 2問目 - Hotel Bytelandia (この記事を編集する[管理者用])

Source

codechef September 2011 Cook-Off 2問目
Problem Statement

問題概要

N人 (100以下) の客が来るタイミングと帰るタイミングが与えられる.
最もたくさんの客がいるとき,何人いるかを求める問題.
来るのと帰るのが同時に発生するとき,帰る方を先に行われるとする.

解法

イベント (来る・帰る) が起こる時間でソートして,シミュレーションする.

C言語のスパゲッティなコード

続きを読む

September 2011 Cook-Off 1問目 - Digit Rotation (この記事を編集する[管理者用])

Source

codechef September 2011 Cook-Off 1問目
Problem Statement

問題概要

正整数N (10^8以下) が与えられる.
1回以上,好きな回数だけ,10進数表記で,最初の文字を最後にもっていく,もしくは最後の文字を最初に持っていく,という操作を行う.
先頭に0が来た場合は,即座にその0は削除される.
得られる最大の整数を求める問題.

解法

以下のパターンを全部試す.
・右にk回シフトする (k=1~8)
・左にk回シフトする (k=1~8)
・右に1回シフトした後,左に1回シフトする
・左に1回シフトした後,右に1回シフトする

C言語のスパゲッティなコード

続きを読む

Beta Round #74 DIV1 C問題/DIV2 E問題 - Chip Play (この記事を編集する[管理者用])

Source

Codeforces Beta Round #74 DIV1 C問題 (1000pt)
Codeforces Beta Round #74 DIV2 E問題 (2000pt)
Problem description

問題概要

m*nのグリッドが与えられる.(面積m*nは5000以下)
それぞれのグリッドは,何も無いか,上下左右のどこかを向いた矢印が書かれているかのどちらか.
矢印のある場所を始点として,
 今いる場所の矢印を消して,消した矢印の方向に進んで,最初の矢印があるセルに到着したら止まる
というのを,矢印に到達できなくなるまで繰り返す.
消した矢印の数がスコアになる.
最大スコアと,そのスコアを達成できる始点の数を求める問題.
矢印は少なくても1つは存在することが保証されている.

解法

各場所から始めた時の結果をシミュレーションする.
リスト構造などを用いて,今いる場所の上下左右にある最初の矢印の位置を高速に求めれるようにしておく.

C言語のスパゲッティなコード

続きを読む

Beta Round #74 DIV1 B問題/DIV2 D問題 - Widget Library (この記事を編集する[管理者用])

Source

Codeforces Beta Round #74 DIV1 B問題 (1000pt)
Codeforces Beta Round #74 DIV2 D問題 (2000pt)
Problem description

問題概要

厳密な仕様は問題文原文を参照.
横軸,縦軸がx軸,y軸に平行な長方形を作る.
以下の3タイプある.
 Widget: 縦,横のサイズが固定された長方形
 HBox: 箱.中身によってサイズが変わる.横に詰め込む.(問題文の図を参照)
 VBox: 箱.中身によってサイズが変わる.縦に詰め込む.(問題文の図を参照)
2種類のBoxには,2つのパラメータ (border, spacing) があって,詰め込む際の隙間のサイズが変わる.(問題文の図参照)
ただし,中身に何も入っていない箱は,パラメータの値に関わらず,サイズ0*0とする.
同じものが中に複数入っているかもしれない.
それぞれの長方形の横,縦の長さを全部求める問題.
入力は,長方形を作る,箱にものを入れる,パラメータを変える,の列からなり,最終的なサイズを求める.
パラメータの値は,設定しなければ,初期値は0.
ボックスの中に (結果的に) 自分自身が含まれることはないことが保証されている.

解法

各箱のサイズをメモ化再帰 (or トポロジカルソート+DP) で求める.

C++言語のスパゲッティなコード

続きを読む

Beta Round #74 DIV1 A問題/DIV2 C問題 - Robbery (この記事を編集する[管理者用])

Source

Codeforces Beta Round #74 DIV1 A問題 (500pt)
Codeforces Beta Round #74 DIV2 C問題 (1500pt)
Problem description

問題概要

一列に並んだn個 (10^4以下) のショーケースに,それぞれa[i]個の宝石が入っている.(a[i]は10^5以下)
防犯システムは,毎秒,隣り合うショーケースの宝石の数の和 (n-1個) を調べ,1つでも変化があったらアラームが作動する.
1秒間にm回 (10^9以下) 行動でき,持ち時間はk秒 (10^9以下) である.
アラームを作動させずに,盗める宝石の数の最大値を求める問題.
1回の行動では以下のどれかができる.
 あるショーケースの宝石を1つ,別のショーケースに移動させる
 あるショーケースの宝石を1つ,自分のポケットに移動させる (盗む)
 自分のポケットの宝石を1つ,あるショーケースに移動させる
最初,ポケットには宝石は1つも入っていないとする.

解法

端からつじつまが合うように考えると,nが偶数の時は何も得になる操作できない.
nが奇数の時は,偶数番目(0番目から数えて)をa減らし,奇数番目をaだけ増やすという操作が可能.(1個ポケットに入れる)
1秒間に操作可能なaの最大値を求めて,それをk秒繰り返すのが最適.
ただし,偶数番目の最小値以上に動かせないことに注意する.

C言語のスパゲッティなコード

続きを読む

Beta Round #73 DIV1 D問題 - Beautiful Road (この記事を編集する[管理者用])

Source

Codeforces Beta Round #73 DIV1 D問題 (2000pt)
Problem description

問題概要

Nノード (10^5以下) の木が与えられる.各枝には距離が付与されている.
全てのノード対の間を移動するした.(N*(N-1)回)
各,移動の際に,経路中の最も長い枝 (複数あるなら全部) に,コインを1枚置いていく.
最終的にコインが一番多く置かれている枝を列挙して,その枝に含まれるコインの数を求める問題.

解法

まず,枝をコスト順にソートし,コストの小さい枝から順番に付け加えていく.
最初に,同じ長さの枝がない場合を考える.
枝を加えるときに,union findで連結成分をまとめてやって,各ノードがもともと何個のノードで構成されていたか (重みと呼ぶことにする) を覚えておく.
すると,枝を加えるときに,(union findする前に)つなげた部分の左右のノードのサイズの積がその枝に置かれるコインの数になる.
同じ長さの枝が複数あるときは,一度に同じ長さの枝を加えて,一時的に森を作る.
森の各ノードは,それより短い枝はすでにunion findでくっつけている状態.
後は,DPで各枝の左右にあるノードの重みの和を求めてやる.
とやってしまったけど,もっと楽な方法があるはず….

C言語のスパゲッティなコード

続きを読む

Beta Round #73 DIV1 C問題/DIV2 E問題 - Interesting Game (この記事を編集する[管理者用])

Source

Codeforces Beta Round #73 DIV1 C問題 (1500pt)
Codeforces Beta Round #73 DIV2 E問題 (2500pt)
Problem description

問題概要

2人でゲームをする.動けなくなったら負け.
最初n個 (10^5以下) の石が1つの山に置いてある.
各ターン,1つの山を選び,それを2個以上の山に分割する.
そのとき,分割した各山の石の数は a, a+1, a+2, ..., a+k-1 個にならなければいけない.(aは任意の生成数,kは分割する山の数)
このゲームが先手必勝なら,最初に何個に分けると必勝か,それとも先手必敗かを求める問題.

解法

grundy numberを計算する.
山の数の取りうる値はそんなに多くないので,愚直に実装しても十分間に合う.

C言語のスパゲッティなコード

続きを読む

Beta Round #73 DIV1 B問題/DIV2 D問題 - Vasya and Types (この記事を編集する[管理者用])

Source

Codeforces Beta Round #73 DIV1 B問題 (1000pt)
Codeforces Beta Round #73 DIV2 D問題 (2000pt)
Problem description

問題概要

void型とそのポインタ,そのまたポインタ,…,のみの型を考える.
型名*でポインタを表し,&型名 で型が指してる場所の型を表す.
ただし,&voidなど,ポインタではないものに&を付けると,errtype型というのになる.
errtype型は&errtype型もerrtype*型もerrtype型と等しい.
&void*などは,&(void*)と解釈してvoid型になる.
typedefとtypeofからなるコードが与えられるので,typeofに対応する型名を出力する問題.
出力する場合は,void,void*,void**,…,またはerrtype型のどれかを返さなければいけない.
 typedef A B: A型を改めてBと命名する (Bには&や*がついていけはいけない,Aは既に定義されている型に&や*がついているかもしれない)
 typeof A: Aの型を出力する

解法

頑張って実装する.

C言語のスパゲッティなコード

続きを読む

Beta Round #73 DIV1 A問題/DIV2 C問題 - Trains (この記事を編集する[管理者用])

Source

Codeforces Beta Round #73 DIV1 A問題 (500pt)
Codeforces Beta Round #73 DIV2 C問題 (1500pt)
Problem description

問題概要

a秒ごとに来る列車と,b秒ごとに来る列車がある.
時間0では同時にくる.
自分は,ランダムなときに駅について,先に来た方に乗る.
次の列車が同時に到着したら,レアな方に乗る.(aとbの大きい方に対応する列車に乗る)
乗る確率が高い列車はどちらか,もしくは,等しいかを判定する問題.
aとbは1以上10^6以下の整数で,等しくない.

解法

シミュレーションする.
時間gcd(a,b)までシミュレーションすれば後は繰り返しなので,そこまですればいい.
シミュレーションは次の電車が来る時間を計算して,その時間まで飛ばす感じ.
次の電車が来る数は高々a+b回なのでO(a+b)時間となる.

C言語のスパゲッティなコード

続きを読む

Timus 1884 - Way to the University (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1884

問題概要

歩くスピードは5km/h,車のスピードは20km/h.
車の幅は2m,長さは5m.道の幅は各車線2mで合計4m.
右から来る車と左から来る車までの距離が与えられる.車の数はそれぞれ300以下.
今の位置から左右に動かす,歩いて道路を横断したいが,途中で止まらず,道路に直交するように歩く.
車に轢かれないような最小の出発時間を求める問題.

解法

車の角に触れるのは可能らしい.
各車に対して,その車がちょうど通りすぎて,角に触れながら移動するための出発時間を列挙する.
それに0を加えたものが答えの候補.
後は,その答えの候補のそれぞれに対して,実際にその時間に出発して車に轢かれないか判定する.
奥の車線の場合,候補は負になり得るが,それは不正なので気をつける.

Timus 1883 - Ent's Birthday (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1883

問題概要

n個 (1000以下) の点が与えられる.
内部および周上にちょうどk点だけ含むような面積が正の凸多角形を1つ求める問題.(10000角形以下でなければいけない)

解法

点をx座標の値でソート,同じx座標はy座標の値でソートして,最初からk個の点を含むような凸包を作ればいい.
x座標の最小のよりもっと小さいところに適当に点をとったりして面積が0にならないようにした.

Timus 1882 - Old Nokia (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1882

問題概要

携帯に登録された,アルファベット順にN人の友人の名前が与えられる.文字数の合計は100000以下.
1つのキーを押すのに1秒かかるとして,N人それぞれの名前を選択するまでに必要な最小時間を求める問題.
最初はアルファベット順で最小の人を選択している.
上キー,下キーを押すと,リストに表示されてるうちで,次の人,前の人に選択を移せる.
リストはサイクリックで,最初の人の前は最後の人,という感じ.
また,文字を入力することができる.
aを入力するのには1秒,bを入力するには2秒,cは3秒,dは1秒,eは2秒,…,zは4秒かかる.問題文の表参照.
文字を追加したら,今まで入力した文字列をプレフィックスとする名前のみ表示される.
その際,選択は,表示されてるうちの辞書順最小の人が選択される.
文字を削除 (最後に入力した文字を1秒で削除できる) すると,リストはもの文字を入力する前の状態に戻るが,選択されている人は変化しない.
文字を入力したときに,表示される人が0人になるような入力は,ボタンを押しても入力できない.そして不快な音がなる.

解法

削除は高々1回しか行う必要はない.
まず,削除せずに上下キーのみで移動する場合,一文字入力して削除して上下キーで移動する場合を全部試す.
後は,一文字入力して,表示される範囲を区切って,同じ操作を再帰的に行う.

Timus 1881 - Long problem statement (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1881

問題概要

n個の単語が与えられる.単語の長さの合計は10000以下.
また,1ページに書くことができる最大の縦幅 (文字数),横幅 (文字数)が与えられる
同じ行に2つ以上の単語を書く場合は,間に半角スペースを一文字挟む必要がある.
1つ単語は複数の行にまたがってはいけない.
できるだけ詰めて書くとして,与えられた単語を順番通りに書くためには何ページ必要かを求める問題.

解法

シミュレーションする.
各単語の文字数を+1,各行にかける文字数を+1するとスペースを挟むことを考えなくてよくなるので少し楽.

Timus 1880 - Psych Up's Eigenvalues (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1880

問題概要

3つの整数列が与えられる.
各整数列は,要素数4000以下で,各要素は全て異なる.
全ての整数列に登場する数字の数を求める問題.

解法

ハッシュなりセットなりマルチセットなりを使って,全体で3回登場した数字をカウントすれば良い.

Timus 1879 - GOV-internship 2 (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1879

問題概要

整数列s1とs2が与えられる.各要素0以上100000以下.
s1の要素数をn1,s2の要素数をn2とする.n1, n2は100000以下.
最初に,s1の各0要素と,s2の各0要素を好きな数字に変更することができる.
s1はサイクリックと考え,各場所から長さn2の連続する部分列をn1個考える.
その部分列と,s2との差を,異なっている文字数とする.(ハミング距離)
その差の和の最小値を求める問題.

解法

すべての要素がすべての要素と当たるので,答えは
 n1*n2 - マッチする文字数の最大値.
マッチする文字数は,
 Σ s1に含まれるkの個数 * s2に含まれるkの個数 (kについての和)
なので,各文字列にある0は全て同じ数字に変えるのが最適で,
 s1に含まれる0は,s2に含まれる最も多い数字に変更.s2に含まれる0は,s1に含まれる最も多い数字に変更.
 s1,s2に含まれる0はすべて同じ数字に変更
だけを試せば良いことがわかる.

Timus 1878 - Rubinchik's Cube (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1878

問題概要

パズル.問題分の図参照.
4枚の板が重なっていて,各板は1回の操作で90度回転できる.透明な部分は透ける.
初期状態が与えられるので,下の図のいずれかになるまでに必要な操作の回数を求める問題.

解法

各板の回転の仕方は4通りしかないので,4^4パターン全部試してみる.

Timus 1877 - Bicycle Codes (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1877

問題概要

4桁の数字を合わせれば開くタイプの鍵を2個持っている.
自転車に鍵をかけるが,奇数日目は1個目の鍵を,偶数日目は2個目の鍵をかける.
泥棒が毎日来て,1日目は0000,2日目は0001,…,と小さい順に試していく.
そのうち自転車が盗まれるかどうかを求める問題.

解法

1個目の鍵が奇数,または,2個目の鍵が偶数,のどちらかならば盗まれる.

Timus 1876 - Centipede's Morning (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1876

問題概要

あるムカデは右足が40本,左足が40本あって,スリッパを履こうとしている.
最初a個の右足用スリッパ,b個の左足用スリッパがある.(a, bは40以上100以下)
まだ履いていない右足があるうちは,右足で1つのスリッパをランダムに選び,
 右足用だったら履く.この操作は1秒かかる.
 左足用だったら,左足でまだスリッパを履いていない足があればそれにパスして履く.この操作は2秒かかる.
 左足用で,もうすべての左足がスリッパを履いていたらスリッパを捨てる.この操作は2秒かかる.
履いていない右足がないなら,右足で1つのスリッパをランダムに選び,
 左足用だったら履く.この操作は1秒かかる
 右足用だったらスリッパを捨てる.この操作は2秒かかる
すべての足にスリッパを履くのにかかる時間の最大値を求める問題.

解法

右足を先に履き終わる場合と左足を先に履き終わる場合の最大値をそれぞれ求めて大きい方を返す.

Timus 1875 - Angry Birds (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1875

問題概要

y軸の正の方向が上,つまり,重力はy軸の負の方向に働く.
5匹の猿の座標が与えられる.x座標y座標共に正.
原点からボールを投げて全ての猿に当てたい.(あたっても軌道は変わらない)
最小で何回ボールを投げればいいか求める問題.
ボールは,x軸方向に等速度,y軸方向に重力の力によって等加速度運動を行う.
原点と2匹の猿が同一直線上にあることはないとする.

解法

原点を通り,上に凸な2次関数を何個書けば点を覆えるかという問題.
原点と2点を選んだ時,2次関数は一意に定まるので,それで当てれる猿を列挙する.
後は,例えばDPして,各部分集合に対応する猿を全部当てるのに必要なボールの数を求める.

Timus 1874 - Football Goal (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1874

問題概要

無限に長い2本の棒が直角に交わっている.
また,長さaの棒と長さbの棒を自由に配置できる.
作れる四角形の最大面積を求める問題.

解法

棒aと無限に長い棒(1つ目)のなす角をA,棒bと無限に長い棒(2つ目)のなす角をBとすると面積は
 ab sin A sin B + 0.5 a^2 sin A cos A + 0.5 b^2 sin B cos B
となる.
各Aに対して3分探索して,その中で各Bに対して3分探索する.

Timus 1873 - GOV Chronicles (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1873

問題概要

Team.GOV (とその前身のAlarm) のヒストリーが与えられる.
メンバーの変更やどんなコンテストに参加したなど.
各登場する人物に何回コンテストに出場したのかを求める問題.

解法

問題文読解.

Beta Round #75 DIV1 D問題 - Grocer's Problem (この記事を編集する[管理者用])

Source

Codeforces Beta Round #72 DIV1 D問題 (2500pt)
Problem description

問題概要

1~Nのpermutationが与えられる.Nは10^5以下.
一度に,5つ以下の要素を選んで,それらを自由に入れ替えることができる.
ソートするまでの最小手数と,その手順を1つ求める問題.

解法

Greedy.
まず,巡回置換の積に直す.
巡回置換で,要素が5より大きいものは,1回の操作で4つだけ正しい場所において,残りはそのままにできる.
後は,巡回置換で,サイズが5以下のものだけ考える.
5のもの,4のものは,1回の操作で行うしか無い.
後は,2のもの,3のものが両方あるうちは,1回の操作で,それらを1個ずつ潰していく.
3のものが3つ以上あれば,3つは,
 1回目: 1つ潰して,1つをスワップしてサイズ2の置換に落とす
 2回目: 1つ潰して,サイズ2の置換に落としたのも潰す
と2回の操作で潰す.
2のものが2個以上あったら,2個を1回の操作で潰す.
後は,サイズ2のもの,3のものが余ってたら潰す.

C言語のスパゲッティなコード

続きを読む

Beta Round #75 DIV1 C問題/DIV2 E問題 - Ski Base (この記事を編集する[管理者用])

Source

Codeforces Beta Round #72 DIV1 C問題 (1500pt)
Codeforces Beta Round #72 DIV2 E問題 (2500pt)
Problem description

問題概要

最初は枝の無いノード数N (10^5以下) のグラフ.
M回 (10^5) 枝を加える操作を行う.
各操作の後に,以下の条件を満たす枝の集合の数をmod 1000000009で求める問題.
 空ではない
 その枝を全部1回ずつ使って閉路がいくつかできる (連結である必要がない)

解法

枝を使うか使わないか,mod 2の世界での連立一次方程式に帰着することを考える.
連立一次方程式は,各ノードの次数がmod 2で0となること.
すると,2^一次従属な条件の数 - 1が答えになる.-1は空集合を除くため.
一次従属な条件は,すでに連結なノード対に枝を加えたときに1つ増える.

C言語のスパゲッティなコード

続きを読む

Beta Round #75 DIV1 B問題/DIV2 D問題 - Queue (この記事を編集する[管理者用])

Source

Codeforces Beta Round #72 DIV1 B問題 (1000pt)
Codeforces Beta Round #72 DIV2 D問題 (2000pt)
Problem description

問題概要

N要素 (10^5以下) の整数列が与えられる.
各要素に対して,自分より厳密に小さい要素で,自分より右にある要素で,最も右にある要素までの距離-1を求める問題.
そのような要素が存在しないなら-1を返す.

解法

数列を小さい順にソートする.同じ大きさなら元々左にあったものが先に来るようにする.
後は,最初から見てやって,もともといた位置の最も右の位置を覚えておいて,そこまでの距離を返す.

C++言語のスパゲッティなコード

続きを読む

Beta Round #75 DIV1 A問題/DIV2 C問題 - Newspaper Headline (この記事を編集する[管理者用])

Source

Codeforces Beta Round #72 DIV1 A問題 (500pt)
Codeforces Beta Round #72 DIV2 C問題 (1500pt)
Problem description

問題概要

長さ10^4以下の文字列Aと長さ10^6以下の文字列Bが与えられる.
文字列はアルファベット小文字のみからなる.
Aをk回繰り返してできる文字列をA^kと書くことにして,A^kがBを部分列にもつような最小のkを求める問題.
そんなkが存在しないならそれを指摘する.

解法

Bにしか含まれない文字が存在するなら-1.
Aの各場所から,次に各文字が登場する場所を全部最初に記憶しておく.
後は,愚直に,A[0]が最初に現れる場所,その場所移行でA[1]が最初に現れる場所,…と辿っていく.

C言語のスパゲッティなコード

続きを読む

June 2011 Cook-Off 5問目 - Super-plane (この記事を編集する[管理者用])

Source

codechef June 2011 Cook-Off 5問目
Problem Statement

問題概要

N個 (10000以下) の飛行機のフライトが与えられる.
フライトの情報は,出発地,目的地,出発する時間,到着する時間が与えられる.
(時差とかではなく,不思議な力で)到着する時間が出発する時間より早いこともありうる.
最初にいる場所と時間,目的地とそこにつかなければいけない時間(ちょうどか,それより前に着けば良い),が与えられた時,
時間内に目的地に辿りつけるか,つけるなら乗る飛行機の数を求める問題.
乗る飛行機は,到着した時間かそれ以降の一番早い飛行機に飛び乗ってしまうとする.
また,目的地に時間内に辿りつけたら,そこで止まる.(目的地に着いても時間内でなければまた乗る)

解法

シミュレーションする.
同じ飛行機に2回乗ると後はループするので到着不可能と判定する.
次に乗る飛行機を探すのは,二分探索することで,O(N log N).

C言語のスパゲッティなコード

続きを読む

June 2011 Cook-Off 3問目 - Correctness of Knight Move (この記事を編集する[管理者用])

Source

codechef June 2011 Cook-Off 3問目
Problem Statement

問題概要

チェス盤 (サイズは8*8) の座標はa~hまでと1~8までをくっつけて,a7とかh3のように表す.
次の形式で座標が2つ与えられる.
 座標-座標
その座標間はナイトがちょうど1回で移動できる関係にあるかどうかを求める問題.
座標が不正,もしくは,形式が不正ならそれを指摘する問題.
各行ごとにテストケースを処理する.

解法

やるだけ.改行文字やスペースの処理に注意.

C言語のスパゲッティなコード

続きを読む

Aizu 2288 - Oh, My Goat! (この記事を編集する[管理者用])

Source

RUPC2011 (Ritsumeikan University Programming Contest)
Aizu 2288

問題概要

日本語なので略.

解法

各のグラフの今どこのノードにいるか,まだ使い切ってない文字列を状態としてDPする.
ある状態にいるとき,使う枝を決めると次の状態に移行できる.
使いきってない文字列は,たかだか片方のグラフにしかなく,4文字以下.
愚直にメモリを取ろうとするとMLEしそうだったので,map<string,int>を使った.

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。