Entries

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

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

Beta Round #45 D問題 - Permutations (この記事を編集する[管理者用])

Source

Codeforces Beta Round #45 D問題
Problem description
Beta Round #45の自分の参加記録

問題概要

1以上10^5以下の数字が10^5個以下与えられる.
それらを適当なグループに分けて,すべてのグループはpermutationになるようにしたい.
そのような分け方を1つ求める問題.不可能ならそれを指摘する.

解法

kの数よりk+1の数のほうが多ければ不可能.
そうでないなら,全部の数字に対して,1~出現した数までを1つずつをグループ番号として割り振れば終わり.

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

続きを読む

Beta Round #45 C問題 - The Race (この記事を編集する[管理者用])

Source

Codeforces Beta Round #45 C問題
Problem description
Beta Round #45の自分の参加記録

問題概要

等差数列の整数部分の最初のn項 (1000以下) が与えられる.
次の項が一意に定まるならその値を出力して,そうでないならそれを指摘する問題.

解法

各項より交差の最大値と最小値を計算して,次の項が一意に決まるか見るだけ.

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

続きを読む

Beta Round #45 B問題 - Land Lot (この記事を編集する[管理者用])

Source

Codeforces Beta Round #45 B問題
Problem description
Beta Round #45の自分の参加記録

問題概要

50*50以下の0または1のみからなる行列が与えられる.また自然数aとbが与えられる.
サイズa*b,またはb*aの長方形の領域で含まれる1の数が最も少ない場所の,1の数の最小値を求める問題.

解法

愚直に全パターンを調べてO(50^4)でも間に合う.
自分より左上のマスに含まれる1の数を最初にカウントしておくと,各長方形に含まれる1の数はO(1)で計算可能で,合計でO(50^2)時間で解くこともできる.
以下のコードはO(50^2).

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

続きを読む

Beta Round #45 A問題 - Rock-paper-scissors (この記事を編集する[管理者用])

Source

Codeforces Beta Round #45 A問題
Problem description
Beta Round #45の自分の参加記録

問題概要

3人でじゃんけんして出した手が与えられるので,1人だけが勝ってる場合は勝者の名前を,そうでないなら?を出力する問題.

解法

やるだけ.

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

続きを読む

Beta Round #43 E問題 - Comb (この記事を編集する[管理者用])

Source

Codeforces Beta Round #43 E問題
Problem description
Beta Round #43の自分の参加記録

問題概要

N*M (1500*1500以下) の整数の書かれた行列Mが与えられる. (整数は絶対値10000以下)
 c1 > c2 < c3 > c4 < … cn
という1以上の数字の列を選んでできる
 M[1][1] + M[1][2] + … + M[1][c1] +
 M[2][1] + M[2][2] + … + M[2][c2] +
  …
 M[n][1] + M[n][2] + … + M[n][cn]
の値の最大値を求める問題.

解法

行ごとに各部分までの和を求めておいて,右からなぞったり左からなぞったりするDP.

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

続きを読む

Beta Round #43 D問題 - Parking Lot (この記事を編集する[管理者用])

Source

Codeforces Beta Round #43 D問題
Problem description
Beta Round #43の自分の参加記録

問題概要

長さLの駐車場があって,順番に車が来たり,出ていったりするクエリが与えられる.
くるクエリの度に,車が停まる場所か,停まれずに出て行くか,を求める問題.
車が来るときは,車の長さが与えられて,
 前bだけ,後ろにfだけはスペースを開くように,最も入り口から近い場所に停める.
また,長さLの駐車場の前後には無限にスペースが開いているが,そこには停められない.
Lは100000以下,車の長さは1000以下,bとfは100以下,クエリの数は100以下.

解法

本当に愚直にシミュレーションする.
あんまり変な実装だとLがそこそこ大きいしTLEしそうだけど,普通に間に合う.

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

続きを読む

Beta Round #43 C問題 - Hamsters and Tigers (この記事を編集する[管理者用])

Source

Codeforces Beta Round #43 C問題
Problem description
Beta Round #43の自分の参加記録

問題概要

合計1000匹以下のハムスターとタイガーが円周上に並んでいる.
2匹をスワップして,ハムスター同士,タイガー同士を分けたい.
スワップの最小回数を求める問題.

解法

どこからハムスターを並べるか1000通り全部試す.
最初にある場所までのハムスターの総数を全部計算して覚えておくことでO(1000)でできるが,
毎回愚直に必要スワップ数を求めてO(1000*1000)でも十分.
以下のコードはO(1000*1000).

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

続きを読む

Beta Round #43 B問題 - T-shirts from Sponsor (この記事を編集する[管理者用])

Source

Codeforces Beta Round #43 B問題
Problem description
Beta Round #43の自分の参加記録

問題概要

サイズS, M, L, XL, XXLの5種類のTシャツの数が与えられる.
K人 (1000以下) が順番にTシャツをもらいに来るので,欲しがってるサイズに最も近いサイズのTシャツを渡していく.
同じ近さのサイズがある場合は,大きい方を優先的に渡す.
それぞれの人が渡されたTシャツのサイズを求める問題.
Tシャツの合計数はK以上.

解法

やるだけ.

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

続きを読む

