Entries

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

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

SRM445 DIV1 (参加記録) (この記事を編集する[管理者用])

2009年07月24日00時から.

Assignment
275,550,1000の変則セット.

EASY
開く.
座標を縦横2倍にしてから,格子点のみ調べれば良いので全探索.
計算量大丈夫だろうか…?
取り敢えず書いてみる.
計算時間は全然平気っぽい.
サブミット.

MEDIUM
一瞬グレイコードかと思ったけどそんなわけない.
考えても全然わからないので最初の256個ぐらいを書きださせてみる.
コード書いてコンパイルするときに気づいた.問題名の最初がTheだ….
writerたぶん特定.この人の問題セットはなぜかいつも解けない….解ける問題なのに.
取り敢えず,最初の256個書きだしてパターンを探す作戦.
パターンが見えない.
下2桁は適当に循環してたり…しない気がする.
わからない.
残り40分ちょっとになってしまったのでHARDに移ろう.
どうせwriterがあの人なら少し面倒なDPな気がする.

HARD
取り敢えず,何も考えずにマッピングだけするプログラムを書いて,矛盾があるなら0を返す.
後はどうするんだ….
マッピング先で自分が使われている,自分の小文字とか使われているかどうか,といった,
まだマッピングされていないアルファベットの種類をいくつか作って,それの残り個数でDPすれば良い.
書き始める.
思ったよりめんどいぞ?
気づけば残り10分.
DPで勘違いしてて状態が足りてないことに気づいた.
終わった.

Intermission
チャレンジはHARD誰も提出してないし,狙うならMEDIUMなんだろうけど,解法が全く思いつかないのでどうしたもんか.
取り敢えず,256個書きだした結果だけは手元に置いておく.

Challenge
チャレンジできない.MEDIUM皆何やってるのか謎.ちゃんと数学しなければわからない.
途中で,自分のEASYが全探索できてないことに気づいて絶望.
チャレンジしないと0点確定で,どっちみちレートは限界まで落ちるので,チャレンジ爆撃するかどうか悩んだけど止めておいた.

System tests
見なくてもわかるので見てない.

SPOJ 4465 - The Ant [ANTTT] (この記事を編集する[管理者用])

Source
Advancement Spring 2009
SPOJ 4465 [ANTTT]

問題概要
線分が1000個以下与えられる.
蟻は線分の上しか歩けなくて,線分が交わっていれば移れる.
ある線分から,別の線分まで移動できるかどうかを判定する問題.
1つのデータセットでクエリが1000個まで有り得る.

解法
線分の交差判定 + union.
愚直にdoubleで書いたら微妙にTLEだった.
なんか,殆ど同じ問題を昔解いた記憶があるんだけど….

UVa 10001 - Garden of Eden (この記事を編集する[管理者用])

Source
UVa 10001

問題概要
n文字のビット列aから新しいn文字のビット列bを次のように決める.
 b[k] = f(a[k-1 mod n],a[k],a[k+1 mod n])
fとbが与えられたときに,対応するaが存在するかどうかを判定する問題.
nは32以下.

解法
DP.
状態は,固定した場所のaの2文字 * 現在見ている場所のaの2文字 * 現在見ている場所,で状態数は4*4*32程度.

C言語のスパゲッティなコード
#include<stdio.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int cnv,n;
char in[1000];
int dp[4][4][33];

int get(int k){ if(cnv&(1<<k)) return 1; return 0; }

int sol(int last,int nex,int now){
  int i,j,k,res=0;
  if(dp[last][nex][now]>=0) return dp[last][nex][now];

  if(now==n-1){
    k = (nex/2)*4 + last;
    if(get(k)!=in[n-1] || last/2!=nex%2) return dp[last][nex][now]=0;
    return dp[last][nex][now]=1;
  }

  rep(i,2){
    k=nex*2+i;
    if(in[now]!=get(k)) continue;
    res |= sol(last,k%4,now+1);
  }

  return dp[last][nex][now]=res;
}

int main(){
  int i,j,k,l,m;

  while(scanf("%d%d%s",&cnv,&n,in)==3){
    rep(i,4) rep(j,4) rep(k,n) dp[i][j][k]=-1;
    rep(i,n) in[i]-='0';
    k=0; rep(i,4) k |= sol(i,i,0);
    if(k) puts("REACHABLE"); else puts("GARDEN OF EDEN");
  }

  return 0;
}

ZJU 3229 - Shoot the Bullet (この記事を編集する[管理者用])

Source
ZOJ Monthly, July 2009 (2009-07-19)
ZJU 3229

