Entries

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

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

UVa 10251 - Min-Max Cake (この記事を編集する[管理者用])

Source
World Final Warm-up Contest
UVa 10251

問題概要
上から見ると,円形または正方形のケーキがある.
そのケーキの上の1点に花が乗っている.
1回だけ直線でケーキを切って2つにわけるとして,花が含まれている方の体積を最小化したい.
体積を求める問題.

解法
数学.
円の場合,体積最小の切り方は簡単にわかる.
正方形の場合は一瞬難しいかと思うんだけど,良く考えて,
切り口のちょうど真ん中の点に花がのっていなければならないことに気づけば,暗算で求まるぐらい簡単.

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

#define EPS 1e-10

int main(){
  double r,h,dx,dy,res,th;
  int i,size,mode;
  char in[999];

  gets(in); size=atoi(in);
  while(size--){
    gets(in);
    mode = sscanf(in,"%lf%lf%lf%lf",&r,&h,&dx,&dy);
    if(mode==3){
      th = 2*atan2(sqrt(r*r-dx*dx),dx);
      res = (th-sin(th))/2*r*r;
    } else
      res = (r/2-dx)*(r/2-dy)*2;

    printf("%.3lf\n",res*h+EPS);
  }

  return 0;
}

ACM-ICPC Japan Domestic Warm Up II (参加記録) (この記事を編集する[管理者用])

2009年06月28日13時から3時間,6問.
[ Link ]

起床
13時10分.寝坊した…orz
参加するかどうか微妙になったけど,取り敢えず裏で解いてみよう.

A. Sleeping Cats
どこの福縞軒だよ!
やるだけ.書いた.

B. Monster Factory
うーん,文字だけ見てなぞれば解ける…のかなぁ?
まぁ,よくわからないし,シミュレーションも線形オーダーでできるし,シミュレーションでいいか.
書いた.

C. Midnight Teatime
DPするだけ.
ノード数的には全探索でも可ってことなんだろうけど.
書いた.

D. Dr. Nakamura's Lab.
状態数は…64^4 + αか.メモリ的にちょっときつい(100^4では駄目).なんとかなる範囲ではあるけど.
どうせ,コンテナは押したら止まらないので,疎なんだろうけど.
保留.

E. Frisbee Dogs
幾何シミュレーション.
二次方程式解きながらシミュレーションするだけ.
書いた.

F. Chocolate with Heart Marks
どうせ探索何だろうけど…,うまく探索する方法が思いつかない.
DPとかでも解けるかもとか思ったけど,それもきつそうだ.
保留.

D. Dr. Nakamura's Lab.
こんな方法でも良いかも,とかいろいろ考えたけど,結構トリッキーなケースがちゃんと作れる.
てか,コンテナ3つしかないし,メモなんか付けずに全探索DFSとかでも良いんじゃないか?
毎回,出口,コンテナの上下左右のどこかに移動して,コンテナの横だったら押す.
書いてみた.TLEが不安.まあ,いいか.送ってみよう.枝刈りも何もしていない.
2.9秒で通った.通ったけども遅すぎる….

送信
Dを送っちゃったので,AからEまで全部送ってみる.
全部一発AC.すんなり通るとか自分らしくない.

F. Chocolate with Heart Marks
残り70分ぐらい.
10分ぐらい考えて,良い探索方法思いつかなかったのと,他にやることがあったので放棄.

送ったコードは続きにおいておく.

続きを読む

Aizu 0516 - Maximum Sum (最大の和) (この記事を編集する[管理者用])

Source
第7回 日本情報オリンピック本選問題 (2007年02月12日)
Aizu 0516

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

解法
やるだけ.
ソースコード貼り付けテストその2.

C言語によるスパゲッティなソース
#include<stdio.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int main(){
  int i,k,n,res,sum,d[100000];
  for(;;){
    scanf("%d%d",&n,&k); if(!n)break;
    rep(i,n) scanf("%d",d+i);
    sum=0; rep(i,k) sum+=d[i]; res=sum;
    REP(i,k,n){
      sum+=d[i]-d[i-k];
      if(res<sum) res=sum;
    }
    printf("%d\n",res);
  }
  return 0;
}

SRM443 DIV1 (この記事を編集する[管理者用])

2009年06月24日10時から.

ソースコードを本文に張り付けるテストをしてみる.
色付けとかはさっき5分で適当に書いたコードに出力させてみた.

Links
Match Overview
Match Editorial
Summary of Japanese (otinn.com)
参加記録 (blog)

