こんにちは。エンジニアの uwi です。
去る3月22日に、Indeedなど10企業の競プロ部のメンバーを集めて、RCOの桜橋オフィスでプログラミングコンテスト+交流会を開催しました。半期末に行われるのが恒例になりつつあります。
RCO社員も含め37人が参加しました。この4月からの新入社員も何名か参加しました。
今回の問題セットはCodeChef October Long Challenge 2017でした。この問題を使ったコンテストをvjudge上で行いました。(懇親会で若干酔っている)4~5人チームで2時間かけて解きます。
問題セットの選定は毎回私が行っています。問題セットは次の条件を満たしていないといけません。
Long Challengeのほとんどの回はこれらの条件すべてを満たしています。問題文が英語なのが難点ですが、日本語で書かれた問題セットでこれらの条件を満たすものは存在しないと思っています。
また、たくさんsubmitしてもらいたいので、同点の場合は最終提出時刻で順位をつけることとし、不正解の場合の追加ペナルティは0分としました。
これは寿司です。
結果は以下のようになりました。表中の数字は”スコア(-不正解回数)“を表します。
順位 | チーム | A | B | C | D | E | F | G | H | I | J | スコア(ペナルティ) |
---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | climpet, drken, kenkoooo, masibonge, hosii | 4(-2) | 5 | 6(-1) | 7 | 8(-2) | 10 | 11(-1) | 51(98) | |||
2 | sky, iehn, iwashi31, togatoga | 4(-1) | 5(-1) | 6(-3) | 7(-2) | 8 | 10(-1) | 11(-1) | 51(102) | |||
3 | logicmachine, ehara, yaoshimax, yumechi | 4(-1) | 5 | 6(-3) | 7(-3) | (-4) | 11 | 16(-4) | 49(107) | |||
4 | kawatea, hasi, roiti46, blue_jam | 4 | 5 | 6(-5) | 7 | 0.8(-2) | 10(-3) | 11 | 2.7(-2) | 46.5(112) | ||
5 | simezitan, darsein, shiratty8, eomole | 4(-1) | 5 | 6(-1) | 7 | 8(-6) | (-1) | 11 | 2.7(-1) | 43.7(117) | ||
6 | tomerun, hiro116s, ncastar, schwarzahl | 4 | 5 | 6(-13) | 7 | 2(-2) | 11 | (-1) | 35(91) | |||
7 | tokoharu, kyuridenamida, kenjih, xyz600 | 4(-1) | 5 | 6 | 7 | (-6) | 11 | 33(56) | ||||
8 | japlj, hs484, ukikagi, ___Johniel | 4 | 5(-1) | 6(-2) | 7(-1) | 11(-1) | (-7) | 33(105) | ||||
9 | uwi, nikeeshi, itohjam, daiju | 4(-3) | 5 | (-4) | 7(-1) | 10(-2) | 2.7(-1) | 28.7(117) |
色付きのセルはFirst Acceptanceを表します。
問題文が難解だったようで、誤読してそもそも問題の問うていることが把握できないということが私のチームでは多発していました。もっとチームメンバーに寄り添えていたらなと思っています。
E,F以降は実装が重い問題でした。H以降をまともに書こうとすると1問あたり1時間以上は潰れてしまいそうです。
Gは私のチーム以外が満点をとっていますが、これはミニマラソン問で、どうやら点数の入る提出であればどれも満点になってしまっていたようです。次回行うとしたら除外する予定です。
終わった後は、各問題の正解者に解説をしてもらいました。
優勝したチームには 日本橋ハーフマラソンの賞品のジャージが授与されました!
以下2問レビューします。
長さ$n~(99991\le n\le 10^5)$の整数列$a$が与えられたときに、次のプログラムを動かします。
このプログラムは32bitのunsigned intで和を求めているため、うまい入力を与えると間違った答えを返します。そうなるような$a$を答えてくださいという問題です。$a$の各要素は$1\sim 10^5$の整数値です。
プログラムが計算している値は、各$i$について、($a$の合計 + $a[i]$)になります。$i=1$を真の答えとしましょう。32bit unsigned intの制約をうまく利用したいので、($a$の合計 + $a[1]$) = $2^{32}-1$としておき、1以外の$a[i]$は$a[1]$より大きくなっていれば良さそうです。
$a[1]=1$として、残りの$2^{32}-1-a[1]*2 = 2^{32}-3$が$a[1]$以外の合計になっていればよく、$n-1$で割ったものを割り当てて余った分を1ずつ割り当てていく等の分配をすれば、上記の条件を満たす$a$が作れます。
他にも解法は色々あります。
長さ$n$の整数列$a$が与えられます。次の$q$個のクエリを処理してください。
$1\le n\le 10^6, 1\le q\le 10^5, 1\le a[i]\le 10^9, 1\le l\le r\le 10^9, 0<x\le 10000.$
この図は、$a=[3,7,2,4,8,7]$, クエリ$=“?~3~1~7”$に対するものです。
'?'
クエリで求めたいものをわかりやすくすると、$a[i]$から貪欲に狭義昇順列をとっていったとき、(値が$[l,r]$内にある要素の個数) + (値が$r$となる要素がなくかつ$r+1$以上になる要素が以降にあるなら$1$)になります。
想定解法は、Segment Tree の特殊な使い方をしていました。
まず、$a$に対し、1点更新可能な、区間最大値を求める Segment Tree を用意します。すると、$i$以降で$r+1$以上になる最初の要素がわかるので、そこより前の範囲にしか上記の昇順列の要素はないことがわかります。
ここで Segment Tree の各ノードに、$ilen$=(ノードに対応する$a$の部分列から昇順列をつくったときの長さ)を持たせます。これの計算は愚直にやると列の長さ分の時間がかかります。初期状態は計算できても、更新には対応できません。
更新は一旦おいておいて、ある区間と$l$が与えられるとき、区間に対応する列から、値が$l$以上の狭義昇順列をつくったときの長さを求めてみます。
更新ですが、現在のノード$cur$について $ilen[cur] = ilen[left~son] + $($cur$の右の子について、$cur$の左の子の最大値+$1$を$l$としたときの上記の長さ)として$O(\log^2 n)$で更新ができます。
私が後で解いた時は、Segment Tree のノードに、$ilen$と狭義昇順列そのものをTreapで持たせていました。これでも間に合うみたいです。
本番で唯一解いたチームは、平方分割を使って、一見通らないであろう計算量で通していました。
RCOアドテク部では、アルゴリズム、あるいは寿司が好きなエンジニアも募集しています。