Entries

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

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

メモを残す方向 (この記事を編集する[管理者用])

Online Judgeで問題解いても昔解いた問題とか覚えてないので, 取り敢えず解いた問題の概要と解法を,できるだけ全部,ログを残しておこうと考えてみる.
できれば,難易度は問わないので,1日平均1問位解きたいなぁ.書くときはまとめて書くと思うけれども.

いつ頃飽きるだろうか….

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

Source
USACO 2003 March Green
PKU 2019

問題概要
N*Nのグリッドに0から250までの整数が書かれている.
K個クエリが与えられて,それぞれのクエリに対して,N*Nのグリッドの一部のB*Bのグリッドに書かれている数字の最大値-最小値を求める問題.
全てのクエリでBは一定.
Nは250以下,Kは100000以下.

解法
最初に全てのB*Bのグリッドに対して答えを計算する.
行については全探索で,列については尺取りメソッドするなどで良い.
愚直に O(N^3 + N^2 * 書かれている整数の種類(251)) とかで計算したけど通った.

PKU 3193 - Cow Phrasebook (この記事を編集する[管理者用])

Source
USACO 2006 February Bronze
PKU 3193

問題概要
M個の文字列,N個の文字列が与えられる.M個の文字列の長さはそれぞれ60以下.
N個の文字列それぞれに対して,M個の文字列のどれかのプレフィックスになっているかどうかを判定して,
プレフィックスになっているものの数を求める問題.
完全に一致するものもプレフィックスとみなす.
Mは1000以下,Nは10000以下.

解法
やるだけ.なんとでもなるはず.
例えば,M個の文字列をソートしておいて二分探索など.
僕は,M個の文字列を全部trieに突っ込んで,N個の文字列それぞれに対して,該当するノードが既に作られているかどうかを調べた.

PKU 2458 - Rigging the Bovine Election (この記事を編集する[管理者用])

Source
USACO 2005 February Silver
PKU 2458

問題概要
5*5のグリッドにHかJの文字が書かれている.
縦横につながっていると思って,連結な7つの文字を取ってきて,Jの方が文字数が多くなるのは何通りあるかを求める問題.

解法
25C7なんてそんなに大きくないので全探索.
枝とか刈らなくても大丈夫だけど,連結でなければいけないとか枝刈るとさらに速くなる.

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

Source
USACO 2006 January Silver
PKU 3182

問題概要
50×50以下のグリッドで,穴が開いていない連続のXと,*が1点与えられる.
*から始まって,*で終わるような,Xをぐるりと一周回るようなパスの最小ステップ数を求める問題.
1ステップでは縦横斜めに進める.

解法
Xのマスの中で最も上(Y座標が最大)のものの1つ上,
最も右上(X+Yの値が最大)のものの1つ上,1つ右,

というように12個のマスを順番に回るようなパスのうち長さ最小を求めればよい.
最も右上のマスが複数存在した場合,そのうちの1個だけを考えればよい.

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

2009年05月28日00時15分から.
登録人数の上限が増えて2000人になったらしい.
しかし,アリーナが落ちたりしてたので,登録したけど参戦できなかった人も多かったみたい.

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

要素数50以下のpermutationが与えられる.
問題文で定義されるperfectなpermutationにするためには要素を最小で何個変更すれば良いかを求める問題.
perfectとは,簡単にいえば,最初一番最初の要素にいて,その場所に書かれている要素に移動するという処理を行うと全て訪れて最初の要素に戻るようなもの.

与えられたpermutationを循環置換の積に直して,積の数が答え.
ただし,1個の積になっているなら答えは0.

ノード数50以下のグラフが与えられる.
問題文の絵に描かれたような操作を何回か行うことでグラフを連結にしたい.
操作の最小回数を求める問題.

孤立点があれば不可能.後,枝が足りてないと不可能.
そうでなければ,1回操作を行うごとに,連結成分の数が1つずつ減るので,連結成分の数を求めればよい.
実際に,閉路を一部分壊しながら,それと繋がっていない枝と組み替えるといったシミュレーションをgreedyにしても良い.

紙を適当に折り曲げて,ある部分(重なっているものすべて)を白く塗って,広げるという作業を何回か行う.
最終的に塗られていない面積を求める問題.

まず塗られる長方形を全て求めて,下端のy座標でソートしておく.
別々に考えなければいけないx座標の範囲それぞれに対して,長方形をなぞっていって塗られている面積を求める.

変更履歴
2009/05/28 12:25 MEDIUMで枝が足りてない場合(入力が連結でない森の場合など)書くの忘れてたので追記.ついでにグリーディーにシミュレーションでも良いと追記.

