競技プログラミングを使って就職活動をするよ~~~ん

こんにちは!天才競技プログラマーのdokinです。

今回の記事では、競技プログラミングを生かした就職活動をについてまとめました。

参考にしていただけると幸いです!

 

我々に期待されていること

私は美容院でよく雑誌を読みます。先日も待合室で本棚を眺めていたのですが、その中に「月刊競技プログラミングは実務の役に立たない」という雑誌を見つけました。

記事には「競技プログラミングは実務の役に立たないどころか人体にとって毒である」「競技プログラミングをやりすぎると体が5Gと接続されQアノンに操作される」と書かれてありました。

怒った私は雑誌を投げ捨てた後、美容院をバットで破壊し倒産させたのですが、やはり競技プログラミングが実務の役に立つかどうかは多くの人にとって気になるところだと思います。

そこで、企業が競技プログラマーにどのような役割を期待しているか、就職活動を通して感じたことをまとめます。

 

おわりに

がんばって書こうとしたのですが、飽きたのでおわります。

またもしかしたら新しい記事を書くかもしれないので、その時はよろしくお願いします。

 

Code Jam to I/O for Women 2021 に出場しました。

Code Jam to I/O for Women 2021で優勝しました。

あまりコンテストの参加記は書いたことがなかったのですが、優勝は気持ちいいので忘れないように記録しておきます(あくまでも記録用なので、見せる用ではないです)。

 

codingcompetitions.withgoogle.com

コンテスト前

過去問や順位表を確認し、戦略を立てていました。

Dのmediumまで早解きするか、満点を取るかで優勝できることがわかりました。

Dは「AtCoderの黄~橙前半diffくらいの実装重め」という雰囲気だったので、「largeを狙いつつ明らかに辛そうだったらmediumを取りに行く」という気持ちで臨みました。

優勝したかったので、出ることはTwitterで黙っていました(ごめんなさい)。

 

A

問題文の速読は練習していたので、落ち着いて題意を理解することができました。

座圧が頭をよぎりましたが、mapを思い出したのでよかったです。出力形式の準備を忘れていたのでそこに手間取り5分近くかかってしましました。(4:44 0WA)

 

B

AGCで以前類題がありました(A - ><)。

AGCの問題では入力のランレングス圧縮が要求されるので実装が厄介ですが、今回はランレングス圧縮された状態で入力が与えられるので、前から見るだけで実装することができました。(11:44 0WA)

 

C

C以降は「見た瞬間解き方がわかる問題」ではないという認識でしたが、実際この問題もそれなりに考察が必要でした。

サンプル2を手で試すと、1度のsessionで頂点間の距離が1短くなることがわかったので、最短路問題に帰着できることがわかりました。(実際は、Managerの頂点のみが使える最短路問題)

実装ではbfsなども検討しましたが、事前にManager間でワーシャルフロイドを回しておき、あとはクエリごとに端点とつながるManagerを全探索しました。(38:33 1WA)

 

D

Cが解き終わった時点で順位表を見たのですが、もうDのvisible(small,med)を通している人がいてかなり焦りました。

ゲームの必勝法の問題だったのですが、奇抜な発想は必要ではない気がしたのでlargeを解きに行くことにしました。

medium解のDPが線形に落ちないことはそれはそうという感じだったので、必勝法をまじめに分析しました。とれる戦略がそんなに多くなかったので、細かく場合分けをして必勝法のようなものに至りました。

実装ですが、かなり筋が悪く手間取ってしまいました(必要のないdequeを使ったり、先手後手で2倍場合分けしたり)。(1:38:12 1WA)

 

残り時間

順位表を見たら45位あたりで「終わった…」となっていました。

ただ、D largeが隠されておりmediumとの難易度に崖があったので、ちゃんと通れば1桁順位に入れるだろうと思っていました。

D largeは自信ありでしたが、C largeはsmallで通っていても普通に落ちる可能性のある解法だったので、「愚直書いてチェックしようかな、面倒だな」とずっとぐだぐだしていました。

