n-knuu's logs

憧れ駆動。だいたい競プロ

Yandex.Algorithm 2016 Online Round 2

Yandex

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の練習帳)

AtCoder

いつも通り、Nim-langでABCに出た
Nim-lang: index - Nim Programming Language
Nim-lang Tutorial: Nim Tutorial (Part I)
Nim Standard Library: Nim Standard Library

abc039.contest.atcoder.jp

A - 高橋直体

2 * (A*B + B*C * C*A)

B - エージェント高橋君

\sqrt[4]{10^9} = 177.8\cdotsなので、1から177まで調べればよい。

C - ピアニスト高橋君

12個分(1音階分)調べれば一意に決まるので、ドから見たとき、レから見たとき、と順に調べていけばよい。

D - 画像処理高橋君

ある画素の8近傍全てが黒であるか、範囲外ならば、収縮前の画像のその画素は黒であってもよい。よって、その条件を満たす画素を黒にして実際に収縮した場合に、与えられた画像と矛盾がなければpossibleとなる。

感想

計算量を殆ど考えなくていい感じのABCらしい問題だった
Dの解法を思いつくのにちょっと時間がかかってダメな感じだった

SRM552 div.1 250 FoxPaintingBalls

二分探索 topcoder

練習会で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

数学 ダブリング codechef

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 div2 C. Vanya and Label

codeforces

問題

文字列S(0..9, A..Z, a..z, -, _)を64進数とみなす。このとき、論理和をとってSと等しくなる文字列の個数を求めよ(ただしmod 10^9+7を取れ)

制約

1 <= |S| <= 10^5

解法

64進数なので、ちょうど6桁ごとに論理和を取って一致すればよい。
よってまず、64×64の組み合わせについて予め論理和を取った後に、文字列を前から順番に見ていって、論理和を取ってS_iになる文字の組の個数を掛けあわせていけば良い。

計算量

O(|S|)

コード


感想

2^iが底じゃないときはどうするんだろう...

Codeforces Round #355 Div.2 A. Vanya and Fence / B. Vanya and Food Processor

codeforces

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分で行える操作は以下。

  1. ジャガイモをA_1から順番に入れられるだけ入れる(ただし、高さがHを超える場合は入れられない)
  2. ジャガイモを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と置くと、以下の図の式が成り立つ
f:id:n_knuu:20160605202308j:plain
これをtについて解くと、t = ceil((A_i + now - h) / k) となるので、O(n)で答えを求めることができる。

  • コード


  • 感想

潰すタイミングをどこで書けばいいか迷って、かなり時間をとってしまった。

AOJ1241 Lagrange's Four-Square Theorem

AOJ

Lagrange's Four-Square Theorem | Aizu Online Judge

  • 問題

整数Kが与えられるので、4個以下の数の二乗和がちょうどKになるような数の組の個数を求めよ

  • 制約

K < 2^15
テストケースの個数 T < 2^8

  • 解法

2乗して2^15以下となる最大の数は181なので、下のように4乗ループを回せばよい

  • コード


  • 感想

最初mapでやってたらすごく遅かったけど、int []でやったら、0.01sになった

Yandex.Algorithm 2016 Online Round 1

yandex

Algorithm 2016 — Yandex.Algorithm 2016 Online Round 1 — Enter

2完523位だった
Tシャツ圏内が3回合わせて512位なので、3回きっちり出て、解ける問題を解けばなんとかいけそうかなあという感じ？
ただ残り2回が、午前3時からと午後4時からという、日本人を潰しにかかったような時間なので、忘れないように出たい

A. Cheese

  • 解法

場合分けすればOK。境界値がサンプルで与えられているので親切。

  • コード


B. Travelling in the Square

  • 解法

4箇所、時計回りと反時計回りに回る2パターンの計8パターンをやればOK

  • コード


(以下は2016/06/08更新)

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

貪欲法 topcoder

練習会に出て1完。Medは解けそうでダメだった。

問題

数列が与えられる(長さ50以下)。隣どうしをswapして良い最大の回数が与えられるので、同じ数が連続する長さを最大にしたい。最大の長さを求めよ。

解法

一箇所を固定してシミュレーションすればよい。
具体的にはある位置を決めたときに、左と右を1個ずつ見ていって、swap回数がなくなるまで、近い順に貪欲に決めた位置までswapしていけばよい。
ただし、1個つめると、次に同じ側で詰めるときはswap回数が1少なくなることに注意。
以下のコードのように左・右と1個ずつ見ていっても良いが、移動させる距離を列挙してソートする解法の方が実装が楽(hamkoさんの解法)。

計算量

以下のコードはO(N^2)
ソートする手法はO(N^2 log N)

コード


感想

左右から箱を詰めていくシミュレーションの問題、よくありそうなので、距離でソートする実装は心に留めておきたい

SnackDown Online Qualifier 2016

codechef

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

AOJ
  • 問題

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

AOJ
  • 問題

Yamanote Line | Aizu Online Judge

  • 解法

1周60分なので、60回起きて寝れば、必ず最初の状態に戻る。よってシミュレーションをして、起きてる間に到着することがあればそれを出力し、60回起きて寝てもダメなら、-1を出力すればよい。

  • コード

AtCoder Beginner Contest #038 (Nim-langの練習帳)

segment tree 最長部分増加列 尺取法 AtCoder

いつも通り、Nim-langでABCに出た
Nim-lang: index - Nim Programming Language
Nim-lang Tutorial: Nim Tutorial (Part I)
Nim Standard Library: Nim Standard Library

abc038.contest.atcoder.jp

  • 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部)らしい。