Entries

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

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

Marathon Match 58 (この記事を編集する[管理者用])

SRM 465に出れなかった腹いせ + 58回記念にMM58に参加登録してみた.
終了後にブログに投下する用に,3日分ぐらい参加記録,裏で書いておこうとしたけど,既に覚えてない…,ちゃんと小まめに書いておこう.

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

Source

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

問題概要

円上に山が1000000個以下ある.それぞれの山の高さが与えられる.
2つの山が互いに見えるとは,円周に沿って,2つの山の小さい方より高い山が間にないと見える.
互いに見える山のペアは何個あるかを求める問題.

解法

最も高い山(複数あるかもしれない)で再帰的に区切って考える.
最も高い山を全部見つけるのはsegment tree (RMQ)で見つける.
すると,考えてる区間では,区間の1つ外にその区間内の最も高い山があって,その区間内の最も高い山とそれぞれ見ることができる.
後は,それをコンビネーションを使って計算していく.

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

続きを読む

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

Source

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

問題概要

車の最大スピード,加速度=減速度,進みたい距離,ある点とそこでの最大速度が与えられるので,進みたい距離を進むのに必要な最小時間を求める問題.
初期速度は0,最終速度はいくらでも良い.

解法

スタート→点→残りと2段階に分けて考えれば良い.

1つ目の方針は場合分けして二次方程式を解きながら計算する方法.
スタート→点は
 最大スピードに達成したのち,いくらか走って,減速する
 最大スピードに達する前に減速し始める
 ずっと加速し続ける
の3パターンで,点→残りは
 最大スピードに達成したのち,そのスピードで走りぬける
 最大スピードに達成する前に到着する
の2パターン.

2つ目の方針は,それぞれ2分探索する方法.
以下のコードは両方とも2分探索で求めている.

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

続きを読む

Beta Round #5 C問題 - Longest Regular Bracket Sequence (この記事を編集する[管理者用])

Source

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

問題概要

1000000文字以下の()からなる文字列が与えられる.
その部分文字列で,きちんと括弧が対応付けられたもののうち,最長のものと,その長さの部分文字列が何個あるかを求める問題.

解法

最初0で(が来ると+1,)が来ると-1してできる数列を考える.
例えば
 (()(()))
だと
 12123210
となる.これを深さとでも呼ぶこととする.
括弧が対応付けられてるのと,深さがマイナスにならずに最後0で終わること,は同値である.
ってことで,)が出てきたとき,そこと同じ深さの(のうち,間に自分の深さより小さい深さが存在しないもののうち,もっとも遠いものまでの距離を求めていけばよい.
なので,深さdで)が登場した最初の位置を全部覚えて置いて,そこより深さがマイナスよりに行ってしまった場合,登場した記憶をリセットする,という感じの方針で解ける.
O(文字列の長さ).

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

続きを読む

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

Source

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

問題概要

与えられた文字列を枠で囲んでセンタリングする問題.
センタリングするとき,左右のスペースが等しく出来ない場合は,1つ余分に左に振り分けて,次に同じようなケースが登場したら右に振り分ける,と交互にやる.
行数と各行の文字数はそれぞれ1000以下.

解法

ちゃんと問題文を読んで,きちんとその通りに実装するだけ.

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

続きを読む

Beta Round #5 A問題 - Chat Server's Outgoing Traffic (この記事を編集する[管理者用])

Source

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

問題概要

チャットのログが与えられる.
発言すると,その発言はログインしているすべての人に送られる.
入室退室では,データの転送量はかからないとして,いくらのデータが送られたか求める問題.
1文字1バイト.

解法

誰が発言しているかとか関係なくて,ログインしている人数だけ覚えておけば良い.
やるだけ.

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

続きを読む

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

2010年03月21日01時から2時間,5問.

A. Chat Servers Outgoing Traffic

チャットのログが与えられる.
発言すると,その発言はログインしているすべての人に送られる.
入室退室では,データの転送量はかからないとして,いくらのデータが送られたか求める問題.
1文字1バイト.

誰々が入室したとか書いてあるけど,中にいる人数だけ覚えておけばよいよね.
適当に書く.サブミット.通った.