UVa 10169 - Urn-ball Probabilities! (この記事を編集する[管理者用])

Source
UVa 10169

問題概要
2つの箱があって,最初は片方の箱に赤い玉が1つだけ,もう片方の箱には赤と白の球が1個ずつ入っている.
次の一連の操作をn回行う.
 二つの箱の中から1つずつランダムに玉を取り出し色を確認して,箱に戻す.
 その後,二つの箱にそれぞれ1個ずつ白い球を追加する.
さて,1回も赤い玉2個同時に取り出さない確率と,n回連続で毎回赤い玉を取り出す確率を求める問題.
ただし,後者はとっても小さい値になっちゃうので,小数点以下何桁0が続くかのみを答える.
nは100万以下.

解法
普通に確率を計算するだけ.DPっぽく計算して配列に答えを残しておくと,最初にO(n)計算するだけで全てのクエリに対して答えが求まる.
小数点以下何桁0が続くかというのは,常用対数取って整数部分を見ればわかる.
というか,普通に確率を計算してるとアンダーフローしちゃうので,最初から全部log取って計算すると良い.

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

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

Assignment
久しぶりのSRM.どきどき.
5分前になったのでアリーナに入ろうとしたら入れない.
ついったーみると,なんか落ちてるみたいだ.

入れた.
後2分で始まるとかいってるー.ちょっと待ってー.
部屋は平和そうな部屋だった.
15分遅れで開始.

Coding
取り敢えず250,500,1000の普通の問題セットだ.

EASY
問題読む.ふむふむ.数学っぽい.
わからない.
わからない.
もしかして,循環置換の積に表したとき,何個の積になるかを返せばいいのでは?
ただし,1個だけなら0を返す.
良さそうな気もするし,書いてみる.
(ローカルで実行して)サンプル通った.
よし,送信だ.
コンパイルしようとすると謎のエラーがでる….
意味不明.あたふた.
アリーナ再起動.コンパイルできた,サブミット.

MEDIUM
問題を読む.グラフのローカルサーチみたいな組み換えして連結にせよ.
うーん.500だし簡単なわけはないんだよな….
でも,Greedyに組み替えてうまくいかない例がよくわからない.
Summary見る.皆瞬殺してる,Greedyでシミュレーションするだけで良いのかもしれない.
そうに違いない,書いた,サンプル通った,送った.

HARD
まだ45分ぐらい残ってる,今回は解けるかも.
紙を折るのかー嫌だー.
取り敢えず,問題読んだ.どうすれば良いのだろう….
座標は大きいけど,折り返す数少ないし,実は縮小座標作って塗りつぶせば良いのでは…?
縮小座標はメモリにのる…,TLEしそうな気もするけど大丈夫な気もする.
書く,書く,ひたすら書く.
バグ入れたりもしながら完成.残り10分.
サブミット.
あれ,もしかして,配列確保してる領域,微妙に足りないんじゃないか,1000回折れば1001個に分割されるぞ?
良く考えろ,実は足りてるかもしれないぞ!…足りないorz
リサブミット.

Intermission
チャレンジケースを考える.
ない.
あれ,もしかしてMEDIUMって,1個だけ孤立してるノードがなければ,いくつ連結成分があるかだけで答え決まるのでは….
取り敢えず,1個だけ孤立してるノードがある例を作っておく.
後,いないとは思うけど,EASYで探索してる人のために,答えが50近くになるテストケースを作っておく.

Challenge
MEDIUMで連結成分の数求めているっぽい人いた.
チャレンジ.ちゃんと例外処理してた.失敗.
同じ日本人のよしみ(昔,嫌なよしみだと友達に言われた)で,MEDIUM開いてみたら落とせそう.
叩いてみる.落ちた.ごめんね.
後はEASYで謎なことしてる人発見.
2回叩いて落ちない.良く見たらコード勘違いしてた.正しそうだ….
合計-25pt.これだからやっぱりチャレンジなんてするもんじゃない.

System tests
HARD落ちたorz
NULL返したらしい,TLEかなぁ?
やっぱり愚直に塗ると時間足りないのかも.

Rating
51落ちた.
まぁ,この問題セットで全完してないので落ちて当然だけど.
微妙に点数が密集してる地帯にいるので,アリーナバグでコンパイルできずに再起動したのとか,チャレンジミスってるのが痛い.
でも,まあ,どっちみち落ちる.

2009/05/28 02:25追記
HARDの計算量見積もる時,1桁勘違いしてた….ギリギリでメモリにのるぐらいなんだから,そりゃ落ちるって….

