2017-11

Latest Entries

スポンサーサイト

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

Codeforces Beta Round #77 Div. 1

B → C → E → Hack (4 成功 2 失敗) → A の順でやった.D は考えなかった.全部通って 4 位.

A: Hockey


n 個の禁止文字列と文字列 w が与えられる.w のうち禁止文字列の出現 (大文字小文字無視) と 1 回以上被る場所について,その文字を異なる文字 (大文字小文字は保つ) に書き換える (書き換えは一斉に行う).書き換え後の文字列について,文字 letter が最も多く現れるもの,同じならば辞書順で最小のものを求める.
n <= 100,(文字列の長さ) <= 100.

文字列とのマッチの判定は愚直に.文字ごとに独立に変えてよいので,letter か 'a' か 'b' かにこの優先順で変える.

B: Lucky Numbers


10 進法で書いて 4 と 7 を同数含みその他の数字を含まない正の整数を super lucky と呼ぶ.n 以上の最小の super lucky な整数を求める.
1 <= n <= 10^100000.

まず,n が奇数桁の場合,あるいは 7..74..4 より大きい場合,n の先頭に 0 を付けて桁を増やす.
その後は先頭から 1 桁ずつ,4 を使えるなら 4,使えないなら 7 としていく.下準備として,「ある場所から見ていき最初に 4 (7) と異なる箇所」を配列として持っておけばよい.

別解として,下の桁で負ける可能性は無視して並べて,失敗したら最後に使った 4 を 7 に変えてもう 1 回行う,という方法がある.繰り上がりが 1 回までなので計算量も問題ない (たぶん).

C: Volleyball


頂点数 n,辺数 m の無向グラフ (距離が重み) として表される街がある.各頂点にはタクシーがいて,「合計距離 t まで使えてコスト c」という情報が与えられる.タクシーはいまいる頂点から高々 1 度しか利用できない.出発地点から目標地点までの最小コストを求める.到達不可能ならば指摘.
n <= 1,000,m <= 1,000.

まずは各頂点から Dijkstra を行い全頂点間最短路を求め,各頂点からタクシーの行き先を O(N) 通り試す Dijkstra.

E: Lucky Country


頂点数 n,辺数 m の無向グラフが与えられる.辺を 0 本以上何本か加えて,いずれかの連結成分のサイズを桁が 4 か 7 のみからなる数にしたい.最小本数を求める.不可能ならば指摘.
n <= 100,000,m <= 100,000.

もとのグラフの各連結成分のサイズを求める.これらの中に異なるものは O(√n) 通りしかないので個数制限付きナップサック DP.O(n √n log n) で解いた (丁寧に解析すればこれより小さく抑えられるかもしれない).

h 個まとめたものを考えるとき DP の値に +h ではなく +1 しかしておらず 1WA.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/39-125c50f5

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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