2018-08-12

Codeforces Round #503 参加記録

Dashboard - Codeforces Round #503 (by SIS, Div. 2) - Codeforces

今回は3完、配点の高いD問題が通せたのでdiv2で74位！レートもめっちゃ上がりました。

f:id:betrue12:20180812133607p:plain

A～Dの4問を振り返ります。

A. New Building for SIS

横に並んだビルがあり、各ビルでは上下の階に移動できる他、 $A$ 階以上 $B$ 階以下のフロアには渡り廊下があってビル間を移動できます。それ以外の階ではビル間の移動ができません。与えられる2地点（どのビルの何階か）の間を移動するためにかかる移動回数を求めよ、という問題。

頑張って問題を読んで、落ち着いてパターンを網羅します。以下の4パターンになります。

f:id:betrue12:20180812135716p:plain

Submission #41472505 - Codeforces

本番では「同じビルかどうか」の考慮を忘れて1WA…

B. Badge

Problem - B - Codeforces

$n$ 人の全ての生徒について、「指名された時、次に誰を指名するか」が決まっています。その指名先をずっと辿っていくと、必ず「2回指名された生徒」が出ます。全ての生徒について、「その生徒を最初に指名したとき、最初に2回指名されるのは誰か」を求めよ、という問題。

ある生徒を最初に指名して、愚直に指名先を辿っていくことを考えます。このとき、誰かが2回指名されるまでのステップ数は高々生徒の人数しかありません。そのため、全生徒についてこれを普通に繰り返しても $O(n^{2})$ で終わります。 $n \le 1000$ なのでこれで通るでしょう。

Codeforces

Rubyで100万、こどふぉで制限時間1秒だと怖いので一応C++で書きました。（後で提出してみたら問題なく通りました）

C. Elections

Problem - C - Codeforces

選挙の投票人と投票先の政党がいて、各投票人について「どの政党に投票するか」「いくら賄賂を渡せば投票先を変えてくれるか」が与えられます。政党1を単独1位にするために必要な賄賂の最小金額を求めよ、という問題。

方針として、「賄賂の少ない投票人から買収していけば良さそう」というのと、「票数の多い政党から削れば単独1位になるためのボーダーを下げられそう」という2つが思いつきます。これを同時に考えるのは難しいので、「政党1が票数 $i$ を得て勝つ」ために必要な賄賂合計を求めることにします。

政党1の目標票数を固定すれば、

まず、政党1の目標票数以上を得ている対抗馬の票を削る必要がある。それらの政党に投票している投票人を安い方から必要数買収する。
その後、目標票数に届くまで、政党1以外に投票している人のうち1.で買収していない投票人を安い方から買収する。

という処理が可能です。

計算量が怖いですが、ソートは前計算で全部できるので、ざっくり見積もって $O(n(n+m))$ くらいだと思います*1。 $n, m \le 3000$ なので、制限時間2秒でC++なら十分でしょう。

Submission #41501142 - Codeforces

本番中は、「支持政党ごとの賄賂額ソート（1.の処理用）」と「ごちゃまぜ状態での賄賂額ソート（2.の処理用）」を用意して、後者のソートを書き忘れる…という何ともつまらないミスで通せず。ただ、これをすっぱり諦めてDに向かったのは良かったのかな…？

D. The hat

Problem - D - Codeforces

偶数人数の人が円状に並んでいて、「隣り合った人が持っている数字の差は1」という条件を満たした数字をそれぞれ持っています。ちょうど対面に座っていて同じ数字を持っているペアを1つ見つけるか、そんなペアがいないということを判定してください、という問題。

インタラクティブ問題で、人数が $n \le 100000$ 、「 $i$ 番目にいる人が持っている数字はいくつですか」というクエリを60回投げることができます。クエリ回数を $O(\log n)$ くらいにしないと足りない感じです。

まず、ある対面の2人についてクエリを発行し数字を得ます。それが等しければそのまま出力して終了ですが、そうでない場合は、以下のように考えることができます。

f:id:betrue12:20180812145400p:plain

その対面の点から、両方時計回りにそれぞれ1人ずつ見ていくことを考えます。その推移を2本の折れ線グラフとして描くと、始点と終点が入れ替わっていることから、これらは少なくとも1点で交わっているはずです。この交わっているところに人がいれば、そこが解になります。

ではこの交わっている点が絶対に解になるかというと、そうではありません。グラフ上は「2.5」みたいな値で交わっているかもしれないからです。この場合、すれ違う格好になり、人がいるところ（整数の点）では数字が一致しません。

これを判別するために、偶奇を考えます。もし向かい合ったペア1組の偶奇が一致していない場合。その1つ隣のペアを見ると、差が1であることから偶数は奇数に、奇数は偶数になります。ということは隣のペアの偶奇も一致しません。これを繰り返して、全てのペアの偶奇が一致しなくなります。これは「偶奇が一致する」に置き換えても同様です。

向かいあったペアの数字の偶奇が一致していれば、折れ線グラフの交点が解になりますし、そうでない場合は絶対にすれ違うので解無しです。実はこれは「総人数 $n$ が4の倍数かどうか」に対応しています。

では、偶奇が一致して解が必ず存在する場合を考えましょう。さきほど考えたように、もし2本の折れ線グラフが交点を持つ十分条件は、始点と終点で大小が入れ替わっていることです。そのため、二分探索で解の存在範囲を絞り込むことができます。

f:id:betrue12:20180812152117p:plain

それぞれの区間の真ん中の点についてクエリを発行します。これが同じ値でしたら解を発見したことになります。そうでない場合、どちらか片方の区間では大小が入れ替わっているはずなので、そちらに絞って探索を続けます。

