2017-06

Latest Entries

スポンサーサイト

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

SRM 525 DIV 1


配点は気にせず,950 → 525 → 300 と解いた.全部通ったが,950 の速度が足りず 4 位.

300: DropCoins


M * N のマス目があり,いくつかのマスにはコインが置かれている.4 方向のいずれかを選び,コインを一斉にその方向へ 1 マス動かすという操作ができる.盤からはみ出たコインは落ちる.盤上のコインをちょうど K 個にするための操作の最小回数を求める.不可能ならば指摘.
1 <= M, N <= 30,1 <= K <= 900.

残せる区画は長方形領域.上下から x0 行,x1 行,左右から y0 行,y1 行削るときの最小操作回数は x0 + x1 + min{x0, x1} + y0 + y1 + min{y0, y1} と求まる.全体で O(M^2N^2).

525: Rumor


N 匹のうさぎがいて,A, B 2 つの噂を流す.最初各うさぎは両方とも知っているか両方とも知っていないかのいずれかである.各うさぎは各日に,知っている噂から 1 つを選び,信用してくれるうさぎすべてに伝達する.信用関係は有向グラフとして与えられる.全員に両方の噂が伝わるまでの最短日数を求める.不可能ならば指摘.
1 <= N <= 16.

各うさぎは同じ噂を 2 回流す必要がないので,行動としては A と B のどちらを優先させて流すかの 2 通り.よって 2^N 通りシミュレーションを行えばよく,N 日あれば終わることから各シミュレーションは O(N^2) で実装できる (拡散を計算する際ビット演算を用いる).

950: MonochromePuzzle


N * N (N は偶数) のマス目があり,各マスは白か黒である.i, j を選び,第 i 行と第 j 行を入れ替え,第 i 列と第 j 列を入れ替える,という操作ができる.目標の盤面は,黒いマスが |i - j| = 1 or i + j = N - 1 or {i, j} = {0 , N / 2 - 1} or {i, j} = {N / 2, N - 1} にあるものであり,これに至るまでの操作の最小回数を求める.不可能ならば指摘.
6 <= N <= 50.

グラフの同型を求める問題.置換が与えられたとき操作の最小回数は N - (巡回の個数).
グラフは N / 2 角柱の形状をしている.まずグラフの無向性と各頂点の次数が 3 であることを確認した.N = 8 はすべての置換を試す (実際は N <= 8 でそうした).N != 8 のとき,ある辺が底面の辺か否かはその辺を含む長さ 4 のサイクルが 1 個か否かで判定できる (適当に書いて O(N^4),存在する辺を辿れば O(N^2)).その結果により長さ N / 2 のサイクルを 2 つ見つけ,どちらのサイクルから回るか,どの場所から回るか,どちら向きに回るか,の組み合わせをすべて試し判定する (適当に書いて O(N^3),自己同型は 2N 個なのでちゃんとやれば O(N^2)).

ある四角形の面の 3 点を固定すれば残りの頂点は決まっていく,という方針でも解ける.

平面で考えており,N / 2 角柱である,という言い換えができなかった.また,自己ループの有無を判定するときに u と v を書き間違えたが,十分に条件を重ねて判定を行っていたため最初に影響はなかった.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/51-9c6d3273

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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