Entries

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

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

LiveArchive 4791 - The Islands (この記事を編集する[管理者用])

Source

ACM/ICPC World Finals - Harbin - 2009/2010
LiveArchive 4791

問題概要

二次元上に100個以下の点があって,左から右へ,と行って,その後,右から左へと行って,往復で全部の点を通る.
ただし,2点与えられて,その2点は両方とも行き,または両方共帰りに寄ることはできない.
最短距離と経路を求める問題.

解法

左から右へ2本のパスを作ることを考える.
左から右に行くほどノード番号が増えていくとして,
 dp[a][b]は現在ノードmax(a,b)まで行っていて,片方のパスの終端がノードa,もう片方のパスの終端がノードbとなるパスの2つの長さの和の最小値
を覚えて置いてDPすれば良い.

LiveArchive 4788 - Castles (この記事を編集する[管理者用])

Source

ACM/ICPC World Finals - Harbin - 2009/2010
LiveArchive 4788

問題概要

城攻めで,全ての城を陥落させるのに必要な兵士の数の最小値を求める問題.
城はグラフでいう木構造で繋がっていて,最初に攻める城は自由に決めて良くて,後は,木構造にしたがって動く.
ただし,同じ城を通るのは2回までで,3回以上横切ってはいけない.
城を攻めるときに,各城ごとに,
 落とすのに必要な兵士の数
 落とすときに死亡する兵士の数
 落とした後,常駐させなくてはいけない兵士の数
が与えられる.
城の数は100以下.

解法

最初にどの城を落とすか,最大100パターン全部試す.
すると,根付木になるのだけど,同じ城を3回以上横切らないという条件から,あるサブツリーの城のルートを落とすと,後はそのサブツリーの城を全部落とすまで戻ってこれない.
ので,サブツリーの城を全部落とすのに,必要な最小兵士の数と(死亡する+常駐させる)兵士の数を再帰的に求めれば良い.
どのサブツリーから落としていくかは,最小兵士の数 - (死亡する+常駐させる)兵士の数が大きい順にgreedyに行けば良い.

LiveArchive 4787 - Tracking Bio-bots (この記事を編集する[管理者用])

Source

ACM/ICPC World Finals - Harbin - 2009/2010
LiveArchive 4787

問題概要

2次元グリッド上に1000個以下壁がある.
壁は東西を向いていて,グリッドのサイズは縦横10^6以下.
右か上にしか動けないとき,初期位置として,一番右上のマスに辿り着けないマスの数を求める問題.

解法

座標圧縮して,出口からDFSで塗りつぶして,塗りつぶされなかったセルの数が答え.

LiveArchive 4786 - Barcodes (この記事を編集する[管理者用])

Source

ACM/ICPC World Finals - Harbin - 2009/2010
LiveArchive 4786

問題概要

太い線と細い線からなるバーコードをデコードする問題.
太い線は細い線の2倍の太さだけど,5%以下の誤差は許容する.
左右どちらから読み込まれているかわからないので反転して読めるならそうする.
チェックサムが2個埋め込まれているので,それも確かめて,それが合わないならそれを報告する.またそれ以外で不都合が生じたらそれも報告.
などなど,問題文に書かれている事柄を忠実に実装する問題.

解法

やるだけ.

UVa 10562 - Undraw the Trees (この記事を編集する[管理者用])

Source

UVa 10562

問題概要

アスキーアートで書かれた木構造のグラフの構造を解析して,フォーマットして返す問題.
サンプル参照.

解法

やるだけ.

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

Source

UVa 10557

問題概要

節点数100以下の有向グラフが与えられる.
各ノードに辿り着く度に,ノードに設定された数値だけHPが減る.
最初あるノードにHP100でいる.
HP0以下にならずに,目的のノードまで辿りつけるかどうかを判定する問題.

解法

ベルマンフォードっぽく,あるノードにたどり着ける最大HPを適当にループを回して更新していった.

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

Source

UVa 10510

問題概要

与えられた有向グラフがcactusかどうかを判定する問題.
cactusとは,強連結でかつ,全ての枝がちょうど1つの単純閉路に含まれていること.
ノード数,枝数は0以上,10000以下.

解法

まず,強連結成分分解とか何かで連結かどうか調べる.
あとは,DFSしながらアドホックに調べてみた.
具体的には,向かう先のノードがすでに訪れているならスタックに入れて,戻ってきた時,スタックの一番上が自分のノードであれば消す.
自分のノードでないことが2回以上あったらダメ,など.

SPOJ 5732 - Paradox [PARADOX] (この記事を編集する[管理者用])

Source

