ひゅ～Menの雑記帳

主にパソコン関係のことについて適当にしゃべります

JOI'20本選 敗退記

全列挙さんに脅されて、この記事を書きました。mencottonです。　

JOI'20本選に参加して244点でした。個人的にはかなり成功したと思ったのですが、3問目を23人も通しており、本選落ちです...

Day0

クエリ系の問題が出てきたときに殴れるように、一応平方分割を書いて寝た。

 

Day1

学校があったので、学校に行った。KCLCメンバーで事前に話し合った結果、別々に行動しつくばに向かうことになっていたので、昼食を中本にすることは朝から決めていた。

（本選前に普通に授業を受けるの図）

 

授業が終わったので、適当にクソツイをしながら、中本へと向かった。

 

クソツイをしてたらいつの間にか御徒町駅で降りていて、中本の前に来ていた。

実家のような蒙古タンメンを食べ、実家のように腹を壊した。（美味しかったです）

 

休憩を終え、無限人いそうなアキバへと向かったが、結局一人でグルコスして終わってしまった（社会性…）

 

グルコスを終えTXに乗ると、本選erが結構いた。

 

蟻本を見たり、ツイッターをしたりするなどし、つくばに到着。

 

割とギリギリだったので、すぐプラクティスをやった。

ところで、プラクティスで全完したあと内輪で固まって談笑するのが恒例となっていますが、内輪外からはどう思われているんでしょうね…（私は内輪側の人間なので分かりませんが…）

 

プラクティスを終え、OSSに関する講義を聞いた。業プロっぽい話を聞くのはあまりない機会だったので、興味深かった。

（なんとその後講演者の方からフォローされ、リプライを頂いた）

 

その後、夕食会場へと直行。自己紹介フェーズでは、人々のツイ垢を特定したり、tk72ersに煽られたりした。

 

バスに乗り、いつもの独房へ。人々と話すなどし、就寝。

 

Day2

絶起を回避し、いつもの朝食を食べた。

 

支度を終え、本選会場に向かうまで暇なので、人々に精神攻撃を仕掛ける。

 

そんなこんなで本選が開始する。クスリも決め、準備万端。

 

本選競技

本選中はスマホの使用が禁止されているため、本選中の行動はその場で手書きしたタイムラインによって記す。（解法のネタバレがあるので注意）

0:01:45 紙の不備が無いことを確かめ、本選開始。取り敢えず1問目「長いだけのネクタイ」に取り掛かる。

0:05:30 1問目なので、適当にソートすれば良さそうなことに気付く。単にソートして調べるだけだと、O(N^2) かかってTLEするので、GCD on Blackboard みたいに左右から累積MAXを取れば良いことに気付く。方針が立ったので、コーディング開始。

atcoder.jp

0:16:30 コーディング終了。テストケースも一発で合わせる。

0:18:15 提出し、1問目をAC。2問目「JJOOII 2」に取り掛かる。

0:21:45 2問目の考察が終了。消す文字数は固定なので、明らかに先頭と末尾の文字列をたくさん消したほうが良い。先頭をいくつ消すかを決めると、累積和を使い O(log N) で末尾をいくつ消すかが求まるので、全体として O(N log N) でできることが分かった。　実装を始める。

0:35:15 2問目の実装が終了。テストケースも一発で合わせる。

0:38:30 提出するも、TLEで13pts。Range-based-for が遅そうだったので、普通のforに直す。

0:40:45 訂正し、提出。無事AC。3問目の「スタンプラリー 3」に取り掛かる。

0:45:15 高々1回しか曲がらないギャグ問かと思い、実装する。

0:55:45 コーディング終了。テストケースが合わないので、少し直す。

1:04:30 直し終わったので、提出。WAで0pts。複数回曲がるケースの存在を確認。

1:06:45 区間DPでいけることに気付くが、その時点での経過時間も持って遷移しなければ行けないことに気付き、あと回しにしたくなる。

1:10:00 競技中1回目のトイレ。

1:13:15 トイレから帰還し、4問目の「オリンピックバス」を読み始める。

1:16:15 5ptsはやるだけだったので、実装することにする。適当な計算量解析の結果、ワーシャルフロイド法でも間に合うと思い、実装。