これを繰り返すと $O(\log n)$ 、具体的には最大で $2 \times \lceil\log_{2} 100000\rceil = 34$ 回ほどで解が見つかるのではないかと思います。

Submission #41492428 - Codeforces

余談ですが、この問題で使った「数直線上の2点が同時に±1ずつ動くときに、偶奇が一致していれば、交差したときに同じ座標を共有する」という考え方は、以下の問題から連想しました。

A - 迷子の高橋君 / Takahashi is Missing!

さいごに

Cが凡ミスで通せなかったのは良くないですが…配点の高いDが解けたのでかなり良い順位が取れました。目指せ紫！

脚注

*1:n < m のときは得票数がゼロの政党があるということなので、その政党を無視してしまえることを考えると O(n²) で良い気がします。

2018-08-12

ABC105 参加記録

AtCoder プログラミング競技プログラミング

結果は25分台全完で45位。1WAを出したのが良くないですね…

f:id:betrue12:20180812021653p:plain

A - AtCoder Crackers

せんべいをなるべく均等に配ったとき、枚数が人数で割り切れるときはぴったり同じ枚数にできますが、そうでない場合は多い人と少ない人で1枚の差ができてしまいます。余りの値で分岐します。

Submission #2983736 - AtCoder Beginner Contest 105

B - Cakes and Donuts

$ax+by=c$ の形をした方程式の、整数解を求める問題。負の値を取っていいなら最大公約数を考えることになりますが、今回は非負の値に限定されているのと、制約がとても小さいので素直に全探索します。

合計金額を超えない範囲で4の倍数 $4n$ を列挙して、 $N - 4n$ が7の倍数か調べればよいです。

Submission #2984464 - AtCoder Beginner Contest 105

C - Base -2 Number

これは難しいと言うか、問題を見た瞬間にちょっとヤバそうな雰囲気がありましたね…

-2進数をいきなり考えるのは難しいので、慣れ親しんだ2進数について少し振り返りましょう。2進数の $i$ 桁目（0始まりとします）は、元の数の「 $2^{i}$ 成分」を表現します。

f:id:betrue12:20180812110137p:plain

2進数において、以下のことが言えます。

下から2ビット目以上が担当する値は全て2の倍数なので、「2で割った余り」は、一番下のビットだけで決まる。
同じく、「4で割った余り」は、下2つのビットだけで決まる。
同じく一般に、「 $2^{n}$ で割った余り」は、下位 $n$ ビットだけで決まる。

これを利用して、10進数を2進数に変換する際に、余りを使って下位ビットから決定していくことができます。これはお馴染みですね。

def to_bin(n)
    return '0' if n == 0

    digits = []
    i = 0
    base = 1
    while n != 0
        if n % (base*2) == 0
            digits[i] = '0'
        else
            digits[i] = '1'
            n -= base
        end
        i += 1
        base *= 2
    end
    return digits.reverse.join
end

さて-2進数です。実はこれと同じことが言えます。

f:id:betrue12:20180812112626p:plain

-2はやっぱり2の倍数であり、-8はやっぱり8の倍数です。そのため、「 $2^{n}$ で割った余りは、下位 $n$ ビットだけで決まる」という性質は同様です。そのため、同じように下位ビットから決める処理をすることができます。

def to_m2(n)
    return '0' if n == 0

    digits = []
    i = 0
    base = 1
    while n != 0
        if n % (base*2) == 0
            digits[i] = '0'
        else
            digits[i] = '1'
            n -= base
        end
        i += 1
        base *= -2    # ここが違う！
    end
    return digits.reverse.join
end

各桁が担当している値（コード中では base ）が-2倍ずつ増えていくことを除けば、2進数の実装と同じですね。

細かい点として、剰余計算の仕様は言語によって様々なのでそこは注意です。「余りが0かどうか」だけで判断していけば、大抵の言語では恐らくそんなに困らないです。

本番コードでは base に-2を掛けていく代わりに、 n を2で割っていって、ビットが立っている時の調整処理で正負を分けています。自分自身が正負を間違えにくい方法なら何でもいいと思います。

Submission #2986709 - AtCoder Beginner Contest 105

逆に上位ビットから決定する…というのもできそうではありますが、ビットが1になる条件がころころ変わるので少し面倒だと思います。いずれにせよ、慣れ親しんだ「10進数から2進数への変換」から始めて、-2進数だとどこを変更する必要があるのか？を考えて解くのがいいと思います。

ちなみに本番WAはサンプルにも用意されている「0」です。サンプルにあるケースでWA出すのはひどい…

D - Candy Distribution

要素数 $N \le 10^{5}$ なので、全区間を調べていてはTLEです。効率的な探し方を考えましょう。

区間の要素の和を求める問題で、単調性がないような場合、累積和を考えてみるとよいです。というのは、区間 $[a, b$ ] の要素和を、累積和 $[1, b$ ] と $[1, a-1$ ] の差として考えることができるからです。

今回は、以下のように考えることができます。

f:id:betrue12:20180812125049p:plain

区間 $[a, b$ ] の要素和が $M$ で割り切れるということは、累積和 $[1, b$ ] と $[1, a-1$ ] の $M$ で割った余りが等しいということと同じです。そのため、各要素について「最初からその要素までの累積和を $M$ で割った余り」を調べて、それが等しいような組み合わせを探せば良さそうです。