問題概要
射命丸文はn日間かけて,幻想郷に住むm人の可愛い少女の写真をできるだけ多く撮りたい.
m人それぞれに撮らなければいけない最小枚数が定められている.
また毎日,ターゲットは(複数)定められていて,それぞれのターゲットを撮る枚数の最小値,最大値が定まっている.
またそれぞれの日で撮ることのできる最大合計枚数も定まっている.
制約を全て満たすような撮り方のうち,最も多くの写真を撮る方法を求める問題(該当する取り方が複数あればどれか1つ求めればよい).
nは365以下,mは1000以下.

解法
m人のそれぞれ撮らなければいけない最小枚数を撮ることができるかどうかの判定は最大流でできる.
後は,撮れるだけ適当に撮ればOK.

ZJU 3230 - Solving the Problems (この記事を編集する[管理者用])

Source
ZOJ Monthly, July 2009 (2009-07-19)
ZJU 3230

問題概要
初期レベルpと,n種類の問題が与えられる.
問題には,解くのに必要なレベル,解いたら上昇するレベルが定められている.
1日に1問まで解ける.
m日後の最高レベルを求める問題.
n, mは100000以下.

解法
解ける問題の中で,一番レベルが上がる問題を解けばよい.
ヒープなどのデータ構造を用いる.

ZJU 3222 - Coverage (この記事を編集する[管理者用])

Source
ZOJ Monthly, July 2009 (2009-07-19)
ZJU 3222

問題概要
無限大の大きさのグリッドの100×100以下の部分以外は全部0で埋め尽くされている.
100×100以下の部分には整数が入っている.
縦X,横Yの大きさの長方形を2つの長方形に分割して,それぞれを重なっても良いのでグリッドの上に乗せる.
回転してはいけない.
長方形の重なっている部分の数字の和を最大化する問題.
重なっている部分は重複して数える.

解法
適当にDPっぽいこと(和を先に計算しておく)をすれば,後は全ての長方形の分け方とどこに置くかを全て調べてお終い.

UVa 11635 - Hotel booking (この記事を編集する[管理者用])

Source
University of Ulm Local Contest (2009-07-18)
UVa 11635

問題概要
ノード10000以下,枝100000以下のグラフが与えられる.各枝には通過するのにかかる時間(分)が与えられる.
また,ホテルがあるノードが与えられる.ホテルの場所は100か所以下.
1日に600分だけしか行動できず,行動後はホテルに泊まらなくてはいけない.
ノード1からノードnに行くためには,最小で何回ホテルに宿泊すればよいかを求める問題.
たどり着けないならそれを指摘する.

解法
ホテルのあるノード(と初期地点,目的地点)だけでグラフを作って,それぞれのホテル間を1日で移動できるかどうかで枝を張る.
後はBFSすればお終い.
それぞれのホテル間を1日で移動できるかどうかを調べるのは,もともとの大きなグラフでダイクストラをホテルの個数回ぐらいやれば良い.

UVa 11634 - Generate random numbers (この記事を編集する[管理者用])

Source
University of Ulm Local Contest (2009-07-18)
UVa 11634

問題概要
4ケタの数字(3桁以下なら頭に0をつけて4ケタとみなす) x[0]が与えられたとき,
 x[k]^2を8ケタの数字と見て,真ん中の4ケタをとってきてx[k+1]とする
という操作を繰り返した時,数列xに現れる数字は何種類あるかを求める問題.

解法
やるだけ.ループした(同じ数字が2度現れた)ら終了.

UVa 11633 - Food portion size (この記事を編集する[管理者用])

Source
University of Ulm Local Contest (2009-07-18)
UVa 11633

問題概要
学食で1個の食べ物の大きさSをどのように設定しようかという問題.
n人の人が食べる量y_iがそれぞれわかっていて,Sが大きいと食べきれない分無駄になるし,Sが小さいと何個も買わなくてはいけない.
最大で1人3つまでしか買えないという制約で,a * 無駄にする量 + b * 買いに来る回数を最小化しましょう.
最小値を求める問題.

解法
端を全て調べる系.
調べるべき値は,y_i / 1, y_i / 2, y_i / 3.

UVa 11632 - Elias gamma coding (この記事を編集する[管理者用])

Source
University of Ulm Local Contest (2009-07-18)
UVa 11632

問題概要
問題で定義されている符号化を最適化して最短の長さの符号にしましょうという問題.

解法
DP.

UVa 11631 - Dark roads (この記事を編集する[管理者用])

Source
University of Ulm Local Contest (2009-07-18)
UVa 11631