1:29:45 実装が終わり、テストケースも無事通ったので、提出。TLEで0ptsが帰ってくる。ダイクストラ法に変更。

1:41:30 ダイクストラ法の実装が終わり、提出。無事に5ptsを獲得。小課題2, 3を少し考えてみたが、何もわからないので5問目の「火事」を見てみる。

1:46:00 5問目の問題を読み終わり、考察に入る。

1:49:45 小課題3までは平方分割+αでできる*1ことが分かる。

1:51:00 競技中2回目のトイレ。

1:53:30 トイレから帰還し、実装を始める。

2:24:30 実装が終わり、テストケースも無事通ったので、提出。しっかりと小課題3までをACし、14pts。C問題に再度取り掛かる。

2:26:00 小課題1, 2は巡回セールスマン問題で解けることに気付く。実装を開始。

2:44:00 実装が終わり、テストケースも無事通ったので、提出。ACし、15pts。小課題3の区間DP解の詳細な考察に入る。

2:47:30 現在位置は始点からみて正の方向にいるか、負の方向にいるかだけ持っておけば良い、それによりDPの遷移もそこそこ単純に書けるとイメージできたので、実装に入る。

3:18:45 実装が終わり、テストケースも無事通ったので、提出。ACし、25pts。この時点で勝ちを確信する。

3:22:30 ここで何を狂ったか慢心し、4問目の嘘解法*2を思いついたので、実装する。

3:25:15 競技中3回目のトイレ。

3:42:30 実装が終わり、テストケースも無事通ったので、提出。WAとTLEが帰ってくる。vector<map<int, pair<long long, long long>>> という型でグラフを作ったので、TLEはある程度想定していたが、小課題1すら通らないのにビビる。適当にINFの値を調整するなどしたが、一向に通らない。

4:00:00 まごまごしている間に終了。最終結果は 3:18:45 時点と同じ、 100+100+25+5+14=244 pts。

 

解析の時間が開始する。全列挙氏から、3問目の本質*3を教えてもらう。確かになぁという感じになった。E869120氏が熱を出していたので少し心配だったが、余裕で3完+部分点を取っており、流石の貫禄。…と思っていたが、想定より3完している人が多い。

昼食中も人々の点数を観測していたが、本当にやけに3完が多い。そしてyuma氏のこのツイートを見て、私の自信は打ち砕かれた。なんと、この時点での投票者40人中、50%が3完以上だったのだ。

 

昼食を終え、解説を聞く。3問目のACコードは、なんと小課題2と3の考察を合わせることで出来ると解説された。そんな発想は全く無かったので、たまげた。

そして得点分布が開示される。やはり異常に多かった。

 

悲しくなり、square1001と一緒に高速バスで帰る。安いわりに割と速く着いたので、アド。

 

音ゲー勢とエンカするが、言及されていた通り無限人いたので撤退し、再びグルコス。

 

かなり暗くなり怖くなったので、1クレだけやり撤収。帰り際に見知らぬ人に声を掛けられ、微妙に怖くなる。適当にツイートをしながら、帰路へ。

 

ツイッターをしていたらkaage氏に煽られたので、仕返しにねぎしに行く。

ちなみに、毎回疑問に思っていた「とろろの食べ方」を、食後にヴァネロピ氏*4に伺うと、このように返ってきた。

 

食後ツイッターを開くと、このようなツイートを発見。

 

折角なので、画像を作ってみた。

f:id:mencotton0410:20200210185324p:plain

疲れていたため、帰宅後はすぐに就寝。

 

Day3

ボーダーは301となり、本選落ちが確定。square1001が銅賞であることも確定。

 

総括

　244点で十分通ったと考えていたために、春合宿に行けないのはただただ自分の精進不足だと感じました。昨年にくらべ今年のボーダーは異常に上がったので、来年のボーダーはさらに厳しくなることが予測されますが、それにも負けないぐらい精進し、次こそは通りたいと思います。

*1:セグ木でもできるが、正確に速く書く自信が無いので…

*2:各辺について最小コストと次点を記録し、指定された辺で遷移しないようにしたダイクストラ

*3:DPの添字と値を入れ替えるテク、EDPC-E みたいなの