数列の頭から最初から累積和を取りながら、「累積和の余りが $r$ になっているような右端の個数」を $r$ ごとに数えていきます。「数列の最初から取る」という場合を取りこぼさないように、最初には余り0の右端がある、というふうに考えます。

条件を満たす区間の個数は、累積和を取る操作の途中で「それより左にあって、累積和の余りが同じ右端の個数」をどんどん足していっても良いですし、最後まで集計が終わってから $_n C_{2}$ のような計算をしても良いでしょう。

Submission #2988059 - AtCoder Beginner Contest 105

数ヶ月前のAGCで類似問題が200点問題として出たので、印象に残っている人も多いのではないでしょうか…

A - Zero-Sum Ranges

さいごに

C問題が難しかったですね…

2018-08-11

Codeforces Round #502 参加記録

Codeforces プログラミング競技プログラミング

Dashboard - Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2) - Codeforces

途中でサーバが落ちて、unratedになってしまいましたが…結果は3完。predictorの数値だとレートはけっこう上がってたみたいなのでちょっと残念です。

f:id:betrue12:20180811120804p:plain

A～Dの4問を振り返っていきます。

A. The Rank

Problem - A - Codeforces

問題の通り「合計点数が大きい順→同点ならidが小さい順」にソートして、id=1が何番目に出てくるか調べればOKです。

Submission #41340341 - Codeforces

B. The Bits

Problem - B - Codeforces

ビット列: $a, b$ が与えられます。 $a$ のビット2つの入れ替え方のうち、入れ替えることで $a | b$ の値が変化するものの数を求めます。

まず、0と0、1と1の入れ替えはもちろん意味がありません。0と1を入れ替えた時にorの値が変化するかどうかは、入れ替えた場所の $b$ のビットに応じて変わります。入れ替えた場所の $b$ の2ビットをそれぞれ $b_{1}, b_{2}$ として表を書きます。

$b_{1}$	$b_{2}$	$10 \vert b_{1}b_{2}$	$01 \vert b_{1}b_{2}$
0	0	10	01
0	1	11	01
1	0	10	11
1	1	11	11

$a$ において1と0を入れ替えた時には、 $b_{1}, b_{2}$ が両方1の時でない限り、orの値が変化します。

そのため、 $a$ の1と0のペア数から、その中で対応する $b$ のビットがともに1であるものを引けばよいです。

Submission #41344556 - Codeforces

C. The Phone Number

Problem - C - Codeforces

$1, ..., n$ の順列のうち、その最長増加部分列（LIS）と最長減少部分列（LDS）の長さの和が最小になるものを1つ作れ、という問題。

この問題ですが、以下のように作るのが最適です。

f:id:betrue12:20180811150554p:plain

$\sqrt{n}$ で数列を分割し、LISとLDSの長さがともに $\sqrt{n}$ になるように構成します。

$\sqrt{n}$ が整数にならない場合でも一番上や一番下で調整することで、LISとLDSの長さの積が $n$ 以上であればこのような構成をすることができます。そのため、 $\sqrt{n}$ が整数でないときは以下のようにします。

$r = \lfloor \sqrt{n} \rfloor$ とする。このとき、 $\sqrt{n}$ が整数でなければ $r^{2}+1 \le n \le (r+1)^{2} - 1$ である。
$n \le r(r+1)$ の時、LDSの長さを $r$ 、LISの長さを $r+1$ とする。
の時、以下のどちらかとする。ともに長さの和はである。
- LDSの長さを $r+1$ 、LISの長さを $r+1$ とする。
- LDSの長さを $r$ 、LISの長さを $r+2$ とする。（ $(r+1)^{2} - 1 = r^{2} + 2r$ であるため収まる）

さて、これが最適であることの証明ですが…AtCoderの問題に似たようなものがあり、その解説に書いてある方法が結構分かりやすかったので紹介します。

E - LISDL

f:id:betrue12:20180811150356p:plain

ある順列を考えます（適当に作りました）。各点に対して、「その点が終点であるような最長増加部分列の長さ」を付けていきます。これらの値は、もちろん数列全体のLISの長さ以下になっているはずです。

ここで、例えば2が付けられた点は、「それ以前の点で、2が付けられたもの」より小さいということが言えます。もし後の点のほうが大きい場合は、前の点を終点とする長さ2の増加部分列に後の点をくっつけると長さ3の部分列ができるので、後の点には3以上の数字が付いているはずです。

ということは、「番号2を持つ点」だけを集めると減少列になります。もちろんこれは全ての番号について言えるので、「同じ番号を持つ点の数」の長さの減少列が作れることになります。

整理すると、

数列全体のLISの長さを $A$ とする。それぞれの点に「その点が終点であるような最長増加部分列の長さ」の番号を付けていく。
点が $n$ 個で番号が $A$ 種類なので、「同じ番号を持つ点の集合」としてサイズが $\lceil\frac{n}{A}\rceil$ 以上のものが必ず存在する。
この「同じ番号を持つ点の集合」は減少列を成すので、数列全体のLDSの長さ（ $B$ とする）は必ず $\lceil\frac{n}{A}\rceil$ 以上になる。

さらにLISとLDSの長さの積を考えると、 $AB \ge A\lceil\frac{n}{A}\rceil \ge n$ となります。これは、任意の順列に対して必ず成立する条件です。

この条件下で $A+B$ を最小にしようとすると、まさに前半で示したような $A$ と $B$ の選び方となります。*1

Submission #41348326 - Codeforces

D. The Wu

Problem - D - Codeforces

公式解説だと半分全列挙が絡んだ解法だったのですが…もう少し単純な方法でも通すことができたので、そちらで書きます。

