Hatena::Grouptopcoder

kuuso1の日記

2018-07-30

オンサイトコンテストで動揺するいつものやつ ~SoundHound Programming Contest 2018 Masters Tournament 本戦 参加記

| 01:43 |  オンサイトコンテストで動揺するいつものやつ ~SoundHound Programming Contest 2018 Masters Tournament 本戦 参加記 - kuuso1の日記 を含むブックマーク はてなブックマーク -  オンサイトコンテストで動揺するいつものやつ ~SoundHound Programming Contest 2018 Masters Tournament 本戦 参加記 - kuuso1の日記

SoundHound Programming Contest 2018 Masters Tournament 本戦に参加してきました.

https://soundhound2018-summer-final-open.contest.atcoder.jp/

背景

 AtCoder社の弛まぬ企業努力と発展から,プログラミングコンテストを主宰する企業が増えてきた昨今,

そろそろあってもおかしくない気がしていた待望の社会人オンリーコンテストが昨日行われました.

Sound Hound社主催のプログラミングコンテスト,その名もSoundHound Programming Contest 2018 Masters Tournament.

 今回,Mastersを冠しているだけあり,既卒者限定30名を決勝招待,さらにover30枠として30歳以上のコンテスタントを優先的に10名選出という

多義的にアグレッシブな選考基準が設けられていました.(実際には40名が決勝参加していたので増枠があったのかも)

 今年は,自身の成績はGoogleCodeJamもFHCもTCOも爆死していたなか予選を88位全完だったので,これはワンチャンあるのではと思って期待していたところ,

TLの人々の通過通知より少しのラグの後私の元にも通知が来ました.ありがとうnuipさん(予選のwriterだった),ありがとうSound Houndさん.

前日から当日

・台風が来ている.本戦開催の土曜日に関東直撃らしい.マジか.

・運営の方から「当日8:30に開催可否の連絡を差し上げます」とのことだったが無事?開催の連絡が届く.

・6年以上ぶりの東海道新幹線はなるほど京都-品川間を2時間10分と迅速な移動を提供してくれたが,

 FenwickTree並みに爆速と名高い北陸新幹線の,新車ならではの快適さ(椅子や常備コンセント)が少し懐かしい.

 (最近無料Wifiまでついたらしい)

・会場は麻布十番の国際文化会館というところで,なにやらハイソな建物に少し物怖じする.

 (スマホアプリによると「普段は会員制の設備ですが,レストランは一般の方もご利用いただけます」とか書いてあった)

・本戦は別館だと示す立て看板を前に,二年ぶりに再会したTangentDayさんと少し話していると颯爽とAtCoder社の社長がタクシーで登場.

・入場手続きで名札とTシャツと交通費を受け取る.「交通費,実質賞金では」と感謝のサイン,ありがとうございます.

・残念ながらステッカーはないらしいが,折よくAtCoderステッカーが配布されていたのでゲット.(写真は帰りの新幹線車中)

f:id:kuuso1:20180731002454j:image

・会場に入るとSound Hound社のプロモ映像が流れているが,完全英語でなかなかハイレベルなところに迷い込んじまったぞという気持ち.

・とりあえず席を確保し,PCセットアップ,ネットワークACする.

 今回,SurfaceProのキーボードが使い慣れないことがあり,愛用の外付け青軸キーボードも持参していたのだけど,

 ここでコミュ障特有の7大スキルの一つ,悪目立ちを避けろ警報が発動してしまい,結局SurfaceProのキーボードで臨むことに.

イントロ1:kenkoooo さんの諸注意タイム

・電源タップがタコ足コードフェスティバルでひっかけると島単位で一網打尽になるので気を付けて.

・ネットワークがそこまで太くないので,動画再生しながらのコンテスト参加はお控えください.

イントロ2:SoundHound社の説明と製品のデモ

・ハンズフリー対話アプリで凄く賢そう.英語でのやりとりだったのでますます凄そうに聞こえる.

・「OK,Hound」が「おけいはん」に聞こえる程度の英語力のワイ.