最終的に終了5分前くらいに愚直を書いて、軽めにチェックをしていました(ここで間違いに気が付いても今更なのですが…)。

あとは歯を磨いたり、順位表を観戦したりしていました。(はますさん強いな―ももはらさんたぶんDlarge解いてるなーなど)

 

結果

コンテスト時間が終了し、順位表を更新したら「1」がでてきて爆笑しました。

うしし

 

反省

優勝できたので良かったですが、2位の人との差が10秒だったのでかなり危なかったです。Dの実装をもうちょっと効率的に進められれば、20分くらいは詰められたなと思います(ペナを出してからACするのに15分くらいかかっていました)。

強くなるまでの道は長いですが、がんばりたいです。

AtCoder橙になりました。

 

この記事は、色変記事 Advent Calendar 2020 12月21日に掲載するためのものです。

 

深夜テンションで思いついた勢いそのまま作成した色変アドカレ企画。

にも関わらず、たくさんの方に記事を寄せていただきました。

みなさま、本当にありがとうございました

 

本日は、企画者本人である 彼氏募集系競技プログラマーdokin の担当です。

 

なお、記事の中で一部気分を害される方がいらっしゃるかもしれませんが、構成上の演出ですので、この場を借りてお詫びいたします。

 

はじめに

 

タイトルの通りではありますが、

 

          私はAtCoderのレーティングでになりました。

 

いえ、この言い方はあまり適切ではありません。

 

 

 

 

 

 

        私はAtCoderのレーティングでにしかなれませんでした。

 

 

以下のレーティング変動をご覧ください。

 

 

f:id:dokinAC:20201221085143p:plain

 

atcoder.jp

黄色までは4か月、比較的順調なペースでレーティングを伸ばせていることがわかります。

この勢いをしっかり続けていれば、今頃は橙上位、もしくは赤になっていたことでしょう。

しかしながら、黄色になった3月以降、急激にレーティングの変動が小さくなっています。

現在のレーティングは僅か2444、いつ黄色に落ちてもおかしくない橙だまり です。

 

 

「コンテストが増えた10月以降は順調じゃないか」と仰ってくれる方はいるかもしれません。

しかし、コロナ渦で十分に精進する機会があったのですから、もっと勢いよくレートはあがるべきでした。

私はここに至るまで、赤パフォを一回しか出せていません

この記事では、なぜ私がこの9か月間レーティングをあまり伸ばすことができず、橙の最下位にとどまっているのかについてを考えをまとめたいと思います。

 

1.精進の甘さ

 

精進勢の代表格のおひとりであるRubikunさんは、あーだこーだーにゲストとしてご出演された際、「1年で4000問解いた 」とおっしゃっていました。

AtCoder以外にも、CodeForces,、TopCoderなどさまざまなコンテストを合わせてです。

しかし、私がこの一年で解いた問題数は、2000問にも到達していない。が少なすぎる思っています。

また、自分に何が足りないのかの分析をあまり行わず、解きたい問題だけを考え、だらだら実装する単純作業に終始していたと思います。

もちろん何事も楽しんでやることが一番ですが、競技者としての自覚が足りなかった点は、大いに反省できると思います。

 

2.メンタル

 

コンテストに対する態度が甘かったです。

ratedコンテストへの参加回数の不足な感が否めません。

精進で難しい問題を解いた経験が、「この問題は必ず解けるんだ」といった良い方向ではなく、「この問題がとけない自分はおかしいんだ」といった悪い方向に作用していました。

また、無理に高いパフォーマンスを狙って、変な順番で問題を解き進め、no subになることもありました。

自分は黄(橙)コーダーなのだから、落ち着いてやれば最低でも黄色以上のパフォはでるという自信

黄(橙)コーダーでしかないのだから、焦っても赤パフォはでないという謙虚さ

頭ではわかっていても、気持ちにしっかりと沁みこんではいなかったと思います。

 

3.嘘考察にはまる

 

赤diff、冠diffの問題は過去問でも多くを埋めており、難しい問題を解くのは苦でないと自覚しています。しかし、コンテストの時間内に通すことができない。

