AD-TECH
Lab BLOG
RCO アドテクLab ブログ

企業競プロ部合同プロコンレポート

2018/04/27uwi

このエントリーをはてなブックマークに追加

こんにちは。エンジニアの 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問レビューします。

C問題レビュー

概要

問題リンク

長さ$n~(99991\le n\le 10^5)$の整数列$a$が与えられたときに、次のプログラムを動かします。

  • 任意の$i$について$(a[1]+a[2]+\ldots +a[i])+(a[i]+a[i+1]+\ldots +a[n])$を計算し、これらのうち最小値を実現する最も小さい$i$を返す。

このプログラムは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$が作れます。

他にも解法は色々あります。

コード

H問題レビュー

概要

問題リンク

長さ$n$の整数列$a$が与えられます。次の$q$個のクエリを処理してください。

  • + i x : $a[i]~+=x$とする。
  • ? i l r : 各$k$に対し、平面上に線分$(k,0)-(k,a[k])$を並べる。その後$(i-0.5,l-0.5), (i-0.5,l+0.5), (i-0.5,l+1.5), \ldots , (i-0.5,r-0.5)$の$r-l+1$点からx軸正の方向にビームを打つ。各ビームが最初に命中した線分のうち相異なるものは何個あるか出力する。

$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$以上の狭義昇順列をつくったときの長さを求めてみます。

  • 長さが$1$のときは自明です。現在のノードを$cur$とすると、
    • $l\le a[cur]$なら、答えを$+1$し、$l = a[cur]+1$とします。
    • それ以外なら何もしません。
  • 入力区間が現在のノードを完全に覆っていない場合、左の子、右の子の順に再帰的に呼んで処理させます。左の子を処理した後$l$は更新されていることに注意してください。
  • 入力区間が現在のノード$cur$を完全に覆っている場合、
    • まず左の子を見ます。
    • 左の子の$\max$が$l$未満なら左の子の中に昇順列の要素はないので右の子を呼んで終わります。
    • そうでない場合、左の子を再帰的に呼びます。そうすると、左の子を処理し終わった後の$l$は左の子の最大値になっています。そうすると、右の子の処理をしなくても右の子で得られる答えがわかってしまいます。$ilen[cur] - ilen[left~son]$になります。 $l$を$\max[cur]+1$に更新して終わります。

更新ですが、現在のノード$cur$について $ilen[cur] = ilen[left~son] + $($cur$の右の子について、$cur$の左の子の最大値+$1$を$l$としたときの上記の長さ)として$O(\log^2 n)$で更新ができます。

私が後で解いた時は、Segment Tree のノードに、$ilen$と狭義昇順列そのものをTreapで持たせていました。これでも間に合うみたいです。

本番で唯一解いたチームは、平方分割を使って、一見通らないであろう計算量で通していました。

コード(想定解法)

コード(自己流解法)

広告

RCOアドテク部では、アルゴリズム、あるいは寿司が好きなエンジニアも募集しています。

採用ページ