・紹介しているときに「クエリに対して~」とお姉さんが説明していて,

 これまでの僕の一般生活の中で初めてクエリという単語が登場したような気がする.

15:00- コンテスト開始.

A問題

・とりあえず読む.

・整数CとDが与えられて,左閉右開区間 [C,D)の中の整数で,2で割って行ったときに[140,170)に入るものの個数を答える問題.

・[140,170) を2倍した [280, 340)は[140,170)と交わらないので,

 どんどん倍々していって,都度,半開区間[C, D)とのオーバーラップを計算するだけ.

・が,コンテスト特有の動揺パニックがkuusoを襲う.for文のループが書けない,手が震える.なんだこれ.

・何回かのタイプミス(CやDを2倍したりしてた)のあととりあえず外側のforを書き,中のオーバーラップ判定部分をif文で書いていくも

 答えが全然合わない.ひどい.20分くらい迷走.

・キーボードが裏目ったよこれ...かばんにキーボード詰めた時の強い精神力はなんだったの・・

・えええマジ?これはさすがにヤバないと思って,順位表を見ると40人の本戦参加者のうち通していないのは3人だけ.

 というか3人のうち2人はメンツ的に高得点側から解く方針だろうし実質零点ワイだけなんですけど.

・やばいやばいやばい.

・周りからこだまするキーボード音がますます焦りに拍車をかける.

 前回DDCCオンサイトに出た時に初めて体験したキーボード音プレッシャーに,「これに焦らないことが大事だよ」と懇親会でいろいろな方に

 アドバイスいただいていたが,やっぱりこれはきつい.

・とりあえず,オーバーラップ判定をべた書き関数ででも愚直に書こうと思いなおし,とにかくあり得るパターンを列挙する.

f:id:kuuso1:20180731001723j:image

 悲壮感漂うメモ書きからの関数実装.

long overwrap(long a, long b, long c, long d){
  if(b <= c) return 0;
  if(d <= a) return 0;
  if(c <= a && b <= d) return b - a;
  if(a <= c && d <= b) return d - c;
  if(a <= c && c <= b && b <= d) return b - c;
  if(c <= a && a <= d && d <= b) return d - a;
  return 0;
}

・なんとかAC,時すでに29分経過.コンテスト開始直前にツイートした「台風の中太陽生やす」をとりあえず回避できて安堵.

・ところでオーバーラップはoverlapですね...

B問題

・整数の列 B_n (N ≤ 100000, -1e9 ≤ B_k ≤ 1e9)と定数 K が与えられる.

・任意のK-連続区間を選んで全てを0に置き換えることができる.この操作は何度でも可能である.

・このとき,適切に操作を行って ΣB_k を最大化せよという問題.

・んん?400点にしてはムズない?コンテスト補正??単に動揺してるだけ???

・(ここから迷走タイム)

・一つ区間を消したなら,その区間に隣接する項が負の項ならどんどん消していける.

・とりあえず総和がマイナスなら,そこを消すことで総和はゲインするんだから,それは消してもいいんじゃね?

・いやいや,そんなこと言い出したら,累積和が0付近を振動するやつはどうすんの??

・それとか,K = 3 で 数列が {2, -10, 1, 11}で {2, -10, 1}をうまく選んで消せないでしょうが.

・分からん.

・分からん.

・分からん.

・ここで問題C,問題D,順位表をみる.

・問題CはN ≤ 30でビット系の制約っぽいが解いてる人が少なくヤバそうな雰囲気.

・問題Dは結構解いている人が多いが,クエリ系の問題だったのでたぶん苦手そう.

・どちらも800だし,B問題を捨ててこいつらを考えるのがいいか,おちついてB問題をもう一度考えるべきか.

・…さすがにB問題解けないってことは無いでしょう…!

・そうは言っても,O(N)かせいぜいO(NlogN)くらいで決めるしかない制約である.(ここまで迷走)

・尺取りみたいになるとして,消す区間を重複なく数えるためにはどうするか.

・左端に代表させるか.左端を決めた時にいくつ消すかを考える.恣意的に決められる??

・決められない,が.

