2017-05

Latest Entries

スポンサーサイト

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

Codeforces Beta Round #73 Div. 1

D → C → A → B の順で解き,E を諦めて hack していたら 4 完最上位の 7 位.

A: Trains


a 分おきに来る電車と b 分おきに来る電車があり,ある時刻には同時に来る.ランダムに出かけるとどちらの電車に乗る確率が高いか求める.ただし両方同時に来た場合は間隔が大きい方に乗る.
a, b は整数,a != b,1 <= a, b <= 10^6.

a < b,gcd(a, b) = 1 としてよい.b が連続で来ることはないので,b に乗る時間は ab 分中 1 + 2 + ... + a 分.これで計算できる.

式を見れば,b = a + 1 のときだけ等しく他は a に乗ることが多いことがわかる.
興味ある時刻が O(a + b) 個しかないので列挙して調べたり時間を進めながらなめたりしてもよい.

B: Vasya and Types


型だけを扱う言語.型に対して後置 * と前置 & という 2 つの演算ができ,* するとレベルが増え & するとレベルが減る.* が優先.void をレベル 0 と考え,レベルが負になるや否や errtype になり,errtype は永久に errtype.
時間順に訪れるクエリが 2 種類.
・typedef A B : 新しい型 B を A (の今の評価値) で定義する.名前が存在した場合上書き.
・typeof A : A の型を void に * をつけて表すか,errtype で出力.

map で管理.void と errtype は最初に入れておいた.負になった瞬間 -INF にしてしまう.

C: Interesting Game


2 人ゲーム.状態は石の山がいくつか.行動は,山を 1 つ選び,それを連続する正整数個の山たち (2 山以上) になるように分ける.行動できなかったら負け.
最初は n 個の石の山が 1 つ.勝敗を判定し,勝てるならば最初に分けるときの山の個数の最小値を求める.
n <= 10^5.

grundy 数が O(n√n) で求まる.300MS 未満だった.

D: Beautiful Road


n 頂点の重み付き無向木が与えられる.n(n-1) 個の頂点の組に対して,それらを結ぶパスを考え,通る辺のうち重みが最大のものすべてに印をつける.印の個数の最大値とそのような辺をすべて求める.
n <= 10^5.

辺 uv につく印の個数は,uv で切ったときに,(u から uv より重い辺を使わず辿り着ける頂点数) * (v から uv より重い辺を使わず辿り着ける頂点数) * 2 となる.よって重い辺を扱うときほど使う辺がたくさんなので,軽い辺から順次付け足す方針を考えることになる.
重みが小さい辺から順に,同じ重みの辺はまとめて処理する.軽い辺によって union find していきグラフを縮約しておけば,新しく追加する辺だけからなる森を考えて,DFS を走らせればよい.全体で O(n).

デバッグ出力を消し忘れたまま提出して 1WA.

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/11-cc68295f

この記事にトラックバックする(FC2ブログユーザー)

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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