*4:ねぎし界のtourist

AtCoder社に行ってchokudaiさんと話したお話

本文中に使われている略

ち：chokudai談
ひ：ひゅ～Men談

なぜ初対面のひゅ～Menのインタビューを快諾してくれたのか？

ち：正直な話、基本的に「会おう」と言われたらできるだけ、どんな要件でも会うようにはしています。というのも、基本的に社長って結構仕事が曖昧で、例えばプログラマなら「このプログラムをちゃんと作る」などという、決まった仕事があります。けれど、「どういう仕事をやるか」とか、「その仕事をどうやって取ってくるか」とか、といったところを決めるところからが社長の仕事なんです。だからどんな話でも聞いてみないことには分からないし、どこからどう繋がるか分からないから基本的に会うようにしています。 実は、日経のコンテストはe-sportsの話から始まったんです。（笑）
ひ：e-sportsというと、ぷよぷよ関連からですか？
ち：少し違って、JeSU*1方面からの繋がりなんですけど、これは話すと長くなるので（笑）どこまで話していいかよく分からない（笑）
ひ：私も2時間でどのくらいしっかり話せるか分からないので…
ち：そうですね。
ち：いろんな話で、結構違うところから繋がることはちょこちょこあります。もとをたどれば日経の話は「フィンテック」という、テクノロジーと経済を融合させるところから来てて、その関係でe-sportsをやっている人と繋がり、そっからコンテストの話が始まって…といった流れです。 そんな感じでいろんな繋がりがあって、そこから仕事を取ることが多いので、いろんな人に会います。だから、学生さんが「AtCoderいいですよ～」といろんなところで言ってくれていることは、割と感謝しています。

広がりを深めるために何をしているのか？

ひ：chokudaiさんはTwitterで競プロ以外のことも話しているじゃないですか。それって広がりを深めるためだと思っているのですが、どうですか？
ち：半々だと思います。半分は競プロ以外の所から人を取ってくるとか、繋がりを作っていろんな知識を得るとか。競プロだけに集中してしまうと、競プロ界隈の常識で考えてしまうので、そこから離れるというのは当然あります。もう半分は趣味で、ぷよぷよなんかは6割以上趣味ですね（笑）
自分が面白いと感じるなかで、いろんなところに顔だそうと思っています。働くだけだとどうしてもつまらないから。

AtCoderで就職

ひ：特に個人的にはIT系はブラックだという印象が強いので働くだけだとどうしてもつまらなくなりがちだという印象があります。
ち：そうですね。AtCoderやっている人はそんなとこ入らないですけど。
ひ：そう思っているのですが、やはり変なところに掴まれたら怖いので…
ち：レート上げとかないと（笑）レート上げたからといって就職できるかというとよく分からないですけど。
ひ：レートはプログラミング力の一種の指標になっていると思います。
ち：そうですね。

就職用に競プロするのはいい？

ひ：そういえば、AtCoderが有名になったことで、就職用に競プロする人が最近増えているように感じます。これは、本来のAtCoderの目的とは少し違うように私は感じたのですが、chokudaiさんはどう思いますか？
ち：正直、競技プログラミングってなかなかやってもらえないから、取っ掛かりとして就職を使うことは否定的には考えてないです。ただ、就職というモチベーションだけで競技プログラミングで通用するレベルまで上達するというのは現実的ではないと思います。それが出来る人は何やってもどうせ就職できるからいいよと思っています。
ち：そういう人だらけになったら少し対策は必要ですが、現時点ではそういう人がランキング上位を牛耳ってはおらず、どちらかというとと競プロを遊びでやっていて、就職にもつながっているといった感じになっていると思います。なので、まだそんなに気にしてはいません。 ひ：（Twitterでchokudaiさんなどが）「競プロはゲーム感覚だ」とおっしゃっていたので、そんな感じだと捉えています。
ち：そうですね。ただ、就職に寄せているサイトもあります。日本だとpaizaがそうです。海外だとHackerRankとかLeetCodeがあります。ただあれをAtCoderの問題として、良しとしたくはないです。
ひ：LeetCodeの問題を見てみたのですが、AtCoderみたいな問題背景が無かったのでゲーム要素は薄い感触を受けました。
ち：そうですね。もっと真面目です。
ひ：やっぱり、問題に面白みが無いと楽しくやっていけないですよ。

