Entries

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

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

ARC 008 D - タコヤキオイシクナール (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #008
問題文

問題概要

N個の箱がある.
各箱iにはパラメータa[i], b[i]が設定されている.(a[i], b[i]の絶対値は1以下)
箱iに数xを入れると,f_i(x) = a[i] * x + b[i]となって出てくる.
最初はa=1, b=0に設定されている.
M回だけ,ある1個の箱を指定して,パラメータを変える操作を行った履歴が与えられる.
また,パラメータを変更する前,各変更の後,合計M+1回だけ,
 箱1に1を入れて,出てきた数字を箱2に入れて,…,出てきた数字を箱Nに入れて出てきた数字を調べる
ということを行った.
つまり,M+1個の
 f_N( ... f_2( f_1(1) ) ... )
の値を調べた.
M+1個の値の最大値を最小値を求める問題.
50点 : Nは1000以下,Mは1000以下.
100点 : Nは10^12以下,Mは10^5以下.

解法

まず,Nが大きいので座標圧縮する.使う箱はたかだかM個.
f_2 * f_1などの合成関数はすべて a * x + b の形で書ける.
セグメントツリーのように,各区間のaとbの値を覚えておけばパラメータの変更と値の計算がlog M程度でできる.

Cによるスパゲッティなソースコード

続きを読む

ARC 008 C - THE☆たこ焼き祭り2012 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #008
問題文

問題概要

N人 (1000以下) の人が2次元平面上にいる.移動できない.
それぞれの人は,投げることができる最大スピードと,受け取る事ができる最大スピードが設定されている.
番号0の人がたこ焼きをN個持っている.
たこ焼きを投げたら,次に投げるまでに1秒以上間隔を開けなくてはいけない.
全員にたこ焼きを配り終わる最小必要時間を求める問題.

解法

ダイクストラで各人に配布するのに必要な最小時間を求める.(1人だけに配るとして)
後は,遠い人から最短パスにそっと投げていけば良い.
最短パスなので,番号0の人が1秒おきに投げるなら,他の人は受け取るのに1秒は間隔が開くので他の人はすぐ投げれる.
自分には投げなくて良いことに注意.

Cによるスパゲッティなソースコード

続きを読む

ARC 008 B - 謎のたこ焼きおじさん (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #008
問題文

問題概要

N文字 (50以下) の文字列Sと,M文字 (50以下) の文字列Xが与えられる.
XをK回繋げて,自由に文字を入れ替えたり,文字を消したりしてSを作りたい.
最小のKを求める問題.不可能ならそれを指摘する.
文字はアルファベット大文字のみ.

解法

各文字について,Sに含まれている数と,Xに含まれている数を調べて,必要なXの個数を求めて,それの最大値を取る.

Cによるスパゲッティなソースコード

続きを読む

ARC 008 A - 元気にお使い!高橋君 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #008
問題文

問題概要

たこ焼き1個15円,10個100円で売っている.
N個以上のたこ焼きを買うのに必要な最小金額を求める問題.
Nは50以下.

解法

とりあえず,残り10個以上買わなくてはいけないなら,10個ずつ買っていく.
残りの端数は,10個買うか,1個ずつ買うか,安いほうを選択する.
無駄にDPしてしまった.

Cによるスパゲッティなソースコード

続きを読む

ARC 007 D - 破れた宿題 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #007
問題文

問題概要

N文字の数字のみから成る文字列が与えられる.
それは,等差数列をスペース無しで続けて書いた文字列で,最初の数文字,最後の数文字を消したものである.(消したのは0文字かもしれない)
ただし,初項は少なくても1文字は残っている.
元々の等差数列として考えられるものの初項と公差を答える問題.
複数あるなら,初項最小のもの,その中で公差最小のものを答える.
ただし,初項,公差は1以上の整数で,03のようにleading zeroは許されない.
25点 Nは4以下,50点 Nは6以下,75点 Nは200以下,100点 Nは1000以下.

解法

最小の初項は簡単に求まる.
例えば,192021だと1だし(2項目は92021で19,20,21は初項がでかい),1001だと100だし,00102でも100だし,000なら1000だし,800183なら800.
後は,2項目がどこからどこまでかを全部試す.
2項目が全部収まっていない時のコーナーケースに注意.
01なら初項10,公差1だし,201なら初項20,公差80だし,202なら初項20,公差1など.

Cによるスパゲッティなソースコード

続きを読む

ARC 007 C - 節約生活 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #007
問題文

問題概要

oとxからなるN文字 (10文字以下) の文字列が与えられる.
その文字列を,周期的に拡張して,長さ無限大の文字列と考える.(k文字目は元々のk mod N文字目)
その文字列をK個用意して,それぞれの文字列の最初にいくつかのxを追加して良い.
十分大きな全ての整数sに対して,K個の文字列のどれかのs文字目はoであるようにしたい.
Kの最小値を求める問題.

解法

最初にxを追加する数は,0からN-1までやれば十分.
なので,N種類の文字列のみ考えれば良い.
後は,どれを使うか2^N通り全探索する.

Cによるスパゲッティなソースコード

続きを読む

ARC 007 B - 迷子のCDケース (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #007
問題文

問題概要

N+1枚のCDがあり,0からNまで番号がついている.
CD 0はCDプレイヤーの中に入っており,その他はCD iはケースiに入っている.
M枚のCDを順番に聞く.
その際,CDプレイヤーの中に入っているCDを聞くなら何もしない.
そうでなければ,CDプレイヤーの中のCDを,聞きたいCDが入っているケースに入れ,聞きたいCDをCDプレイヤーの中に入れる.
最終的に,それぞれのケースに入っているCDの番号を出力する問題.
N, Mは100以下.

解法

愚直にシミュレーションする.

Cによるスパゲッティなソースコード

続きを読む

ARC 007 A - 帰ってきた器物損壊!高橋君 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #007
問題文

問題概要

アルファベット小文字1文字Cと,アルファベット小文字から成る文字列Sが与えられる.
SからCを全部消した文字列を出力する問題.

解法

やるだけ.

Cによるスパゲッティなソースコード

続きを読む

ARC 006 D - アルファベット探し (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #006
問題文

問題概要

H*W (1000*1000以下) のグリッドが与えられ,各セル白か黒.
アルファベットのABCがいくらか書かれている.
アルファベットは90度の整数倍回転してるかもしれず,鏡像反転してるかもしれず,正整数倍拡大しているかもしれない.
ただし,アルファベットは重なっておらず,アルファベットに属さない黒いセルもない.
ABCがそれぞれ何個書かれているか求める問題.

解法

色々やりかたはあると思う.
縦横斜めに連結と思い,各連結成分ごとに黒のセルの数を数え,例えば,その数が12*k^2の形ならAとする,などと判定した.

Cによるスパゲッティなソースコード

続きを読む

ARC 006 C - 積み重ね (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #006
問題文

問題概要

N個のダンボールが順番に運ばれてくる.
それぞれの重さが与えられる.
自分の上に積み重ねるには,自分より軽いダンボールしかすぐ上には置けない.
一度おいたら動かせない.
最小で何個の山を作れば良いかを求める問題.

解法

greedy.
置ける場所のうち,最も軽いダンボールの上に置く.
積み重ねられないなら,新しく山を作る.
もしくは,山を1つずつ作っていく感じで,ダンボールの中からgreedyに最も長い非増加列を引き抜いていく.

Cによるスパゲッティなソースコード

続きを読む

ARC 006 B - あみだくじ (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #006
問題文

問題概要

あみだくじのアスキーアートが与えられる.
あたりは左から何本目かを判定する問題.

解法

下から辿っていく.

Cによるスパゲッティなソースコード

続きを読む

ARC 006 A - 宝くじ (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #006
問題文

問題概要

ロト6っぽい宝くじが何等か判定する問題.
宝くじで,選ばれた数字6個,ボーナス数字1個,自分が選んだ数字6個が与えられる.

1等 : 6つ数字が一致
2等 : 5つ数字が一致し,残りの1つの数字がボーナス数字と一致
3等 : 5つ数字が一致で,2等でない
4等 : 4つ数字が一致
5等 : 3つ数字が一致
ハズレ : 全部に該当しない

解法

やるだけ.

Cによるスパゲッティなソースコード

続きを読む

ARC 005 D - 連射王高橋君 (We have nothing to do with him) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #005
問題文

問題概要

0123456789+=のボタンのある電卓がある.
壊れているボタンが与えられる.ただし01+=は壊れていない.
最終的に表示させたい数 (10^18以下) を表示するまでに押さなくてはいけないボタンの回数の最小値化したい.
そのような方法を1つ出力する問題.

解法

数字をそのまま打てるならそうする.
そうでなければ,DP + 経路復元する.
まず,使える数字を使ってk (200以下ぐらい) を作る最小個数の組み合わせは最初にDPで計算しておく.
後は,各桁ごとにDPしていく.下の桁から見ていく.
何個の数字の和で作るかは全探索する.
状態は,どの桁を見ているか,繰り上がりはいくらあるか,前の桁で使った数の数(足し合わせるものの中でその桁が存在する数).

Cによるスパゲッティなソースコード

続きを読む

ARC 005 C - 器物損壊!高橋君 (Search and destroy) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #005
問題文

問題概要

H*W (500*500以下) のグリッドが与えられる.
各セルは,通れるセルか,塀があるセルかのどちらか.
上下左右に移動でき,2個まで塀を壊すことができる.
スタートからゴールまで移動できるかどうかを判定する問題.

解法

何回塀を壊したかでノードを多重化してBFS,DFSなどする.

Cによるスパゲッティなソースコード

続きを読む

ARC 005 B - P-CASカードと高橋君 (This story is a fiction) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #005
問題文

問題概要

9*9のグリッドの各セルに1文字の数字が書かれている.
最初の場所と,方向が与えられるので,その方向に4文字読む問題.
端に到達したら,鏡に反射したように進行方向を変える.

解法

やるだけ.

Cによるスパゲッティなソースコード

続きを読む

ARC 005 A - 大好き高橋君 (Love me do) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #005
問題文

問題概要

N個 (50以下) の単語からなる文字列が与えられる.
各単語はアルファベットのみから成り,単語と単語の間には1つのスペースがある.
また,最後の単語の直後に1つのピリオドがある.
単語の中に,TAKAHASHIKUN,Takahashikun,takahashikunが何個あるか,合計値を求める問題.

解法

やるだけ.

Cによるスパゲッティなソースコード

続きを読む

UVa 12481 - K-Neutral Rectangles (この記事を編集する[管理者用])

Source

First Bangladeshi Contest of 2012-2013 Season (2012-07-07)
UVa 12481

問題概要

N*M (1000*1000以下) のグリッドの各セルに整数が書かれている.
長方形の領域で,その領域内で隣合う2セルの差の絶対値がすべてK以下のものを考える.
そのような領域の面積の最大値を求める問題.
上下左右に隣合うものとする.

解法

各セルから,幅1だとすると,上に向かって何セル選んでも大丈夫か,
一つ右の列も選ぶ (幅2) とすると,何セル選んでも大丈夫か,をDPで前計算しておく.
すると,長方形領域の下の辺を固定すると,ヒストグラム中の最大長方形面積の問題に帰着される.
ALGORITHM NOTE http://algorithms.blog55.fc2.com/blog-entry-132.html 参照.

UVa 12478 - Hardest Problem Ever (Easy) (この記事を編集する[管理者用])

Source

First Bangladeshi Contest of 2012-2013 Season (2012-07-07)
UVa 12478

問題概要

9*9のグリッドの各セルにアルファベットが書かれた画像が与えられる.
そのグリッドの中には,縦横斜めに連続してみると,このコンテストの出題者の名前 (問題文参照,計8人) のpermutationが登場する.
登場回数は1人を除いて1回で,1人だけ2回出てくる人がいる.
その人は誰かを出力する問題.
入力はない.

解法

探さずに,適当にそれっぽい人を出力したら2回目であたった.
81文字写すのは大変だけど,目で探すのはもっと大変.

UVa 12475 - Elliptic Athletics Track (この記事を編集する[管理者用])

Source

First Bangladeshi Contest of 2012-2013 Season (2012-07-07)
UVa 12475

問題概要

長軸の長さの半分a,短軸の長さの半分bが与えられるので,その楕円の周の長さを求める問題.

解法

ググって近似公式を調べる.
例えばWikipediaの楕円のページなどに書いてある.

UVa 12474 - Draw and Score (この記事を編集する[管理者用])

Source

First Bangladeshi Contest of 2012-2013 Season (2012-07-07)
UVa 12474

問題概要

頂点を1個ずつ付け加えて頂点数Nの2分木を作る.Nは10^15以下.
その際,バランスされている頂点とは,
 その頂点の子供が1つ以上ある
 その頂点の左の部分木と右の部分木に含まれるノードの数が同じ
であること.
頂点を付け加えた際,
 バランスされてなかった頂点が,バランスされたら +1 点 (そのような頂点が複数あったらその数だけ加点)
される.
付け加える順番を最適化したとき,得られる最大点数を求める問題.

解法

Ad-hoc.
最大点数となる付け加える順番の規則を探す.
Nがなんでもこういう順番に付け加えれば良いという感じでもない.
詳しいことは忘れてしまった.

UVa 12473 - Common Palindrome (この記事を編集する[管理者用])

Source

First Bangladeshi Contest of 2012-2013 Season (2012-07-07)
UVa 12473

問題概要

60文字以下の文字列A, Bが与えられる.
A, Bの共通の部分列 (部分文字列ではない) の中で最長の回文の長さを求める問題.
文字はアルファベット小文字のみ.

解法

まず,それぞれのアルファベットに対して,それぞれの場所より右(左)で,最初に出てくる場所を計算しておく.
(制限時間が長いのでそこまでしなくても通る気がするが)
回文の最初の文字で場合分けすると,A,Bのある区間の中で最長の回文を探す問題に帰着されるのでDPできる.
状態数はO(60^4)で,計算量O(60^4 * 26)だけど,実際はそんなに調べないので遅くない.

UVa 12472 - Binary Substring (この記事を編集する[管理者用])

Source

First Bangladeshi Contest of 2012-2013 Season (2012-07-07)
UVa 12472

問題概要

0,1のみからなる文字列Pが与えられるので,
2進数表示したとき,部分文字列としてPを含むような整数Sのうち,A以上B以下のもので最小のものを求める問題.
存在しないならそれを指摘する.
A,Bは10^15以下.

解法

Sは2進数で何桁かを全部試し,更に,Pが何文字目から始まるかも全部試す.
Pの前後はgreedyに埋めていく.

UVa 12442 - Forwarding Emails (この記事を編集する[管理者用])

Source

World Finals Warmup I (2012-02-25)
UVa 12442

問題概要

N人の人がいる.(Nは50000以下)
各人について,自分がメールを受け取ったら,転送する相手(1人につき1人)が与えられる.
誰かに1通だけメールを送って,できるだけ多くの人に知らせたい.
誰に送れば良いかを求める問題.複数答えがあるなら一番番号が小さい人に送る.

解法

強連結成分分解して,DPする.

UVa 12439 - February 29 (この記事を編集する[管理者用])

Source

World Finals Warmup I (2012-02-25)
UVa 12439

問題概要

日付が2つ与えられるので,その間に2月29日は何回あるかを求める問題.
与えられる年は2000以上2*10^9以下.

解法

やるだけ.
最初に与えられた日付のほうが後ならswapする.
400年に97回あるので,適当に端折る.

UVa 12437 - Kisu Pari Na 2 (この記事を編集する[管理者用])

Source

World Finals Warmup I (2012-02-25)
UVa 12437

問題概要

ノード数N,枝数Mの無向グラフが与えられる.(Nは10000以下,グラフはループがない,つまり森)
枝を1回移動するたびにコストが1だけかかる.
10000個以下のクエリが与えられる.
各クエリでは,1つの正整数Kが与えられるので,異なるK個のノードを訪れるための最小コストを求める.
最初はどこにいても良いし,最初にいるノードは訪れたとみなして良い.

解法

各森について,ノード間の距離の最大値を求めておく.
その最大値以下なら,いったり戻ったりせずに移動できる.
そうでなければ,その最長パスにそって,途中で寄り道しながら移動したと思えば,最大値を超えた分は1ノードあたりコスト2かかる.

UVa 12436 - Rip Van Winkle's Code (この記事を編集する[管理者用])

Source

World Finals Warmup I (2012-02-25)
UVa 12436

問題概要

問題文でコードと同じ動作をするもっと速いコードを書けという問題.
配列のサイズを250000以下として,以下のクエリ(最大400000個)に答えられれば良い.
 A ある区間[st, ed]を指定して,data[st] += 1; data[st+1] += 2; ... data[ed] += ed-st+1;と階段状に足す.
 B ある区間[st, ed]を指定して,data[st] += ed-st+1; data[st+1] += ed-st; ... data[ed] += 1;と階段状に足す.
 C ある区間[st, ed]を指定して,その区間の要素を全部xに変更する.
 D ある区間[st, ed]の和を求める.

解法

セグメントツリー+遅延評価.

UVa 12435 - Consistent Verdicts (この記事を編集する[管理者用])

Source

World Finals Warmup I (2012-02-25)
UVa 12435

問題概要

2次元平面上の格子点にN人の人がいる.(Nは1000以下)
それぞれの人が順番に銃を鳴らす.
ある実数があって,距離R以下で鳴らされた銃の音は聞こえる.
自分の銃以外で,何個の銃が聞こえたかという配列のを考える.
その配列は何種類考えうるかを求める問題.

解法

最初0で,Rを増やしていくと徐々に増えていく.
基本的には,聞こえる聞こえないの閾値はC(N,2)ぐらいあるので,C(N,2)+1が答えになる.
が,2点間の距離が同じ組があればそのぶん縮退して答えが少なくなる.
2点間の距離を列挙して,異なるものが何個あるかを数える.

SRM557 DIV1 HARD - XorAndSum (この記事を編集する[管理者用])

Source

TopCoder SRM557 DIV1 HARD (1000pt)
Problem Statement

問題概要

n要素の非負整数からなる数列が与えられる.nは50以下で,各要素は10^15以下.
好きなだけ以下の操作を行う.
 数列の要素A[i]とA[j]を取ってきて,A[i]をA[i] XOR A[j]に変える.(A[j]はそのまま,iとjは異なってなければならない)
最終的に得られる数列の各要素の和の最大値求める問題.

解法

Ad-hocかつgreedyにやる.色々やりかたはあるみたいだけど,以下は自分の解法.
まず最上位ビットが1な要素を1つだけにする.
その要素を取り除いた時に,最上位ビットが1なのを1つだけにする.
と繰り返していき,基底を作る.幾つかの要素は0になるが,それは最後に最大値とXOR取れば良いので除外して考える.
最上位ビットを保ったまま,それぞれの数字を最小化する.
それは,自分の最上位ビットより下位ビットしかないものとXORを取って減るならgreedyにXORを取るというのを繰り返せば良い.
次に最も大きい要素だけ最大値にする.それも,greedyにXOR取る.
後は,最大値以外の全ての要素は最大値とXORを取って終わり.
これで和が最大になる証明は難しくないと思う.

C++によるスパゲッティなソースコード

続きを読む

SRM557 DIV1 MEDIUM - Incubator (この記事を編集する[管理者用])

Source

TopCoder SRM557 DIV1 MEDIUM (550pt)
Problem Statement

問題概要

n人の少女がいる.(50以下)
また,各少女が,各少女が愛しているかどうかが与えられる.
好きな少女を魔法少女にすることができる.
魔法少女になると,魔法少女が愛している少女を守ることができて,また,守られている少女が好きな少女も守られる.
守られていない魔法少女の数の最大値を求める問題.

解法

各少女について,その少女が魔法少女になれば結果的に守られる少女を調べるために,ワーシャルフロイドやら何やらしておく.
魔法少女になったら,自分を守ることになる少女は,魔法少女にするだけ損なので除外して考える.
するとグラフはDAGになって,最小パス被覆を求める問題になって,二部マッチングで解ける.

C++によるスパゲッティなソースコード

続きを読む

SRM557 DIV1 EASY - FoxAndMountainEasy (この記事を編集する[管理者用])

Source

TopCoder SRM557 DIV1 EASY (250pt)
Problem Statement

問題概要

n+1要素の数列を考える.(nは100000以下)
その数列は非負整数のみからなり,その階差数列 (D[i] = A[i+1] - A[i]) はすべて1か-1.
階差数列の連続する部分がmin(n,50)要素以下与えられる.
また,数列の初項A[0]と末項A[n]が与えられる.
そのような数列が存在しうるかどうかを判定する問題.

解法

階差数列で与えられない部分で,1の要素の数,-1の要素の数は計算可能. 後は0を下回らないように,1を全部使って,与えられた部分を使って,-1を全部使えば良い. 本番では,1を使う数は,0を下回らないぐらい使って,後はgreedyに0に近づくようにシミュレーションした.

C++によるスパゲッティなソースコード

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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