Entries

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

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

SRM306 DIV2 HARD - BlockDistance (この記事を編集する[管理者用])

Source

TopCoder SRM306 DIV2 HARD (1000pt)
Problem Statement

問題概要

1000文字以下の文字列A, Bが与えられる.
1回の操作では以下のことができる.
 Aの好きな場所に,好きな文字列(何文字でも良い)を挿入する
AをBに一致させるために必要な最小手順数を求める問題.
不可能ならそれを指摘する.

解法

DPする.状態は
 dp[a][b][fg] = Aの最初a文字,Bの最初b文字,だけが入力の時の答え
 ただし,fg=1のときは,Aの最後に何かを挿入している(次にAの最後に挿入するときにコストが掛からない)
とする.

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

続きを読む

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

Source

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

問題概要

要素数50以下の配列aが与えられる.
各要素は-1000以上1000以下の整数で,すべて異なる.
1回の操作では,以下のどちらかのことができる.
 1つの要素を取り出して,一番最初に付け加える
 1つの要素を取り出して,一番後ろに付け加える
昇順にソートするのに必要な最小手順数を求める問題.

解法

1つ目の操作をK回,2つ目の操作をL回行うというのは,小さい方からK個,大きい順からL個の要素を無視するというのと同じ.
(取り出す順番を考えれば,必ずソートされている順番にできる)
L, Kを全部試して,残りの部分がソートされているかどうかを調べれば良い.
DIV2 EASYが類題.

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

続きを読む

SRM306 DIV2 EASY - SortMachine (この記事を編集する[管理者用])

Source

TopCoder SRM306 DIV2 EASY (250pt)
Problem Statement

問題概要

要素数50以下の配列aが与えられる.
各要素は-1000以上1000以下の整数で,すべて異なる.
1回の操作では,以下のことができる.
 1つの要素を取り出して,一番後ろに付け加える
昇順にソートするのに必要な最小手順数を求める問題.

解法

K回操作を行うというのは,大きい順からK個の要素を無視するというのと同じ.
(取り出す順番を考えれば,必ずソートされている順番にできる)
Kを0から増やしつつ,残りの部分がソートされているかどうかを調べれば良い.
DIV1 EASY/DIV2 MEDIUMが類題.(以下のコードはそのコードから1行コメントアウトしただけ)

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

続きを読む

SRM300 DIV2 HARD - CircleOrder (この記事を編集する[管理者用])

Source

TopCoder SRM300 DIV2 HARD (1000pt)
Problem Statement

問題概要

円の形をした道路がある.
その上に,$25$台以下の車(アルファベット小文字)と,それぞれの車の目的地(対応するアルファベット大文字)が与えられる.
車は$1$台ずつ動かし,途中で立ち止まらず,目的場所に移動する.
車はすれ違うことはできない.
どの順番で動かせば,全ての車が目的地に辿り着けるか,その順番の中で辞書順最小のものを求める問題.
不可能であるなら,それを指摘する.

解法

まず,全ての車が目的地に辿り着ける必要条件(必要十分ではない!)は
 与えられた文字列から小文字だけ抜き出した文字列を$S$
 与えられた文字列から大文字だけ抜き出した文字列を$T$
としたとき,$S$か$T$を適当に回転(頭から数文字をお尻にくっつける)したとき一致すること.
このときだけ考えると,車はすれ違わないので,どの車から動かしても,他の車が目的地に辿りつけなくなるようなことはない.
(逆に,ある車が目的地にたどり着いた後でないと,動かせない車はある)
なので,greedyに動かせる車のうち,アルファベット順で最も早い車から動かしていって,最終的に全部の車が辿り着けるかどうか調べれば良い.

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

続きを読む

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

Source

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

問題概要

円周上に$50$人以下の人が並んでいる状態が文字列で与えられる.
男性はアルファベット小文字,女性はアルファベット大文字で表される.
また,$100$以下の正整数${\rm K}$が与えられる.
以下の操作を繰り返した時,デートするカップルを選ばれた順番に出力する問題.

男性,女性のどちらかがいなくなっていれば終了.
最初の人を1番目と数えて,${\rm K}$番目の人を選ぶ.
また,その人の異性の中で,アルファベット順で最も早い人を選ぶ.
その2人をデートするカップルとして選び,円周上から除外する.
次回の最初の人は,${\rm K}$番目として選ばれた人の次の人.

解法

頑張ってシミュレーションする.

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

続きを読む

SRM300 DIV2 EASY - Taxi (この記事を編集する[管理者用])

Source

TopCoder SRM300 DIV2 EASY (250pt)
Problem Statement

問題概要

2点間$(x_1, y_1)$と$(x_2, y_2)$との距離を2種類定義する:
 マンハッタン距離 $|x_1 - x_2| + |y_1 - y_2|$
 ユークリッド距離 $\sqrt{ (x_1 - x_2)^2 + (y_1 - y_2)^2 }$
${\rm maxX}, {\rm maxY}, {\rm taxiDist} \leq 1000000$が与えられる.
3条件
 (1) $0 \leq x_1, x_2 \leq {\rm maxX}$
 (2) $0 \leq y_1, y_2 \leq {\rm maxY}$
 (3) $(x_1, y_1)$と$(x_2, y_2)$とのマンハッタン距離が${\rm taxiDist}$
を満たすとき,$(x_1, y_1)$と$(x_2, y_2)$とのユークリッド距離の最大値はいくらか求める問題.
3条件を満たす2点$(x_1, y_1)$と$(x_2, y_2)$が存在しないときはそれを指摘する.

解法

$x_1 \leq x_2,\; y_1 \leq y_2$としてしまって良い.
最初の2条件は$d_x = x_2 - x_1 \leq {\rm maxX}, \; d_y = y_2 - y_1 \leq {\rm maxY}$となる.
$d_x$を決め打てば,$d_y = {\rm taxiDist} - d_x$で求まるので,$d_x$を(整数の範囲で)全探索する.
もしくは,できるだけ長細い($d_x$が最大,または,$d_y$が最大)の時が答えになるので,それを場合分けして求める.

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

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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