AtCoderの問題管理システムはなぜ変化したか？

ひ：詳しくは知らないのですが、少し前までは問題セットを有志が作って、投稿するといったシステムだったと思います。それが最近のABCでは、オレンジコーダー以上を集めて、皆で問題を作っていくといった感じにしていると思います。それまでのシステムのままでも、問題の質はすごくいいと感じているのですが、どういう風な意図があって変えたのですか？
ち：AtCoder側のシステムが変化し、今まではspreadsheetで問題を管理していたものが、自社サービスに置き換わった影響です。そのおかげで問題を1問ごとに管理しやすくなりました。ちなみにサービスの前後ともにrng_58が問題を見ているのですが、解答が付いてない状態で解いているんです（笑）
ち：さらに、このシステムにすることで投稿者が1問ずつ投稿しやすくなりました。これらの理由で管理システムが新しくなりました。

AtCoderのサービスは誰が作っている？

ひ：こういうサービスって誰が作っているんですか？
ち：snukeです。
ひ：snukeさんってWeb系強いんですか？
ち：会社入ってから学び始めたのですが、普通にバリバリかけます。やっぱり競技プログラマーは一般的な開発やらせても強いです。

有志コンテスト開催にあたり、どのような準備がされているのか？

ひ：パ研コン*2みたいな、有志コンテストがAtCoderで数多く開かれていると思うのですが、どのように連絡しているのでしょうか？
ち：バイト勢*3がいたら、AtCoderのSlackで連絡します。そうじゃない場合は、TwitterのDMだったり、メールだったりバラバラです。
ひ：有志コンが数多く開かれているのは、おっしゃっていた「広がりを深める」という意義もあるのですか？
ち：実は、そこまで積極的に開催はしていません。というのも、writerが問題を作れる量には限りがあると思うので、できれば強くなるまでその問題を残しておいて、その問題の良し悪しが分かるようになってからAtCoderの公式に出してほしいからです。
ひ：でも開催しているということは、AtCoderにいつも問題を提供している人には信頼を置いているからですか？
ち：そうですね。ただ、Ratedを増やしてほしいという要望がたくさんある中で、労働力とか問題とかを有志コンに割きすぎるのは避けたいと感じています。しかし、コンテスト運営者はAtCoderでダメと言われたら、他のコンテストサイトでやるだろうから、AtCoderでやらせてあげるかと思い、やらせています。
ち：問題作成は早いうちからやる必要はないと思います。強い人が普段のコンテストで使えない問題を有志コンで使うのはありだと思います。Xmasコン*4とか。
ひ：そうすると技術室奥プロコン*5みたいのを私の部でもやりたいと思っていたのですが、厳しいですか？
ち：正直あまり推奨は出来ません。AtCoderが問題をチェックする余裕は無いので、ある程度信頼できる人に任せています。その影響で解答とかが怪しい場合が結構あるためです。でも、やりたければやればいいとは思います。楽しいことをやってもらいたいので（笑）でも有志コンは大変です。
ひ：square1001さん・E869120さんがTwitter上で有志コンの準備の進捗を挙げているのを見ると、実感します。
ち：双子は問題作成能力高いです。しかし、レートが高くても問題が作れない人もいるので、やはり作問は簡単ではありません。作問の過程でコーナーケースを列挙できなければいけないことも難しいです。
ち：そういった関係で、正確な問題を作ることは非常にコストがかかります。お遊びで作る分にはそうではないですが。ただ、お遊びで作った問題をAtCoderのトップページに載せると、AtCoderのブランドが落ちるので、そこの判定はしっかりしています。

コーナーケースの見つけ方

ひ：コーナーケースを考えるときって、どのようにしていますか？
ち：解くときと近い感じです。しかし、一人だとカバーしきれないので、rng_58・writer・testerの三人で考えています。
ひ：正直、問題を解くときにコーナーケースを意識しなくても水色まではこれてしまったので、実感が湧かないです。
ち：極端なケースを考えることが一番大切です。一番大きい・一番小さい・両極端といったもので、これらを考えるだけでも全然違います。グラフの問題だったら一直線のケースとか二分木のケースとかです。パターンが多いわけではないので、問題のパターンごとにおさえるといいと思います。
ち：しかし、適当な嘘貪欲などの対策はかなり難しいです。こういうのは思いついたら落とすけど思いつけなかったらしょうがないという風に捉えています。