問題概要
連結なグラフが入力.ノード数200000以下,枝数200000以下,枝には長さが定義されている.
現在は,全ての道路にイルミネーションをつけているが,もったいないので節約したい.
でも,夜は危ないので,イルミネーションが付いている道路だけをとって全ての都市を行き来できるようにする.
イルミネーションを消すことができる最長の長さを求める問題.

解法
最小全域木.

UVa 11629 - Ballot evaluation (この記事を編集する[管理者用])

Source
University of Ulm Local Contest (2009-07-18)
UVa 11629

問題概要
各文字列にdoubleの値が割り当てられる.
その後,
 文字列1 + 文字列2 + ... + 文字列n comp 実数
という式が与えられるので,それは正しいかどうかを判定する問題.
compは等号または不等号の類.

解法
文字列処理.やるだけ.

UVa 11628 - Another lottery (この記事を編集する[管理者用])

Source
University of Ulm Local Contest (2009-07-18)
UVa 11628

問題概要
30回以下宝くじが発売される.
i回目の宝くじの賞金は2^iで,売られた籤からランダムに1つ当たりが選ばれる.
10000人以下の人が勝ったそれぞれの宝籤の枚数が与えられるので,i人目の人が最も多くの額が当たった確率をそれぞれ求める問題.
各宝くじは1枚以上10^9以下の売り上げがある.

解法
最後に当たった人が勝者.
なので,最後の宝くじで自分が買った枚数 / 全員で買った枚数が答え.

SPOJ 4483 - Roads Repair [MROADS] (この記事を編集する[管理者用])

Source
COI 2006
SPOJ 4483 [MROADS]

問題概要
ノード数100000以下の根付き木が与えられる.
各枝には,現在の時間距離と最小の時間距離が与えられる.
コスト1000000が与えられ,その分だけ枝の時間距離を減らすことができる.
根から最も時間距離の遠いノードまでの時間距離を最小化する問題.

解法
二分探索.
最も遠いノードまでの時間距離を決めつければ,コストを費やす枝は根に近い方からgreedyに選べば良いので,DFSで必要コストを求めることができる.

SPOJ 4485 - MobiZone vs VinaGone [MOBIVINA] (この記事を編集する[管理者用])

Source
SPOJ 4485 [MOBIVINA]

問題概要
250人以下の人が2つの電話会社の中からどちらかを選択する.
それぞれの人が,それぞれの電話会社にしたときのコストと,
それぞれ2人の人が違う電話会社にしたときに必要なコストが与えられるので,コストの和を最小化する問題.

解法
グラフの最小カットに帰着できるので,フローを流す.

SPOJ 4343 - Empty Boxes [EBOXES] (この記事を編集する[管理者用])

Source
SPOJ 4343 [EBOXES]

問題概要
N個の空の箱(Type1)がある.
Tターンだけ次の操作を行う.
 現在tターン目だとして何個か適当なType(t+1)の箱を選んで,それぞれの箱の中にType(t+2)の箱をK個入れる.
最終的な空の箱の数Eが与えられるので,箱の総数を求める問題.

解法
少し数学すれば閉じた式が得られる.

SPOJ 4206 - Fast Maximum Matching [MATCHING] (この記事を編集する[管理者用])

Source
SPOJ 4206 [MATCHING]

問題概要
2部グラフの最大マッチングを求める問題.
左右のノードはそれぞれ50000以下,枝は150000以下.

解法
最大流に帰着させてSPOJ 4110 [FASTFLOW]と同じコードを使いまわしてもギリギリ通った.

SPOJ 4525 - Digger Octaves [UCI2009D] (この記事を編集する[管理者用])

Source
SPOJ 4525 [UCI2009D]

問題概要
8*8以下のグリッドのいくつかのマスにダイヤモンドが落ちている.
1ターンに上下左右に動けるとして,8ターンで8個ダイヤモンドがとれるようなダイヤモンドの集合の数を求める問題.

解法
動き方は高々8*8*4^7しかないので全て試す.
違う動き方でも同じダイヤモンドの集合を拾ってしまうので重複して数えないように注意する.

SPOJ 4523 - Binomial Coefficients [UCI2009B] (この記事を編集する[管理者用])

Source
SPOJ 4523 [UCI2009B]

問題概要
0以上1000以下のNが与えられるので(A+B)^Nを展開した式を求める問題.
ただし係数は素因数分解した形で表示する.

解法
やるだけ.

SPOJ 4580 - ABCDEF [ABCDEF] (この記事を編集する[管理者用])

Source
SPOJ 4580 [ABCDEF]

問題概要
100個以下の-30000以上30000以下の整数の集合が与えられる.
a, b, c, d, e, fはその集合の元(ただしdは0でない)で
 (ab+c)/d - e = f