要因の一つとして、嘘考察に一度嵌ると抜け出せない悪癖があると感じています。

解けそうだけど解くことのできない方針に拘泥し、時間をどんどん失い、焦り、の悪循環で多くのパフォーマンスを失いました。

普段の精進だと、仮にうまくいかなくても別の日にリフレッシュして考えればあっさり解けることがありますが、本番の時間内にはうまくいきませんでした。

 

解けそうな方針を深追いする頭の回転の速さだけではなく、ダメそうな方針を判断し即座に撤収する頭の回転の速さをつきつめていく

・解けた方針にのみ注目するのではなく、ダメだった方針にも注目し、なぜダメだったのか分析する

といった意識で精進していくことが肝要だと思いました。

 

4.実装の遅さ

 

最近YouTubeで問題を解く動画の配信をする機会があるのですが、配信した動画を見返すと、自分の実装が、あまりにも想像以上に遅すぎることに気づきました。

簡単な実装箇所でも平気でつまる、何を考えているのかよくわからない時間が何十秒もある、ただただ退屈な配信を垂れ流しています。簡単な問題であっても、スムーズに実装できた問題は少なかったです。

最近JOIの過去問を埋め始めています。JOIは実装が重めの問題が多く、実装練習に最適です。

JOIを解く際は、何分で解き終わるかを実装前に予測し、その時間内に実装を終えることを目標にしています。

 

「その一秒を削り出せ」

簡単な問題にも難しい問題にも共通する、競技プログラミングの基本です。

 

5.細部を詰める甘さ

 

わたしはDPの添え字をバグらせ、時間を空費することが多いです。

バグらせるだけならまだよいのですが、考察自体が嘘であることに、デバッグの最中で気づくということさえ、とてもよくあります。

問題が解けた際、きっちり細部をつめた立式をおこなうことなく、ふわふわしたまま実装した結果、バグを生み出しているのだと思います。

立式をしっかりおこない、ノートを適切に活用して、バグや嘘の少ないコーディングを心がけたいと思います。

 

6.レベルの違い

 

実際のところ、青コーダーと黄コーダーでは求められる水準が一色分以上に異なると思っています。

青色まではABCがratedです。

ABCでは教育用の問題も多く出題され、典型テクニックとその適用方法を頭に定着させるだけでレーティングを伸ばすことができます。

一方で、ARC,AGCでは、どこから手を付けて良いのかわからない問題、解法に至るまでのステップ数が多い問題が多く、自分の頭の強さを引き出していく能力が、ABC以上に要求されます。

また、ABCではunratedの黄コーダー、橙コーダーが順位表の上を占拠するわけですから、当然ABCに比べて良いパフォーマンスが出づらくなります。

黄色下位で停滞してしまうのも、そこに壁があるのですからある意味当然なのかもしれません。

 しかし、色変後スムーズに黄色下位を抜ける方はたくさんいます。レベルの違いのみを理由にするのは浅はかです。

橙コーダーになって、そういった壁は目の前にありません。

つまり、今後は「レートの停滞=実力の停滞」に他なりません。

覚悟を持って精進していきたいです。

 

おわりに

 

このような記事を書くと、自分は頭が悪いとアピールをすることで逆説的に自分が賢いことをアピールしたい人間だと、後ろ指をさされるもしれません(界隈にはそういう方がよくいますね)。

 

批判は甘んじて受け止めますが、私は競技プログラミングのことを何よりも一番に考え、人生を競技プログラミングに賭けているとして当然のことを書いたと思っています。

 

むしろ、アドベントカレンダーの宣言は達成したわけですから、この程度の自責で済んでいるのかもしれません。

 

宣言を達成してできなかった方は、何が足りなかったのか、どこが甘かったのか、反省点は枚挙にいとまがないでしょう。

 

にもかかわらず、「がんばりまーすw」だけで済ませたり、笑いをとることに逃げたりしている人たちは一体何を考えているのでしょうか。

 

他のことで人生が充実しているので、そんな舐めたことをやっても何とも思わないのでしょうか。

 