競プロの「典型」とは？どうすれば身に付く？

ひ：コーナーケースを探すときにはいくつかパターンがあると言ってました。そして、競プロにもいくつかのパターンがあると、はてなブログの記事*6でおっしゃってましたが、そこに載っていた「典型」という概念が広いと感じました。汎用的な「典型」を身に付けるためには、どうすればいいですか？
ち：「典型」という言葉自体が曖昧で、多くの人が自分にとって簡単な問題を呼んでいると思います。自分の場合はそういう意図ではないので、ブログ中で取り上げた「典型」を身に付けるには最低でも2000問ぐらい解く必要があります。なので、効率的に身に付けることは難しいです。しいて言うなら、問題を解いた後に「この問題の肝はどこだったか？」というのをしっかり考えることは大切です。一色下の人に対して、30文字ぐらいで伝えようとしたときのヒントが、この問題の肝だと思います。それを考えると、汎用的な「典型」をつかみやすいと思います。
ひ：個人的には、後輩に教えるときも結構発見があります。躓きやすいポイントを発見できたりするので。
ち：さっき作問はお勧めしないといいましたが、「この問題のこのエッセンスを使って他の問題を作る」というのはいいと思います。1問解いただけで3,4問分の経験が積まれることになるので。作れればの話ですが（笑）

プログラミングの天下一武道会

ひ：ブログ*7で、「プログラミングの天下一武道会を開きたい」と書いてありました。これは、AtCoder World Tour Finals*8によって実現されると思っているのですが…
ち：そうですね。1回のコンテストでいえばそうですし、普段のコンテストもそうだと思います。
ひ：世界中のプログラマーが同じフィールド上で戦うという意図で使っていたのですか？
ち：何を範囲にしてやってもいいと思います。世界中が範囲なのがAtCoder World Tour Finalsです。こういうので世界で戦う場を設けることができるのはすごく面白いと思っています。それぞれの人が競いやすい場を作っていきたいと思っています。
ひ：JOI*9とかICPC*10とかを卒業した人向けにAtCoder World Tour Finalsを開くということですか？
ち：ICPCは修士1年ぐらいまでは出れるので、卒業はまだ早いと思いますが、JOI卒業層はターゲットですね。中高生向けにはあまりAtCoderはやっていません。JOIだったり、PCK*11だったりに任せています。今のAtCoderの収入源は就職につなげるところなので難しいですが、本当はそこも手を付けたいのですね。

感想

まず、このインタビュー記を書き終わるのにインタビュー日から一か月程経過してしまったことを深くお詫びいたします。遅くなって申し訳ございません。Twitter上でも割と絡んでくださるchokudaiさんですが、今回インタビューを快諾してくださったことには本当に感謝をしています。ありがとうございました。また、実際にお会いして話してみると、思っていた以上に話しやすい方でした。2時間、お時間を頂戴しましたが、すぐに過ぎてしまいました。インタビューを通して、全年齢が対象であるTwitter上ではなかなか聞くことのできない、学生に向けた話を深く掘り下げて聞けたので、とても充実した体験だったと思います。また機会があったら、今度は部活の後輩と一緒に伺えたらいいなぁと思いました。
ここまで読んでくださった皆様、インタビューを受けてくださったchokudai様、ありがとうございました！！！

*1:https://jesu.or.jp/

*2:https://atcoder.jp/contests/pakencamp-2018-day2

*3:オレンジ以上のコーダーで、ABCの問題作成をやっている人々

*4:https://atcoder.jp/contests/xmascon18

*5:https://atcoder.jp/contests/tkppc3

*6:http://chokudai.hatenablog.com/entry/2018/04/23/165232

*7:http://chokudai.hatenablog.com/entry/2018/04/23/165232

*8:https://atcoder.jp/posts/170

*9:日本情報オリンピック

*10:国際大学対抗プログラミングコンテスト

*11:パソコン甲子園