はまやんはまやんはまやん

hamayanhamayan's blog

TCO 2017 Round 1A 問題と解説

問題

Easy. PingPongQueue

M人の参加者がいて、それぞれ力skills[i]を持っている。
キューには0さんからM-1さんまで順番に入っている。
以下のルールでゲームをする時、K番目のゲームの勝者と敗者の力の大きさを答えよ。
1. 2人の参加者が揃っていないなら、キューの先頭から取ってくる
2. skillsの大きい方が勝ち
3. 負けた方はキューの最後尾に並ぶ
4. N回連続で勝った場合は、負けた人の後にキューの最後尾に並ぶ。さもなければ、場に残る

Med. CheeseSlicing

(A,B,C)の直方体のチーズがある。
これを上手くスライスして、良いスライスをいくつか作る。
良いスライスとは最も短い辺の長さがS以上のスライスである。
最適にスライスしたとして、できた良いスライスの面積(最も長い辺*中くらいの辺)の総和の最大を求めよ。

Hard. PolygonRotation

(0, ymax)から始まり、(o, ymin)を含む凸包が与えられる。
この凸包をy軸を回転軸として回転させたときの体積は?

以下、解説

続きを読む

AtCoder Grand Contest 012 解説

http://agc012.contest.atcoder.jp

A. AtCoder Group Contest

http://agc012.contest.atcoder.jp/submissions/1194360
考察すると、降順で並べた時の偶数番目(2番目,4番目,6番目…)を選択していけば良いと分かる。
それを取る。
Atcoder300点はそんなにつらい実装を要求しないので、簡単なやり方があるんじゃないか的な。

B. Splatter Painting

http://agc012.contest.atcoder.jp/submissions/1197833


辺に着目して計算していくのは全く気づかなかった。頭いい。

部分点解法(partial関数)
各クエリについてdfsで塗っていく(木っぽくしてるけど、木っぽく探索しても大丈夫)。

想定解法(sol関数)
dp[v][d] := 頂点vから距離dで塗られる{クエリ番号, 色}
を更新していく。
まずクエリはdp[V[i]][D[i]] = {i + 1, C[i]}として入力していく。
dp[v][d]をdを10から1まで降順で処理していく。
各dについて以下の処理を行っていく
1. 全ての頂点について、既に塗られている色を距離d-1に伝搬する
2. 全ての辺について、隣接する頂点について距離dの色を距離d-1に伝搬する
dpにクエリ番号を含めることで塗られた時間を保存しておき、最新の色を塗る。
答えはdp[v][0]のsecond

C. Tautonym Puzzle

http://agc012.contest.atcoder.jp/submissions/1199007
こんな方法思いつくかよって感じだけど、傾向ってあるんだなぁ


説明は難しいので解説放送を見よう。
相変わらず、とても分かりやすい。www.youtube.com

1 2 3 4 ... 80 と数列を作っておく。
その後ろに順列を作るが、その順列の単調増加列の個数が、今回求めたい個数となる。
よって、問題が単調増加列がN個である順列を求める問題となる。

以下のように構成する

{} -> 1個(0個)
{1} -> 2個(1個)
{1 2} -> 4個(3個)
{3 1 2} -> 5個(4個)
{3 1 2 4} -> 10個(9個)
最初を1にすると、前に追加で+1, 後ろに追加で*2となる

最初の空集合は0個ではなく1個にしておくと計算しやすいので、1から+1と*2をつかってN+1を作るように構成していく。
前に後ろに追加するのでdequeを使うとよい

D. Colorful Balls

http://agc012.contest.atcoder.jp/submissions/1199141
玉を頂点と考え、交換可能な玉の間に無向辺を貼る。
この辺で成分分解をして(merge関数)、成分分解毎に玉の組合せを計算して合わせる(count関数)と答え。

count関数ではmerge関数で連結成分でマージしてあるUnionFindを見ながら交換パターンを全て求める。
同じグループであればどんな形にでも変形できるので、「同じものを含む計算」(ぐぐると分かる)をする感じで計算していく。
以下、merge部分の愚直解と最適解。

愚直解
全ての2頂点間について同色・異色で辺が張れるかチェックする。
O(N^2)で当然間に合わない

最適解
まず、処理に移る前に色について玉をまとめて、重さで昇順ソートしておく

1. 同色の辺
最も軽い玉と他の玉の間の辺だけ考えれば良い。
2. 異色の辺
全ての色から最も軽い玉だけを集めた時に、その中でも最も軽い2つの玉だけ考える。
この2つの玉から任意の玉との間の辺だけ考えれば良い。

解説動画と合わせた解答なので、動画を見つつ、ソースを見つつ考えると分かるかと思います。

Codeforces Round #407 問題と解説

http://codeforces.com/contest/788
http://codeforces.com/contest/789

A. Anastasia and pebbles

