Entries

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

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

ARC 012 B - アキレスと亀 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #012
問題文

問題概要

高橋くんとカメが徒競走をしている.
高橋くんの速度を $v_a$,カメの速度を $v_b$ として,最初カメは高橋くんから $L$ だけ前にいる.($v_a > v_b$)
今カメがいる場所まで高橋くんが移動するのを1ステップとして,$N$ ステップ後には高橋くんとカメとの距離を求める問題.
$N \leq 100$.

解法

シミュレーションする.
距離はステップ数に関して幾何級数的に減少するのでpowなどを使って求めても良い.

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

続きを読む

ARC 012 A - 週末 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #012
問題文

問題概要

曜日の英語名が与えられるので,土曜日または日曜日までの日数を求める問題.
すでに土曜日または日曜日なら0が答え.

解法

やるだけ.

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

続きを読む

UVa 12686 - Trending Topic (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12686

問題概要

$1$ 日毎のWebに掲載された文章が与えられる.
また,$1$ 日毎の文章の間にクエリが与えられることがある.
各クエリでは,最近 $7$ 日間の文章に出てきた単語のうち,出現頻度が高い順から $N$ 個,出現回数と単語をペアで出力する.
ただし,同率 $N$ 位の単語があれば,同率 $N$ 位の単語はすべて出力する.
同じ出現頻度の単語はアルファベット順に出力する.
また,$3$ 文字以下の単語は無視する.
単語は $20$ 文字以下でアルファベット小文字のみからなる
日数は $20000$ 以下
$1$ 日の文章中に出てくる単語の数は $20000$ 以下
全体で出てくる単語の種類数は合計で $20000$ 以下

解法

適当に実装する.
例えば,過去 $7$ 日間の単語の出現頻度をmap<string,int>などで管理し,クエリが飛んできたらマージしてソートして出力する.

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

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12685

問題概要

無限に大きい $2$ 分木を考える.
各ノードは,左の子供ノード,右の子供ノード,上に親ノードを持っている.
ただし,ルートの親のノードはルートとみなす.
命令の列 $S$ と $T$ が与えられる.
命令はL, R, Uの3種類で,それぞれ,今いるノードから左,右,上のノードに移動することを意味する.
最初はルートにいて,命令列 $S$ を全部こなす.
その後,命令列 $T$ をこなすのだが,命令列 $T$ に関しては,各命令をこなすか,その命令をスキップするかを選ぶことができる.
全ての操作が終わった時に,最後にいること可能性のあるノードの数を mod $ 21092013$ で求める問題.
$S, T$ の命令の数はそれぞれ $10^5$ 以下

解法

まず,$S$ を眺めていって,Uでなければその命令を追加,Uなら最後に追加した命令を削除,として,
$S$ が終わった地点でのいる場所を,ルートからL, Rのみの列を用いて表しておく.
また,命令列 $T$ の各命令に対して,その後に出てくる一番最初の命令L, R, Uの場所を後ろからなぞって計算しておく.
$T$ のある場所以降で,LとRのみを用いて移動できるノードの数をDPで計算する.この時,上で計算した各命令が出てくる最初の場所を使えば $O(|T|)$ で計算できる.
まず,現在位置から,$1$ 歩左に行ってから,および,右に行ってから,その先に移動パターンをDP表から答えに足す.
後は,上に何回か移動した後,逆方向に進んでから,その先の移動パターンを足していく.

UVa 12684 - VivoParc (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12684

問題概要

$N$ ノードのグラフが与えられる.
枝がつながっているノード通しは別の色に塗ることにして,$4$ 色で塗り分ける方法を $1$ つ出力する問題.
答えが存在することは保証されている.
$N \leq 100$

解法

枝刈り探索で間に合う.

UVa 12683 - Odd and Even Zeroes (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12683

問題概要

$f(k)$ を $k!$ を $10$ 進数で書いた時,最後に $0$ が続く数とする.
$f(0), f(1), \ldots, f(n)$ のうち偶数の物の数を求める問題.
$n \leq 10^{18}$

解法

$f(k)$ が偶数である条件は
 $k$ を $5$ 進数で書いた時,$5^{2m}$ の桁の数字を足したら偶数になる
ということ.
与えられた $n$ を $5$ 進数に直して,桁DPする.

UVa 12682 - Joe is learning to speak (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12682

問題概要

Joe君は,昨日までに聞いた英語の文章の連続する $k$ 個の単語の列を全部覚えている($k=1,2,\ldots,n$ で $n$ は入力で与えられる).
また,Joe君は,"Joe"という単語は既に知っており,昨日までに聞いた英語の文章は全部与えられる.
今日聞いた文章が $1$ つずつ与えられるので,各文章に対して
 知らない単語があれば,その単語の意味を聞く
 文章が $2$ つ以上の単語からなり,その文章の連続する $k$ 個の単語の列で,知らないものが $1$ つでもあれば,文章の意味を聞く($k=1,2,\ldots,n$)
もちろん,$1$ 度聞いた文章は昨日聞いた文章と同様に覚える.
Joe君が発する言葉を出力する問題.
単語は,大文字と小文字が違うだけのものは同じとみなす.
Joe君が単語の意味,文章の意味を聞くときは,その時与えられた文章,単語と同じように大文字小文字を使い分ける.
$2 \leq n \leq 5$
$1$ 単語の文字数は $20$ 文字以下で,アルファベットのみ.
$1$ つの文章に含まれる単語の数は $100$ 以下.
出てくる単語の種類は合計で $2 \times 10^4$ 以下
前日に聞いた文章,今日聞いた文章の数はそれぞれ $1000$ 以下

解法

頑張って実装する.
文字列をそのまま扱うと重たいので,単語の連続する列をハッシュ値に変換にしてsetに突っ込んだ.

UVa 12681 - Decoding the Hallway (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12681

問題概要

最初線分が $1$ 個あって,方向は左から右に進むことを考える.
時間 $t=1$ で,$1$ 回線分を左方向に折り曲げる.($2$ つの線分に別れる)
時間 $t=n+1$ では,時間 $t=n$ の各線分に対して,進行方向にそって,左,右,左,右,・・・と折曲げていく.
問題文の図を参照.
時間 $t=n$ の線分を移動するときに,曲がる方向の列を文字列として $S_n$ と書く.
$n$ と文字列 $T$ が与えられるので,$T$ が $S_n$ の部分文字列かどうかを判定する問題.
$n \leq 1000$
$|T| \leq 100$

解法

$S_1 = {\rm L}$ で
 $S_{n+1} = S_n + {\rm L} + f(S_n)$
で求められる.ただし,$f(x)$ は $x$ の文字列の順番を反転させた上に,LとRを反転させたもの.
この規則から,十分大きな $n$ 以降は,$100$ 文字以上の部分文字列が新しく増えることはないので,$n$ が大きい時は,$n=10$ ぐらいに落とす.
後は愚直に判定すれば良い.

UVa 12680 - Shopping Malls (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12680

問題概要

ショッピングモール中の $N$ 個の施設とその場所(何階にあるかと $x,y$ 座標)が与えられる.各フロア間の距離は $5$ m で,$x,y$ の単位は m.
施設間に移動する方法が $M$ 個与えられる.
それぞれの移動方法は $2$ つの施設間を移動でき,以下の $4$ 種類がある.
 walking または stairs:歩く距離は $2$ つの施設間のユークリッド距離(walkingとstairsの違いは施設が同じフロアにあるかどうかのみ)
 lift:歩く距離は $1$ mで移動できる
 escalator:順方向には $1$ mで移動でき,逆方向には,施設間のユークリッド距離の $3$ 倍歩けば移動できる.
クエリが $Q$ 個与えられる.
各クエリでは,施設 $a$ から $b$ に移動する方法のうち,最小の歩く距離で移動する方法を出力する.
たぶん移動方法は一意に定まるか,複数の最適解があればどれを出力しても良いと思われる.
全ての施設間で移動する方法があることは保証されている.
$N \leq 200$
$M \leq 1000$
$Q \leq 1000$

解法

各クエリごとにダイクストラして経路復元する.

UVa 12679 - It Can Be Arranged (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12679

問題概要

$N$ 個の授業があり,授業 $k$ の開始時間 $A_k$ と終了時間 $B_k$,その授業の受講者 $S_k$ が与えられる.
$1$ つの部屋を借りると最大で $M$ 人まで収納できる.
また,ある部屋で授業 $i$ を行った後,授業 $j$ を行う場合,清掃時間として間を $C_{ij}$ だけ空けなくてはいけない.
借りなくてはいけない部屋の最小数はいくらか求める問題.
$N \leq 100$
$0 \leq A_k \leq B_k \leq 10^7$
$0 \leq C_{ij} \leq 10^7$
$1 \leq M, S_k \leq 10^5$

解法

DAGの最小パス被覆の変形版.
それぞれの授業に必要な教室数 $\lceil S_k / M \rceil$ は先に計算しておく.
 すべての授業を別の教室を用いた場合の必要数 - 使いまわした教室ののべ数
で答えを計算する.
使いまわせる最大数は,最大流で求めることができる.

UVa 12678 - Mixing Colours (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12678

問題概要

色を混ぜ合わせると新しい色ができる,
 $C_A + C_B = C_C$
という形のルールが $R$ 個与えられる.
連続する色の列の,隣り合う $2$ つを上のルールを適応して $1$ つの色になるまで続けるというゲームが有る.
ただし,ルールに無い場合は,そのような $2$ 色を混ぜ合わせることはできない.
おそらく,任意の列に対して,どの順番でルールを適応しても最終的にできる色は一意に定まると仮定して良いと思われる.(もしくは $1$ 色のみできない場合も有り得る)

いくつかクエリが与えられる.
各クエリでは,$C$ 個の色の列が与えられる.
ただし,各要素は厳密に何色なのかはわからず,この色である確率がいくらという形で与えられる.
混ぜていって最終的に $1$ 色できるような色の列のうち,最も確率が大きい物を考える.
その列を用いて最後にできる色は何かを求める問題.
ただし,最終的に $1$ 色にできない列しかないならそれを指摘する.
$R \leq 100$
$C \leq 500$

解法

区間DPする.
それぞれの区間において,この色ができるという最大の確率をメモする.
状態数が $O(C^2 R)$ で,計算量は $O(C^3 R)$ になる.($O(C^3 R^2)$ などにすると多分まずい)

ARC 016 D - 軍艦ゲーム (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #016
問題文

問題概要

ノード数 $N$,枝数 $M$ のDAGが与えられる.
ノード $1$ からノード $N$ に移動するまでのかかる時間の期待値の最小値を求める問題.
以下の手順で移動する.
また,最大体力は $H$ で,初期体力は最大値である.
 1. 今いるノードから,出ている枝を $1$ つランダムに選び,その枝に沿って移動する.枝が出ていないなら移動できない.
 2. 辿り着いたノードに設定されている数値 $D_i$ だけ体力を減らす.体力が $0$ 以下になった場合は,それ以上何もできないので,そのようなことにはならないようにする.
 3. 現在の体力を $C$ として,$H-C$ だけ時間を消費して,ノード $1$ に移動しても良い.移動した場合は体力は全回復する.
1.~3.までの行動を $1$ 回行うと時間が $1$ だけ経過する.
ただし,期待値が無限大になる場合,ノード $N$ に辿りつけない場合はそれを指摘する.
$1 \leq N \leq 100$
$1 \leq H \leq 100$
答えは $10^6$ を超えない(期待値として有限時間で辿り着けるなら)

解法

3. のノード $1$ に戻る選択肢がなければ,今いるノードと現在体力を状態としてDPすれば良い.
答えを $X$ だと決め打ちすると,ノード $1$ に戻るときにかかる時間の期待値を $X$ を使って表すことができ,DPできる.
その結果の答え $T_X$ は,本当の答えを $T$ とすると,
 もし,$X \leq T$ ならば,帰るときに小さく見積もってしまうので $X \leq T_X \leq T$ となり,
 もし,$X \geq T$ ならば,帰るときに大きく見積もってしまうので $X \geq T_X \geq T$ となる.
これを利用して $2$ 分探索で答えを求めれば良い.

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

続きを読む

ARC 016 C - ソーシャルゲーム (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #016
問題文

問題概要

カードが $N$ 種類,ガチャが $M$ 種類ある.
各ガチャを $1$ 回まわすコストと,どのカードが出るかという確率が全て与えられる.
全てのカードを集めるまでにかかるコストの平均値の最小値を求める問題.
$1 \leq N \leq 10$
$1 \leq M \leq 4$
部分点あり(原文を参照のこと)

解法

今どのカードが集まっているかを状態としてビットDPする.
既に持っているカードが出てくることがあるので,
 $X = pX + Y$

 $X = Y / (1-p)$
にするような式変形をする.

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

続きを読む

ARC 016 B - 音楽ゲーム (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #016
問題文

問題概要

リズムゲームの譜面が与えられる.
譜面は $9$ 列,つまりボタンの数が $9$ 個で,ボタンを押す場所は x で書かれ,ボタンを押さない場所は . で書かれる.
また, o は連続した o の間ボタンを押しっぱなしにする.
ボタンを押す回数を求める問題.
$1 \leq$ 譜面の行の数 $\leq 100$

解法

答えは,xの数 + 上の列がoでないoの数,なとど求める.

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

続きを読む

ARC 016 A - クイズゲーム (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #016
問題文

問題概要

クイズにおいて,選択肢が $N$ 個の問題を考える.
選択肢の番号は $1,\ 2,\ \ldots,\ N$ で,正解の選択肢は $M$ である.
不正解の選択肢を $1$ つ出力する問題.
$2 \leq N \leq 5$

解法

どうやっても良い.
例えば, $M=1$ なら $2$ を出力し,そうでないなら $1$ を出力する.

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

続きを読む

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

Source

TopCoder SRM597 DIV1 MEDIUM (600pt)
Problem Statement

問題概要

頂点数 $N\ (3 \leq N \leq 50)$ の凸多角形が与えられる.(頂点が反時計回りに与えられる)
各頂点の座標は整数で,絶対値は$10^5$以下.
任意の $3$ 頂点は一直線上にはない.
$2$ 人でゲームをする.行動できなくなったほうが負け.先手必勝か後手必勝かを判定する問題.
各ターンでは,以下の様な凸多角形を作り,次のターンには与えられた凸多角形の代わりにする.
 各頂点は格子点で,与えられた凸多角形の内部,および,周上にある
 各頂点は,与えられた凸多角形の頂点と異なる
 任意の $3$ 頂点は一直線上にない

解法

与えられた多角形の内部に,三角形が作れれば先手の勝ち,そうでなければ後手の勝ち.
なぜなら,後手が打つ手があるなら,その手を先手が打てば良い.(というのを再帰的に繰り返すと後手が打つ手が無い三角形を書ける)
したがって,多角形の内部,および,周上に,一直線上にない $3$ 点が取れるかどうかを判定する問題になる.
基本的には,内部および周上の点を全部列挙して,それらが全て一直線上にあるのかどうかを判定すれば良い.
それは,$x$ 座標を $-10^5$ から $10^5$ まで全部試して,内部の点の $y$ 座標の最大値と最小値を求めれば良い.
ただし,全列挙すると数が多すぎるので,一直線上にあるなら内部の点は高々 $2 \times 10^5$ ぐらいなので,それを超えたらやめるか,
各 $x$ 座標について,数点のみを列挙するなどして適当に端折る必要がある.

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

続きを読む

SRM597 DIV1 EASY/DIV2 MEDIUM - LittleElephantAndString (この記事を編集する[管理者用])

Source

TopCoder SRM597 DIV1 EASY (250pt)
TopCoder SRM597 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

アルファベッド大文字からなる文字列 $A$ と $B$ が与えられる.
1回の操作で,文字列 $A$ から任意の1文字を取り出し,$A$ の先頭にくっつけることができる.
最小で何回の操作で $A = B$ とできるかを求める問題.
不可能ならそれを指摘する.
$1 \leq |A| = |B| \leq 50$

解法

$A$ と $B$ で含まれる個数が違う文字があれば不可能.
$B$ の後ろから $k$ 文字が $A$ の部分列(部分文字列ではない)ならば,$|A| - k$ 回で可能.
そのような $k$ の最大値を全探索で探す.
部分列になっているかどうかは $B$ の後ろの $k$ 文字をgreedyに $A$ の文字と対応させていってチェックする.

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

続きを読む

Round #209 DIV2 E問題 - Neatness (この記事を編集する[管理者用])

Source

Codeforces Round #209 DIV2 E問題 (2500pt)
Problem description

問題概要

縦横 $n$ マスのグリッドが与えられる.
各セルは部屋で,合計 $n^2$ 個の部屋がある.
最初,各部屋が電気が付いているかどうかが与えられる.
また,最初にいる部屋の位置 $(x_0,\ y_0)$ が与えられる.
全ての部屋の電気を消した上で,最初いた部屋に戻る方法を $1$ つ求める問題.
手順数は最小である必要はないが,手順数は $3 \times 10^6$ 以下でなければならない.
できる手順は以下の通り:
 上下左右にずっと進んだ方向に,$1$ つ以上電気がついた部屋があるなら,上下左右に $1$ マス移動できる
 今いる部屋の電気をつける,もしくは,消す
なお,不可能ならそれを指摘する.

解法

DFSで行けるセルを全て巡る.
その際,初めてそのセルに到着した時に,電気がついていないなら電気をつけ,
最後にそのセルから立ち去るときに,電気を消していけば良い.
以下の解答では,$1$ 回目のDFSで電気をつけて回って,$2$ 回目のDFSで電気を消して回った.

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

続きを読む

Round #209 DIV2 D問題 - Pair of Numbers (この記事を編集する[管理者用])

Source

Codeforces Round #209 DIV2 D問題 (2500pt)
Problem description

問題概要

正整数の配列 $a_1,a_2,\ldots,a_n$ が与えられる.
以下の条件を満たす $(L,\ R)$ を全て列挙する問題.
 1. $a_L, a_{L+1}, \ldots, a_R$ が全て $a_j$ の倍数となるような $j$ が存在する ($1 \leq L \leq j \leq R \leq n$)
 2. 1.の条件を満たすもののうちで,$R-L$ が最大となる
$1 \leq n \leq 3 \times 10^5$
$1 \leq a_k \leq 10^6$

解法

色々な方法があると思う.
$a_j$ は $a_L, a_{L+1}, \ldots, a_R$ の中で最小の要素.
小さい順に $a_j$ を全て試し,全てが $a_j$の倍数となる最大の区間 $[L,\ R]$ を全部求めた.
ただし,一度でも区間 $[L,\ R]$ に含まれた要素は,$j$ として選ばないようにした.
他の方法としては,segment treeでgcdを管理して2分探索で $L, R$ を求める方法など.

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

続きを読む

Round #209 DIV2 C問題 - Prime Number (この記事を編集する[管理者用])

Source

Codeforces Round #209 DIV2 C問題 (1500pt)
Problem description

問題概要

 $\displaystyle \frac{1}{x^{a_1}} + \frac{1}{x^{a_2}} + \ldots + \frac{1}{x^{a_n}} = \frac{s}{t},\ t = x^{a_1+a_2+\cdots +a_n}$
と書いた時,$s/t$ をいくら約分できるか,つまり,${\rm gcd}(s,t)\ {\rm mod}\ (10^9+7)$ を求める問題.
$1 \leq n \leq 10^5$
$2 \leq x \leq 10^9$
$0 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq 10^9$

解法

普通に通分すると,分母は $x^{a_n}$ なので,とりあえずそれを基準に考える.($x^{a_1+a_2+\cdots+a_{n-1}}$ では取り敢えず約分できる)
後は,$a_n$ と等しい要素の数 $D$ が,$x$ の倍数なら,もう $1$ 回 $x$ で約分できる.
更に,その時,$D/x + (a_n - 1$と等しい要素の数$)$ が $x$ の倍数なら,更にもう $1$ 回 $x$ で約分できる.
というのを繰り返していく.

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

続きを読む

Round #209 DIV2 B問題 - Permutation (この記事を編集する[管理者用])

Source

Codeforces Round #209 DIV2 B問題 (1000pt)
Problem description

問題概要

要素数 $n$ の置換 $a$ で,
 $\displaystyle \sum_{i=1}^n \left| a_{2i-1} - a_{2i} \right| - \left| \sum_{i=1}^n (a_{2i-1} - a_{2i}) \right| = 2k$
となるものを $1$ つ求める問題.
$1 \leq n \leq 50000$
$0 \leq 2k \leq n$

解法

$2k \leq n$なので,適当に,どうやっても良い.
例えば,$a_1 = 1+k, a_2 = 1$ として残りは昇順にする.
または,$a_i = i$ としておいて,$k$ 箇所だけ $a_{2i-1}$ と $a_{2i}$ をスワップするなど.

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

続きを読む

Round #209 DIV2 A問題 - Table (この記事を編集する[管理者用])

Source

Codeforces Round #209 DIV2 A問題 (500pt)
Problem description

問題概要

縦 $n$ マス,横 $m$ マスのグリッドが与えられる.
各セルは $1$ か $0$ かが書かれている.ただし四隅のセルは全て $0$.
以下の手順を最小で何回繰り返せば,すべてのセルに色を塗ることができるかを求める問題.
 $1$ が書かれているセル $(x_1,\ y_1)$ と,四隅のうちの $1$ つのセル $(x_2,\ y_2)$ を選ぶ.
 その $2$ セルを対角線とする長方形の領域に色を塗る
 つまり,$(x,\ y)$ は $\min(x_1,x_2) \leq x \leq \max(x_1,x_2),\ \min(y_1,y_2) \leq y \leq \max(y_1,y_2)$ であれば色が塗られる.
同じセルに何回色を塗っても良い.
$3 \leq n,m \leq 50$
$1$ が書かれているセルが,少なくても $1$ つある

解法

上下左右の端に $1$ のセルがあれば $2$ 回で全部塗れる.
そうでなければ $4$ 回.

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

続きを読む

Round #208 DIV2 E問題 - Dima and Kicks (この記事を編集する[管理者用])

Source

Codeforces Round #208 DIV2 E問題 (3000pt)
Problem description

問題概要

縦 $n$ マス,横 $m$ マスのグリッドが与えられる.
一度でも訪れた部屋は $1$,訪れなかった部屋は $0$ で表される.
部屋は,上下左右につながっている.
以下の条件をみたすように移動する.
 $1$ 回の移動では,上下左右のどちらかの方向に必ず $k$ マスだけ進む.
 必ず $1$ 回以上移動している.
 $2$ つの部屋を繋ぐドアで $2$ 回以上通ったものはない.
考えうる $k$ を全て列挙する問題.不可能ならそれを指摘する.
$1 \leq n, m \leq 1000$

解法

全ての $k$ について条件をみたすか調べる.
一番左上の訪れたことがある部屋を起点として,$k$ マス飛ばしで見て,その間は通路だと思う.
通路が全部 $1$ になっていればそこは通ったということ.
部屋が全部連結で,奇数次数の部屋が $2$ 箇所以下なら一筆書きで移動できる.
余分な $1$ がないかは,部屋と通路で使った $1$ の数を数えればわかる.
後は,結構愚直に調べても大丈夫.

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

続きを読む

Round #208 DIV2 D問題 - Dima and Hares (この記事を編集する[管理者用])

Source

Codeforces Round #208 DIV2 D問題 (2000pt)
Problem description

問題概要

$1$ 番から $n$ 番のうさぎが一列に並んでいて,好きな順番に餌を $1$ 回ずつあげる.
うさぎ $k$ が餌をもらった時,両隣のうさぎですでに満腹なうさぎが
 $0$ 匹なら $a_k$ だけ
 $1$ 匹なら $b_k$ だけ
 $2$ 匹なら $c_k$ だけ
満足度が得られる.
最も左,最も右のうさぎの隣のうざぎがいない部分は空腹なうさぎとみなす.
満足度の和の最大値を求める問題.
$1 \leq n \leq 3000$
$1 \leq a_k, b_k, c_k \leq 10^5$

解法

最も左の,自分の左右より先に餌付けされるうさぎの場所で場合分けして,DPする.
ただし,一番左のうさぎは自分より右だけを見る.
選ばれたうさぎより左のうさぎは,右から順番に餌付けされることになる.
もしくは,左からどこまで見たか,最後に見たのうさぎは一つ右より先に餌付けされたかどうか,を状態にしてDPしても良い.

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

続きを読む

Round #208 DIV2 C問題 - Dima and Containers (この記事を編集する[管理者用])

Source

Codeforces Round #208 DIV2 C問題 (1500pt)
Problem description

問題概要

スタックとキューとデックが1個ずつあり,最初は全部空.
$n$ 回だけとある非負整数が与えられるので以下のようにする.
 与えられた非負整数 $a$ が $0$ なら,スタック,キュー,デックそれぞれ高々 $1$ 個の要素を取り除いて,取り除いた整数の和をスコアに加える.そして,スタック,キュー,デックを空にする.
 与えられた非負整数 $a$ が $0$ でないなら,スタック,キュー,デックのどれかに挿入する.
入れられる場所,取り出せる場所はそれぞれのデータ構造に依存する.
最大のスコアを得られる方法を $1$ つ求める問題.
$n \leq 10^5$
$0 \leq a \leq 10^5$

解法

色々方法はあるけど,一番簡単なのは,デックの片側に要らないものを全部押し付ける方法.
$a=0$ が来るまでの大きい方から $3$ つをスタック,キュー,デックのもう片側に $1$ 個ずつ入れておいて取り出せば良い.

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

続きを読む

Round #208 DIV2 B問題 - Dima and Text Messages (この記事を編集する[管理者用])

Source

Codeforces Round #208 DIV2 B問題 (1000pt)
Problem description

問題概要

$n$ 個のアルファベット小文字からなる単語 $w_1, w_2, \ldots, w_n$ が与えられる.
単語を順番につなげて,各単語の間と最初と最後に "<3" を挿入した後,更に何らかの文字をいくらか挿入した.
その結果が文字列 $S$ になったという.
矛盾していないか調べる問題.
$|w_1| + |w_2| + \cdots + |w_n| \leq 10^5$
$|S| \leq 10^5$

解法

"<3"を挿入した文字列を実際に作って,$S$ の部分列になっているかどうか調べる.

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

続きを読む

Round #208 DIV2 A問題 - Dima and Continuous Line (この記事を編集する[管理者用])

Source

Codeforces Round #208 DIV2 A問題 (500pt)
Problem description

問題概要

$n$ 個の異なる整数 $x_1,x_2,\ldots,x_n$ が与えられる.
$2$ 次元平面の $y \geq 0$ の部分に,$(x_i, 0)$ と $(x_{i+1}, 0)$ を直径とする半円を描く.
半円が($y > 0$ の部分で)交わるかどうかを判定する問題.
$n \leq 1000$
$-10^6 \leq x_k \leq 10^6$

解法

全ての半円の組に対して交わるかどうかを調べる.

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

続きを読む

天下一プログラマーコンテスト2013予選B E - 天下一最短路コンテスト (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

まず,以下の問題を考える.
2次元平面上にN個の点が与えられるので,最初に与えられた点から出発して,全ての点を通るようなできるだけ短い経路を出力せよ.
この問題に対する貪欲なアルゴリズムとして,
・アルゴリズム1
 まだ通ってない最も近い点を選び,その点に行く,を繰り返す
・アルゴリズム2
 まだ通ってない点が3点以上あるなら,2番目に近い点に行く,を繰り返す
 まだ通ってない点が3点未満になったら,最も近い点に行く,を繰り返す
ただし,同じ距離の点が複数ある場合は,与えられた順番に近いとみなす.
この時,アルゴリズム2の方が,短いかアルゴリズム1と同じ長さの経路を返すようなデータセットを1つ求める問題.
Nが大きいほど点数が高く,N=100で満点だが,Nは100を超えてはいけない.

解法

適当にやればなんとでもなる.以下は解答の一例.
アルゴリズム2が良い結果を返す小さい点のパターンを見つけ,うまく繋げる
95点程度をほぼ1箇所に固めて,残りの点をランダムに配置して,条件を満たすまで繰り返す.(以下のコードはこれ)
アルゴリズム1の経路長 - アルゴリズム2の経路長などをスコアとして山登り,焼き鈍すなどの局所探索を行う.
はしご型や,規則正しく点を配置して,アルゴリズム2が勝つパターンを見つける.

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

続きを読む

天下一プログラマーコンテスト2013予選B C - 天下一ジグソーパズルふたたび (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

縦$N$マス,横$M$マス,全体で$NM$ピースのジグソーパズルを考える.
上下左右に隣り合うピースは,片方が凹で,片方が凸,端の辺は直線.
KLabのマークであるKっぽい,1辺が直線,3辺が凹のピースの数を最大がしたい.
ただし,4辺とも凹のピースを$A$個以上使って,4辺とも凸のピースが最大でも$B$個までしか使えない.
$2 \leq N, M \leq 8$.
部分点もある.(原文を参照)

解法

DPする.
左上から順番にピースを決めて行って,
 今の場所,4辺凹のピースを使った数,4辺凸のピースを使った数,過去1列分の下向きに接する面は凸か凹か?,一つ左のピースの右側の辺は凸か凹か?
を状態として,K型のピースの最大値をメモする.
状態数は多く見積もっても$1.2 \times 10^7$以下程度だが,配列で愚直にメモリ確保するとMLEに引っかかる可能性があるのに注意する.
いろいろ頑張って枝刈りすれば全探索も可能らしい.

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

続きを読む

天下一プログラマーコンテスト2013予選B B - 天下一後入れ先出しデータ構造 (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

スタックのシミュレーションを行う問題.
ただし,1回の命令で,同じ数字をたくさん入れたり,たくさんPopしたりできる.
また,スタックに入っている数の数や,スタックのトップの要素を答えたりするクエリが混じっている.
また,スタックのサイズが決まっており,サイズを超えたり,空のスタックからPopしたりトップの要素を参照すると途中でエラーを出して止める.
詳細は問題文を参照.

解法

シミュレーションをやるだけ.
たくさん追加するのは,1つずつやるとTLEになるので,まとめて処理して,何が何個入っている,という形で保存する.
スタックのサイズが,符号付き32ビット整数で表せる限界まで来るので,オーバーフローに注意.(素直に64ビット整数使って気にしないのが楽)

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

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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