コンテストでうまくいかなくてもヨシヨシしてくれる恋人がいるのでしょうか。わたしにはいません。

 

 

わたしにはいません・・・

 

 

 

 

 

 

 

 

 

彼氏欲しいです。

なんでいないんですか?

なんでわたしは一人でしくしく精進しているんですか?

さっき、嘘をつきました。

競プロのことを一番に考えているなんていいましたが、彼氏つくりのほうが優先に決まっています。

他愛のない話で一緒に笑い、落ち込んだときは一緒に泣き、お互いを認め合い、支え合い、常に自分と同じ方向を向いている生身の人間が、上がったり下がったりを繰り返す感情のない4桁の数字を下回る要素は、どこにも見当たりません。

嘘をついてごめんごりごり。

また、せっかく記事を書いてくださった方々に舐めているだのいったことも謝ります。

もちろん皆様、記事にするまでもなく、悔しい思いや目に見えないの努力をされているでしょうし、先ほどの言葉は本心ではございません。

彼氏がおらずぼっちなので嫉妬心に間が差した帰結です。

酷いこといってごめんごりごり。

 

 

 

dokinさん、決して悪い物件ではないと思うんだけどな~

 

最後になりましたが、みなさま良い年末年始をお過ごしください!

競プロも彼氏作りもがんばっていきましょ~(*^▽^*)

CODE FESTIVAL 2016 Final G - Zigzag MST

公式解説とは違う方法で解いたので記録用に残しておきます。

・問題
atcoder.jp
・提出コード
atcoder.jp


最小全域木なので、クラスカルかプリムをしたいですが、流石にクラスカルな気がします。
priority queueに辺を突っ込んで、重みが小さい順にみていくアレですね。
辺の本数が多すぎて、間に合わん模様なので、木に追加する可能性のない辺ははじめからpriority_queueにいれたくないです。

ところで、各クエリ列は2つの部分列に分割することができます。
例えばi番目のクエリ列に関して、それぞれのクエリを辺(頂点1、頂点2、重み)で表すことにすると、
・(A_i,B_i,C_i),(A_i+1,B_i+1,C_i+2),(A_i+2,B_i+2,C_i+4)...
・(A_i+1,B_i,C_i+1),(A_i+2,B_i+1,C_i+3),(A_i+3,B_i+2,C_i+5)...
に分割します。
すると、各分割クエリ列について、各辺(頂点1-頂点2)は定数であり、辺(a,b,w)の次の辺は(a+1,b+1,w+2)になります。

このことより、たとえば辺(a,b,w)を木に追加する必要がないならば(追加しようとするとき既にa,bが連結であるならば)、その次の辺(a+1,b+1,w+2)も追加する必要はがないことがわかります。(1つシフトしているだけなんだから、そらそうよ)

というわけで、priority_queueには、各クエリ列の先頭の辺のみいれてやります。
そして、priority_queueから辺を取り出した際、
・辺(a,b,w)を木に追加する必要があったならば、(a+1,b+1,w+2)を新しくpriority_queueに入れる。
・辺(a,b,w)を木に追加する必要がないならば、(a+1,b+1,w+2)を新しくpriority_queueに入れる。
という流れで、クラスカル法を進めていきます。

すると、priority_queueに入れる辺の本数の合計は、
(はじめに入れる2*Q本)+(木に辺を追加した直後に入れるN-1本)ですから、O(N+Q)です。
合計の計算量は、O( (N+Q)log(N+Q) )になります。

一人で他人のアドベントカレンダーを全部埋めるチャレンジに失敗しました。

この記事は、もすーんアドベントカレンダー12月6日に掲載するために書きました。

 

adventar.org

 

もすーんさん(@Mo_SoooN)による「もすーんアドベントカレンダー」が1日も埋まっていなかったので、一人でアドベントカレンダーを埋めようとしたのですが、25日間の完走に失敗しました。

 

原因は2つあります。

 

①昨日記事を投稿し忘れた

おまめについての記事を投稿しようと思っていたのですが、忘れました。