B. Center Alignment

与えられた文字列を枠で囲んでセンタリングする問題.
枠は最小.
センタリングするとき,左右のスペースが等しく出来ない場合は,1つ余分に左に振り分けて,次に同じようなケースが登場したら右に振り分ける,と交互にやる.

書くだけ書くだけ.
書いた.サブミット,WA.
あれ,よくみたらサンプル2つ目なんか合ってないな….
おおぅ,左右に順番に振り分けるとか読み飛ばしてたよ….
サブミット.WA.
左右に振り分け方,行ごとに変えてた….等間隔にできないと振り分け方を変えるのだよ….
サブミット.WA.
むぅ…?
枠は最小でないといけない,1つは正の長さの行があるって言ってたから,最初と最後に空行があれば消してたんだけど,消さないようにしてみる.
Accept….そういうことだったのか!

C. Longest Regular Bracket Sequence

1000000文字以下の()からなる文字列が与えられる.
対応付けられた括弧になる最も長い部分文字列の長さと,その数を求める問題.

(が現れると+1して,)が現れると-1して,)が現れたとき,自分の値を下回らないように辿り着ける自分と同じ値の(までの距離の最大値を取ればいい.
Segment treeでMRQすれば良いんじゃね?
適当に書く.
サンプルは通ったが.取り敢えずサブミットしてみよう.WA.
適当に色々試すとダメっぽいことが発覚.
ちょっと修正してサブミット.WA.
ケアレスミスあったので修正してサブミット.WA.
なんか,泥沼.
もうちょっと良く考えようよ.頭の中整理して!
取り敢えず,今まで書いてたコードは削除.
うーん,segment treeとか要らなくないか?
普通になぞるだけでできそうだぞ.
自分の深さから)が来たら,出現した記憶をリセットして,自分と同じ深さが以前出現した場所までの距離の最大値をとれば良い.
書いた.サブミット.Accept.

D. Follow Traffic Rules

車の最大スピード,加速度=減速度,進みたい距離,ある点とそこでの最大速度が与えられるので,進みたい距離を進むのに必要な最小時間を求める問題.

スタート→点→残りと2段階に分けて考えれば良い.
スタートから点にたどり着くときにどれだけ加速して良いかは2分探索で求めよう.
がりがり.
後は,点にたどり着いた時の速度を用いて残りの距離を走るのに必要な時間は….
場合分けとか色々面倒な気がするので,これも2分探索でいいや.
書いた.サンプルは1発で通った.
まあ,とりあえずサブミットしてみようよ.Accept.

E. Bindian Signalizing

円上に山が1000000個以下ある.それぞれの山の高さが与えられる.
2つの山が互いに見えるとは,円周に沿って,2つの山の小さい方より高い山が間にないと見える.
互いに見える山のペアは何個ありますか?

うーん?
2つの山が与えられて,その間が見えるかどうかはsegment treeでMRQすれば良い.
が,2つの山の選び方が多すぎてどうにもならない.
あー,取り敢えず,一番大きな山を見つけて,そこで区切ると良さそうな気がする.
そうすると,円形は考えなくて良くて,区間にできる.
区間でも同じで,一番大きい山を見つけてそれで区切って再帰的にやれば良いのではないか!
で,見ることのできるペアは,区間に分けたときの両端(区間の外)と,その区間で最も高い山(複数あるかもしれない)の間は見えるので,n*(n-1)/2とか足していけばよい.
書いた.MLE.
むー,いちいちvector<int>(をC言語で実装した自分のライブラリ)とか使ってるとメモリ足りないのかな….
普通に配列で確保して,上手く使いまわすようにしよう.
サブミット.RE.
ほぇ….あ,再帰の深さが深すぎる気がする.最大で深さ1000000.
スタック使って書きなおす.
サブミット.RE.
ほぇ….どこか配列溢れているのかな…?
適当に配列のサイズを増やす.サブミット.RE.
多分最悪ケースは1 2 3 ... 1000000だよな,作って入れてみる.普通に答え返ってくる.
あれぇ….ランダムでテストケースを作る.segment fault来た.残り15分ぐらい.
何がおかしいんだ?
ミス発見…,同じ区間で2つ以上の山が最大の高さのときに,無限ループで,どんどん配列の先にアクセスしている.
vector<int>は無限に要素をpush_backし続けるコードになっていた.
全部これが原因じゃないかorz
1文字直す.サブミット.Accept.

