SnackDown 2016 Online Elimination Round
SnackDown 2016 Online Elimination Roundにe-monさんと出た
361位でTシャツラインにあと61位届かなかった
VCake
- 解法
制約から、切るのは2回だけなので、切り方は2回に対して[縦に切る, 横に切る]の2通りあるから、計4通りある。
また、どの大きさのケーキから切り出して行くかで、3!=6通りあるので、4*6=24通りについて全て調べていけばよい。
- コード
Chocolates for Everyone
- 問題
初項と公差が正の整数で、等差数列のN項の和がCになるような列について、初項と公差を1つ答えよ
もしなければNoと出力せよ
- 解法
等差数列の初項をa0, 公差をdとおくと、等差数列の和の公式より、N*(2*a0 + (N-1)*d)/2 = Cが成り立つ
よってまず、2*C%N=0が必要となる
式を整理すると、2*a0 = 2*C/N - (N-1)*d
左辺が偶数でないとダメなので、dを2*C/Nと(N-1)の偶奇によって場合分けして考える
- 2*C/Nと(N-1)がともに偶数、もしくは奇数のとき
- dは何であっても右辺は偶数になる
- ここでa0が正の整数になるためには、dはできるだけ小さい正の整数であったほうがよい
- よって、d=1として、a0が正になるか計算すれば良い
- 2*C/Nが偶数、(N-1)が奇数のとき
- 右辺が偶数になるには、(N-1)*dが偶数でないといけないので、dは偶数
- (i)の場合と同様、dはできるだけ小さい正の整数であったほうがよいので、d=2として、a0が正になるか計算する
- 2*C/Nが奇数、(N-1)が偶数のとき
- 右辺は偶数にならないので、条件を満たす等差数列は存在しない
- コード
Coloring A Tree
- 問題
N頂点の木が与えられ、木の各頂点をK色塗ることを考える
同じ色を塗ったあとの木を、違う色が接続している枝で切断したときに、同じ色の頂点が全て連結になるような塗り方は何通りあるか
- 解法
切断の仕方と、切断してできたグループの色塗り方を考えるだけでよい(入力が木なので、切断する枝が決まれば、切断後のグループが一意に決まる)
よって、i種類の色を使うときは、N-1の枝からi-1本選んで切断し、K種類からi個の色を塗るので、このときの場合の数は(N-1) C (i-1) * K P i 通りであり、これを、i=1からi=min(N, K)まで和をとれば良い
- コード
感想と反省
- チーム戦難しい
- チームメイトに問題を任せる判断とか、問題概要の伝え方とか
- 問題概要を伝えるのが苦手っぽい
- わかりやすくなるように、と思ってやってはいるものの、いくつか抜け落ちたりしていることがあった
- e-monさんに聞いた問題は自分で殆ど読まずに解いてたし、なんとか上手く伝えられないか考えたい
- そのためにブログ書いてるはずなんだけど、おざなりになったりすることもあるし、かといって時間かけすぎるのも厳しいし、なんとも...
Yandex.Algorithm 2016 Online Round 2
Algorithm 2016 — Yandex.Algorithm 2016 Online Round 2 — Enter
午前3時からという日本人を潰しにかかったような時間だったけど、2完242位だった
これで総合4完327位なので、頑張ればTシャツいけそう?
A. Role Distribution
- 解法
問題文の例では長い部分文字列を作れば良いようにも見えるが、結局各文字が各役者のセリフに含まれているかが問題となる。
よってS[i]が各役者のセリフに調べているかどうかを調べて、coolさ最小のactorを選べばよい。
もしどの役者のセリフにもS[i]が含まれてなければ、-1を出力して終了する。
- 計算量
O(SM log w)
- コード
B. Binary Representation Game
- 解法
LからRまでの、各ビットに合計何個1が立っているかを求めれば、各ビットに対して、(ビットが立っている)*2 < L-R+1 ならば、そのビットを1に、それ以外はそのビットを0にすれば、期待値が最も大きくなる。
0からNまでを2進数表記したときの、各ビットに合計何個1が立っているかはlog(N)(=Nのビット数)で求めることができる。
参考: SRM543 div.1 250 EllysXors - n-knuu's logs
- 計算量
O(log^2 R)
- コード
AtCoder Beginner Contest #039 (Nim-langの練習帳)
いつも通り、Nim-langでABCに出た
Nim-lang: index - Nim Programming Language
Nim-lang Tutorial: Nim Tutorial (Part I)
Nim Standard Library: Nim Standard Library
A - 高橋直体
2 * (A*B + B*C * C*A)
B - エージェント高橋君
なので、1から177まで調べればよい。
C - ピアニスト高橋君
12個分(1音階分)調べれば一意に決まるので、ドから見たとき、レから見たとき、と順に調べていけばよい。
D - 画像処理高橋君
ある画素の8近傍全てが黒であるか、範囲外ならば、収縮前の画像のその画素は黒であってもよい。よって、その条件を満たす画素を黒にして実際に収縮した場合に、与えられた画像と矛盾がなければpossibleとなる。
感想
計算量を殆ど考えなくていい感じのABCらしい問題だった
Dの解法を思いつくのにちょっと時間がかかってダメな感じだった
SRM552 div.1 250 FoxPaintingBalls
練習会で1完だった
問題
TopCoder Statistics - Problem Statement
リンク先の図のように、ボールを並べてN段のtriangleにR,G,Bの3色で、ボールどうしで色が隣り合わないように色を塗る(図はN=3)とする。
R, G, Bで塗れる回数がそれぞれ決まっているときに、最大何個のN段のtriangleを作ることができるか?
制約
0 <= R, G, B <= 10^18
1 <= N <= 10^9
SnackDown Online Pre-elimination round A
SnackDown Online Pre-elimination round Aにe-monさんと出た。
1000位以上が次のOnline Elimination roundに進めて、204位だったので進めた。
Art(MAKEART)
e-monさんが読んで解いたので知らない
N different palindromes(NDIFFPAL)
僕が読んで書いた
- 問題
文字列Sの部分列S[i..j]が回文となる組(i, j)の個数がN(10^4以下)となるようなSを答えよ
テストケースT個(10^2以下)
- 解法
"abc...xyzabc..."と順番にアルファベットをN個出力すれば、(1, 1), (2, 2), ..., (N, N)のみが回文となる。
O(TN)
- コード
Sharing Candies(GIVCANDY)
e-monさんが読んで、僕とe-monさんで解法を考えて、e-monさんが書いた
- 問題
AlvinはA個の、BertoはB個のキャンディを持っている。AlvinにC個ずつのキャンディの袋を、BertoにD個ずつキャンディの袋を、それぞれにいくつか与えることで、AlvinとBertoの持っているキャンディの個数の差の絶対値を最小にしたい。そのときの最小値を求めよ。
- 解法
Alvinにx袋、Bertoにy袋与えたとする。このとき、答えがK(>=0)の場合、|(A+Cx)-(B+Dy)| = K、つまりCx-Dy=K+B-AもしくはDy-Cx=K+A-Bとなる。
gcd(C, D)=1のとき、方程式Cx-Dy=1は必ず解を持つので、K=0とできる。
つまり、Cx-Dy=B-Aは、A<=Bのとき必ずx,yが0以上となる解を作れる。A>Bのときは、Dy-Cx=A-Bを考えれば同様に可能。
gcd(C, D) = g(>1)のとき、Cx-Dy=K+B-Aが解を持つには、(K+B-A) % g = 0にならなければいけない。よって、K=min((B-A+g)%g, (A-B+g)%g)が答えになる。
- コード
Longest Increasing Subsequences(MAKELIS)
僕が読んで、e-monさんが考えて解いた
- 問題
LISの総数がKになるような、長さNの順列(但しNは100以下)を求めよ。
- 解法
素因数分解してうまく埋めるとできるらしい(また後で書く)
Chef and his study plans(SUBSEG2)
僕が読んで解いた
- 問題
開区間[start_i, end_i]がN個(10^5以下)が与えられる。
このとき、以下のクエリがQ個(10^5以下)が与えられるので、それに答えよ
クエリ: 開区間[plan_start_j, plan_end_j]が与えられるので、その区間で区間スケジューリング問題を解け
1 <= start_i <= end_i <= 10^6
1 <= plan_start_i <= plan_end_i <= 10^6
Time Limit: 0.75s
- 解法
区間スケジューリング問題なので、ある値tが与えられたときに、次にどの区間を取ればいいかが一意に決まる。
よって、1<= t <= 10^6について、時刻tで次の区間をとったときの終わりを記録しておけばよい。
これは、時刻tでとる次の区間は、時刻t-1で取る区間よりも前にならないことを利用して、尺取り法っぽくやれば線形でできる。
ただ、クエリが与えられるたびに、そのまま次のものを辿って数えていくと最悪O(QN)になる。
そこで、時刻tから2^k個、区間をとったときの終わりの時刻を求めておいて、クエリのたびに二分探索すればlogオーダーに落ちて間に合う。
この操作は蟻本のLCA*1のところに書いてある操作(ダブリング)を真似すればよい。
- 計算量
最大の時間をTとすると、O(T + T log T + Q log T)
(座圧すると、O(T)=O(N+Q)になるのでもう少し速くなりそう?)
- コード
感想
チーム戦楽しい
e-monさん、用事があるっぽかったのに3問も任せてしまって申し訳ない感じだった
*1:第二版 p.293
Codeforces Round #355 Div.2 A. Vanya and Fence / B. Vanya and Food Processor
Dashboard - Codeforces Round #355 (Div. 2) - Codeforces
4問解くか、3問早解きか、みたいな回だった
A. Vanya and Fence
- 問題
数列Aの各値を、H以下なら1、Hより大きいなら2と変換する。変換後の和を求めよ。
こんな問題文だからreadforcesとか揶揄されるんだ
- 解法
implement
- コード
B. Vanya and Food Processor
- 問題
ジャガイモを高さhまで入れられて分速kセンチ潰せるミキサーで、ジャガイモを潰すことを考える。
高さA_1, ..., A_nのジャガイモが与えられる。このとき、1分で行える操作は以下。
- ジャガイモをA_1から順番に入れられるだけ入れる(ただし、高さがHを超える場合は入れられない)
- ジャガイモをKセンチ潰す
これを繰り返して、全てのジャガイモを潰したとき、何分かかるか?
- 制約
1 <= n <= 10^5
1 <= k <= h <= 10^9
- 解法
単純にシミュレーションすると最悪O(h)かかってTLEする(ex. K=1, h=10^9, A={10^9, 10^9, 10^9, ...})ので、次のものを入れるためにはどこまで潰す必要があるかを式を立てて求める。
潰すのにかかる秒数と今の高さをそれぞれt, nowと置くと、以下の図の式が成り立つ
これをtについて解くと、t = ceil((A_i + now - h) / k) となるので、O(n)で答えを求めることができる。
- コード
- 感想
潰すタイミングをどこで書けばいいか迷って、かなり時間をとってしまった。
AOJ1241 Lagrange's Four-Square Theorem
Lagrange's Four-Square Theorem | Aizu Online Judge
- 問題
整数Kが与えられるので、4個以下の数の二乗和がちょうどKになるような数の組の個数を求めよ
- 制約
K < 2^15
テストケースの個数 T < 2^8
- 解法
2乗して2^15以下となる最大の数は181なので、下のように4乗ループを回せばよい
- コード
- 感想
最初map
Yandex.Algorithm 2016 Online Round 1
Algorithm 2016 — Yandex.Algorithm 2016 Online Round 1 — Enter
2完523位だった
Tシャツ圏内が3回合わせて512位なので、3回きっちり出て、解ける問題を解けばなんとかいけそうかなあという感じ?
ただ残り2回が、午前3時からと午後4時からという、日本人を潰しにかかったような時間なので、忘れないように出たい
A. Cheese
- 解法
場合分けすればOK。境界値がサンプルで与えられているので親切。
- コード
Opencup
- 問題
1000チームが出場する試合があり、30位まで点数が与えられる。現時点での上位10チームの自分のチームとの得点差が与えられるので、次の試合で上位10チームがどのような順位になっても、10チームのうちのいずれかより点数が高くなるようには次の試合で最低何位を取らなければならないか?(同点の場合はランダムに順位が振り分けられるものとする)
もし何位をとってもダメな場合は0を出力せよ。
- 解法
上位10チームの最低得点は、現時点での得点差が小さいほうから順に1位, 2位, ...と取っていった場合である(ただし自分のチームと順位が被る場合は一つずらす)。
よって、自分のチームが1位だったとき, 2位だったとき, ..., 30位だったとき, 31位以下だったときを順に調べていき、もしk位になったときに、min(10チームの点数) >= (自分のチームの点数) となったら、31位以下でもmin(10チームの点数) < (自分のチームの点数)となる場合は1000を出力する。
- コード
- 感想
コーナーケース〜〜〜〜〜〜
SRM551 div.1 250 ColorfulChocolates
練習会に出て1完。Medは解けそうでダメだった。
問題
数列が与えられる(長さ50以下)。隣どうしをswapして良い最大の回数が与えられるので、同じ数が連続する長さを最大にしたい。最大の長さを求めよ。
解法
一箇所を固定してシミュレーションすればよい。
具体的にはある位置を決めたときに、左と右を1個ずつ見ていって、swap回数がなくなるまで、近い順に貪欲に決めた位置までswapしていけばよい。
ただし、1個つめると、次に同じ側で詰めるときはswap回数が1少なくなることに注意。
以下のコードのように左・右と1個ずつ見ていっても良いが、移動させる距離を列挙してソートする解法の方が実装が楽(hamkoさんの解法)。
計算量
以下のコードはO(N^2)
ソートする手法はO(N^2 log N)
コード
感想
左右から箱を詰めていくシミュレーションの問題、よくありそうなので、距離でソートする実装は心に留めておきたい
SnackDown Online Qualifier 2016
SnackDown Online Qualifier 2016にe-monさんと出ました。
1問解けば次に進めますが、僕とe-monさんで2問ずつ解きました。
Kitchen Timetable
僕が解いた。
- 問題
各人が料理を始めるタイムテーブルA_1, ..., A_N(A_1 < A_2 < ... < A_N)と、料理の完成にかかる時間B_1, ..., B_Nが与えられる。ある人が料理を始めてから、次の人が始めるまでに料理が終わらない場合は、途中で打ち切られ、次の人が料理を始める。
最後まで完成できる人は何人か?
- 解法
Aから料理できる時間を計算してBと比較するだけ。O(N)
- コード
Better Maximal Sum(MMSUM)
e-monさんが解いた
- 問題
数列Aから1つだけ要素を取り除けるときの、Aの最大の部分連続列の和を求めよ。
- 解法
{S[i], E[i]}を、{iで始まる, iで終わる}最大の部分連続列の和とすると、答えは、max{max{E[i], E[i-1]+S[i+1]} for i in 1 to N}で求められる。
{S[i], E[i]}に関しては、数列Aを{後ろから, 前から}見ていって、{S[i]=max(A[i], S[i+1] + A[i], E[i+1]=max(A[i+1], E[i]+A[i+1])}と更新していくことで、O(N)で求められる。
- コード
K-good Words
- 問題
アルファベット小文字の列Sが与えられる。各文字種x_1, ..., x_nごとに数を数えたとき、任意の文字種x_i, x_jに対して、abs(S.count(x_i) - S.count(x_j)) <= Kが成り立つとき、SはK-goodな単語であるとする。SとKが与えられたとき、Sから文字をいくつか削除してK-goodにしたいとき、最小何文字削除すればよいか?
- 解法
文字種ごとのカウント数の列をソートしたものをc_1, c_2, ..., c_nとする。このときの答えは、あるc_iを決めたときにc_1, ..., c_(i-1)に対応する文字列を全て削除し、j > i かつ c_j - c_i > Kとなるc_jを全てc_i + K以下にした場合の削除した文字数が最小になるときの削除した文字数である。今回はnが26以下なので、O(n^2)などで容易に求められるが、尺取り法でO(n)でも求められる。
結局はO(|S| + n log(n) + n)
- コード
AOJ1356 Decimal Sequences
- 問題
Decimal Sequences | Aizu Online Judge
- 解法
nが10^3以下なので、作れる数はn*(n+1)/2 < 10^6個となる。よって、予め作れる(6桁以下の)数を作って、setなどで持っておき、0から順に調べていけばよい。*1
- コード
*1:n*(n+1)/2個の数を全てstringで作るとMLEする
AOJ2639 Yamanote Line
- 問題
Yamanote Line | Aizu Online Judge
- 解法
1周60分なので、60回起きて寝れば、必ず最初の状態に戻る。よってシミュレーションをして、起きてる間に到着することがあればそれを出力し、60回起きて寝てもダメなら、-1を出力すればよい。
- コード
AtCoder Beginner Contest #038 (Nim-langの練習帳)
いつも通り、Nim-langでABCに出た
Nim-lang: index - Nim Programming Language
Nim-lang Tutorial: Nim Tutorial (Part I)
Nim Standard Library: Nim Standard Library
- A - お茶
末尾がTに等しいかを見るだけ
pythonだとhoge[-1]と書くところをNimではhoge[^1]と書く
- B - ディスプレイ
全部検査すればOK
- C - 単調増加
尺取法
単調増加な部分を求めて、その長さをLとすると、答えにL*(L-1)//2を加えていく
- D - プレゼント
x_i < x_(i+1) かつ y_i < y_(i+1)となる最も長い点列の長さを答える問題。本番では解けなかった。
これは、dp[y_i] := (iまで使ったときの最長の点列) として、dp[y_i] = max{dp[y_j] | x_i < x_j かつ y_i < y_j} + 1 で更新するDPで解けるが、愚直にやるとO(長さ^2)かかるのでダメで、segment treeを使ったDPが必要。詳しい説明は割愛するけども、yの大きい方から調べていくことで、それよりも小さいyのsegment treeの値が0になっていることがポイント。
あと、今回は真に大きいものしか選択できないので、segment treeの更新は高さが同じものを一気に行わないといけない。
もっと楽な方法として、x座標でソートしておくと、y座標の列の最大増加部分列問題に帰着できる。こちらの方がずっと短いし楽。
DみたいなDPは以前codeforcesでも見ていたのに解けなかった
Dの3次元パターンがICPCで出たことがあり(Longest Chain | Aizu Online Judge)、名前のついてない典型テク(skyaozoraの日記 - TopCoder部)らしい。