Kurukshetra OPC 2010
SPOJ 5732 [PARADOX]

問題概要

n人の人がいて,それぞれの人が,人kの言っていることは本当か嘘かのどっちかだと言っている.
矛盾があるかどうかを調べる問題.
nは100以下.

解法

2-SATなので強連結成分分解.

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

Source

TopCoder SRM457 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

六角格子7マスを2n以下の数字を埋めたい.
ただし,同じ数字は2回以上使えない,隣り合う数字はmod nで等しいとダメ.
回転して同じものは同じとみなす.
何通り入れ方があるか?
nは150以下.

解法

mod nで同じ数字を何回使うかで場合分けする.
他の方法は,DPするとか,2つは決めつけて良くて残りを全探索するなど.

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

続きを読む

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

Source

TopCoder SRM457 DIV2 HARD (1000pt)
Problem Statement

問題概要

六角格子7マスをn以下の数字を埋めたい.
ただし,同じ数字は2回以上使えない,隣り合う数字はmod kで等しいとダメ.
回転して同じものは同じとみなす.
何通り入れ方があるか?
kは9以下.

解法

k^7通りの入れ方を全部試す.

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

続きを読む

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

Source

TopCoder SRM460 DIV1 MEDIUM (500pt)
Problem Statement
SRM460 参加記録

問題概要

2人の人がいて,それぞれ街kに行くと,
 Jさんは minJ[k]以上maxJ[k]以下の整数の点数 (最大40点)
 Bさんは minB[k]以上maxB[k]以下の整数の点数 (最大40点)
が手に入る.
2人がそれぞれランダムにm個の都市に訪れるとき,同じ点数を得る各率は幾らか.
都市の数は40以下.

解法

DPでそれぞれ1点の確率,2点の確率,…を全部求める.

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

続きを読む

SRM460 DIV2 MEDIUM - TheFansAndMeetingsDivTwo (この記事を編集する[管理者用])

Source

TopCoder SRM460 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

2人の人がいて,それぞれ街kに行くと,
 Jさんは minJ[k]以上maxJ[k]以下の整数の点数 (最大50点)
 Bさんは minB[k]以上maxB[k]以下の整数の点数 (最大50点)
が手に入る.
2人がそれぞれランダムに1つの都市に訪れるとき,同じ点数を得る各率は幾らか.
都市の数は50以下.

解法

両方が1点の確率,両方が2点の確率,を全部求めて足す.

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

続きを読む

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

Source

TopCoder SRM460 DIV1 EASY (250pt)
Problem Statement
SRM460 参加記録

問題概要

質問にはYES,NOで答える.
同じ質問には同じ答えをする.
questions個の質問を,9回以下したその答えの列が与えられるので,考えうる質問の列の数を求める問題.
各質問を1回はしなくてはいけない.

解法

適当に組み合わせの数を計算する.
DPなどでも計算可能.

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

続きを読む

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

Source

TopCoder SRM460 DIV2 EASY (250pt)
Problem Statement

問題概要

質問にはYES,NOで答える.
同じ質問には同じ答えをする.
何とおりの解答方法があるかを求める問題.

解法

2^質問の種類.

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

続きを読む

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

Source

TopCoder SRM457 DIV1 EASY (250pt)
TopCoder SRM457 DIV2 MEDIUM (500pt)
Problem Statement
SRM457 参加記録

問題概要

一部が壊れて表示されていない時計の表示が与えられる.
それを表従事に直したとき,考えうる時刻の中で辞書順最小のものを求める問題.
形式は23:45 GMT+7のような感じで,時間は00~23で,GMT-0はない.

解法

全部試す.

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

続きを読む

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

Source

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

問題概要

斜め45度傾いた正方形の真ん中から,端に移動するまでのパスの数を求める問題.

解法

適当にDPした.
パスカルの三角形が4つあると思えば簡単に書ける.

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

続きを読む

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

Source

TopCoder SRM249 DIV2 HARD (1100pt)
Problem Statement

問題概要

12個以下の椅子が一列にある.
客はk人グループで来る確率が全部与えられる.
来たら,連続して座れる場所全てに当確率で座る.
最初に座る場所がなくて変える客が出てきた時に,埋まっている椅子の数の期待値を求める問題.

解法

ビットマスクを使ったDP.

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

続きを読む

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

Source

TopCoder SRM248 DIV2 EASY (250pt)
Problem Statement

問題概要

アルファベットからなる文字列が与えられる.
節の数を求める問題.
節は「子音の塊+母音の塊」で子音は無い可能性も有る.

解法

やるだけ.

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

続きを読む

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

Source

TopCoder SRM462 DIV2 HARD (1000pt)
Problem Statement