Result

結果は全完の中では圧倒的大差で最下位.
ICPC形式のコンテストだと,正解数のみしか気にしなくて,取り敢えずサブミットしてしまえ,って感じなのだけど,いくらなんでも酷過ぎるなぁ.
一度しみ込んだ癖は直らないと思うので,取り敢えずサブミットしてしまえで通るようになりたい…,ってのは間違った考え方かなorz
レートはアップ.ようやく黄色くなったよ.

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

Source

ACM/ICPC North America - Mid Central - 2009/2010
LiveArchive 4578

問題概要

双六があって,1ターンで1マス以上sマス以下自由に選んで進める.
各マスに止まったときに得られるポイントが書かれている.負もあり.
合計でtターン以内にゴールしないといけない.
最高合計得点を求める問題.
マスの数は200以下.

解法

DPするだけ.
O(マスの数×制限ターン数×s).

LiveArchive 4577 - Cell Towers (この記事を編集する[管理者用])

Source

ACM/ICPC North America - Mid Central - 2009/2010
LiveArchive 4577

問題概要

電波塔が幾つかある.
ある折れ線上の道を距離1ずつ移動して行った時,どこの電波塔からの電波が一番強く感じられるかを全部求める問題.
1移動して,前と同じ電波塔なら出力しない.(変更したときのみ出力する)
受信する電波の強さは,
 round(電波塔から発する電波の強さ/電波塔までの距離の2乗) (ただしroundは一番近い整数を返す)
道の最終地点は,前のポイントから距離0.5未満であれば無視する.そうでなければ,未知の最終地点を次のポイントに設定する.

解法

やるだけ.

LiveArchive 4575 - Rock, Paper, Scissors (この記事を編集する[管理者用])

Source

ACM/ICPC North America - Mid Central - 2009/2010
LiveArchive 4575

問題概要

2人でじゃんけんを何回かして,それぞれが出した手が与えられる.
どちらが何回勝ったかを出力する問題.

解法

やるだけ.

LiveArchive 4574 - Duplicate Removal (この記事を編集する[管理者用])

Source

ACM/ICPC North America - Mid Central - 2009/2010
LiveArchive 4574

問題概要

数列が与えられるので,連続する同じ要素を1つの要素に置き換える問題.

解法

やるだけ.

LiveArchive 4573 - Black Vienna (この記事を編集する[管理者用])

Source

ACM/ICPC North America - Mid Central - 2009/2010
LiveArchive 4573

問題概要

18枚のカードが有って,3人に5枚ずつ配られる.配られた結果は入力で与えられる.
ある人に,3種類のカードを選んで,そのカードを何枚持っているかを尋ねるということを繰り返す.(どういう尋ね方をしたかは入力で与えられる)
その結果は皆に伝えられる.
誰かが,配られなかった3枚のカードを特定できたターン数を求める問題.

解法

他の人のカードの配り方は72000通りぐらいしかないので,全部覚えて置いて,尋ねた結果が与えられるたびに,不適切なのを外していく.
残りの3枚のカードが同じものしかなくなった人がいれば,そのターンが答え.

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

Source

ACM/ICPC North America - Mid Central - 2009/2010
LiveArchive 4572

問題概要

プログラムとDLLが使用するメモリ量が与えられる.
プログラムを起動すると,必要なDLLが読み込まれる.
プログラムは複数起動するとその分メモリが必要だが,DLLは複数のプログラムから呼び出されていても1個分のメモリしか食わない.
DLLは必要とされるプログラムが全て閉じられたときに,メモリを開放する.
プログラムを起動した,終了した,という列が与えられるので,メモリ使用量最高時のメモリ使用量を求める問題.

解法

やるだけ.

LiveArchive 4571 - Gnome Sequencing (この記事を編集する[管理者用])

