ぷぇ

競技プログラミングとかについて書きます。

JAG夏合宿2017 参加記

参加記 ぽえむ AtCoder ICPC

ICPCアジア地区大会2017の参加権を持っていませんが、JAG夏合宿に参加させていただきました。

合宿を開催して下さったJAGの皆様、本当にありがとうございました。

ものすごく楽しくてためになるので、来年も是非参加したいです。

普段Twitterで観測しているプロ達が本当にこの世に存在しているということを確認できる数少ない機会の一つだと思いました。

 

以下、参加記

参加記というよりぼやきとかぽえむとかの方に近いかもしれないので、苦手な方はごめんなさい。それと、この記事に知見はありません。

 

 

Day -1 以前

ACPCにオンラインで参加していた。

チームは aotenjou ( @vinami @oshiboripinku @1119_2916 ) いつもどおり。

フル参加だったので少しハードでしたがとても楽しかったです。

主催してくださった会津大学競技プログラミング部の皆様やスポンサーのRCOの関係者様、問題を作って下さったwriterやテスターの皆様ありがとうございました！！！！

参加記もどきはこちらのモーメントにまとめた。

 

 

 

Day 0 (夏合宿前日)

弊学は夏休みが終わっているので普通に授業。

◯◯LAN 系クソなぞなぞの流れがあった。

 

 

名札を用意したが、会場でも貸出があった。

 

ACPCのおかげで日本時間を理解していたので、早めに就寝。

 

Day 1

 家から１時間半くらいで会場に辿りつける感じだったので、ちょっと早く起きて荷物を準備し出発。参宮橋駅で minami (@vinami), oshibori ( @oshiboripinku ) が揃う。

お昼ごはんに日本一を主張する唐揚げを食べ、オリセンへ向かった。

たどり着いて合宿の説明を聞いたらすぐコンテスト。

 

コンテストのリンクはこちら

 

DHJKの４完で30位でした。私はKをバグらせる担当をしました🌽

時系列順にコンテストの振り返りをしたのがこちら

  • チームの方針は、minami がコーダーをして、残り2人は思い思いに問題を解いていく、という感じ。順位表をちょこちょこ見てAC数が多い問題をどんどん見ていく。コーダーは、コーダーといっても全ての実装をするわけではなく、コーダーがPCに張り付いてじっくりと少し難しめか実装の多い問題をやり続け、残りの2人は紙プログラミングをしていい感じになったらコーダーからPCを受け取る、という雑なもの。
  • 問題文が日本語だったので、全員が適当に問題を見ていって簡単そうなものを探す
  • minami がJ問題をAC(8:24)
  • D問題が簡単そうなのでいろいろ考えていたがわからず、K問題が僕の好きそうな感じだったのでDを oshibori と Jが終わったminami に投げてKを考え始める
  • K問題でコスト小さい順とゲイン大きい順の2通りを試せばどっちかが最適になるのでは？という発想のソースを提出しWAをもらう(36:56)
  • Kは絶対この方針であってるから！！と謎の主張を minami にするが、「絶対間違ってる」とのこと。この後ずっとWAケースを生成出来ず苦しみ続ける。
  • Dの方針をまとめた2人がソースを書き提出、AC。プロ！(65:02)
    ？？？「中学受験の気持ちになった」
    ？？？「難関中学合格した」
  • この構文解析はやるだけなのでは？ということで minami にE問題を任せる。
  • Kに苦しんでいる間に片手間でHの考察をしていたので、oshibori になんとなく問題概要を伝え移動すると8方位それぞれこの値のコストがかかるよの図を渡す。
  • Kの最初の方針を信じて疑わない私がオーバーフローによるWAが原因なのでは？と思い #define int long long し提出。WA。(104:50)
  • Kについて、得られるマナの総和が一定であり、全てを抽出する状態から1枚だけ召喚した時、消費マナは c[i] + g[i] であることに気づく。
  • 消費マナが小さい順に採用する貪欲は自明だったので、c[i] + g[i] をソートする貪欲でAC。(124:09)
  • 順位表を見てAC数が多かったA問題の考察を始める。
  • oshibori がHを書いて提出。WA。minami がデバッグに参加する。思い返せばもうちょっと前から合流してやっていたような気がするが、Kに必至だったので覚えていない…
  • Hのバグを minami が指摘したようで、AC。やはり実験系は oshibori に任せて良さそう（プロ）(160:58)
  • Aで a -> ab -> b -> bc -> ... という感じで遷移すると最適っぽいので、
    i 文字 -> i+1文字 -> i 文字 -> ... という遷移をすると最適なのでは？と発想するがなんだかダメそう。
  • コンテスト終了