Beta Round #43 A問題 - Ball Game (この記事を編集する[管理者用])

Source

Codeforces Beta Round #43 A問題
Problem description
Beta Round #43の自分の参加記録

問題概要

1~nの番号が付けられた人が円周上に並んでいる.
最初1番目の人がボールを持っていて,
 1個隣の人に投げる
 2個隣の人に投げる
 …
 n-1個隣の人(逆周りで隣の人)に投げる
と投げたとき,受け取った人,n-1人の番号を順番に出力する問題.
nは100以下.

解法

やるだけ.

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

続きを読む

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

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 5002

問題概要

N (1000以下) 人の上下関係が木で与えられる.
N人の人が一列に並ぶとき,自分の親より前に並ぶことはできない.
並び方は何通りあるか mod 1000000007で求める問題.

解法

N! / 1の子孫の数 / 2の子孫の数 / …

LiveArchive 5001 - Making Quadrilaterals (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 5001

問題概要

N (4以上60以下) が与えられる.
N本の正整数の長さの棒の組で,どの4つを取ってきてもその長さの辺を持つ四角形を作れないようにしたい.
そのような集合の中で,最も長い長さの最小値を求める問題.

解法

Greedy.
N=3なら全部1で良くて,N=4からは前の結果の最も長い方から3つの長さの和のものを追加していく.

LiveArchive 5000 - Underwater Snipers (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 5000

問題概要

2次元世界で y=k (kは-10^8以上10^8以下) より上(y座標の大きいほう)が陸地で,下が海.
陸地の整数座標にN (10000以下) 人の敵がいる.
射程D (10^9以下) のスナイパーを海の整数座標に配置し,スナイパーを移動することなく敵を全部倒せるように配置したい.
最も上にいるスナイパーのy座標を最小化したい.最小値を求める問題.
全部倒せないならそれを指摘する.

解法

二分探索 + Greedy.
最も上のスナイパーのy座標で2分探索し,スナイパーは全部そのy座標に置けば良い.
後は,スナイパーのx座標をgreedyに決めていく.

LiveArchive 4997 - ABCD Tiles (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 4997

問題概要

15*15以下の升目が与えられて,いくつかにAのタイルが敷き詰められている.
問題文の頭の形のタイルB, C, Dが無数に使用できるので,タイルが敷かれてない場所にB, C, Dのいずれかのタイルを敷いて埋める.
タイルは重なってはいけないし,しかれていないマスがあってもいけない.
また,Bのタイル同士,Cのタイル同士,Dのタイル同士が上下左右斜め9マスで接していてはいけない.
敷き詰め方のうち,辞書順で最小のものを求める問題.
不可能ならそれを指摘する.

解法

5マスのタイルの領域に分け,グラフの彩色問題に落とす.
後は全探索しても大丈夫.

LiveArchive 4996 - Scientefic Experiment (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 4996

問題概要

0階から卵を落とすと割れない,n (1000以下) 階から卵を落とす問われることを知っている.
また,k階から卵を落として割れるなら,k+1階から卵を落として割れることを知っている.
卵を落とすと割れる最小の階数を求めるために必要な最小コストを求める問題.
卵は1個までしか運ぶことができず,ビルの中で卵はx円で売っている.
結果を見るために落とすとビルから外に出なければいけない.卵が割れずに残っていたら拾わなければいけない.
卵を持たずにビルに入るにはy円かかり,卵を持った状態でビルに入るにはz円かかる.
最終的に,結果が判明したとき,卵が割れずに残っていたらx/2円で売ることができる.(ビルに入ることなしで)

解法

割れるかどうか不確定な階数の幅を状態としてDPする.

LiveArchive 4995 - Language Detection (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 4995

問題概要

挨拶が与えられるので,それが何語なのか判定する問題.
何が与えられたら何を返すかという表が問題文で与えられており,それ以外が入力されたらUNKNOWNと返す.

解法

やるだけ.

LiveArchive 4994 - Overlapping Scenes (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Kuala Lumpur (Malaysia) - 2010/2011
UVa: Kualalumpur Regional Semilive (2010-12-11) (blog)
LiveArchive 4994

問題概要

10文字以下の文字列が6個以下与えられる.
最初は空の文字列で,与えられた文字列を自由な順番でそれに追加していった際に,最終的な文字列の最小の長さを求める問題.
追加する際は,最後に追加するのだけど,サフィックスと追加する文字列のプレフィックスが一致するならそれを重ねて追加する.
追加する際は,最も重なる部分が多くなるように追加する.

解法

実際に6!通りの追加方法を全部試す.
賢くやろうとすると逆に間違えやすいので注意.

Kualalumpur Regional Semilive (この記事を編集する[管理者用])

2010年12月11日18時から5時間,10問.(ランキングリスト分けて5時間追加)
[ Link ]

結構バリエーション豊かな問題セットでした.
簡単なのから難しいのまで,あんまり強い実装問題はないのかな.
ABCDGHIの7問解いた.

・問題A
全パターンやるだけ.
最初に書く文字列をつなげるコストを計算してビットDPっぽくやるとダメってのにちょっと気づかなくてWAもらってた.
・問題B
流石にやるだけ.
・問題C
DPするだけ.
・問題D
greedyでいいかと思ってWA.ちゃんと全探索する問題だった.
・問題G
二分探索をするだけ.
・問題H
greedyに使えないように,最後に追加した3項を足して追加していく.
・問題I
n! / Π子どもの数 ってどこかでそうなるなーって考えたあったから,今回は何も考えずにそうした.

Beta Round #45 (参加記録) (この記事を編集する[管理者用])

2010年12月12日17時から3時間,8問.ACM/ICPCルール
[ LINK ]

A. Rock-paper-scissors

3人でじゃんけんして出した手が与えられるので,1人だけが勝ってる場合は勝者の名前を,そうでないなら?を出力する問題.

やるだけ.サブミット.Accepted.

B. Land Lot

50*50以下の0または1のみからなる行列が与えられる.また自然数aとbが与えられる.
サイズa*b,またはb*aの長方形の領域で含まれる1の数が最も少ない場所の,1の数の最小値を求める問題.

これもやるだけ.O(50^4)でもいいんだろうけど,O(50^2)で書く.Accepted.

D. Permutations

1以上10^5以下の数字が10^5個以下与えられる.
それらを適当なグループに分けて,すべてのグループはpermutationになるようにしたい.
そのような分け方を1つ求める問題.不可能ならそれを指摘する.

すでにDを解いてる人が結構いて,Cより簡単そうなのでこっちからやる.
うん,やるだけ.
kの数字の数はk+1の数字の数より小さいとダメ.
あとは,現れた回数を愚直にグループ番号として割り振るだけ.
Accepted.

C. The Race

等差数列の整数部分の最初のn項 (1000以下) が与えられる.
次の項が一意に定まるならその値を出力して,そうでないならそれを指摘する問題.

TopCoderのDiv1 Easyでかつて見たような問題.
公差の最大値と最小値を愚直に計算して,次の項を求めておしまい.Accepted.

E. Ivan the Fool VS Gorynych the Dragon

ドラゴンは頭と尾があって,合計でR本を超えると暴走モードになって殺される.
頭をk個切ると,頭がA[k]個増えて,尾がB[k]個増える.
尾をk個切ると,頭がC[k]個増えて,尾がD[k]個増える.
という関係が与えられたとき,ドラゴンの頭と尾をなくすための最小ターン数を求める問題.
不可能なら,無限に戦いが続けられるならそれを指摘する.
それも不可能なら,生き残れる最大ターン数を求める.
Rは200以下.

うーん?
ループが存在するかどうか,愚直にベルマンフォードはTLEだよなぁ.
そろそろUVaでコンテストが始まるのでそっちに行く.

問題 F~H

読んでない.

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

2010年12月29日11時02分から.

Assignment

250-550-1000の微変則セット.

EASY

一直線上の地面にN本 (50以下) の木が立っている.木の場所と高さが与えられる.
いくつかの木を切って (高さ0にすることも可能) 木の最も高い点が全部同一直線上にあるようにしたい.
切らなければいけない最小の木の数を求める問題.

サンプル見てだいたい問題理解してから,問題を読む.
ふむふむ,思ったとおり.
で….
2本選んで,その頂点を通る線上になるようにすればいい気がする.
えー…,整数だけで計算可能だが面倒.
doubleでも多分大丈夫なはず,このぐらいなら…,きっといける!
doubleで行く.
サンプルが全然合わない.
あ,xとy逆だった.
1個合わない.
なるほど,1個だけ切らなくていい場合があるのか.
高さはマイナスにできないのでそういうこともあるのか….
1個だけ切らない場合は常に可能なのでそうする.
これでサンプル全部通るがなんか怪しいなぁ.
もっと,ちゃんとロジカルに考えてみろ!
1個だけ切らない場合は常に可能.
2個以上切らないなら,それで直線は一意に定まる.
だからこれで良い!
ってことで,良さそうだった.提出.

MEDIUM

ノード数N (50以下) の無向グラフが与えられる.枝にはコストがつけられている.
ノード番号が順番にM個 (50以下) 与えられて,その順番に訪れたい.
ただ,ブラウザの戻るボタンのように,前いたノードに戻るのは無コストで移動可能.(一度戻ると,先に進むには普通にコストが必要)
最小コストを求める問題.

うーん?
DP…だよなぁ.
多分,与えられたノード番号のある区間を部分問題として,状態数O(m^2).
で,最後に最初のノードに戻ってくる場所で場合分けして行く.
で,範囲を2つに分けて部分問題に帰着,後ろの問題は,今の場所から次の場所に移動しなきゃいけないからそのコストを足すだけ(*).
えーと,愚直に書くとO(m^3)でいける.
最初,(*)を思いつかなくて今いる場所を覚えておかないといけないかと思ったけど,O(n m^3)だと実は間に合わないとか言う罠がありそうなのでO(m^3)で書く! 550ptだし.
最後のサンプルが合わない.
サンプル見ずに理由を考える.
…,途中で寄り道してもいいよね….
どうしよう….
うーん.
やっぱり今いる場所を覚えておけばいいのでは?
O(n m^3)でいけ…ない.
どこに寄り道するかも調べないといけないから愚直に書くとO(n^2 m^3)になる….
どうやってオーダー1つ落とすのか….
わからない.
とりあえず,浮気してHARDを開くだけ開く.
問題文長かったので読まずに帰ってきてしまった.
うーん.
とりあえず,O(n^2 m^3)でいいから書いてみよう.
お,サンプルは通った.
とりあえず,ランダム最大でも作って実行時間調べてみましょう.
1.4秒…,え,間に合うの?
たしかに定数部分は小さい気がするが….
サブミット.

HARD

読んでない.

Challenge

250はdoubleでEPS使ってない人が落ちそうだったが,どうやって落とせばいいのかわからず.
550がランダム最大ケースを入れられたらしく落とされた.WAらしい.

System tests

250はdoubleだったけど通った.よかった.

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

2010年12月19日01時02分 (JST) から.

Assignment

250-600-900の変則セット.
こういうセットは600からやるか,900からやるか迷って困る.まぁ普通に600からやろう.
自分以外に赤のいない部屋.落ち目になるとこういう部屋によく配置される気がする.
フロリダ (アメリカ) のホテルから参加.TopCoderと同じタイムゾーン.
モバイルノートPCの解像度が低くてやりにくいので,始まる前にやりやすいウインドウの配置を研究した.

EASY

6面対のサイコロの作り方のパターン数を求める問題.回転して重なるなら同じとみなす.
各面にはそれぞれ異なる1~Nの数字を書き,向かい合う面の数字の和は全部一定で,それはK以上でなければならない.
Nは1000以下,Kは2000以下.

ちょ,狐の次郎さんとか問題文に書いてあるのですが….
ま,まぁ,解かなきゃ.
取り敢えず,サイズが小さいから,向かい合う面の数字は全パターンの試そうかな.
で,後は,それを達成する数字の組の数を求めて,コンビネーション足していけば終わり.
それを達成する数字の組は…,図を描いて考える.
うーん,場合分け面倒じゃないか.
違う違う!
このサイズなら全部ループ回して探しても問題ないじゃん!
ループ回す.
合わない….
あ,数字0も使えるようになってた….
修正.サンプル通った.サブミット.

MEDIUM

長さ50以下の文字列がN個 (16以下) 与えられる.文字列はアルファベット小文字のみからなる.
各文字列の中の文字を適当に入れ替えても良い.
与えられた文字列でTrieを作ったときの最小ノード数を求める問題.

Nが16とかどう見ても2^NのDPっぽい.
でも,どうするのかパッとは,わからないなぁ.
50 * 2^16の配列でもつくってDP…,じゃないな,50はどの文字から使っても良いからダメ.
まぁ,取り敢えず,2^Nなんだから,文字列を分離して部分問題にするわけよね.
あ,わかった…かも?
取り敢えず,各部分問題は,全部に共通する文字をgreedyにおいて行って,後はどの部分問題に分けるか試せば良いよね.
あ,O(N^3)なのか,それで16なのか.
greedyに置いていくのは…,全部に共通する文字数だけ最初に求めておけば数式一発で書けそう.
書く.
書いた.
ケアレスミス直して,サンプル通して,サブミット.

HARD

それぞれN枚 (50以下) のカードの山AとBが与えられる.
それぞれのカードには1以上100以下の実数が書かれている.
K回,次の手順を行う.
 それぞれの山から1枚ずつカードを選び,その数字をSとTとして,
  X := X + max(S,T)
  Y := Y + min(S,T)
このとき,X/Yの最大値を求める問題.

うーん.
取り敢えず,比なので取り敢えず2分探索でしょう.
 max(S,T) - 答え min(S,T)
を得られる点数として,最終的に正にできるかどうかの判定問題になる.
うーん.
取り敢えず,大きい物同士,小さい物同士でいいのでは?
てか,そうじゃなかったら,解けない気がするし,取り敢えずそれで.
サンプルは通るなぁ.通るようにサンプル作られてる気がするけど.
サブミット.
さて,妥当性を検証しよう.
ランダムに入れ替えて,それより大きい答えが出てこなければ良さそう.
やってみる.
ランダムに入れ替えても全部同じ答えになる.
なんと!?
2分探索の範囲を初期化してなかった….
あー,普通に反例あるなぁ.
さて,どう解くのやら.
きっとフローか何か.
ってか,普通に単なる最小費用流じゃないか….
!?
ノートPCにライブラリないorz
それは,ちょっと厳しい….
無理でした.

Challenge

900でgreedyの人がいたので適当に落とす.
600で,何故か長さも状態に入れてて50倍遅い人がいたのでTLEで3人落とす.
そうこうしてるうちに自分の900が落とされる.当然.

System tests

なんかエラーってなかなか結果が出なかった.
900が荒ぶって,なんかほとんど落ちていた.なんでだろう.doubleコストの最小費用流だからかな?
チャレンジで結構稼げたのでまあまあいい順位.
それと,チャレンジの最後2分程度が正常に機能しなかった部屋があったみたいで,Ratedにするかどうか議論されたが,Ratedになった.
ターゲットに復帰.

December 2010 Challenge (この記事を編集する[管理者用])

2010年12月01日18時から10日間,6問.(1問はマラソン形式)
[LINK]

アルゴリズム問題を4問解いて,マラソン問題は適当にサブミット.
以下,大体の行動.

まずはざっと問題を眺める.
 A String Gameはすぐ解ける.
 Byteknights and Byteknavesは辞書順最小を求めるのが怪しいが多分解ける.
 Delivering Breadはマラソン問題.後回しでOK.
 Even Coefficientsはわからない.
 Odd Binomial Coefficientsもわからない.
 The Hungry Bearは解けそうだが,よくわからない.
まぁ,書いてみようか.
 A String GameはGrundy数求めるだけ.書く.Accept.
 The Hungry Bearも,x座標の範囲はO(n^2)で全部調べるとして,あとは尺取メソッドで行けることに気づく.
  書く.Accept.
 Byteknights and Byteknavesは…,segment treeを使えば,辞書順最小をO(n log n)で求めれることに気づいた.
  書く.TLE.えー.
  ローカルで実行するとたしかに時間かかる….
  答えが少ないときは,全部愚直に調べてみる.Accept.えー.
  答えが少なくない時も全部愚直に調べる.O(n^2).Accept.しかもさっきより早い.えーえーえー.
  まぁ,通ったからいいか….
すぐ解けそうなのは終わった.
Odd Binomial Coefficientsを考える.
 うーん.問題サイズ的には包除原理っぽいんだが.
 そもそも,項の数が1個の時の答えがわからない.
 調べる.
 ほう.
 どうやら,べきを2進数で表したときの1のビット数をXとして,2^Xが答えなのか.
 で,さらに調べると….
 2個の項が合ったとして,両方共,奇数になる項の数は,べきを2進数でANDを取った時の1のビット数をXとして,2^X.
 綺麗過ぎる.
 じゃ,包除原理で行ける.
 書く.TLE.えーえーえーえーえー.
 なんでcodechefってこんなにタイムリミット厳しいの….
 DPして,オーダーを1つ落とす.Accept.
Even Coefficientsがわからないので,Delivering Breadを適当にサブミット.
これも,微妙にタイムリミットが厳しいし,うまい方法もわからない.
まぁ,Even Coefficientsが解けない限り,Delivering Breadを解いても大して意味はないので,とりあえず保留.
なんかリジャッジが来た!
 Byteknights and Byteknavesが全部TLEになってる….
 まぁ,O(n^2)が通ったらそれはそれでダメな気がするし.
 うーん.とりあえず,どうやって辞書順最小を求めるのか,が問題.
 segment treeじゃなくて,Fenwick treeでできないかな…?
 できそうな気がしてきた.書いた.駄目じゃんこれ最悪でO(n^2 log n)じゃん.却下.
 うーん.
 リスト構造みたいなのを作って頑張る.
 オーダー見積もれないけど速そう.サブミット.Accept.
Even Coefficientsは….
 うーん,適当に変数に何か代入してすべて偶数になるかどうかを調べれば….
 と思ったら,サンプルの1個目が反例.
 わからなかった.

A String GameのC言語によるソースコード

続きを読む

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

2010年12月09日01時02分から.

Assignment

250-550-1000の微変則セット.
書くのが遅くなったのでうろ覚え.

EASY

ある場所にアイテムが溜められて,
 N分 (10億以下) 置きに全部捨てられる
 M分 (10億以下) 置きにアイテムが1個追加される
追加されたと同時に捨てられるかもしれない.
最初,0分でアイテムが追加され,同時に捨てられた.
これを無限に続けたとき,アイテムのこの場所の滞在時間の平均値 (の極限) を求める問題.

結局周期的になるはずで,1周期のアイテムの滞在時間の平均を求めれば宜しい.
で,周期は….
最大で10億に決まってるよな….
なんか数学的にやらないとダメな気がする.
うーん.
とりあえず,N=5, M=3のサンプルを手計算してみる.
待機時間はそれぞれ0, 1, 2, 3, 4になる!
てか,ある意味当たり前で,GCD(N,M)=1なら答えは(N-1)/2だ!
GCDがそうじゃないなら,NとMをGCDで割って,後でGCD倍すれば良いよね.
書く.サンプル通った.サブミット.
ちょっと,ちゃんと考える.うん,良いよね.

MEDIUM

高々1300個程度の単語のリストと,携帯で打ちたい文字列 (長さは最大で50) が与えられる.
文字列を打つために押さなければならないキーの最小値を求める問題.
アルファベットはそれぞれ数字に対応しており(違うアルファベットが同じ数字に対応していることがある),
登録されている単語の最初とマッチする辞書順で最小の文字列が表示される.
辞書順で次の文字列を表示するには1キーかかり,決定にも1キーかかる.
決定と同時に,最後の1文字消去するのは,決定だけと同じキー数ででき,それ以降最後の1文字消すのには1キーかかる.
ルールの詳細,厳密な定義は問題文を参照のこと.

なにこれ,超面倒くさいだけの問題っぽい.
シミュレーションするだけなのかなぁ.
いや,最小キー数を求めるんだから,単なるDPか.
まぁ,書くだけ.
最初に,各単語から,その最初のk文字を打ち込むときの最小キー数をまず愚直に求めよう.
クリアキーを2連続で押したほうが良いこともありそうだから,ちゃんと考えて,求める.
あとはDPするだけになる.
DPするだけ,書き書き.
サンプル合わない.
うー.
最小キー数の計算バグってた.直す.
合わない.
うー.
なんか,単語にスペースが入っているのですが….
!!
単語はスペース区切りで与えられるのか!
適当にsplitする.めんどい.修正完了.
合わない.
サンプルを見比べる.
!!
問題勘違いしていた.
ABC ABD ACCで11と入力して,辞書順で次のを表示させるとACになるのか!
→ ABが2つあるから,2回次にを押さなきゃACにならないのだと思っていた.
うげー.
これ修正だけで結構面倒な書き方してしまったなぁ.
最初からちゃんとサンプル見て確認しておくべきだったか.
直す.
合った!
提出.
・・・.
・・・・・・!?
単語の数の最大数50じゃないよ!
スペースで区切られてるから1200個ぐらいまでありそうorz
配列のサイズが足りてない…,修正&リサブミット.
うう・・・.
まぁ,これは流石に実行時間とか大丈夫だろう.
と思いながら最大ケースを入れてみる.
Runtime Error!
えええええ.
単語の数の配列サイズ1箇所書き換えて,もう1箇所書き換えてなかったorz
もう1階リサブミット.最低点になってしまった….

HARD

縦横20マス以下の升目が与えられる.
横はそれだけだが,縦は同じマスが周期的に無限に連なっている.
ある座標から,ある座標に移動する最小コストを求める問題.
壁は通れない,同じ列にちょうど2つのワープマスがあることがあって,ワープマスからもう一方のワープマスへは無コストで移動可能.
座標は,縦は-10^15以上10^15以下.

いや,まぁ,行列べき乗なのは明らかですが….
細かい処理が面倒で,コーナーケースとかもありそうで怖い.
てか,ちゃんと考えると,その細かい処理が結構難しい気がする.
というか,550のせいで時間なくて書く気がしない.

Challenge

この550が皆解けるとは思えない!
クリアキー2連続を忘れてる人はいるだろうし,バグってる人も多そう!
配列サイズが小さいと落ちて,クリアキー2連続で押さなきゃいけないテストケースを用意する.
自分以外に提出してる3人にブラインドアタック.
1成功2失敗.
皆解けてるのか.凄いなぁ.てか,プラスマイナス0で済んでよかった.

System tests

両方通った.
が,550が最低点でターゲットから転落.

Beta Round #43 (参加記録) (この記事を編集する[管理者用])

2010年12月05日17時から3時間,7問.ACM/ICPCルール
[ LINK ]

A. Ball Game

1~nの番号が付けられた人が円周上に並んでいる.
最初1番目の人がボールを持っていて,
 1個隣の人に投げる
 2個隣の人に投げる
 …
 n-1個隣の人(逆周りで隣の人)に投げる
と投げたとき,受け取った人,n-1人の番号を順番に出力する問題.
nは100以下.

やるだけっぽい.
書く.サンプル合わねぇ.
問題勘違いしてるらしい.
うーん,一度受け取った人は受け取らない…とか?
違うなぁ.
サンプルが間違っているって修正がきた.なんじゃそれw
サブミット.Accepted.

B. T-shirts from Sponsor

サイズS, M, L, XL, XXLの5種類のTシャツの数が与えられる.
K人 (1000以下) が順番にTシャツをもらいに来るので,欲しがってるサイズに最も近いサイズのTシャツを渡していく.
同じ近さのサイズがある場合は,大きい方を優先的に渡す.
それぞれの人が渡されたTシャツのサイズを求める問題.
Tシャツの合計数はK以上.

すごいやるだけ.
書く.Accepted.

C. Hamsters and Tigers

合計1000匹以下のハムスターとタイガーが円周上に並んでいる.
2匹をスワップして,ハムスター同士,タイガー同士を分けたい.
スワップの最小回数を求める問題.

和をちゃんと覚えておいたらO(1000)でできそうだけど,愚直にハムスターの範囲を全探索でO(1000^2)でいいや.
書く.Accepted.

D. Parking Lot

長さLの駐車場があって,順番に車が来たり,出ていったりするクエリが与えられる.
くるクエリの度に,車が停まる場所か,停まれずに出て行くか,を求める問題.
車が来るときは,車の長さが与えられて,
 前bだけ,後ろにfだけはスペースを開くように,最も入り口から近い場所に停める.
また,長さLの駐車場の前後には無限にスペースが開いているが,そこには停められない.
Lは100000以下,車の長さは1000以下,bとfは100以下,クエリの数は100以下.

やるだけゲー…,と思ったけど愚直にやると時間が足りないか?
まぁ,なんとかなるような気もするし取り敢えず書いてみよう.
L+b+fの長さの配列を確保して,本当に愚直にシミュレーションする.
書いた.サンプル合った.WA.
えー.
bが1じゃないとき間違えてた.先頭の座標をb足さないとダメなのになんで1を足してるのやら.
実行時間30msでAccepted.

E. Comb

N*M (1500*1500以下) の整数の書かれた行列Mが与えられる. (整数は絶対値10000以下)
 c1 > c2 < c3 > c4 < … cn
という1以上の数字の列を選んでできる
 M[1][1] + M[1][2] + … + M[1][c1] +
 M[2][1] + M[2][2] + … + M[2][c2] +
  …
 M[n][1] + M[n][2] + … + M[n][cn]
の値の最大値を求める問題.

問題文が意味わからない.
何言っているんだ….
ああ,わかった.DPするだけだ.
書く.Accepted.

F. Hercule Poirot Problem

読んでない.

G. Emperors Problem

読んだけど考えてない.

模擬ICPCアジア地区予選2010 関西オンサイト (この記事を編集する[管理者用])

2010年12月04日11時から5時間,10問.(大阪大学豊中キャンパス)
[ LINK ]

ICPCの参加権がないのに,何故かチーム「京大4」としてソロチームで参加.
まぁ,オンサイトで人に合う機会が基本的にないので,とにかく,楽しかったです.
8問解いた.以下本番での行動順.

入力がファイルからということでfreopenを書く.
 引数の順番がわからない
 全探索してコンパイラに怒られないのを探そう….
  "A.txt"と"r"って逆でもコンパイラ怒ってくれなくないか?
  ちゃんと試そう.
  うまくいかない….
  …
  fopenしてfscanfで読み込むよ!
A問題をのんびり読む.
 読んでる間にもう解いてるチームは解いてるなぁ…,すげー.
 ふむふむ.やるだけ.O(NQ)でクエリごとに入力全部なぞればいいよね.
 まぁ,書くかな.
 書いた.サンプル合った.提出しない.
B問題をのんびり読む.
 さっそくのDP臭.
 同じ場所を2度連続で踏んではいけないのか,ふんふん.(読み間違え)
 右足と左足の位置でvalidかどうかの配列を最初につくって適当にDPすればいいや.
 100000*9*9*9?
 あれ?間に合わなくないか?
 違うや,次に置く場所は与えられるんだから100000*9*9か,右足と左足で2倍だけど,まぁ誤差.
 微妙だけど時間制限20秒とか書いてるし間に合うだろう.
 書く.
 サンプル1個だけ合わない.
 えー.
 あ,同じ場所を連続して同じ足で踏むのはありなのか.
 あれ,じゃ,9×9の状態とか要らなくないか?まぁいいや.
 サンプル通る.提出しない.
C問題をのんびり読む.
 どこからどこへ行くとかじゃなくて,ルートが与えられてるのか.
 態々ダンジョンマップで与えられるとか誰得….
 まぁ,やるだけか.
 使ったポーションの組と,今何歩あるいたか,残りHP,を状態にしてその状態に辿りつけるかどうかBFS….
 いや,状態数多いし.
 残りHPって,今まで受けたダメージと使ったポーションの組から回復量分かるし,状態に含めなくてよろしい.
  嘘!
  オーバー回復すると計算が合わない.
 うーん.
 あれ,単純に,使ったポーションの組と,何歩歩いたかを状態にして,残りHPの最大値を記録しておけばいいだけでは.
 良い.
 書く.
 サンプル合った.提出しない.
D問題をのんびり読む.
 めんどそう.
 取り敢えず次の問題を読もうか.
E問題を読む.
 図と雰囲気から無理ゲーの香り.逃げよう.
H問題を読む.
 問題タイトルと,入出力形式から,これは解けそうな気もする,と思ったから.
 単に,最短路に含まれうる枝を求めて,各ノードに入っていく枝で最もコストの小さいのを使うだけ.
 簡単.書く.
 ダイクストラなので,ライブラリ使えないし,しょうがないけどC++で書く.priority_queue便利だね.
 サンプル通る.なんとなく送ってみる.通った.
自分の席の前の方で,C問題の入力間違えてる疑惑などが囁かれている.
 じゃあ,C問題送ってみましょうか?
  送る.通る.
I問題を読む.
 えっと,オペレーターの最小値.
 オペレーターは最適な対応をする.(と読み間違えた)
 ふむふむ.
 DAGのパス被覆みたいな感じで最大流か何かに落ちる…?
 わからん.
J問題を読む.
 どうみてもDAGのパス被覆.
 じゃあI問題は全く違う方法で解くのかー.
 最大流書くのめんどい.
 しかし,Jが一番楽だよなぁ….
 書く.サンプル通る.サブミットしない.
F問題を読む.
 幾何.だがシミュレーションするだけで難しくないのでは.
 どうやって転がる? 円運動かな? そうっぽい.
 まぁ,適当に書く.
 めんどい.普段はライブラリに頼ってるからなぁ.ライブラリは偉大.
 うーん,流石に,2次元の点の構造体ぐらいは作ったほうが楽っぽいなぁ,書き書き.
 答えが合わない.
 あ,ここ,符号逆っぽい? 逆にする.サンプル合った.
 提出.コンパイルエラー.えー.
 cosとかsin使ってるので怒られてるっぽい?
 前回も同じ怒られ方して,clar投げて,-lm付けてもらったはずなのに….
 ヘルプを頼む.
 C++で提出してくださいとか言われたー.えーw
 C++で提出.WA.
 うーん,合ってそうなんだけどなぁ.
 あ,半径が0の時,回転角が0/0でNaNになってるのか.
 修正.通った.
D問題を書くかー.面倒だけど.
 うーん,どうせ答えって,たかだか4か5ぐらいだよね.
 適当にIterative deepeningでいいや.
 書く.回転の対応をハードコーディング.がりがり.
 書いた.実行.止まらない.
 間違ってた.サンプル通った.サブミット.WA.
 添字違った.サブミット.WA.
 まだ違った.サブミット.通った.
残り問題は無理ゲーに見える.
 E問題とG問題は実装ゲー.書ける気がしない.
 I問題は方針がわからない.
 残り1時間.
 貯めてた問題をそろそろサブミット.
 A問題・C問題・J問題を提出.通った×3.
I問題でも考えようか.
 ん,あれ.
 あ,電話かけてる人の中で一番IDが若い人から処理するのか.
 じゃ,シミュレーションするだけでね?
 2分探索して,O(N^2 log N)ぐらい.
 本当に2分探索して大丈夫? 計算量的にこうだろ.
 書く.
 サンプル合わない.
 2分探索したらダメらしい.
 えー.
 O(N^3)は無理っぽ.
 でも提出.TLE.
 ちょっとコード整理して枝刈りして提出.WA.え?
 書け直すタイミングが1間隔の時,処理ができてなかった.通った.ええええ.
終了.

ソースコード 問題A (C言語)

続きを読む

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

2010年11月30日21時02分から.

Assignment

300-500-1000の変則セット.
少し遅れて部屋に入って,そのまま参加したから途中まで気づかなかったけどたくさんの日本人と同じ部屋だった.

EASY

2つの玉を入れると,1つの玉が出てくる機械がある.
玉の種類はN種類 (50以下) で,どの組み合わせを入れたら,どの種類の玉が出てくるかというリストが与えられる.
複数の玉を持ってるとして,それを1つになるまで任意の順番で機械に放り込んでいく.
最終的に得られる玉が,(入れる順番に依らず)最初持っている玉の情報から一意に定まるかどうかを判定する問題.

rngセットっぽい!
メンバーラウンドはテスターやるとか言ってた気もするが,普通に問題作ってないか…?
さて…,難しい.
全然方針がわからないが….
玉に番号付けて,min(持ってるの1,持ってるの2,…)が最後に残るようになってる場合だけが一意に定まるとか….
そんなわけないな.
単純に,結合法則が成り立てば良いだけとか….
いや,ABCDでAとCを先にくっつける場合もあるから,結合法則だけじゃダメ?
うーん….
部屋内で誰もサブミットしてないなぁ,と思ったらsummary見ると結構瞬殺されてる.
結合法則だけで良いに違いない.
サブミット.
(可換だから結合法則だけで十分)

MEDIUM

サイコロが座標(0,0)に1の目が上に向いてる状態で置いてある.
サイコロを右か上方向に転がすことができる.
途中で1の目が上にならず,座標(x,y)に到達した瞬間1の目が上になるように移動する方法は何通りあるかを求める問題.
xとyは1以上10億以下.

へ….方針が立たない.
サンプル見ると全部答えが2.
xかyかどっちかが1なら答えは0で,そうでなければ答えは2とかでいいのでは….
んなわけないない.
うーん….
取り合えず,この2通りってのはどういうのだ?
1回転がして,そうでない方向に,ずーーーっと転がして,1回・1回・ずーーーっと,みたいな感じか…?
いや,まて,僕は何してるんだ?
こんなの考えたところでわからないし,抜けがあるに決まってるんだから,プログラムで書けよ!
書く.
11*11ぐらいまで全列挙する.
法則が見えるので,その通りに書いてサブミット….

HARD

D個 (100000以下) の点が一直線上に等間隔に並んでいる.
N種類 (40以下) の木を,それぞれD個の点の何処かに植えたい.
各木にはパラメータr[i] (40以下) が定められており,距離r[i]以下に他の木を植えてはいけない.
植える方法は何通りあるか,mod 1000000007で求める問題.

えーっと….
Fenwick treeを使ってO(D*N*log N)のDP…,じゃない.
植える順番を自由に変えれるのか….
うーん.r[i]が40以下という小ささがキーのハズ!
そもそも,植える順番が固定なら,どれだけ無駄に開けれるかを求めて,それをどこの間で消費するか,でコンビネーションで一発で求まる.
いや,それだ.
最も詰めて置いたとき,どれだけ幅が必要なパターンがどれだけあるかをDPで求める.
で,後は,100000まで階乗とその逆数求めて,適当にかけて足せばお終い.
DP…が不明だ….
40!はいらなくても,どうやっても2^40必要に見える.
うーん.
r[i]の大きい順とかにソートしておいて,両端と今の必要幅でDPできないかな….
できそう,書け書け.
全然できそうじゃなかった.

Challenge

300は間違ってたとしても撃墜ケース作れないし…,500だろうなぁ.
開く.合ってそう.次.と思ったらもう皆落とされた後だった.むぅ.

System tests

チャレンジで生き残ってたのは,部屋内全員全部通る.
ちなみに,rngさんはDIV1のwriterで,DIV2のtesterだったみたい?

Appendix

Recent Articles

ブログ内検索

Ads


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