問題概要

ノード数50以下の有向グラフが与えられる.
スタート場所から各ノードまでの距離,各ノード間の距離,各ノードから終了場所までの距離も与えられる.
また,各ノードを通るごとに距離がさらにノードに設定された数字だけ足される.
高々ノードをN個以下しか通らない最大の距離を求める問題.
Nは100以下.

解法

問題の形式が少し面倒なだけで,普通のDP.

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

続きを読む

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

Source

TopCoder SRM247 DIV2 HARD (1000pt)
Problem Statement

問題概要

2つの文字列間の距離を,
 長さが違うと無限大
 長さが同じだと,違う文字の数
で定義する.
与えられた文字列のうち,1~99までの数字で一番近いものを返す問題.
複数あるなら-1を返す.
数字をどうやってアルファベット表記するかは問題文で定義されている.

解法

やるだけ.

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

続きを読む

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

Source

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

問題概要

母音で,同じ単語内に,左右どちらにも子音がある文字を消す問題.

解法

やるだけ.

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

続きを読む

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

Source

TopCoder SRM461 DIV2 HARD (1000pt)
Problem Statement

問題概要

ゲームセンターなどでプレイヤーネームを入力する感じで文字列を打ちたい.
ぐるぐる回る文字列の中には同じ文字があるかもしれない.
最小で上下に何回移動すれば良いかを求める問題.
打ちたい文字列,ぐるぐる回る文字列はそれぞれ2500文字以下.

解法

何文字目まで打ったか,ぐるぐる回る文字列のどの文字を現在選んでいるか,でメモするDP.
Aって文字を入れたいときは,上下どちらに回して一番近いAの場所に移動するかの2パターンのみを考えることで2500^2の計算量となる.
01-BFSでもOK.(ダイクストラでも解けるが計算時間が怪しいらしい)

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

続きを読む

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

Source

TopCoder SRM286 DIV2 HARD (1000pt)
Problem Statement

問題概要

変数と関数の型の定義が与えられるので,変数か関数の型を求める問題.
関数は,同じ名前でも引数の型が違えば別の型を返すかもしれない.

解法

文字列,構文解析.やるだけ.

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

続きを読む

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

Source

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

問題概要

与えられた文章と,アルファベットの出現頻度が最もよく似ている文章を選ぶ問題.
類似度の関数は問題文中に与えられている.

解法

やるだけ.

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

続きを読む

SRM247 DIV2 MEDIUM - FracCount (この記事を編集する[管理者用])

Source

TopCoder SRM247 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

a/bという分数が与えられるので,それは
 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, ...
という0より大きく1より小さい既約分数を並べた列の何番目に出てくるかを求める問題.
aとbは1000以下で,GCD(a,b)=1であることは保証されている.

解法

やるだけ.

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

続きを読む

SRM249 DIV2 MEDIUM - FieldPairParse (この記事を編集する[管理者用])

Source

TopCoder SRM249 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

表で中身のみ書かれている.
横の要素数は2の倍数として,最も太い枠として縦線を引きたい.
各線の太さは異なっていても良いので,枠の太さの求める問題.

解法

連続する空白を数えるだけ.

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

続きを読む

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

Source

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

問題概要

ビンゴカードと,今まので出た数字が与えられる.
ビンゴは1~75の数字を使う.
ビンゴカードのうち,どのサブセットが全部出ていればいくら貰えると言った規則が与えられる.
次に1個ボールが来たときに,得られる金の増加分の期待値を求める問題.

解法

今まで出た数字を消して,残り1個で揃うものを足していく.

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

続きを読む

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

Source

TopCoder SRM251 DIV2 EASY (250pt)
Problem Statement

問題概要

各州のそれぞれの人が,自分か,対立候補か,どちらに投票したかが与えられる.
最も自分の得票率の低い州を求める問題.
同じ得票率の州が複数あるなら,最も番号の小さい州を返す.

解法

やるだけ.なんだけど,何も対策せずにdoubleで計算すると,丸め誤差で落ちるらしい.

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

続きを読む

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

Source

TopCoder SRM250 DIV2 EASY (250pt)
Problem Statement

問題概要

3本の色の帯から抵抗の値を求める問題.
それぞれの帯は10の位,1の位,指数に対応しており,その値は問題文に表で与えられている.

解法

やるだけ.

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

続きを読む

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

Source

TopCoder SRM249 DIV2 EASY (250pt)
Problem Statement

問題概要

チャットログと人の名前が与えられるので,その人のしゃべった回数を求める問題.
その人のしゃべった発言は
 名前: 内容
の形をしている.

解法

やるだけ.

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

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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