〜ここから反省〜

K問題で自分の解法を信じすぎた。

構文解析を minami に投げてハマらせてしまった。構文解析、幾何のようなバグる系、実装系は慎重に選ばなければならなさそう。つまり状況による。

A問題を解きたかった。Aに着手した時点で結構頭が疲れていたのか、考察が惜しいところまでいっていたのに残りを詰められなかった。体力をつけるか最適な立ち回りをするべき。　というかKで体力を使っていなければAも通せたのでは？

AEFのなかからあと2問くらい解けていたらいい感じだったのかなぁ。

コーダーがほとんどPCを触っていなかったらしいので、PCが開く時間が結構あったらしい。これはチーム全体の動きの問題ですね。

参加記を書くことによって自分がチームの状況を全く確認できていなかった事に気付いたので、私は全体に問題を適切に割り振る係をするのならばもっとしっかりやらなければならないと分かった。チーム戦略をちゃんと練ろうね。

K問題、問題文のスヌケさんがマヌケさんに見えてしまってつらいので、snukeさんかすぬけさんって書いて欲しいです。おねがいします。（ごめんなさい）

 

結果

 

反省会をしつつ夕飯へ。

 夕飯後に解説があったのですが、大雨で靴が濡れてしまってその後の2日間をつらい気持ちで過ごさなければならなくなった。来年はサンダル的なものを持って行こう…。

解説はwriterであるすぬけさんによるもの。すぬけさんを初めて観測した。保冷剤を顔に当てていたのはなぜだろう。

やはりプロの解説はとても刺激になった。Day1, 良問揃いでした。

 

 

解説の後、らてあさん( @ratetion )が来てくれたのでお話。風呂のあとボードゲームしましょう！となる。そのあとTreeoneさん ( @treeone ) に話しかけて解説の会場を出た。

 

道中のエレベーターでやざてんさん( @Yazaten ) にお会いしてACPC day3 のYazatenjou についてちょこっとお話したり、ゆらふなさん( @yurahuna )にお会いしてお久しぶりですって言ったり、やなさん( @yana87cp )にお久しぶりですと話しかけたりした。

確かチェックインの時間辺りだった気がするけどしっかり覚えていない…もっとじっくりお話したかったです！ 

 

入浴後に談話室に行くと既に フェリンさん( @ferin_tech15)と Treeoneさんとらてあさんが居たので aotenjouの3人が合流して6人でボドゲ。別の談話室でも人々がボドゲをしていた。

 上の画像は クー というボードゲーム。

職業カードが2枚伏せて配られるので、そのカード特有の行動をしてゲームを進行する事が出来る（行動の選択肢は複数あり、毎ターン1つ選んで行動する）が、カードは自分しか確認できないので、職業を偽って行動をしてもよい。しかし他人が職業を偽って行動していると疑いをかけることができる。嘘がバレたり他のプレイヤーの行動により暗殺されたりすると、伏せられたカードが1枚表になり、2枚とも表になると負け、みたいな感じ。

らてあさんの説明が上手くてすぐ理解できたのと、初プレイのはずの人々がみんな上手くて†地頭†を感じた。

後から Divさん( @Div9851 ) といむらんさん ( @__imulan__ ) がいらしたのでもっと大人数でできるゲームに変更。

コードネームというボードゲームをしました。

連想ゲーム、マジカルバナナ的なゲームで、
刑事モノ -> 事件 -> 探偵オペラミルキィホームズ -> オペラ と連想したり
刑事モノ -> 警官 -> コップ と連想したりしていて面白かった。

結局12時ギリギリまでボードゲームをし続け、その日は解散。