Source

ACM/ICPC North America - Mid Central - 2009/2010
LiveArchive 4571

問題概要

要素数3の数列が与えられるので,降順または昇順にソートされているかどうかを判定する問題.

解法

やるだけ.

LiveArchive 4570 - Up and Down (この記事を編集する[管理者用])

Source

ACM/ICPC North America - Mid Central - 2009/2010
LiveArchive 4570

問題概要

ワープゾーンが40箇所以下ある双六を行う.
ワープゾーンは市口と出口が決まっていて,入り口に止まると強制的にワープする.
1ターンで進むマスは1マス以上sマス以下で自由に選べるとして,ゴールするまでの最小ターン数を求める問題.
マスの数は10^9以下.sは6以下.

解法

それぞれのワープゾーンをノードとして,ワーシャルフロイドした.
ワープゾーンの位置口に泊まると強制的にワープしてしまうのが少しトリッキー.

SPOJ 6285 - Another Game With Numbers [NGM2] (この記事を編集する[管理者用])

Source

SPOJ 6285 [NGM2]

問題概要

k個の100以下の正整数が与えられる.
1からnまでの正整数の中で,k個のいずれの倍数でも無い物の数を求める問題.
kは15以下,nは10^9以下.

解法

包除原理.

SPOJ 6256 - Inversion Count [INVCNT] (この記事を編集する[管理者用])

Source

SPOJ 6256 [INVCNT]

問題概要

長さ200000以下の整数列a[k]が与えられるので転倒数を求める問題.
転倒数とは,
 i < j かつ a[i] > a[j]
となる(i, j)の数.数列の要素は10^7以下.

解法

まず座標圧縮して,Fenwick Treeで数えた.

SPOJ 6221 - Increasing Powers of K [INCPOWK] (この記事を編集する[管理者用])

Source

American Invitational Mathematics Examination 1986
SPOJ 6219 [EDIST]

問題概要

kの冪数(1,k,k^2,...)と異なるkの冪数の和からなる集合を考える.
その集合の中で小さい方からN番目の要素を求める問題.
kは3以上9以下,Nは10^200以下.

解法

Nを2進数表示して,a桁目が1ならk^aを足す.
多倍長問題.

SPOJ 6219 - Edit distance [EDIST] (この記事を編集する[管理者用])

Source

SPOJ 6219 [EDIST]

問題概要

2000文字以下の文字列X,Yが与えられるので,XとYの編集距離を求める問題.
編集距離とは,XをYにするために
 任意の1文字消す
 任意の場所に1文字付け加える
 任意の1文字を別の文字に変える
の操作を行わなければならない最小数.

解法

DP.典型問題.

SPOJ 5831 - Permutation Jumping [PERMJUMP] (この記事を編集する[管理者用])

Source

Codechef Snackdown
SPOJ 5831 [PERMJUMP]

問題概要

問題を意訳すると,N次置換で,循環置換の積として表した時,それぞれの循環置換のサイズが2以上K以下となるものの数をmod 1000000007で求める問題.
Nは100以下.

解法

コンビネーションや階乗など組み合わせの数を使いながらDPする.

SPOJ 665 - String it out [SUBS] (この記事を編集する[管理者用])

Source

SPOJ 665 [SUBS]

問題概要

文字列のべき乗を,同じ文字をm回繰り返すものとして定義する.例えば
 (abss)^3 = aaabbbssssss
長さ500010以下の文字列XとYが与えられたとき,
 Y^mがXの部分列 (部分文字列ではない)
となる最大のmを求める問題.

解法

答えに対する2分探索.

SPOJ 660 - Dungeon of Death [QUEST4] (この記事を編集する[管理者用])

Source

SPOJ 660 [QUEST4]

問題概要

120*120のマスの一部の床が壊れている.
1*120の板を横か縦かに置いて,壊れている床を全部覆いたい.
最小で何個の板が必要かを求める問題.

解法

最大流.グラフは
 ソース - 列 - 行 - シンク
みたいな形.

SPOJ 423 - Assignments [ASSIGN] (この記事を編集する[管理者用])