2次元平面.互いに共通点を持たない円周が50個以下与えられる.
始点と終点が与えられるので,始点から終点まで連続的に移動する場合,跨がなければならない円周の最小数を求める問題.

片方のみを含む円の数を返せばよい.

A個の0とB個の1がある.
1ターンに厳密にK個の数を選んで0と1を反転させる.
最小何ターンで全て1になるかを求める問題.不可能なら-1を返す.
A, B, Kはそれぞれ100000以下.

解法は2通り.
1つ目はBFSする.
ただし普通にやるとTLEなので,状態をmod 2で分けておくと,枝は連続した区間にはられるのでそれを利用する.

2つ目はiターンで可能かどうかを逐次判定していく方法.
判定方法は,A個フリップするとして,残りのフリップ回数を無駄に消費できるかどうかを判定する.
ソースは次の通り.
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class BinaryFlips {
public:
int minimalMoves(int A, int B, int K) {
  long long i,rest,use;
  rep(i,A+B+1){
    rest=i*K-A;
    use=((i/2)*B+((i-1)/2)*A)*2;
    if(rest>=0 && rest%2==0 && rest<=use) return i;
  }
  return -1;
}
iターン行うとしてフリップする合計回数はi*K.
もともと0だったものをフリップするものとして,残りのフリップ回数rest=i*K-A.
B枚それぞれfloor(i/2)回までひっくり返して元に戻すということを行えるし,
A枚は,最初に1回ひっくり返したとしてfloor((i-1)/2)回までひっくり返して元に戻せる.
なので,無駄に消費できるフリップの回数use=( (i/2)*B+((i-1)/2)*A )*2.
rest>=0 かつ rest%2=0 かつ rest<=useであれば全て1にできる.

曲のリストが与えられるので,続けてa分以上,b分以下聞く方法は何通りあるかを求める問題.
ただし,それぞれ曲は高々9種類のカテゴリに属し,長さは1以上9分以下で整数*分.
あるカテゴリの曲の次に,聞けるカテゴリが制限されている.
aとbは大きい.

遷移行列作ってべき乗する.
参加記録で書いた方法でもできると思うけど,そんな面倒なことするまでもなく,行列を1回かけたら1分だけ時が進むとしても作れる.

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

2009年06月24日10時から.

開始前
11時からだと勘違いしてて寝るのが遅くなった.
まあ,この時間帯のSRMは参加者少ないので,直前登録でも良いだろうと踏んで寝る.
6時半就寝,9時45分起床.眠い.とりあえず眠い.
予想通り登録はできた.目は覚めてない.なんで最近プラクティスルームが1個分しかないの?

Assignment
300-600-1000の変則セット.
1000はいつもどおりの難易度として,300と600が面倒な問題なんだと予想.
 → 今回は完全に外れた.

Easy
半分寝てる状態で問題オープン.
なんか取り敢えず絵を眺めてうとうとしてる.
駄目だよ!問題読まなきゃ!
読んだ.
…,2点の片方を内部に含んでいて,片方が外部の円の数が答えなんじゃ….
 → 300なんだし,そんな簡単なわけないじゃん!
 → …,いや,たぶん証明できるぞ.
書いた.寝ぼけててx2とx1を書き間違える.直した.送った.
皆瞬殺してる.300なのに,やっぱりこんなのでよいのか.

Medium
状態数が高々200000.
 → BFSでいけるに決まっている,という良くわからない思考回路が働く.
3行ぐらいプログラム書いたところで,枝数が200000*100000ぐらいになることに気づいた.
いや,でも枝刈ればいけそうな気もするぞ….
いや,次数が10000とかだったら1ステップでも苦しいのにそれを10ステップしなければいけない…?
グリーディーでもいけるんじゃないか?
閃いた!
i回スワップすると,合計でi*k文字スワップすることになる.
A個はスワップするとして,残りのスワップ回数を無駄に消費できるかどうかだけ調べれば良いんだ!
とても簡単なプログラムなはずなのに,寝ぼけてふわふわしている頭で,理論的になかなか書けない.
なんとか書けた.超簡単.寝ぼけてなければ後数分早く書けたはず….
サブミット.
サマリーを見ると,medium提出,自分で2人目!
なんで,皆こんなに梃子摺っているのだろう.不安になってきた.
まぁ,点数的にhardを先に解いているんだと思って納得.

Hard
与えられる行列の行と列が直感的に捕らえると逆になっているように見える.
 → これはチャレンジポイントか!?
 → 逆向きにたどれば同じ答えが出てくるのでチャレンジできない.
 → そもそも自分の部屋ではhard提出者0でした.
で,問題自体は,どうみても遷移行列作ってべきを計算する問題にしか見えない.
てか,この前のWaterlooコンテスト問題Cの類題だ.
最後の曲のカテゴリと長さ mod 10を状態に,その区間の長さに始めて到着した時点だけに着目すれば遷移行列が作れる.
行列サイズは100でちょうど何とかなりそう.
書き出すと,いろいろなところが厄介なのに気づく.
ある時間以下のものを全て求めなければいけない.
 → 行列n乗だけじゃなくて,I+A+A^2+...+A^nとかいうのも必要.
 → DPして行列をいじった後またDPしなければいけない.
気づけば残り5分とかになってた.
諦めた.

Challenge
easyは流石に間違えないだろうし,mediumを見ていく.
あれ,自分以外全員BFSしてるぞ!?
 → 適当につつけば落ちるんじゃないのか?
 → 教えてPetr先生ー.
 → Petr先生がBFSしてる….落ちるんだったら僕のほうだ…orz
取り敢えず,10分ぐらい掛けてBFSの解法を理解する.
なるほどー,状態をmod 2で分けておけば,張られる枝は連続な区間に張られるので,まだ到達してない状態の列挙が簡単にできる.
それでO(n+m)ぐらいで結局解けちゃうって寸法か.賢すぎる.
で,チャレンジ自体は何もできないまま終了.

System tests
何事もなく通った.良かった.
頭が(良い方向に)おかしいターゲットのwataとかいう人がいなければ,medium最速だったみたい.惜しい….
レートは前回暴落した分,少し取り戻した.

UVa 10257 - Dick and Jane (この記事を編集する[管理者用])

Source
UVa 10257

問題概要
簡単にいえば,非負整数s,p,y,jが与えられるので
 a = b + s または a = b + s + 1
 b = c + p または b = c + p + 1
 a = c + y または a = c + y + 1
a + b + c = 12 + j
を満たす非負整数a,b,cを求める問題.

解法
やるだけ.
全通り試して矛盾が無いものを出力しても良いし,場合分けでも良い.

Aizu 0508 - String With Rings (この記事を編集する[管理者用])

Source
第5回 日本情報オリンピック本選問題 (2006年02月12日)
Aizu 0508

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

解法
問題文を焼きなおすと,無向グラフで同じ頂点を高々1回通る,最も長いパスの長さを求める問題.
DFSで全探索で通った.

Aizu 0507 - Square (この記事を編集する[管理者用])

Source
第5回 日本情報オリンピック本選問題 (2006年02月12日)
Aizu 0507

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

解法
実装するだけ.再帰.

Aizu 0506 - String (この記事を編集する[管理者用])

Source
第5回 日本情報オリンピック本選問題 (2006年02月12日)
Aizu 0506

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

解法
実装するだけ.

Aizu 0505 - Questionnaire (この記事を編集する[管理者用])

Source
第5回 日本情報オリンピック本選問題 (2006年02月12日)
Aizu 0505

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

解法
ソートするだけ.

UVa 10290 - {Sum+=i++} to Reach N (この記事を編集する[管理者用])

Source
Math Lovers' Contest
UVa 10290

問題概要
9*10^14以下の正整数nが与えられるので,それを連続する正整数の和
 a + (a+1) + ... + b
に分割する方法は何通りあるかを求める問題.

解法
昔はタイムリミットが120秒ぐらいとかとても長かったので,愚直な方法でも通ったのだけど,最近3秒に修正された.
 2n = (b+a)(b-a+1)
であるので,要するに2nを2つの積に分ける方法をカウントすれば良い.ただし,
 (b+a) + (b-a+1) = 2b + 1
なので,2つの和は奇数となるもののみをカウントする.他に制約はない.

UVa 10203 - Snow Clearing (この記事を編集する[管理者用])

Source
UVa 10203

問題概要
道路上の雪を除去するのに必要な最小時間を求める問題.
初期地点と,道路(線分)の両端が与えられる.道路は100個以下.
道路の雪を除去するためには,その道路上を時速20kmで走れば良い.
除去し終わった道路は時速50kmで走れる.
道路は両側に走ることができるので,両方の向きに走らないと雪は除去できない.
道路の交差点や,道路の終点では自由に向きを変えることができる.
差表の単位はメートル.道路の数は100以下.初期地点から全ての道路に移動できることが保証されている.
出力形式は時間:分.

解法
結局,両向きに走らなければならないので,全ての道路を2方向に1回ずつ走ればOK.
なので, 道路の両向きの総距離/(20km/h) が答え.

UVa 11087 - Divisibility Testing (この記事を編集する[管理者用])

Source
IIUPC 2006
UVa 11087

問題概要
要素数100000以下の整数の配列が与えられる.
その中から別々の要素を2つ選んで,その和がkで割り切れるようになる2つ組はいくつあるか.
別々の要素をとってきたとしても,同じ数字同士のペアは重複して数えてはいけない.
kは500以下.

解法
最初に配列に2つ以上入っているものは,それを2つ選んだときにkで割り切れるなら答えに1を足していって,除去しておく.
(3つ以上入っていても1個分しか足してはいけないことに注意)
後は,配列を全てkで割った余りに置き換えて,
 iとなる要素の数 * k-iとなる要素の数
みたいなのを足していくだけ.
答えは32bit整数で扱えないことに注意.

PKU 2384 - Harder Sokoban Problem (この記事を編集する[管理者用])

Source
Northeastern Europe 2004, Far-Eastern Subregion
PKU 2384
TJU 2370

問題概要
箱が1個の倉庫番を考える.
マップの形状と,箱を運ぶ最終地点のみが与えられるので,最初の人物の位置と箱の位置を自由に決めて,最小移動回数を最大化したい.
解くために必要な移動回数の最大値を求める問題.
マップのサイズは25*25以下.

解法
状態数は25^4 (40万以下)しかない.
答えの盤面(箱が目的地)を全て列挙して,それを始点に倉庫番ゲームを逆向きにBFS辿る.

PKU 2380 - Sales Report (この記事を編集する[管理者用])

Source
ACM/ICPC Northeastern Europe 2004, Far-Eastern Subregion
PKU 2380
TJU 2366

問題概要
列ID,行ID,数値の3つ組が500000個以下与えられる.
各セルは対応する入力の数値の和となるような表を出力する問題.
IDの値や数値は10^9以下,各セルの値は2^31未満であることが保証されている.
セルの数は10^8以下であることが保証されている.

解法
適当に,列ID,行IDを圧縮して表を作って足す.
PKUだとタイムリミットは3秒.
GCCだとTLEだったけど,Cだと1300msぐらいで通った(scanfおよびprintf使用).

PKU 3171 - Cleaning Shifts (この記事を編集する[管理者用])

Source
USACO 2005 December Silver
PKU 3171

問題概要
N匹の牛がいて,それぞれ,雇うとある金額である区間の掃除をしてくれる.
掃除したい区間[M,E]が与えられるので,全ての区間を少なくても1匹の牛が掃除するように雇う.
コストを最小化する問題.
Nは10000以下,区間の幅は86400以下,コストは64bit整数で計算すればOKな範囲.

解法
基本的にはDP.
N匹の牛を区間の最初の値でソートして,小さい方から順番に処理していく.
で,DPでメモしておくことは,ある場所まで全て掃除している状態でのコストの最小値で,DPの更新するとき,その配列のある場所より後ろの最小値が必要となる.
何も考えずにループを回すとO(N * 区間の幅)でTLEになるので,DPテーブルの管理のデータ構造としてsegment tree (range minimum query)を使う.

UVa 10092 - The Problem with the Problem Setter (この記事を編集する[管理者用])

Source
UVa 10092

問題概要
プログラミングコンテスト用の問題のストックがn問ある.
それぞれカテゴライズされていて,1つ以上のカテゴリに属している.
プログラミングコンテストを開くにあたって,それぞれのカテゴリで出題する問題数が決まっている.
複数のカテゴリに属するものは,どれか1つのカテゴリの問題として出題することができる.
では,それぞれのカテゴリの問題をストックから選んでください,という問題.
不可能ならばそれを指摘する.
nは1000以下,カテゴリの種類数は20以下,コンテストの使う問題の合計は100問以下.

解法
典型的な最大流の問題.

PKU 2500 - Pia's Party (この記事を編集する[管理者用])

Source
TUD Programming Contest 2005 (Training Session), Darmstadt, Germany
PKU 2500

問題概要
直径dの円周上に等間隔にn点がある.点は0からn-1までの番号をつけられている.
その中のc個の点のうち4か所に拡声器を置く.
c個の点の番号は
 (g*k) mod n, k=0,1,...,c-1
で与えられる(gとnは互いに素).
拡声器を置かれた4点で囲まれる四角形の面積を最大化したい.
面積を求める問題.
nは10^9以下,cは1000以下.

解法
まず,四角形の対角線(2点)を決めつける.
後は,2点に挟まれる点の中で最も遠い点(三角形の高さが高くなる点)をバイナリサーチで探す.
これだとO(c^2 log c)ぐらい.
僕はバイナリサーチをせずに,尺取りメソッドで探した.これだとO(c^2).

PKU 3573 - I18n (この記事を編集する[管理者用])

Source
ACM/ICPC Europe - Northeastern Europe - 2007/2008 (Northeastern Europe 2007)
LiveArchive 4051
PKU 3573

問題概要
文字列が与えられるけど,ときどき省略された形の単語がある.
省略されている単語を元の単語に戻して文章を全て出力する問題.
省略形はI18nみたいに[アルファベット1][数字][アルファベット2]な形をしていて,それは以前出てきた単語の真ん中[数字]文字だけ省略したもの.
単語はアルファベット以外の文字を区切りとして,アルファベットの連続で,全部小文字,最初だけ大文字,全部大文字の3種類しか登場しない.
単語は大文字小文字区別せずに同じ単語と思って,省略系が3パターンのどれに属するかは,[アルファベット1],[アルファベット2]が大文字か小文字かで区別する.
ただし,以前に該当する単語が存在しない場合,複数あって何の省略形かわからない場合は,置き換えずに省略形のまま出力する.
入力は1000行以下,各行80文字以下.単語は32文字以下のものしかでてこない.

解法
文字列処理,やるだけ.
26*26*33ぐらいの配列を用意して,先頭のアルファベット,最後のアルファベット,文字列の長さごとに出てきた単語の位置を覚えておくと簡単に処理できると思う.

PKU 2558 - Genetic Code (この記事を編集する[管理者用])

Source
University of Ulm Local Contest 2003
PKU 2558
SPOJ 1804 [GENETIC]

問題概要
長さnでN,O,Pの3文字からなる文字列のうちで,全ての隣り合うsubstringが等しくないものを1つ求める問題.
例えば,NOPNPNOはNPとNPが等しい隣り合うsubstringなので駄目.
nは5000以下.存在しないならそれを指摘する.

解法
長さ5000のを1回求めたら,後は,それから長さnだけ切り取って表示すれば良い.
5000のを求めるのは,なんか普通にDFSしたらすぐ求まった.

PKU 2005 - Blackjack (この記事を編集する[管理者用])

Source
ACM/ICPC North America - Rocky Mountain - 2004/2005 (Rocky Mountain 2004)
LiveArchive 3050
PKU 2005

問題概要
トランプを52枚をnセット使ってブラックジャックをする.
といっても,2枚ずつ配るだけで,それ以上のカードをもらうことはできない.
ディーラーのカード1枚とプレイヤーのカード2枚がわかっているので,プレイヤーの勝率を計算する問題.
ドローは負け.

解法
やるだけ.

Aizu 0040 - Affine Cipher (この記事を編集する[管理者用])

Source
パソコン甲子園2004 (PC Koshien 2004)
Aizu 0040

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

解法
全ての可能なα,βについて実際に全て復号してみてthatかthisが含まれていればそれを出力する.

PKU 2425 - Jersey Politics (この記事を編集する[管理者用])

Source
USACO 2005 February Gold
PKU 2425

問題概要
3*k個の街があって,それぞれ街の人口は1000人で,それぞれの街に自分を支持してくれる人が何人いるかが与えられる.
では,k個ずつ3つのグループに街を分割して,2つ以上のグループで過半数の人が自分を支持してくれている状態にしたい.
そのような分け方を1つ求める問題.答えは存在することが保証されている.
kは60以下.

解法
グループの1つは何でも問題ないので,支持してくれる人が少ない順にk個選んで,それらは排除して2つにわけることを考える.
DPで過半数を超える組み合わせのうち最も小さいものを求めて,それと残りに分ければ良い.
普通にDPするとTLE.どうせ素だろうと適当に枝を刈ると500msぐらいで通った(TLは1000ms).
良く考えると,kは60以下なので,long longでビットに埋め込めて計算量はO(k*(500k))ぐらいになって普通に通る.

PKU 1091 - 跳蚤 (この記事を編集する[管理者用])

Source
HNOI 2001
PKU 1091

問題概要
ノミたちがたくさん住んでいる町のバラエティTV番組の話.
N+1枚のカードが与えられ,そのうちN枚は1以上M以下の自然数,最後の1枚はMが書かれている.
無限に長い線の上を,ノミがジャンプして移動する.
ジャンプするのはカードの中から1枚選んで,それに書かれている数字の距離だけを左右どちらかにジャンプする.
1枚のカードで何回でもジャンプできて,ジャンプする順番も自由.
ゲームの目的は,最初の位置から左に1マスの位置に辿り着くこと.
さて,NとMが与えられたとき,目的が達成できるカードのパターンは何通りあるかを求める問題.
カードには順番があって,順序が違うと別の組と数える.
Nは15以下,Mは10^8以下.

解法
包除原理.
辿り着けるカードのパターンはN+1個の自然数のGCDが1であるとき.
Mを素因数分解してでてくる素数を列挙して,k個(p1,...pk)だったとする.
M^NからGCDがpiの倍数のもの((floor(m/pi))^n)を引いて,GCDがpi*pjの倍数のものを引いて…といった感じ.
多倍長で計算しないとダメなはず.

PKU 2126 - Factoring a Polynomial (この記事を編集する[管理者用])

Source
ACM/ICPC Northeastern Europe 2003, Northern Subregion
PKU 2126
TJU 2706

問題概要
次数20以下の整数係数多項式が与えられる.
その多項式が実数の範囲で,因数分解可能かどうかを判定する問題.

解法
全ての多項式は,1次と2次の多項式の積で書けるので,…(1)
3次以上は因数分解可能,1次以下は不可能.
2次の多項式は,判別式を計算して実数解をもてば因数分解可能.
(1)は,実数解をもてば,その分は1次多項式で,虚数解の部分は共役のと含めて2次多項式というやつ.

Aizu 0190 - Eleven Puzzle (この記事を編集する[管理者用])

Source
パソコン甲子園2008 (PC Koshien 2008)
Aizu 0190

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

解法
流石に何も考えずに全探索するとつらいので枝刈りする.
1から11までのピースの現在の位置と正しい位置のマンハッタン距離の和だけはターン数がかかるので,
それを考えて20ターン以内に解けないなら枝刈り,として後は普通のBFSで通った.

Aizu 0502 - Dice (この記事を編集する[管理者用])

Source
日本情報オリンピック予選 (2006年01月15日)
Aizu 0502

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

解法
ダイスを転がすのをシミュレーションすれば良い.
さいころライブラリとか作っているとコピペで終了.

PKU 1970 - The Game (この記事を編集する[管理者用])

Source
Tehran Sharif 2004 Preliminary (Tehran 2004 Iran Nationwide)
PKU 1970
TJU 1312

問題概要
19*19の盤面で行う5目並べ.
ただし,同時に6個以上連続して並べても勝ちにならない.
盤面が与えられるので,勝者と,5つ並んでいる石のうち,最も左,その生で最も上の石の座標を出力する問題.
まだ終わってなければ(勝者がいなければ)それを指摘する.

解法
書くだけ.全部調べる.

UVa 10097 - The Color Game (この記事を編集する[管理者用])

Source
UVa 10097

問題概要
有向グラフ.
n個のノードがあって,それぞれのノードにはそれぞれ別々の色が付いている.
各ノードからはn色それぞれの枝が高々1個出ている.
最初に2つのノードN1とN2に一つずつ駒を置く.
移動するときは,自分ではない駒がいるノードの色に対応する枝のみ通ることができる.
1つの駒をN3に移動するのに必要なターン数の最小値を求める問題.
移動できないなら,それを指摘する.
nは100以下.

解法
状態数は高々O(n^2)程度なのでBFSすれば良い.

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

Source
Waterloo Local Spring 2009 (2009-06-13) [blog]
UVa 11627

問題概要
ゲートの中(端でも良い)をくぐりつつゴールするのに時間最小のスキー板を求める問題.
スキー板の種類は100万個以下で,下降(y軸に負の向き)速度が決まっていてその速度で一定に下降していく.
ゲートはx軸に平行で,全て幅がW.ゲートの数は10万以下.
x軸方向に移動する速度は最高速度が与えられている.
最初と最後のゲートはどこにいても良い.

解法
2分探索.
下降速度を固定すると,各ゲートのときにいることができるx座標の範囲を計算していけばよい.

Appendix

Recent Articles

ブログ内検索

Ads


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