K個だけ入るポケットが2つある。
N種類の小石がそれぞれW[i]個ある。
1日に各ポケット

  • 最大K個だけ入れられる
  • 同じ種類しか入れられない

最短何日で全て回収できるか

B. Masha and geometric depression

B[1], Qが与えられる。
B[i] = B[i - 1]*Qで計算される。
B[1]から初めてL <= abs(B[N+1])となるまで数列を列挙する。
M個のダメ数A[i]がある。
B[1]~B[N]の中でダメ数ではない数は何個あるか。
もし、数列が無限に列挙されるならば、"inf"と答える。

C. / A. Functions again

N要素の数列Aが与えられる。
f(L,R) = sum{i=L...R-1}(abs(A[i] - A[i + 1]) * (-1)^(i-L))
任意のL,Rの中でf(L,R)の最大値を求めよ。

D. / B. Weird journey

N頂点M辺の無向グラフがある。
このグラフ上で

  • M-2辺は丁度2回通る
  • 2辺は丁度1回通る

ように経路を良い経路とする。
良い経路は何通りあるか。
なお、経路で使った辺の多重集合が同じであれば同じ経路とみなす。
自己辺はあるが多重辺は無い。

E. / C. The Great Mixing

K個の数A[i]がある。
A[i]を重複を許して任意個選択する。
分母を(選択した個数)*1000
分子を選択したA[i]の総和
とした分数がN/1000と等しくなるための選択の個数の最小値を求めよ。

以下、解説

続きを読む

CSAcademy #22 問題と解説

https://csacademy.com/contest/round-22/

問題

Triangle Count

N本の棒があり、長さが分かっている。
この中から任意の3本を選んで三角形が作れる組合せは何通り?

Frequency Exception

N要素の配列がある。
この中で配列の中に現れる回数が他と異なる要素が1つある。
それを探せ。

Black Shapes

H(=N)行W(=M)列のマス目がある。
それぞれ白(=0),黒(=1)で塗られている。
マス目の中の白マスをどれか1つだけ黒に塗って、黒を最も多く隣接させる。
最大、何個黒を隣接させられるか。

Distinct Rotations

0と1と?から成る文字列がある。
?に0か1を入れて回転させた時の周期が最小になるものを答えよ。
例)010010ならば 010010 -> 100100 -> 001001 -> 010010なので周期3

Limited Swaps

素数Nの配列Aが与えられる。
この配列の隣接している要素を最大K回スワップして、辞書順最大となる配列A'は?

以下、解説

続きを読む

Educational Codeforces Round 18 問題と解説

http://codeforces.com/contest/792

問題

A. New Bus Route

N点の座標が与えられる。
任意の2つの座標の最短距離とその最短距離となる2つの座標のペアの組合せを求めよ。

B. Counting-out Rhyme

N人が円状に昇順で並んでいる。最初リーダーを1さんとし、以下の操作をK回行う。
1. 現在のリーダーの次のK番目の人を削除する
2. 削除した次の人をリーダーにする
i回目に削除した人をすべて答えよ。

C. Divide by Three

ある数Nが与えられる。
その数の任意の位を削除することでリーディング0でない3の倍数を作る。
削除すべき位を最小化したときの答えは?
3の倍数にできないならば-1

D. Paths in a Complete Binary Tree

N頂点の完全二分木がある。
この木は「左のノードが全てラベル付けされたら自分をラベル付けして右のノードをラベル付けする」
というルールで頂点が割り当てられている。
これに対し、Q個の以下のクエリを答えよ

  • 初期頂点uがある
  • 操作Sがあり、'U'は親ノードへの移動、'L'は左側の子ノードへの移動、'R'は右側の子ノードへの移動を指す
  • 移動後の頂点を答えよ
E. Colored Balls

N種類の色の箱がある。
各箱には同色のボールがA[i]個入っている。
以下の条件をみたすようにボールをグループ分けするときのグループ数の最小値は?
1. 1つのグループには1色のボールしか入らない
2. 任意の2つのグループのサイズの差は1以下である

以下、解説

続きを読む

Topcoder SRM 711 問題と解説

Div1 https://community.topcoder.com/stat?c=round_overview&rd=16880

問題

Div1 Easy. ConsecutiveOnes

整数N,Kがあり、以下の性質を満たす最小のmを答えよ。
1. N ≦ m
2. mを2進数にすると少なくともK個連続した1がある

Div1 Med. OrderedProduct

素数を昇順で格納した配列Pがある。P[0]=2,P[1]=3,...
個数Nの配列Aが与えられる。
X = P[0]^A[0] * P[1]^A[1] * ... * P[N-1]^A[N-1]とする。
Xを因数分解して列とするときの組合せは何通りか(mod10^9+7)
例)X=12なら(2,6),(3,4),(4,3),(6,2)の4通り

以下、解説

続きを読む