6時間近くやったらしい。合宿中のどのコンテスト時間より長くやったはずなのに一瞬に感じた。ボドゲオフかオンラインボドゲ会が求められている…！！

Treeoneさんのふぁぼ爆を観測して就寝。

 

 Day 2

 起床、朝食。

食堂でゆらふなさんとお会いしてご一緒する。

チーム戦略の話やチーム練習の話をしたような記憶がある。じっくりお話したのは初めてだったような気がするが、なんとなくそんな気がしなかったのでやはりTwitterは偉大。

ごはんを終えたらすぐコンテスト。

 

コンテストはこちら。直接参加登録画面に飛びます。

 

コンテスト開始20分前とかに、satanicさん (@satanic0258 ) の
限界まで息を止めて一気に吸うことで脳の働きを活性化させる手法
を試そうと盛り上がっていた。

 

 脳みそがすっきりするような感覚が得られるので本当に効果があるのかもしれない。

命を削って競プロをしている感覚がたまんねぇな とか思っていた。

 

コンテストを時系列順に振り返ります。

  • 難易度順でないこと、前半に難しい問題があることを聞かされていたので、後半から、或いは問題文が短いものから読んでいくことにした。
  • 前日に細かく初動を決めてダメだったので、今日は初動は何も決めず適当にいこう、という方針にする。
  • oshibori が一番英語ができるため、難しい問題文は oshibori に渡す。
  • minami は前日に引き続きコーダーをするので、簡単そうな問題を発見したらすぐ渡す。
  • 開始1時間ほどを使って和訳＋要約した問題文を作り、後半を楽にする作戦をとることにした。
  • 前日同様順位表を見て解けそうな問題からやっていく。
  • コンテスト開始。問題文が短い3問を読んでゆく。
  • L問題を読んでいると比較的簡単だということに気づく。取り組む。
  • L問題でプールがnレーンあり、レーン毎に存在する人々の数が与えられる。1レーン当たり1人移動する事が出来る時、最大の人数を保有するレーンにいる人々の総和はいくつか？という問題に誤読する。（大体10分経過）
  • minami が J問題を提出。WA。(15:42)
  • L問題で1レーン当たり1人ではなく、全体で1人移動させる、だということに気づく。（大体15分経過）
  • 最大値が1つの時、最大値が複数の時の2通りのなかでそれぞれ、2番目の最大値が最大値−1のとき、そうでない時で場合分けすればよさそうと思い、書いて提出。WA。(34:27)
  • その後私はひたすらL問題をバグらせ続ける。約2時間。
  • minami がJ問題提出。WA。(39:28)
    ここでJ問題を捨てて別の問題に行った様子。（英断だったと思う）
  • minami がAC数が多かったG問題に取り組み始める。
  • oshibori が大体解ける可能性のありそうな問題（この時点でACが1つでも出ている問題）の翻訳を終える。プロ。（1時間半後くらいだった気がする）
  • oshibori がH問題を考察し始める。いつからだったかは覚えていない。
  • minami の手を少し借りてL問題をAC。(1:59:09)
    ひたすらにバグってとてもつらかったのを覚えている。6WA出した。
  • L問題が終わったので oshibori のG問題考察に混ざる。この時点で考察が7割り方終わっていた。minamiのアドバイスもあった模様。
    一列に並んだNマスを全て1度ずつ通りたい。移動方法は隣に飛ぶ、1個飛ばして隣に飛ぶ、の2通り。開始位置と終端位置が与えられた時、隣に飛ぶ最小の回数を出力せよ。全てのマスを1度ずつ訪れる事が出来ない場合は−1を出力せよ。という問題。
  • minami がG問題を提出。WA。(2:22:33)
    ここから minami のデバッグ地獄が始まる。
  • L問題の考察を oshibori と詰めて、丁寧に場合分けを判断して行った結果、一発AC。(2:52:54) 最高の気分だった。
  • AC数が多かったB問題を oshibori と二人で考察し始める。
    DP[文字列の長さ][括弧のネストの深さ]の方針で考え続ける。
    解説によると何故かこの添字のDPだとWAになってしまうらしい。
  • この後ACはなくコンテスト終了。

 

