2017-07

Latest Entries

スポンサーサイト

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

Yandex.Algorithm 2011 Finals

Onsite と同時に参加.B → C → A で手を付けたが B は解けなかった.A と C は通った.

A: Domino


28 種の標準的なドミノのセットを並べた形状が与えられる (目のみが隠される).これを 2x2 の正方形 7 個に区切ったとき各正方形内では目の数が 4 つ揃っているようなドミノの配置が何通りあり得るか答え,さらにそのうち 1 通りを出力する.
(幅), (高さ) <= 30,解が 1 つ以上存在.

正方形への区切り方は左上から貪欲でよい.正方形への数の割り当て方は 14! / (2!)^7 通りで,最初の出現を順に 0, 1, ..., 7 としてして後で 7! 倍すれば間に合うサイズになるので,あとは探索.

B: Superset


平面上の n 個の格子点が与えられるので,それらを含む m 個の格子点 (m <= 200,000) であって,その中の任意の異なる 2 点 A, B に対して以下のいずれかを満たすようなものを 1 つ求める.
・直線 AB が x 軸または y 軸に平行.
・A と B の bounding box 上 (境界を含む) に A, B 以外の点が存在.
n <= 10,000.

分割統治.中央の縦線を引いて,現れる y 座標の箇所すべてに点を打ってしまえば残りは左右それぞれで満たされればよい.O(n log n) となり足りる.点は set に入れて管理.

定数がゆるい O(n) だろうと思って誤答を投げ続けてしまった.

C: Winning Strategy


ある大学から ICPC finals に無限回参加する.選手は無限に供給されるが,同じ選手は 2 回までしか参加できない.チームは n 人からなる.このうちの i 人が過去参加経験がある場合にメダルを得る確率を p[i] とするとき,派遣戦略を動かしてメダル獲得確率の平均値の最大値を求める.
3 <= n <= 100,0 <= p[0] <= p[1] <= ... <= p[n] <= 1.

平均を考えるので初年度まわりは無視してよく,さらに派遣戦略は周期的になるとしてよい (たぶん).各年度で (過去参加経験あり) - (過去参加経験なし) を足していくことを考えると,この値に対応する -n, ..., -1, 0, 1, ..., n を頂点として x から x + i - (n - i) への重み p[i] の辺があるグラフで最大平均長閉路を求めればよい.O(n^3).

右に行く辺と左に行く辺を選べば閉路が作れることから,i として 2 通り試せば解けることもわかる.

スポンサーサイト

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.

Codeforces Beta Round #76 Div. 1

手を付けた順は D → E → A → B.E はすぐ書いたものは TLE で一旦放置して最後に解いた.Hack は残り 10 分で部屋の E をすべて落とした.4 問通って 2 位.

A: Frames


Windows のエクスプローラ.n 個のアイコンが 1 行に m 個ずつ並んでいる.a 番目から b 番目までを選択したい.1 回の操作で選択できるのは長方形領域で,二重に選択されると選択が解除される.最小操作回数を求める.
n, m <= 10^9.

場合分け.
・a と b が同じ列にあれば 1 回.
・「a が行の先頭」かつ「b が行の末尾 or b = n」ならば 1 回.
・「a が行の先頭」または「b が行の末尾 or b = n」ならば 2 回.
・a の行の 1 つ下が b の行であれば 2 回.
・a の列の 1 つ左が b の列であれば 2 回 (これのみ縦に区切る).
・その他は 3 回.

4 つ目と 5 つ目を忘れていて pretest で何回か WA を出した.

B: End of Exams


n 個のミルクの瓶があり,それぞれに w 入っていて,これらを m 人で等分したい.同じ瓶からは高々 2 人までに配るとするとき,可能かどうか判定し,可能ならその方法を出力する.
1 <= n <= 50,2 <= m <= 50.

「長さ m の棒が n 本あり,それぞれを高々 2 つの整数長さに分割し,m 人に長さ n ぶんずつ配れるか」という問題として考えられる.
n < m かつ n が d = m - n で割り切れないときを考える.m の分け方として (n, d), (n - 1, d + 1), ... が考えられるが,たとえば (n - 1, d + 1) を使うと n - 1 に対応して長さ 1 が必要になるが 1 は作れないのでこれは使えない,といったようにしていくと,(n - kd, (k + 1)d) しか使えないことがわかる.すると各棒からは d で割り切れない断片は高々 1 つしか生じず,m 人には与えられない.よって不可能.
一方,その他の場合は 1 人目から順番に貪欲に使っていけば可能であることがわかるのでそうする.

コンテスト中は証明をせず,貪欲に配り途中で棒が 3 分割されたら不可能,というコードを出した.

C: Azembler


26 箇所のメモリがある.最初,1 つ目のメモリにある数が入っていてそれを n 倍してどこかに保存したい.他のメモリは最初 0.可能な演算は,x <- kz or x <- ky + z (x, y, z はメモリ,k = 1, 2, 4, 8).最短操作数を求めて操作を 1 つ求める.
1 <= n <= 255.