を満たす組み合わせの数を求める問題.

解法
式を変形して
 ab+c = d(e+f)
を満たすもの(d!=0)の数を求める.
両辺3変数なので,両辺の割り当て方はそれぞれn^3通りしかない.

SPOJ 339 - Recursive Sequence [SEQ] (この記事を編集する[管理者用])

Source
IV Podlasian Contest in Team Programming
SPOJ 339 [SEQ]

問題概要
数列aを,直前のk項の線形結合で定めていく.
その係数と,初期値が与えられたとき,a[n] mod 10^9を求める問題.
与えられる数字は全て10^9以下.ただしkは10以下.

解法
有名問題.数列の漸化式をベクトル形式で書いて,行列の冪を求める問題に帰着させる.

Aizu 0540 - Amidakuji (あみだくじ) (この記事を編集する[管理者用])

Source
第8回 日本情報オリンピック 本選 2009年02月08日
Aizu 0540

問題概要
問題文が日本語なので省略.

解法
最初に,一番上の左からi番目のスコアを全部求めると同時に,各横枝でスワップされるものを覚えておく.
後は,全ての横枝に対して,それを消した時のスコアの差を求めて一番小さいもの(もしくは0)をもともとのスコアに足す.

Aizu 0536 - Shuffle (シャッフル) (この記事を編集する[管理者用])

Source
第8回 日本情報オリンピック 予選5 2008年12月14日
Aizu 0536

問題概要
問題文が日本語なので省略.

解法
少し面倒なだけの実装問題.
データは連続する区間で持ちながらシミュレーションする.
O(m^2).

Aizu 0530 - Pyon-Pyon River Crossing (ぴょんぴょん川渡り) (この記事を編集する[管理者用])

Source
第7回 日本情報オリンピック 2008年02月10日
Aizu 0530

問題概要
問題文が日本語なので省略.

解法
DP.

Aizu 0526 - Boat Travel (船旅) (この記事を編集する[管理者用])

Source
第7回 日本情報オリンピック 予選 2007年12月16日
Aizu 0526

問題概要
問題文が日本語なので省略.

解法
グラフを更新しながら,客の注文がきたときにダイクストラするだけ.

Aizu 0524 - Searching Constellation (星座探し) (この記事を編集する[管理者用])

Source
第7回 日本情報オリンピック 予選 2007年12月16日
Aizu 0524

問題概要
問題文が日本語なので省略.

解法
星座の1つ目の星が,夜空の写真のどの星に対応するのかを全探索する.
夜空の写真の星の座標はハッシュを計算しておくとか,ある座標に星が存在するかどうかを簡単にチェックできるようにしておくと良い.

Aizu 1162 - Discrete Speed (離散的速度) (この記事を編集する[管理者用])

Source
ACM/ICPC Japan Domestic 2009
Aizu 1162

問題概要
日本語なので略.

解法
各ノードに(今いる都市×次にいけない都市×現在のスピード)という情報を付加してグラフを作ってダイクストラする.
ノード数の最大数は30*30*30程度.

Aizu 1106 - Factorization of Quadratic Formula (この記事を編集する[管理者用])

Source
ACM/ICPC Japan Domestic 1999
Aizu 1106

問題概要
a,b,cが与えられるので
 ax^2 + bx + c = (px + q)(rx + s)
と整数の範囲で因数分解する問題.
できないならそれを指摘する.
gcd(a,b,c)=1,a,b,cはそれぞれ絶対値10000以下,aは正.

解法
値が小さいので愚直に全探索すればOK.
ただし,pとrはaの約数,qとsはcの約数であることぐらいの枝刈りは行う.
cが0の場合は例外処理する.

Aizu 1105 - Unable Count (この記事を編集する[管理者用])

Source
ACM/ICPC Japan Domestic 1999
Aizu 1105

問題概要
n, a, bは1以上100万以下の整数.
1からnまでの整数の中で
 a*i + b*j
の形で書けないものの個数を求める問題.ただしiとjは非負整数.

解法
DPでa*i + b*jの形で書けるものを全部求める.

Aizu 1104 - Where's Your Robot? (この記事を編集する[管理者用])

Source
ACM/ICPC Japan Domestic 1999
Aizu 1104

問題概要
前,後ろにkマス進む,左右を向くというコマンド列が与えられるので,最終的なロボットの位置を求める問題.
周りは壁に囲まれていて,壁に向かって動くコマンドが与えられたら壁際までしか移動しない.

解法
シミュレーションする.

Appendix

Recent Articles

ブログ内検索

Ads


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