〜反省〜

英語かつ難易度順でない問題セットに取り組んだのは初めてだったので、経験になった。

初動はちゃんと考えて決めたほうがいい。

Hの誤読が多かったらしいので、誤読せず正確に読んでくれた oshibori に感謝。

Gは全体のAC数の割に弊チームのバグがすごかったので、minami 一人に任せっきりにしないで私も1から考えてみればよかった。こういうパターンは似たような考察でも実装のアプローチを変えるとスッと通ったりするので考察に混ざるのではなく全く別で考え始めるという手もあると思うがどうだろうか。

私のDP力が低い。B問題が解けるようになるとワンランク上の競プロerになれる気がする。

L問題みたいな場合分けがきつい自明な問題に2時間もかけてしまうのは明らかに失敗。こういう問題は目の前のバグったコードをベースになんとかしようとするのではなく、ちゃんと問題文を最後まで紙上で考察しきって実装する事が大切。場合分けの穴はコードのバグを直してもACにならないんだよなぁ…。

ICPC系コンテストでバグが凄い時は、ペアプロでバグ取りをしたい。
しかしこれを効率化するのは難しそう。ペアプロをし始めるまでの時間コストも気になるのでその辺りを天秤に掛けて上手く判断する必要がありそう。

 

結果

 HL2完で終了。とてもつらい。虚無虚無言いながら夕飯へ。

この虚無の後にコドフェス予選するのか…とか言っていた。

 

 夕食のサラダのラインアップが前日と変わっていて、とうとうコーン🌽が出てしまっていたので、クソダジャレを投稿しました。

 

 おるふぇくん ( @_olphe ) が喜びそうだなとか考えていた。

クソダジャレ流行るといいなと思うけど、クソなぞなぞの下位互換感がね。

後からDivさんフェリンさんが来たので、競プロの話をしながら夕飯。

競プロerと、競プロや競プロを取り巻く環境の話等をするのは楽しい。競プロにお金を出してくれる会社の話などもした。

夕食後はボードゲームをしたかったけれど、5時間コンテストの疲れをしっかり取ってからコドフェス予選に挑みたかったため、断念。ボードゲームしたかった…！

 

コドフェス予選の準備を終えた時点で、50分ほどコンテストまで時間があった。

そわそわした気持ちを落ち着けるために談話室に行くと結構人々が集まっていて、邪な方法でコドフェス予選を通過する話をしたりして盛り上がった。

この時ちょっとお話をしていた方がばた子さん ( @btk15049 ) だったということに後で気づく。自己紹介的な事が出来ず申し訳ない気持ちになった。

コンテストを談話室でする人々もいて、JAGの方がなんとルーター等？を準備して下さっていて素晴らしかったが、落ち着いて出たかったので個室で参加。JAG最高すぎる…！！

 

コドフェス予選は結局上手く行かず予選突破ラインより遥か下の順位を取った。

コドフェス予選の参加記（考察記）を書くかもしれないし、書かないかもしれない。
書いた場合ここにリンクが貼られるかもしれない。

 

コンテストが終わると談話室に人々が続々と集まってきて密度が凄いことになった。

解けた人の解説を聞いていたらwriterさんが現れたりしたので、いま自分がいる環境はすさまじいんだなぁと思うなどしたが、やっていることは普段のTwitterのTLと全く同じだったのでそれもまた面白かった。

 

予選B, Cは通過目指して頑張ります！！

つらいなぁと思いながら就寝。翌朝はチェックアウトなので早起きしなければならない。夏合宿の朝は早いを思い出した。解いた事ないけど。

 

Day 3

起床成功。チームメイトもちゃんと起床したので、朝食に向かう。

談話室でNAIST勢とQU勢とフェリンさんに出会ったので一緒に朝食。

QUの競プロ事情などが聞けた。弊学ももっと競プロ普及させたいと思うなどした。

部屋に戻りチェックアウトの準備をし、部屋の鍵とシーツを提出しコンテストへ向かう。

コンテストまでの時間にクソツイートを生やしたりした。

しっかり動きを確認してコンテストへ。