26 個も使わないことはすぐわかるので,今まで作った数をすべて記憶できているとしてよい.また演算は数を減らさないので,昇順に作っていくとしてよい.これをもとに探索する.
作った数の vector からの map で,最短手数と次に作るべき数,を pair にしてメモ化再帰したら通った.
より単純には,iterative deepning + DFS で見つけることもできる.

D: Flags


白・黒・赤・黄の 4 色からなる 1 * n の旗を作る.満たすべき条件は,
・同じ色は隣接しない.
・白と黄は隣接しない.
・赤と黒は隣接しない.
・黒,白,赤あるいはその逆の順に並ばない.
裏返しを同一視するとき,L <= n <= R において何通りあるか mod 1,000,000,007 で求める.
1 <= L <= R <= 10^9.

行列累乗.直前 2 文字のパターンと,「終了した」という状態を考えれば,n <= N の場合の数がわかる.裏返しを除くには線対称な旗の個数を足して 2 で割ればよいが,線対称で条件を満たす旗は必ず n が奇数で,n = 2m + 1 で線対称な旗が条件を満たすことは,中央までの n = m の旗が条件を満たすことと同値なので,これも数えられる.

E: Lostborn


a[1], ..., a[k] は互いに素.n 以下の正の整数であって,a[1], ..., a[k] のいずれでも割り切れないものの個数を求める.
1 <= n <= 10^13,1 <= k <= 100,1 <= a[i] <= 1,000.

包除原理.ただし愚直に DFS を書くと 100^4 以上回るので間に合わない.
包除原理の DFS を呼ぶとき,x / y / z = x / (y * z) (除算は切り捨て) を用いると最初に N で呼んで割り算で再帰していくことができる (互いに素であることを使っている).よってそれ以降の結果は「n について a の i 番目以降で解く」のような形になるので,小さい値についてのメモ化ができる.a をソートしておけばこれで間に合う.

コンテスト中は,「メモ化」という考えに至らず,n が小さいときに (n, i) に関して直接問題を解く,ということを行った (テーブルのサイズの計算量).素数を並べたケースで間に合うことを確認して提出したが,1 と素数たち,というケースで TLE する様子 (ジャッジデータには入っていないと思われる).a に 1 があれば答 0 なのでその処理は加えるべきだった.

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 を使って問題なかった.

Codeforces Beta Round #74 Div. 1

C → A → D → B の順で解き,A の Hack と E を並行させた.E が無理そうなので Hack に戻ったところ B のミスに気づき再提出と B の Hack.C が落ちて 6 位.

(追記)
E に rejudge が入りすべて落とされた模様.4 位になっていた.

A: Robbery


n 個の金庫があり,箱 i にダイアモンドが a[i] 個ある.ダイアモンドを 1 つ (箱または手元) から (箱または手元) に移す操作が,1 秒に m 回できる.1 秒ごとに,a[i] + a[i + 1] の値は変化してはならない.k 秒間で最大何個のダイアモンドを手に入れられるか求める.
1 <= n <= 10^4,1 <= m, k <= 10^9,0 <= a[i] <= 10^5.

n が偶数のとき全体の和が不変なので答は 0.n が奇数のとき,(n + 1) / 2 回の操作でダイアモンドを 1 個得られ,a[2j] が 1 ずつ減るので,floor(m / ((n + 1) / 2)) * k と min{ a[2j] } の小さい方まで取れる.

B: Widget Library


Widget,HBox,VBox がある.HBox は x 方向に,VBox は y 方向に他の物たちを詰め込む,物が定義されたり詰め込んだ様子が与えられたり,余白や詰める間隔が変更されたりするので,それぞれの物のサイズを答える.

入力を読むのが面倒.サイズを求めるときはメモ化再帰でよい.

同じものを 2 個ずつ詰め込んでいくとどんどん大きくなり,int だとオーバーフローする.%lld の注意があったのに忘れてしまい再提出.

C: Chip Play


n * m のマスのいくつかに矢印が書かれている.いずれかの矢印から始め,矢印方向で最も近い,まだ乗っていない矢印マスに移動する.移動回数の最大値と最大となるスタート地点の個数を求める.
n * m <= 5,000.

すべてのスタート地点を試してシミュレーション.次の行き先のリンクを次々張り替えていく (Union-Find の経路圧縮のようなもの).全体で O((nm)^2).

行き先を求めるとき set の lower_bound を使ったら TLE した.

D: Space mines


n 個の球があり,球 i には m[j] 本の針が刺さっている.針は球の中心を端点とする線分で,長さは球の半径の 3/2 倍以下.動く球のスタート地点と速度が与えられるので,最初に球か針に当たるまでの時間を求める.ずっと当たらなければそれを指摘.最初は当たっていない.
n <= 100,m[i] <= 100.

針の長さの条件から,最初の接触は球面あるいは針の端点.よって最初に当たる時間の候補はすべて「点 p との距離が d になる時刻」と書けるので,2 次方程式を解いて正の解を見る.

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.

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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