$n$ 桁のビット列2つに対して計算される値で、「上から $i$ ビット目が一致していれば $w_{i}$ 加算」という値を全ビットについて合計したものをWu値と呼ぶことにします。先にビット列集合 $s_{1}, ..., s_{m}$ が与えられ、その後にクエリで1つずつ文字列 $t$ とボーダー値 $k$ が与えられるので、 $s_{1}, ..., s_{m}$ のうち $t$ とのWu値が $k$ 以下であるものの個数を答えなさい、という問題。

まず、ビット列の長さが最大でも12しかありません。先に与えられるビット列の数もクエリの数も多いですが、ビット列は全部で4096通りしかないので、それを超えたぶんは必ず重複しています。これらをまとめて考えられそうです。

また、ビット列2つのペアのWu値がいくつになるかは最大 $4096^{2}$ 回（入れ替えを除けばもっと少なく）計算すれば求められます。やってやれないことはない回数です。

また、Wu値の値もあまり大きくなく、制約から最大でも1200です。

以上の情報から、クエリを処理するために以下のような前計算が現実的な時間で可能です。

ビット列集合から、 $2^{N}$ 通りのビット列がそれぞれいくつあるかの分布を計算する。
考えられる入力（ $2^{N}$ 通り）と、ビット列集合に含まれる列（ $2^{N}$ 通り）の全ペアについて、Wu値を計算する。これとさきほどのビット列集合の分布から、「クエリでこの入力が来た際に、Wu値がこの値となるビット列の個数」が全部計算できる。
これをWu値が少ない方から累積和を取ると、「～～Wu値がこれ以下のビット列の個数」となる。

この前計算ができれば、各クエリは計算結果を参照するだけで求められます。

ということで十分現実的な計算量なのですが、入力数が多いこともあり、 cin ではなく scanf を使うなど細かいところにも気を遣わないとTLEでした…

Submission #41400858 - Codeforces

さいごに

Dの実装がなかなか詰められずに悩んでいましたが、ふと画面をリロードしたらサーバが落ちていて…これがこどふぉか。

今のところ、Div.2は4完目標くらいを考えておけばいいのかな…？Dは通したかったですね。

脚注

*1:数式で証明しようとすると、相加相乗平均の関係を使いつつ、整数でなければならないという制約を上手く処理してあげることになると思います。

2018-08-05

ABC104 参加記録

AtCoder プログラミング競技プログラミング

AtCoder Beginner Contest 104 - AtCoder

全完43分台で46位。今回は手こずる問題が多かったです…

f:id:betrue12:20180805214841p:plain

A - Rated for Me

不等号で比較してifで分岐すればOK。

Submission #2950051 - AtCoder Beginner Contest 104

入力上限の4208、コンテスト当日時点でのtouristのhighestレートですね…

B - AcCepted

処理するだけといえば処理するだけなのですが、地味に実装が面倒です。私のコードの方針としては、

先頭が A であるかチェック
3文字目～末尾から2文字目の間に C がちょうど1つあるかチェック
上記2文字を取り除いてしまう
残りの文字が全部小文字であるかチェック

です。提出する際はヒヤヒヤしましたね…

Submission #2952457 - AtCoder Beginner Contest 104

C - All Green

ボーナス点の扱いが面倒なので、ボーナス点を固定してしまいたいですね。ボーナス点は「その点数の問題を全部解くかどうか」を決めれば固定できます。

幸い、点数の種類数が $D \le 10$ と非常に小さいので、それぞれの点数種類を全部解くかどうか、 $2^{D}$ の全探索を試みることができます。

「全部解く点数種類」を固定すれば、それらの問題の素点とボーナス点、そして問題数がまず計算できます。そこからは、合計点数が目標に足りるまで、点数の大きい順に解く問題を追加していけばよいです*1。 $2^{D}$ 全探索して、最も問題数が少なかったものが答えです。

Submission #2954029 - AtCoder Beginner Contest 104

D - We Love ABC

この問題はけっこう難しいです。 ? が出現するたびに増えていく文字列のパターンを、まとめて考える必要があるからです。

考え方としてはDPです。文字列を前から見ていって、

その時点までの A の個数
その時点までの AB のパターン総数（離れていても良い）
その時点までの ABC のパターン総数（離れていても良い）

を計算していきます。

まずは ? がややこしいので、? がないパターン、すなわち文字列1通りで考えます。そのとき、「文字列を1文字足す」ことによって、以下の効果が得られます。

f:id:betrue12:20180806000350p:plain

以前に出現した A それぞれに対して、 B がくっつくと AB ができます。
また、以前に出現した AB のパターンそれぞれに対して、 C がくっつくと ABC ができます。
また、 A がくっつくと、もちろん A が増えます。

このような遷移で、文字列が1通りの場合は計算していけます。

問題は ? があるときです。 ? が登場するたび、文字列の総数は一気に今までの3倍になります。これを個別で数えるのは不可能なので、全部まとめて数え上げるという方法を取ります。すなわち ? が存在する場合は、先ほどの数え上げるものリストを少し発展させて

その時点までの A の個数を、全文字列について合計したもの
その時点までの AB のパターン総数を、全文字列について合計したもの
その時点までの ABC のパターン総数を、全文字列について合計したもの
文字列の総数（←NEW！）

を計算します。

とはいえ、複数文字列を考慮した際の遷移は、先ほどのものとあまり変わりはありません。

f:id:betrue12:20180806000453p:plain