これだけなら何事もなかったかのように、更新すればよかったかもしれないです。

 

②別の方がアドベントカレンダーの日を確保された

たかはしよしぴろさんに、12月16日を確保されてしまいました。これでは手も足も出ません。(もちろん、たかはしよしぴろさんは悪くありません。もすーんアドベントカレンダーはみんなのものです。)

 

今後も、出来る限り記事を掲載し続けたいと思います。

もすーんアドベントカレンダーをよろしくおねがいいたします。

たのしいスポーツ観戦

この記事は、もすーんアドベントカレンダー12月4日に掲載するために書きました。

 

adventar.org

 スポーツ観戦はとても楽しいです。

そこて、今日はスポーツ観戦の魅力を、私自身の体験を通じて記事にします。

 

・野球

野球の魅力はなんといっても球審の白井です。

みなさまも野球中継でピッチャーがストライクを投げた時に奇声をあげるおじさんを見たことがあるでしょう。あの人が白井一行さんです。

審判のスケジュールは素人には予想できません。

わたしは球審の白井とその奇声を是非生で感じたい、その思いで忙しい大学生活の隙間をぬい甲子園球場に通い詰めました。

そして、ついに球審が白井の時に観戦することができたのです!

 

しかし、そこで聞こえたのは割れんばかりの奇声ではなく、観客の騒ぎ声と売り子がビールを売る声、耳をすませばわずかに聞こえる裏声だけたったのです。

わたしは、楽しみを裏切られた失望と、白井を生でみた人間しか知らないことを知った喜びの入り混じった複雑な感情のまま、酒臭い阪神ファンの詰め込まれた電車に揺られ家路につくのでした。

 

・相撲

角界には珍四股名の力士がいますが、その中でも爆羅騎(ばらき・式秀部屋)と羅王(らおう・立浪部屋)の兄弟は異彩を放っています。

彼らの四股名、実は本名で、それぞれ伊藤爆羅騎さん、伊藤羅王さんです。(フランスのヤクザ映画のタイトル「バラキ」、北斗の拳の登場人物「ラオウ」が由来だそうです)

一体そんなロックな名前を息子につけた父親はどんな人なのか、今まで出会ったことのないくらい最高にロックな人なんじゃないのか、わたしは気になって夜も眠れませんでした。

そんな折、偶然国技館のチケットを融通していただき相撲観戦をしたのですが、同行の方の仲介でなんと伊藤父にあうことができたのです!

 

ロックな人を期待していたわたしはびっくり、息子たちを応援しに国技館に通うとても優しそうな方でした。

「息子に付ける名前で人を判断してはいけない」勉強になった一日でした。

 

以上です。自粛の続くご時世ですが、スポーツ観戦をみなさまも是非してみて下さい。

 

インドの世界遺産について

この記事は、もすーんアドベントカレンダー12月3日に掲載するために書きました。

 

adventar.org

 

インドには世界遺産がたくさんあります。

そこで、わたしが行ってみたいインドの世界遺産ランキングを紹介します。

 

 第三位 ダージリン・ヒマラヤ鉄道

観光の最大の敵は疲労です。

その点列車は、自分の力で歩かなくても移動してくれるので、観光するときも楽です。

他にも2つの鉄道と併せて、インドの山岳鉄道群として世界遺産に登録されています。

 

第二位 エローラ石窟群

日本人はスタンプラリーが大好きで、わたしも例に漏れずです。

エローラ石窟群には、3つの宗教の34個の石窟があります。

スタンプはたぶんおいていないですが、これらをただただ順番にまわることで、達成感が得られそうです。

 

 第一位 タージ・マハル

何かを観光した時の感動は、その施設の大きさ、形状、厳かな雰囲気、でだいたい決まります。

タージ・マハルは大きいですし、日本では稀な形状、さらに歴史のある厳かな雰囲気も兼ね備えており、しっかり感動できるはずです。

 

他にも美しそうな施設がたくさんあり、是非行ってみたいところです。

みなさまもインドに行ったときは是非世界遺産に訪れてみてください。