PKU 1946 - Cow Cycling (この記事を編集する[管理者用])

Source
USACO 2002 February
PKU 1946

問題概要
N人でレースを行う.
最初N人とも,エネルギーをEだけ持っている.
K人目が単位時間当たりX周走ると,K人目のエネルギーがX^2消費して,K+1人目以降のエネルギーがXだけ消費される.
ただしXは整数でなければいけない.
単位時間ごとにスピードを変えることができ,自由に次の人に交代することができる.
途中でエネルギーが0未満になってはいけない.
合計でD周する最小時間を求める問題.
Nは20以下.DとEは100以下.

解法
DP+DP.
まず,1人の場合,残りエネルギーと進む周の数が与えられたとき,それを達成できる最小時間をDPで計算しておく.
N人の場合は,上で求めた情報を使ってDPで計算する.

PKU 2069 - Super Star (この記事を編集する[管理者用])

Source
ACM/ICPC Japan 2001 (Asia - Hakodate - 2001/2002)
PKU 2069
LiveArchive 2407
Aizu 1231

問題概要
3次元空間上のn点の座標が与えられたとき,それらを全て内部に含む球のうち半径が最小のものの半径を求める問題.
nは30以下.

解法
山登り.
球の中心を最も遠い点の方向に少しずつ移動させていく.

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

Source
USACO 2002 February
PKU 1949

問題概要
やらなければならない雑用がN個あって,1からNまで番号がつけられている.
各雑用に対して.
 その雑用を終えるのに必要な時間
 その雑用を始める前に,終えてなければいけない雑用のリスト
が与えられる.
K番目の雑用を始める前に,終えていなければいけない雑用は1からK-1しかなく,100個以下である.
雑用はいくらでも並列に処理できるとして,全ての雑用を終えるまでに必要な最小時間を求める問題.
Nは10000以下.

解法
DAG上のDP.O(枝の数).

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

Source
USACO 2008 February Gold
PKU 3667

問題概要
長さNの配列が最初は0で満たされている.
以下の2種類のクエリに答える問題.
 クエリ1) 配列のある区間を0にする
 クエリ2) 一番最初の連続するn個の0を1に書き換えて,その場所を返す
Nは50000以下,クエリの数は50000以下.

解法
たぶんsegment treeで解けるんだと思う.
計算量的に大丈夫そうだったので,配列を200個ずつ区間に分けて,それぞれの区間の連続する0の個数の最大値と,
区間の最初,最後に0がいくつ並んでいるか,などを記憶しながら計算した.
segment treeでもやることは基本的に一緒のはず.

UVa 11622 - Le Compte est Bon (この記事を編集する[管理者用])

Source
VII Programming Olympiads in Murcia (2009-05-23) (blog)
UVa 11622

問題概要
 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75, 100
の14個の整数から重複を許して順序付きで6つ選ぶ.
6つの中から自由な順番でいくつか使って,四則演算した結果,nになることができるような,選び方は何通りあるかを答える問題.
nは1以上8000以下.

解法
これも問題文が意味不明.
どうやら,カッコは自由に使って良いけど,途中で負の数になったり,整数じゃない数字が出てきてはいけないらしい.

前計算で全部結果を求めて,埋め込んで送ってACをもらった.
ソースコード制限はUVaは40KBらしく,適当に圧縮しないと埋め込めれない.

コンテスト中WAもらったのは,枝刈りにハッシュを使ってて,適当にハッシュの生成方法変えても答え変わらないから大丈夫だと信じ込んでたのが問題だった.

UVa 11621 - Small Factors (この記事を編集する[管理者用])

Source
VII Programming Olympiads in Murcia (2009-05-23) (blog)
UVa 11621

問題概要
n以上の整数で,2と3以外の素数で割り切れないもののうち,最小のものを求める問題.
nは2^31未満.

解法
2^31以下の2^i * 3^jの形の数字を全部列挙する.
そんな数字は高々31^2個ぐらいしかない.
その後は適当に探せば良い.

UVa 11620 - City of Egocentrics (この記事を編集する[管理者用])

Source
VII Programming Olympiads in Murcia (2009-05-23) (blog)
UVa 11620

問題概要
100×100の升目に数字が書いてある.
同じ列で,自分より左と自分より右にある数字を足して等しい場所を全部出力する.
同様に,行に対して,自分より上,自分より下の数字の和が等しい場所,
同様に,斜め2方向に対しても行う問題.

解法
O(升目の数).
同じ列で自分より左にある数字の和などを前もって全部計算しておけば良い.