ちょっと大変ですが、1手前の文字列が3パターンある場合（AA? に対応します）の場合を列挙してみました。前から順番にDPを進めていくと、1手前に含まれる文字列の集合について、さきほどの4つの値が求まっているはずです。その後に A, B, C それぞれがくっついたときの遷移は、図に示した通りとなります。最後まで探索し終わったときの ABC のパターン総数が答えです。

くっつく文字列が ? の場合は、 A, B, C 全パターンの計算結果を全部足し合わせます。このとき、文字列の総数も3倍になることに注意しましょう。

考察が正しいのか結構不安になりますが、最後のサンプルが通ればほぼWAはないと思うので、サンプルを全部合わせることを目指して実装しましょう。

Submission #2955903 - AtCoder Beginner Contest 104

さいごに

今回は難しかったですね…

脚注

*1:問題のルール通り厳密に処理すると、後半のパートで点数の高い問題を解いたときにも、コンプリートボーナスが発生したらそのぶんの点を追加しないといけません。ただ、そのようなケースは他の全探索パターンに含まれているため、やらなくても大丈夫です。

2018-08-05

Mujin Programming Challenge 2018 参加記録

AtCoder プログラミング競技プログラミング

Mujin Programming Challenge 2018 - AtCoder

結果は3完18分台で274位でした。Cまでは順調でしたが、Dでハマり、Eに切り替えて方針は見えたものの実装を詰めきれず…という感じでした。

f:id:betrue12:20180805003007p:plain

A～Eを振り返っていきます。

A - コンテスト名

先頭5文字を何らかの方法で取ってきて比較します。解説放送でも触れられていましたが、与えられる文字列が短い時に範囲外参照しないよう注意しましょう。言語や書き方によりますが、Rubyの str[s, length] は数が足りなくても取れるだけ取ってくれるので大丈夫です。

ACコード：Submission #2941689 - Mujin Programming Challenge 2018

B - セキュリティ

Mujin Programming Challenge 2018 - AtCoder

文字列を前から見ていって、数字を増やしたり減らしたりします。サンプル3は優しさですね（ありがとうございます）

Submission #2942354 - Mujin Programming Challenge 2018

C - 右折

最初、RPGの氷の床みたいに障害物に当たるまで進み続けるものと思ってました…問題はよく読みましょう。

この問題は、「曲がり角」となる点を固定して考えるとよいです。

f:id:betrue12:20180805005519p:plain

曲がり角を固定すると、例えば「左側からその点まで来て、曲がって下側に行く」という経路は、「障害物を挟まずに、その点の左にいくつマスがあるか」と、「同じく、下にいくつマスがあるか」の掛け算で計算できます。

これを4通りの方向について足せばよいため、

$(左 \times 下) + (下 \times 右) + (右 \times 上) + (上 \times 左) = (左 + 右) \times (上 + 下)$

で「その点を曲がり角とする経路」が求められます。

では、各点について「上下左右に、障害物を挟まずにいくつマスがあるか？」はどのようにして求めましょうか。これを求める良い方法があります。

f:id:betrue12:20180805010831p:plain

図では「左にいくつマスがあるか」を考えています。左に障害物や外壁（範囲外の領域）がある場合はもちろんゼロです。そうでない場合は、左のマスの「左にいくつマスがあるか」の値に1を足したものになるはずです。ということは、左から順にこの数を更新していけばよいです。

上下左右それぞれについてこの方法を使えば、先程の

$(左 \times 下) + (下 \times 右) + (右 \times 上) + (上 \times 左) = (左 + 右) \times (上 + 下)$

の計算ができるため、問題が解けます。前計算、曲がり角の全探索、ともに $O(NM)$ です。

ACコード：Submission #2943455 - Mujin Programming Challenge 2018

制約と解法を認識した瞬間にC++に切り替えたのが功を奏しました。

同じような考え方ができる問題を紹介します。

D - うほょじご

すごく「Snuke Numbers」っぽさを感じたので、初手実験！と思って法則性を探そうとして、失敗しました…

この問題は「整数の遷移をグラフとして考える」というパターンを思い出すべきでした。整数のペアを頂点として考え、遷移に対応する辺を張り、「閉路に到達する」か「 $(0, x)$ または $(x, 0)$ に到達してしまう」かを調べればよいです。

閉路検出しようとしても、書き方が良くないとTLEするのですが…公式解説の「到達してはいけない点である $(0, x)$ および $(x, 0)$ から逆辺を辿る」というのがすごいです。

ACコード：Submission #2946353 - Mujin Programming Challenge 2018

Rubyコードではペア $(i, j)$ に対応する頂点を番号 $i \times 1000 + j$ として扱っています。これを配列で扱うと実行時間がキツいです…。

是非とも英語対応のratedコンテストに出して、タイトルを英訳して欲しかった…と思いましたが、よく考えたらratedでこの問題は見たくなかったですね。良かった良かった（よくない）

E - 迷路

各時刻を $K$ で割った余りごとに、移動できる方向が異なります。これは言い換えると、「現在時刻を $K$ で割った余りに依存して、次に上下左右それぞれの方向に移動するためにかかる時間が変動する」ということです。

まずはこれを求めておきましょう。各時刻において、例えば次に上方向に移動できるのは、文字列 $d$ においてその時刻を $K$ で割った余り以降で、最初に U が登場するような時刻です。これは文字列 $d$ を後ろから見ていって、最後に U が現れてから何文字通過したかを記録していけばよいです。…これ、先程のC問題と考え方は同じですね。

このとき余りがループするのを考慮して、文字列 d を2周すると実装が楽です。

f:id:betrue12:20180805023420p:plain

