日々drdrする人のメモ

今日も明日もdrdr

DCJ 2017 (Round1)

Distributed Code Jam 2017のRound1参加
Dashboard - Distributed Round 1 2017 - Google Code Jam

前日体調最悪で寝込んでたら、GCJ Round2終わってた...。
なので、代わりにDistributed Code Jam (DCJ) Round1の方に出てた。

3時間4問。500位までRound2進出とTシャツ。
41pts(B,C,D-small,E-small)とれて395位。
500位以内には入れたのでDCJ Round2進出+Tシャツが飛んで来るはず。

準備

Quick-Start Guide | Google Code Jam
ここにローカルでテストできるツールがおいてあるので利用した。
practiceやってるメールが飛んできてたけど、気づいたころには終わってたっぽい。

提出コード: Distributed Code Jam 2017 - Round1 · GitHub
以下、B問題~E問題の雑解法メモ。

B. Pancakes

問題

食事する人が {D}人がいて円周上のテーブルを囲んで座っており、時計回りに0から {D-1}までの数字が割り当てられている。
あなたはパンケーキサーバーで、積み上げられたパンケーキを持っている。

各パンケーキにはタイプがあり、0から {D-1}までタイプがある。
また、各人には好みがあり、それは各人の数字に対応するパンケーキのタイプである。(例えば、4の人であれば、4のタイプのパンケーキが好み)

あなたは、0の人の位置から始めてテーブルを時計回りに周回しながら、積み上げられたパンケーキを上から、そのタイプの好みの人に取ってもらう必要がある。あなたがパンケーキがなくなるまで周回したとき、何周まわる必要があるか。

制約

Small:
ノード数 = 10
 {0 \le \text{GetStackSize()} \le 10^5}
{0 \le \text{GetNumDiners()} \le 10^6}

Large:
ノード数 = 100
 {0 \le \text{GetStackSize()} \le 10^8}
{0 \le \text{GetNumDiners()} \le 10^9}

解法

パンケーキのstackを順番に見ていき、周回する回数を計算した。
前回のパンケーキのタイプAと今回のパンケーキのタイプBをチェックして、 {B < A}であれば、1周追加すると計算した。

あとは、各ノードにある区間のstackを等分割して並列計算させて、周回の合計を集約して出力させた。

これで、Small, Large共に解けた。

C. Weird Editor

問題

10進数の正の整数を編集するためにテキストエディタをインストールした。
このテキストエディタは、ある桁を削除して、数字の右端に0を追加する操作しかできない。
例えば、3001であれば、十の位に対して操作を行い、3010に変更できる。
この操作で整数を最大にした時いくらになるか。 {10^9 + 7}の余りで出力せよ。

制約

Small:
ノード数 = 10
 {2 \le \text{GetNumberLength()} \le 10^6}

Small:
ノード数 = 100
 {2 \le \text{GetNumberLength()} \le 10^9}

解法

ある桁の数字Aについて、この桁より右にAより大きい数字がある場合、この数字Aを消した方が大きくなる。
(例えば、5234であれば、2,3を削除して5400にした時が最大)
これを考えた時、最終的に最大になるのは"[9のみ][8のみ][7のみ]...[1のみ][0のみ]"という形になる。

計算としては桁の右端から順番に調べていき、現在の位置の桁から右端の桁までで最大になる数字Xを保持しながら、その保持する数字Xと一致する桁の数を、その数字Xの個数としてカウントした。このカウントの結果は、最終的に最大になる時に残る各数字の数になる。
桁数が大きいので、ノードごとに桁を等分割してこのカウントを計算し、一つのノードにこの結果を集約して、全体のカウントを計算した。

カウントした後は、実際に出力する値を計算するが、これは繰り返し二乗法で各数字Xについて"XX...X00...0"の値を計算し、その和を計算する。

これでSmall, Large共に解けた。

D. Todd and Steven

問題

ToddとStevenの二人がいる。ある数列に対して、Toddが数列の内の奇数をソート、Stevenが偶数をソートして、マージしてソートの結果を得ようとしている。ToddとStevenがソートした後の数列2つが与えられるので、マージしてもらいたい。

出力としてマージした数列を0-indexedと考えた時の {\sum_j X_j \text{xor} j}を計算して {10^9 + 7}の余りで出力しなさい。

制約

Small:
ノード数 = 10
 {1 \le \text{GetToddLength()} \le 10^6}
 {1 \le \text{GetStevenLength()} \le 10^6}

Large:
ノード数 = 10
 {1 \le \text{GetToddLength()} \le 10^9}
 {1 \le \text{GetStevenLength()} \le 10^9}

解法

Smallは一つのノードでマージして計算するだけでできた。
Largeは数列が長いのでToddとStevenの持つ数列のうち、ある区間に含まれる数値をうまく分割して100ノードに分割して計算する必要がある。
とりあえず、各ノードに数列を等しく100等分するのがよいと思ったので、Toddの持つ数列に二分探索しながらStevenの持つ数列に二分探索をかけて二人合わせて全体の100分の1になるように計算しようとしたらバグったので終了。

E. Query of Death

問題

ある個数の0-1の数字が与えられる。この数字の {i}番目の数字はGetValue(i)で参照できるが、ある {i_{qod}}番目を参照すると、最初は正しい値を返すが、それ以降そのノードで参照する全てのiについてGetValue(i)の値が壊れてランダムになってしまう。
この状況の中で、 {\sum_i \text{GetValue(i)}}を求めなさい。

制約

Small:
ノード数 = 10
 {1 \le \text{GetLength()} \le 10^4}

Large:
ノード数 = 100
 {1 \le \text{GetLength()} \le 10^8}

解法

Smallでは、一つのノードで一つの数字について100回参照することで {i_{qod}}を見つけておき、別のノードで正しい値を計算した。
Largeは、数字を100等分して、各数字に対し10回参照して、ランダムになってしまったら、集計ノードで再計算するというコードを書いた。しかし、集計ノードで{i_{qod}}を踏んでしまったらアウトということを見落として終了。(10回参照で {i_{qod}}を見つけ出せるかどうかもちょっと怪しそう)

思ったこと

DCJは始めて参加したけど、いかにうまくデータを分散して並列計算し集計するかを問う問題が出てて、いつもとは異なる視点から考えるコンテストで楽しかった。
あと問題を解いていた時に、ノードに分割する際にノード数よりデータが少なくてデータがないノードが出てきた場合に変な値を返さないようにうまく処理をするよう心がけるべきだなと思った。(過去問解いたらちょっとやらかしたので)

追記

Tシャツ届いた!