Source

SPOJ 423 [ASSIGN]

問題概要

n人の人とn個のトピックがある.
1人の人に別々の1つのトピックを割り当てる.
それぞれの人にどのトピックが割り当てれるかの表が与えられたとき,割り当て方の総数を数える問題.
nは20以下.

解法

計算時間O(n*2^n)のDP.
制限時間が厳しいように見えたので,ビット演算とか使いつつちょっと頑張ってみたら,制限時間20秒で2.11秒でAcceptされた.

Aizu 2189 - Addition Game (足し算ゲーム) (この記事を編集する[管理者用])

Source

UTPC2009 (東京大学プログラミングコンテスト2009)
Aizu 2189

問題概要

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

解法

どんな順番でやっても結果は変わらないので,適当にシミュレーションする.

Aizu 2188 - Unit Converter (単位変換器) (この記事を編集する[管理者用])

Source

UTPC2009 (東京大学プログラミングコンテスト2009)
Aizu 2188

問題概要

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

解法

文字列系実装問題.がんばる.

SPOJ 6236 - Matches [FERT21_0] (この記事を編集する[管理者用])

Source

SPOJ 6236 [FERT21_0]

問題概要

2つの箱の中に,N本ずつマッチが入っている.
2つの箱を当確率に選んで,その中のマッチを1本取り除くという作業をN回繰り返す.
空箱が得られる確率を求める問題.
Nは1000以下,小数で厳密に求める.

解法

0.5^(N-1)を多倍長を用いて計算するだけ.

SPOJ 1744 - Evaluate the polynomial [POLEVAL] (この記事を編集する[管理者用])

Source

SPOJ 1744 [POLEVAL]

問題概要

999次以下の多項式f(x)の係数が与えられる.
100個以下の整数x1, x2,...が与えられるので,f(x1), f(x2),...の値を求める問題.
係数は整数で,答えは絶対値が2^63-1以下の整数になることが保証されている.

解法

やるだけ.
 ax^3 + bx^2 + cx + d → ((ax+b)x+c)x+d
のように計算すると速い.

SPOJ 63 - Square Brackets [SQRBR] (この記事を編集する[管理者用])

Source

III Polish Collegiate Team Programming Contest (AMPPZ), 1998
SPOJ 63 [SQRBR]

問題概要

2*nの長さの[か]からなる文字列を考える.
k箇所指定されて,そこ場所は[しか置くことができない.
きちんとカッコが対応付けられた文字列は何通り考えられるか?
nは19以下.

解法

DPする.左から置いていくとして,状態は 今何文字目を考えているか×今より左にある[の数-]の数 でO(n^2).

Aizu 2195 - Cat Numbers! (この記事を編集する[管理者用])

Source

UTPC2009 (東京大学プログラミングコンテスト2009)
Aizu 2195

問題概要

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

解法

満たすべき条件を適当に書き下して
 A^2 + (2*10^b-1)A - B^2 + B = 0
を因数分解して
 (A+B+10^b-1)(A-B+10^b) = 10^b(10^b-1)
になるので,右辺を素因数分解して右辺の約数を求める.

Aizu 2193 - The Door into Summer (夏への扉) (この記事を編集する[管理者用])

Source

UTPC2009 (東京大学プログラミングコンテスト2009)
Aizu 2193

問題概要

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

解法

 自分が何もしなくても,猫が初期位置から辿りつけるノードの集合A
 自分が何もしなくても,猫がゴールから辿りつけるノードの集合B
をBFSで求めて置く.
猫が自力でゴールできることがわかったら0を出力して終了.
そうでなければ,自分があけるドア数を距離として,
 自分の初期位置から各ノードiまでの距離d1[i]
 各ノードiから集合Aに辿り着くための距離d2[i]
 各ノードiから集合Bに辿り着くための距離d3[i]
を計算して,d1[i]+d2[i]+d3[i]の最小値が答え.
UTPC本番の時も同じ方針で書いたはずなのにWAってた…,何ミスってたのだろう…(当時のコードはもうない)

Appendix

Recent Articles

ブログ内検索

Ads


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