これを4方向全てについて求めておきます。前計算部分は $O(K)$ です。

その後、実際に目的地に到達する最短時間を求めていくわけですが…遷移ルールが少し特殊とはいえ、過去に遷移することはできません。ということは、スタート地点からの到達時間が短いマスから順に遷移を確認していけば、効率的に各マスへの最短時間を求められそうです。これはまさに、ダイクストラ法の考え方です。

遷移にかかる時間（辺のコスト）が可変であるため普通のダイクストラ法には当てはまりませんが*1、ダイクストラ法における距離の更新は

コスト $c$ の辺 $v \rightarrow u$ を使った距離の更新を考えるとき、始点から $v$ までの最短距離 $dist(v)$ を使って、 $dist(u) = \min(dist(u), dist(v) + c)$ と更新する。

であるため、今回はこれを発展させて次のように考えればよいです。

遷移 $v \rightarrow u$ を使った最短時間の更新を考えるとき、始点から $v$ までの最短時間 $dist(v)$ と、それを $K$ で割った余り $r$ を使う。 $v \rightarrow u$ が上下左右どちらの方向であるかと余り $r$ の値が分かれば、次の移動にかかる時間は前計算しているため、その値を $c$ として $dist(u) = \min(dist(u), dist(v) + c)$ と更新する。

優先度付きキューを用いるとダイクストラ法の計算量は頂点数 $V$ 辺数 $E$ として $O(V \log E)$ であり、今回の問題だと頂点数が $NM$ で辺数は頂点数の4倍で抑えられるので $O(NM \log(NM))$ です。あとは「障害物や外壁の方向には遷移できない」というのを忘れずに実装しましょう。

ACコード：Submission #2946098 - Mujin Programming Challenge 2018

本番でも方針は合っていましたが実装のバグを取りきれませんでした…

さいごに

各種特典（Tシャツやオフィスツアー）のボーダーには入れませんでしたが…Cまでがまあまあ速かったので順位はわりとマシなほうでしたね*2。

Dは頭が凝り固まっていたので色々な可能性を考えてみるべきでしたし、Eは方針は合っていたので時間内に実装を詰められるようにならないと…ですね。

脚注

*1:余りごとに頂点を分割すれば一応普通の最短路問題に帰着できますが、今回はKが大きいので頂点数が爆発します。逆に言うと、頂点数が爆発しないような制約であればこのような解法を取れる可能性があります。

*2:700点獲得者の中では最速のようです…。

2018-08-04

Educational Codeforces Round 48 参加記録

Codeforces プログラミング競技プログラミング

Dashboard - Educational Codeforces Round 48 (Rated for Div. 2) - Codeforces

初めてのこどふぉ参戦！

結果はA～Dの4完で478位でした。

f:id:betrue12:20180811155629p:plain

1問ずつ振り返っていきます。

A. Death Note

Problem - A - Codeforces

英語よりも、一番下のNoteを見ると分かりやすいです。1を $a_{1}$ 個、2を $a_{2}$ 個…というのを各ページに $m$ 個区切りで書いていきます。そのとき、それぞれの数字を書く際に何回ページをめくりますか、という問題。 ただし、「ちょうど書き終わった」時にもページをめくるものとします。*1

$m$ 個書くたびにページをめくるので、累積で $x$ 個目の数字を書いた後のページは $floor[\frac{x}{m}$ ] ページ目になります。累積和を計算して、それぞれの数字を書く前と後のページ数で差を取ればよいです。

ACコード：Submission #41161044 - Codeforces

1問目から英語に手こずるという…もしサンプルが「ちょうど書き終わった」時の処理を含んでいなかったら、それに気付かずWA地獄になっていたと思います…。

B. Segment Occurrences

Problem - B - Codeforces

文字列 $s, t$ が2つ与えられ、クエリで $s$ の範囲が指定されるので、その範囲から連続部分文字列として $t$ が取れる箇所はいくつあるか、という問題。

「 $s$ の $i$ 文字目から $i+M-1$ 文字目までが $t$ と一致するか」は前計算できます。全箇所調べるのに $O(nm)$ かかりますが、 $10^{6}$ くらいなので間に合います。

この前計算の結果を使ってクエリを処理するのですが、そのままやると $O(nq)$ 。 $10^{8}$ くらいなので速い言語だとこのまま通りそう…？ですが、累積和を取っておけば高速化できます。

クエリの範囲が狭すぎる場合はちゃんと別で処理してあげないとマイナスとかになるので気をつけましょう（2敗、ひどい）

本番ACコード：Submission #41169639 - Codeforces
ちょっと書き直したコード：Submission #41196250 - Codeforces

C. Vasya And The Mushrooms

Problem - C - Codeforces

ゴリゴリ実装しましたが、どう解くのがスマートなんだろう…

まず、可能な動きのパターンを整理します。全部のマスを1回ずつ通らないといけないという制約から、動きのパターンは以下のようなものに限定されます。

f:id:betrue12:20180804110723p:plain

実際に可能な動きのパターンは全部で $n$ 通りあります。意外と少ないですが、各経路を毎回計算していると $O(n^{2})$ かかってアウトなので高速化します。

まず、横Uターンの経路の得点をそれぞれ前計算しておきます。そして、「途中まで縦ジグザグした後に、横Uターンする」時の得点を、縦ジグザグを1手ずつ進めながら計算していきます。

縦ジグザグ部分の得点は、順次足し算をしていけばよいです。そして横Uターンの得点は、「縦ジグザグを進めることで、横Uターン部分の得点はどう変化するか？」を考え、差分だけ更新していきます。