UVa 11619 - SPAM! (or not) (この記事を編集する[管理者用])

Source
VII Programming Olympiads in Murcia (2009-05-23) (blog)
UVa 11619

問題概要
学習用にスパムやそうでない文章が与えられて,判定したい文章が与えられたとき,それがスパムかどうかを判定する問題.
文章に含まれている単語に注目し,問題文の通りに確率を計算する問題.

解法
文字列操作,実装問題,やるだけ.
問題文が意味不明.P(w|S)って何だ…,本当に確率なのか?
1つの文章内に,同じ単語が複数存在した場合,重複して処理すると通る.

UVa 11618 - The Amazing Triangle Counting Machine (この記事を編集する[管理者用])

Source
VII Programming Olympiads in Murcia (2009-05-23) (blog)
UVa 11618

問題概要
互いに重ならない,交わらない線分が何本か与えられる.
そうやって作られる図形の中に,オーバーラップしない三角形は何個あるかを求める問題.

解法
全探索で,3本の線分をとってきて,それが三角形をなしていればカウントする,という方法で通った.
計算時間的な問題や,コーナーケースとかありそうな気がするけど,そもそも問題文がよくわからない.

UVa 11617 - An Odd Love (この記事を編集する[管理者用])

Source
VII Programming Olympiads in Murcia (2009-05-23) (blog)
UVa 11617

問題概要
2次元の升目に1から9までの数字が書かれている.
最初左上から始まって,1ステップで左右か下に進むことができる.
偶数が書かれている升目を全て通るためには最低で何ステップ必要かを求める問題.

解法
各行に対して,偶数が現れる最も左のマス,右のマスに着目して,
同じ行の偶数を全て訪れたうえで,そのマスまで辿り着くのに必要なステップ数をDPで求める.
O(盤面の面積).

UVa 11616 - Roman Numerals (この記事を編集する[管理者用])

Source
VII Programming Olympiads in Murcia (2009-05-23) (blog)
UVa 11616

問題概要
ローマ数字をアラビア数字に変換する,もしくはその逆を行う問題.
扱う数字は4000まで.

解法
やるだけ.

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

Source
VII Programming Olympiads in Murcia (2009-05-23) (blog)
UVa 11615

問題概要
高さnの完全2分木において,ノードaの子供とノードbの子供をそれぞれ同一視する.
実質何個のノードが含まれているかを求める問題.
nは20以下.

解法
Ad-hoc.
a=bならば同一ノード無し.
そうでなければ,aとbの深い方の子孫をカウントしなければ良い.

UVa 11614 - Etruscan Warriors Never Play Chess (この記事を編集する[管理者用])

Source
VII Programming Olympiads in Murcia (2009-05-23) (blog)
UVa 11614

問題概要
1列目には1人,2列目には2人,…,k列目にはk人並ぶ.最後の列はその限りではない.
n人並ぶとき,何列になるかを求める問題.
nは10^18以下.

解法
2次方程式を解く.もしくはバイナリサーチ.

VII Programming Olympiads in Murcia (この記事を編集する[管理者用])

2009年05月23日16時30分から4時間,9問.
[ link ]

9問中8問解いた.
基本的にクオリティは低め.
去年も意味不明な問題文やら,ジャッジが間違えてるっぽかったりしたコンテスト.

Fは,同一メール内に同じ単語が2回以上でてきても1回しかカウントしないと信じ切ってWAを12回もらった.重複して処理すればOKだった.
問題文的には重複して処理してはいけないように読めるんだけどなぁ.

Iも問題文が意味不明.適当に解釈して,とりあえずローカルで3分かけて8000まで全部求めてみたら8000のときは合っていたので,埋め込んでサブミットしてみるもWA.

UVa 11613 - Acme Corporation (この記事を編集する[管理者用])