問題セットはこちら。

  • 難易度順にならんでいないと思っていたので、全体を見て問題文が短いものから見ていくことにした。
  • コーダーを minami から私に変更し、minamiは考察に専念することにした。
  • 問題文の要約は作らず、読んだ人に問題概要を聞くスタイルにすることにした。
  • beta.atcoderが使えたので、順位表を自動更新にして開いておくことで First AC を観測してその後を追う作戦を取ることにした。
  • コンテスト開始。問題文が短いものを探すのにもたつく。それぞれ読むものを決めて読んでいるうちにA問題が解かれる。どうやら難易度順に並んでいるようだ、という事が分かる。
  • Aをminamiが、Bを私が、Cを oshibori が読むことになった。すぐに minami がA問題をAC (7:16)
  • B問題はどこかで見たことのある問題のような気がした。数列が与えられるので、その数列を順に足していった時、一番はじめにその和が一定以下になるのはいつか？数列は循環する。という問題。
  • まず1回試して、周期全体の和を見るのが解法だと知っていたが、周期内での累積和の最小値を求めると、周期内でその値より小さいものが出現しない事がわかるので、累積和を先に求めてその最小値を引いた目標値を周期の総和で割った値を答えとした。プラスマイナスを逆にするなどして1WA出したがAC(32:56)
  • minami がF問題を考えているようだった。oshibori がC問題を考えていたので問題概要を聞いて考察に参加。この時点で左上を固定すると一意に定まる事がわかっていたので、頂点の次数から判断して順番に決めていくだけだった。実装をバグらせたのでその後デバッグをする。AC。(3:06:23)
  • minami がひたすらデバッグをしていた。oshibori がDの考察をしていたのでDの考察に混ざる。DはbitDPのようだけど上手く遷移が出来ずひたすら悩んでいた。
  • Dの解法を生やす。
    DP[じゃんけんに参加する人々][自分がどの手を出すか] = その時の勝率
    というDPテーブルをメモ化再帰で解けばいけそう。すぐに実装を始めるが、微妙に実装量があってバグが出そう。気をつけて書いてゆく。
  • だいたい書き上げて動かすとサンプルが合わないので印刷してデバッグ。minamiがFのバグの原因が分かったというので交代交代でデバッグをしていく。
  • Fを記念提出だなーと言いながら終了30秒前に提出。AC。(4:59:31)
  • Dはバグったままでした。

 

〜反省〜

バグらせている時間が長すぎたので参加記に書くことが少ない。悲しい。

当たり前のことだが、ICPC系コンテストでは特に実装の考察をちゃんと詰めないとデバッグで時間を取られすぎるという事が分かった。

C問題に2時間半掛けたのが明らかにダメで、どうしてこうなったかというと実装の考察をちゃんとしなかったからである。

F問題について、グラフを倍化して解く、という方針で解かなかったらしいので、典型テクニックの知識が足りていないらしい。45度回転とか、グラフの倍化とか、そのあたりの知識をつける必要がある。

DFEから難しくなるコンテストだったので、ABCをいかに早く解くかも大切なポイントだったので、とにかくC問題での失敗が悔やまれた。折角C問題を2人で考察したのだから、ペアプロするなどしていればバグが減ったかもしれない。

最後にFが通ったおかげで順位が少し上がって激冷えを免れた。

コーダーやらの役割分担が形だけになっていて意味がないので、ちゃんと実力に合ったチーム戦略を考える必要があると分かった。チーム戦略についても知見をまとめた記事が色々あるので学ぶ必要がある。

 

結果

 ABCFの4完で32位でした。C問題をもっと早く解いてD問題に時間を掛けられればもう1完できたのかなぁ。

その後は交流もなく解散。aotenjouの3人で3日間のコンテストの反省をしつつ帰路に着いた。折角だし時間のある方を探して遊びに行くなどすればよかったと少し後悔している。

 

 

総括すると、JAG夏合宿で僕はバグ生やしを担当しました。

夏合宿で学んだことを活かして来年こそ国内予選突破するぞと決意し、

参加記を書いて夏合宿終了です。

運営してくださったJAGの皆様、本当にありがとうございました！

 

https://twitter.com/

19_2916/statu

s

/910811943