f:id:betrue12:20180804112637p:plain

縦ジグザグを進めた際に、横Uターンの得点は

既に通過した点から得られるはずだった得点が得られなくなる。
通過していない点は、通るのが先延ばしになるため、倍率が増える。*2

と変化します。それぞれの差分が分かれば、横Uターン部分の得点が計算できそうです。

まず「通過していない点は、通るのが先延ばしになるため、倍率が増える」については、通過していない点の $a_{i}$ または $b_{i}$ の合計を持っておけば、それを足すことで実現できます。最初に全部足した値を持っておいて、通過した点を順次引いていきましょう。

次に「既に通過した点から得られるはずだった得点が得られなくなる」ですが、これを正しく除くには「その時点で、その点が何倍として扱われているか」を知っている必要があります。このとき、前述の「倍率が増える」操作も考慮する必要があります。最初に横Uターンの得点を計算した時点で何倍として扱われて、そこから何回倍率が増やされたか、を管理しておけばよいです。

前計算しておけば1回1回の計算は $O(1)$ なので全体で $O(n)$ のはずなんですが…Rubyだと時間ギリギリですね…

ACコード：Submission #41177718 - Codeforces

D. Vasya And The Matrix

Problem - D - Codeforces

閃き勝負の問題。Cより先にこっちを解いておけばよかった…

$n \times m$ の行列において、各行と各列のxorが条件として与えられるので、それを満たす行列を求めよ、という問題。

まず、解が存在する必要条件が思いつきます。行xorを全部xorすると、全部の要素のxorになるはずです。同様に、列xorを全部xorすると、やはり全部の要素のxorになるはずです。ということは、これが一致しない場合は「解無し」です。

では、「行xor全部のxor」と「列xor全部のxor」が一致するときに必ず解が存在するかというと、実は存在します。以下のように構成すると、条件を満たすことができます。

f:id:betrue12:20180804115438p:plain

これを思いついてしまえば、コードもすぐに書けます。

ACコード：Submission #41179410 - Codeforces

さいごに

今回初めてのCodeforces参戦でしたが、いきなりコンテスト開始が遅延して「こどふぉった」を体験しました。

問題については、AtCoderのような点数が出るわけではないので難易度の見極めが難しいです。あと、英語はやっぱり時間取られて、心理的にも「読み間違いがあるんじゃないか？」という不安がつきまといます。慣れるしかないですね。

順位を決めるペナルティについては、まだあまり仕組みを理解できていませんが…AtCoderのように「コンテスト全体で、最後に点数が増えた時刻」が使われるのではなく、各問題ごとの時刻が使われるようなので、解く順番がけっこう重要なのかなと思いました。

あとは開催時刻…想像以上に眠かったです。とりあえず、深夜の参加は金曜土曜だけにしておこうかなと思います…生活が壊れそう。

言語はRubyが使えるだけでもありがたいですが、バージョンが2.0なので、これ以降に新しく追加されたメソッドを使わないように注意ですね。けっこう時間制限もキツそうだし、おとなしくC++使えという話もありますが。

こどふぉを始めた理由は、AtCoderの過去問解きがそろそろ800点くらいになってきて、解いている問題に対して実力が足りないので数をこなしたいなあと思ったからです。あと、最近AtCoderでratedコンテストが少ないので手を付けてみたという理由もあります。

やっぱりコンテストは楽しいですね。こどふぉにもちょっとずつ慣れていきたいです。

脚注

*1:原文「Note that you always turn the page when it ends, it doesn't matter if it is the last day or not.」に対応。

*2:正確には、1手進めるごとに「横Uターン1」「横Uターン2」いずれかの倍率が増えます。実験して、辻褄が合うようにコードを書いていきましょう。

2018-07-31

SoundHound Programming Contest 2018 Masters Tournament 本戦　参加記録

AtCoder プログラミング競技プログラミング

SoundHound Programming Contest 2018 Masters Tournament 本戦 - AtCoder

3週間ほど前に行われた予選では、残り2分で全完という快挙（？）を成し遂げ…なんと本戦に参加することができました！

当初の予定より参加枠が増えたようで…かなりギリギリで通ってた*1と思うので、とてもありがたいです。

そして結果は…1完の40人中37位。うーん…参加者のレベルがとても高いので順位はそこまで気にしないですが、せめて2問は解きたかった。悔しいです。

f:id:betrue12:20180730211302p:plain

5問のうち、コンテスト後に通せたものを含むA, B, Dを振り返っていきます。

A - Feel the Beat

曲のBPMのほうを2で割っていくと、小数が出たり範囲内の曲数を把握しにくかったりして計算しづらいです。逆に140～170のほうを2倍していくと楽です。

スマートなACコード：Submission #2923471 - SoundHound Programming Contest 2018 Masters Tournament 本戦
本番コード（場合分けが細かい）：Submission #2912893 - SoundHound Programming Contest 2018 Masters Tournament 本戦

B - Neutralize

本番中はSegTreeを使った貪欲ができないか考えたり、 $O(N^{2})$ のDP*2を考えていましたが…正しいDPが見えず。解けそうなものがないかとB～Dを行ったりきたりするだけで1時間ほど費やしてしまいました…

「薬品列（ $1, 2, ..., N$ ）の $i$ 番目までだけを考える部分問題においての、効用の最大値」を dp[i] とするDPを考えます*3。このとき、実際の問題においては $i$ 番目が薬品列の途中だったとしても、部分問題においては $i$ 番目が薬品列の端だとして考えます。つまり効用を0にする長さ $K$ の区間が $i$ 番目より右にはみ出ることを許しません。