Source
The first contest of the new season (SohelH's Marriage Ceremony Contest, 9th May, 2009)
UVa 11613

問題概要
ある製品を作って売って最大利益を求める問題.
考える区間はMか月で,各月ごとに
 その製品をその月に作ることができる最大個数
 その製品をその月に1個作るコスト
 その製品をその月に売ることができる最大個数
 その製品をその月に売る時の1個当たりの値段
 その製品をその月に作ったものは最大で何ヶ月間保存できるか
が与えられる.
また,月末に在庫が存在する場合,1か月あたり製品の個数に比例するコストがかかる.
Mは100以下,その他の変数は100万以下ぐらい.

解法
価格を正負反転させて,最小費用流.
ただし,最大流ではない.
最小費用最大流で,例えばprimal dualだったら,コストが負である限り流し続けるとかすると良い.

コンテストのとき,解いてる人が少なかったので問題文すら読まなかったんだけど,最小費用流ライブラリ持ってたら瞬殺できる問題だった.
やればよかった….

この記事を書いている時点でサンプルアウトプットが間違っているので注意.
正解は2ではなくて20.

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

Source
USACO 2007 Open Gold
PKU 3281
TJU 2823

問題概要
牛がN匹,食べ物がF種類,飲み物がD種類ある.
各牛ごとに食べることができる食べ物,飲むことができる飲み物リストが与えられる.
牛は食べれる食べ物と飲める飲み物が与えられれば満足する.
各食べ物,飲み物は1匹の牛にしか与えることができない.
最大で何匹の牛が満足するようにできますか,という問題.
N,F,Dはそれぞれ100以下.

解法
最大流.
グラフは
 ソース - (食べ物) - (牛) - (牛) - (飲み物) - シンク
という形.

TopCoderで昔やった気がする問題.これやってれば解けたんだろうなぁ….

PKU 3280 - Cheapest Palindrome (この記事を編集する[管理者用])

Source
USACO 2007 Open Gold
PKU 3280
TJU 2822

問題概要
M文字の文字列が与えられるので,それを回文にするのに必要な最小コストを求める問題.
アルファベットごとに,任意の場所に挿入する,削除するコストが設定されている.
Mは2000以下.

解法
状態数,計算時間ともにO(M^2)のDP.
ある文字を挿入するのと削除するのは結局同じことなので,コストの小さいほうを採用する.

PKU 1944 - Fiber Communications (この記事を編集する[管理者用])

Source
USACO 2002 February
PKU 1944

問題概要
円上にN個のノードがあって,隣同士のみ枝を張ることができる.
P個のノード対が与えられて,それらを全て連結にするためには,最低で枝を何個張れば良いかを求める問題.
Nは1000以下,Pは10000以下.

解法
O(NP).
答えはn-1以下で,1か所は枝を張らなくても良い部分があるはず.
1か所枝を張ってはいけない場所を決めると,ある2つのノードを連結にするための枝の張り方は一意に決まる.
なので枝を張ってはいけない場所を1か所決めて全て試す.

PKU 3277 - City Horizon (この記事を編集する[管理者用])

Source
USACO 2007 Open Silver
PKU 3277
TJU 2824

問題概要
見えるビルの面積を求める問題.
具体的には,左端,右端の座標x1,x2と高さhが与えられるので,(x1,0)-(x2,h)からなる長方形を描いていって,最終的に塗られる面積を求める.
ビルの数はN=40000以下.

解法
O(N log N)とかであれば,どうやっても良いと思うけど,
例えば,左から順番に処理して,ビルが始まったら,高さをセットに入れる,ビルが終わったらセットから消す,各区間でセット内の最大要素×幅を足していく,とか.

Aizu 1031 - Simple GUI Application (この記事を編集する[管理者用])

Source
University of Aizu, ACM-ICPC Japan Domestic Contest Warm Up I, 16 May, 2009 (blog)
Aizu 1031

問題概要
GUIのウインドウの情報が入れ子構造のタグみたい文字列で与えられる.
ある座標にある一番上のウインドウの名前を答える問題.
ついでに,そのウインドウのすぐ上にあるウインドウの数も数える.

解法
簡単な構文解析でグラフに落として適当に調べれば良い.

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

PKU 2187 - Beauty Contest (この記事を編集する[管理者用])

Source
USACO 2003 Fall
PKU 2187

問題概要
平面上のN点が与えられたとき,2点間の最も距離が遠いものの距離を求める問題.
Nは50000以下.

解法
取り敢えず,凸包をO(N log N)で求めて,それの上に乗っている点のみを考えればよい.
O( 凸包上の点の数^2 ) で愚直に調べても通ってしまった.効率よく調べる方法がわからない.

PKU 2188 - Cow Laundry (この記事を編集する[管理者用])

Source
USACO 2003 Fall Orange
PKU 2188

問題概要
N本の糸が上から下に張られている(原文の図を参照).
N本の糸には1からNまでの番号がつけられていて,上は左から何番の糸がついているか,下も左から何番の糸がついているかが与えられる.
上か下の隣り合った糸を入れ替えることで交わらないようにしたい.
最小でいくら入れ替えなければいけないか.
Nは1000以下.

解法
転倒数を数えるだけ.
O(N log N)で解けるけど,O(N^2)で間に合う.

Appendix

Recent Articles

ブログ内検索

Ads


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