2017-05

Latest Entries

スポンサーサイト

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

Codeforces Beta Round #75 Div. 1

C → B → A → D の順で解き (それぞれ次の問題を読まずに解いてみた),E を読んで残り 20 分だったので Hack に.l と 1 の見間違いにより 2 失敗.4 問通って 6 位.

A: Newspaper Headline


文字列 s1 と s2 が与えられる.s1 の n 回連結の部分列 (連続でなくても良い) で s2 が作れるような最小の n を求める.存在しなければそれを指摘.
|s1| <= 10^4,|s2| <= 10^6,文字はアルファベット小文字.

s1 の ∞ 回連結から貪欲にとっていけばよい.その際,位置とアルファベットから次の位置を与えるテーブルをもっておけば O(s2).

B: Queue


並んでいる n 人の年齢が与えられる.それぞれの人について,自分より前に並んでいる自分より若い人で最も前に並んでいる人が,自分より何人前に並んでいるか求める.
N <= 10^5.

年齢の低い順に,「今まで処理した人で最も前に並んでいる人の場所」を持っていけばよい.同じ年齢の人はまとめて処理したのちに最前の更新.

C: Ski Base


n 頂点の無向グラフを考える.辺が 1 本ずつ m 本追加されていくので,各時点での,「回路いくつかの和集合で書ける辺の空でない集合」の個数を mod 1,000,000,009 で求める.
n <= 10^5,m <= 10^5.

空の場合も含めて考えると,辺を加えたとき,連結成分の個数が変わらなければ答は 2 倍される.これは,求める集合はサイクルたちの xor 和により書けて,サイクルの xor 和について F_2 上線形独立なサイクルの個数の最大値はサイクルに含まれる辺を追加したとき 1 増えるため.

D: Grocer's Problem


n 元の置換が与えられる.5 元以下の置換を最小回数行って id にしたい.手順の 1 つを出力する.
n <= 10^5.

まず巡回置換の積に書き,サイズ 5 の巡回は削ってサイズ 2, 3, 4 に帰着してよい.同じ巡回を一度に処理すべきでないケースは 3, 3, 3 のみ (2 回でできる) なので,3, 3, 3 をいくつ作るかを安全を期して O(n) ですべて試した.
4 を 2, 3 として処理しようと考えたがそれらがくっつくと出力が厄介なのでやめた.

E: Igloo Skyscraper


n 要素の配列 a, b と q 個のクエリが与えられる.クエリは l, r, t の組で,l <= x <= r であって a[x] + b[x] * t が最大である x を 1 つ求める,というもの.
n <= 10^5,q <= 10^5.

メモリが O(n log n) の segment tree を作る.各区間について,t に対しての 1 次関数たちの最大値は折れ線になるので,それをマージしていく.
交点については,double を使って問題なかった.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/27-d81832d5

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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