このようなDPを考えると、 dp[N] が答えとなります。そしてこのDPの遷移は、 $i$ 番目の薬品を使うか使わないかを場合分けして次のように考えられます。

f:id:betrue12:20180730221354p:plain

dp[i] = max(dp[i-1] + b[i], dp[0], dp[1], ..., dp[i-K]) *4 という遷移ができます。 max(dp[0], dp[1], ..., dp[i-K]) が必要ですが、左端は dp[0] で動かないので、DPを進めるごとに逐次maxを取れば大丈夫です。

ACコード：Submission #2915356 - SoundHound Programming Contest 2018 Masters Tournament 本戦

余談ですが、公式解説のDPがよく分かりません…

C - Not Too Close

解説読んだけど遷移が全然頭に浮かばず…頭が元気なときに考えます。

D - Propagating Edges

本番中は順位表を見たところCより多く解かれていたので挑戦してみました。まあまあ惜しいところまで行ったような、そうでもないような…。

公式解説の繰り返しになってしまいますが、「addクエリで直接追加された辺」と「completeクエリによる完全グラフ化で追加された辺」は分けて考えると良いです。checkクエリでは、どちらかで辺が追加されていれば Yes を出力します。

addクエリで追加された辺はset等を使って直接管理します。

completeクエリではグラフの一部が完全グラフ化するため、「完全グラフ化した頂点集合」を管理したくなります。Union-Findを用いれば良さそうです。

completeクエリの処理の際には、クエリで与えられた頂点 $u$ と連結な頂点を探す必要があり、これは隣接リストを使ったBFS/DFS等で最大 $O(N)$ かかります。1クエリの中で $O(N)$ の処理をするのは非常に危険ですが、これは頂点の「縮約」によって回避することができます。完全グラフ化した頂点は縮約してしまうことで、BFS/DFSで探索したぶんだけ頂点数がどんどん減っていき、「問題中の全てのcompleteクエリの合計で」訪れる頂点数が高々 $O(N+Q)$ 個になります。

以上の内容をまとめると、addクエリで直接追加された辺を管理し続ける「縮約しないグラフ」と、連結性およびcompleteクエリによる縮約状況を管理する「縮約するグラフ」の2つを考え、それぞれから別々の情報を得ていくことになります。それぞれに対する操作は以下の表の通りです。

クエリ	縮約しないグラフ	縮約するグラフ
add	元の頂点番号を使い、辺集合(set)に追加	縮約後の頂点番号を使い、隣接リスト等に追加
complete	何もしない	隣接リストを用いて頂点 $u$ と連結な頂点番号を探索し、Union-Findで併合し、頂点を縮約
check	辺集合に存在すれば `Yes`	Union-Findで併合されていれば `Yes`

ここまで公式解説と同じですが…イメージが付きやすいように、図を描きます。

f:id:betrue12:20180730233349p:plain

実装上は、縮約後の代表頂点番号としてUnion-Findにおける根ノードの番号を使い、縮約直後に代表頂点番号の隣接リストを空にしてしまうとよいです*5。連結な頂点を全て縮約してしまった直後は、その頂点はどことも繋がっていないはずなので。

ACコード：Submission #2915854 - SoundHound Programming Contest 2018 Masters Tournament 本戦

$Q = 200,000$ を見た瞬間にRubyだと厳しいことを悟るので、C++での実装です。

本番中は、「addクエリで連結になった」と「completeされた」という情報をともに1つのUnion-Findの中に持たせようとして失敗しました…。

E - Hash Swapping

本番中は全く手をつけなかった問題。

平衡木の知識がないのですが、解説の最後にあるSegTreeを用いた解法はなるほどと思いました。そのうち、これで実装してみたいです。

おまけ

せっかくのオンサイトコンテストだったので、当日会場での話も少しだけ。

台風が来ていたのでどうなることかと思いましたが、奇跡的に行きも帰りも全く雨に降られずに済みました。

当日いただいた、Tシャツとボールペン（写真だと見えないですがSoundHound Inc.と印字されています）。初めての競プロTシャツゲット！

f:id:betrue12:20180730235824p:plain

こちらはちょくだいさんから頂いたAtCoderステッカー。Twitterで見かけたときから欲しかった一品。

f:id:betrue12:20180730235842p:plain

写真はないですが、コンテスト前にはお菓子を頂き（おいしかったです）、コンテスト終了後には懇親会もありました。参加者には社会人しかいないということで、私は飲んでないですがお酒もありました。

懇親会では全ての人が初めまして状態だったのでどうしようかと思っていましたが、京都からいらっしゃった橙コーダーの方とずっとお話させていただきました。ありがとうございました…！

SoundHound社の紹介もしていただきました。何年前か忘れましたが、たまたま鼻歌検索のアプリを知って「スゴイ！」と思った記憶があります。こんな形で関わりが持てるとは…。

という感じで、非常に楽しいオンサイトコンテストでした。また何かの機会で参加できるように、実力を付けていきたいです。

脚注

*1:交通費受け取りの際に名簿がありましたが、下から3番目くらいでした。あれが通過順かな…？

*2:高速化に落とせるようなDPではなく、「i番目までを使い、i番目までの連続不使用要素がj個である時の効用最大値」みたいなのを考えていました…

*3:dp[0] = 0

*4:対応がわかりやすいようにb[i]の添字を1, ..., Nとして書いています。実装の際はインデックスをずらすか、b[0]にダミーを入れてください。

*5:根ノード以外の頂点の隣接リストは今後使わないので、消しても放置してもよいです。