・あ,左から見ていってi番目に今いるとして,K個以上前方を消すか,今のB_iを吸収するかの選択をすればいいのか.

 dpですねヤッター.

・K個以上前方を消すというのが,愚直に書くとO(N^2)になるけど,飛んできたということを区別しておけば,

 最大値だけを覚えて前に伝えていけば,Kより前方を塗りつぶしたdpと同じ意味になるな.

・とりあえず書く,サンプル通る,投げる,半分WA

dpテーブルをprintfデバッグ+手書きdpテーブルベリファイする.

 dpの定義が少しあいまいだったやつ

dp[t]:B_tを目の前にしてこれまでの最大値,推移は前方K個先にdp[t]をそのまま持って行くか,B_tを加えたものをt+1番目に伝播するか)

f:id:kuuso1:20180731005841j:image

public void Solve(){
  long Inf = (long) 1e18;
  long[] dp = new long[N + 1];
  for(int i=0;i<N+1;i++) dp[i] = - Inf;
		
  long[] ma = new long[N + 1];
  for(int i=0;i<N+1;i++) ma[i] = - Inf;
		
  dp[0] = 0;
  dp[K] = 0;
  ma[K] = 0;
  for(int i=0;i<=N;i++){
  long now = dp[i];
    if(i > 0) ma[i] = Math.Max(ma[i], ma[i - 1]);
    now = Math.Max(now, ma[i]);
    dp[i] = now;
    if(i + K <= N){
      dp[i + K] = Math.Max(dp[i + K], dp[i]);
      ma[i + K] = Math.Max(ma[i + K], dp[i]);
      ma[i + K] = Math.Max(ma[i + K], ma[i + K - 1]);
    }
    if(i + 1 <= N){
      dp[i + 1] = Math.Max(dp[i + 1], dp[i] + B[i]);
    }
  }
  Console.WriteLine(dp[N]);
}

・投げる.F5連打定期.こんどこそ通る.115:17.

・諦めないで良かった.泣きそうだったし成績もヨレヨレだが2時間満喫した感じは悪くない疲労感.

・怒りの半開区間クラスライブラリ実装を自分への宿題とした.

17:00- 歓談,コンテスト解説,懇親会,表彰.

・隣近所の席の方々と感想戦をするなどした.

 言うて強い人ばっかりだったが皆C問題に苦戦されていたようだった.

 ワイは疲弊しきっていて言葉が出ねぇ.mamekinさんが「貰うdpの方が書きやすいですよ」と教えてくださったが

 2日経ってからほんまやってなるやつだった.

 (範囲変更が絡むdpは貰う方が処理が楽なことが多いというノウハウはTDPC L - 猫なんかにある)

・解説,記憶がないがDは聞く限りはコンテスト中に着手したかったなぁと.

・懇親会は,「ここには未成年はいない,一人もな」ということでアルコールもあり大変満足.

・表彰式,10位まで賞金がいるという事で下位から順に賞金の授与が行われていましたが,

 なんということでしょう,ここにはレジェンドしかいない.

 最終順位表

・リアル知り合いはほとんど競プロをしていないので,コンテストやオフ会ぶりにあう方々と久しぶりに話せて大変満足.

 しかし私は口を開けば「やっぱり周囲のタイピング音で動揺してしまうんですよねorz」みたいな話しかできなかった気もする.

 こんどこそ青軸投入でワヤしていけという思いを新たにした.

・あと実は直接話したことがまだない方ともしゃべってみたいと思っていたが,疲労からか再びコミュ障の楔が発動してしまってそこはとても残念.

・20:00過ぎに解散,新幹線で帰路に.

 台風だが東海道新幹線は定刻どおりに発車.途中強風のため徐行し,30分遅れながら京都に到着.

 が,ここから乗るべき普通列車が全休していてしかたなくタクシー召喚.まぁまぁいい値段したね.仕方ないね.

感想

やっぱりオンサイトいいですね.また出られるように精進します.

あと次の機会があったとき,こんどこそ動揺しないために,わりと冗長にオロオロした様を日記につけておきましたとさ.