30歳で競プロに目覚めた霊長類のブログ

チンパンジーと一般人のあいだ

AtCoder青になるまでの軌跡


2018年12月29日のAGC030 (=今年最後のAtCoderコンテスト)にて、
ついに、ここ1年7ヶ月力を注いできたAtCoderで青コーダーになりました!!!! 上のレートグラフからも苦労の様子がある程度わかりますが、本当に紆余曲折ありましたので久々にブログに記していこうと思います。

前半はAtCoderに出会うまでの自分語り的なことも多少書くので、 興味がなければ適宜読み飛ばしてください(><)


目次


(推定) 茶色になるまで

まだAtCoderには出会っていない頃の話ですので(推定) と付けました

情報系学部を卒業した

大学をギリギリ卒業しました。成績は下の下の[検閲により削除] でした。
(恥ずかしい記事ですが下記に当時の状況を少し書いています) 1
競プロと出会うまで(前編) - 30歳で競プロに目覚めた霊長類のブログ

学ぶのには最適な環境だったはずなのですが、学業について行けず、諸々やる気も出ずに、かといって休学などもせず 無駄に学費をつぎ込んで2 虚無をして過ごしてしまいました。

記憶に残っているのはダイクストラ法を授業で教わったときはなんか凄い、面白いって思いました
当時はこれを実装するなんて思いもしませんでしたが、今ではスラスラと書けるぜー当時の自分よ!

1年ぐらい趣味で自分なりにコードを書いた

これは大学に在籍していた最後の1年ぐらいのことなのですが、ようやくこの時期になってプログラミングって楽しいって思えたんですね
(プログラムを書くお仕事をしたい、とハッキリ思ったのもこの時期でした)
自己流なので誰かにレビューしてもらうわけではないですが、下のようなものを書いたりしていました

CUIでオセロできるやつ

自分 vs. 自分で対戦したり、自分 vs. AI で対戦できるオセロゲームを書きました
AIといってもαβ法みたいなことは挑戦していなくて、各マスに固定の優先度がつけられてるだけのシンプルなやつでした(笑)

数独ソルバ

数独の解を見つけるプログラムをこの時期に書きました。
条件分岐と配列をすごく駆使して、えぐいスパゲッティコードになっていたと思います。
このとき、実は今思うと自己流の深さ優先探索を書いていたんじゃないかと思います。
自明でないマスはとりあえず仮定を置いて、そのマスに深さ1の仮定だよとマークをつけて、さらにその仮定でマスが埋まりきらなかったら深さ2の仮定を置く...
みたいな感じだったと思います。
自己流なので、当然再帰なんて使おうとも思いませんでした。
今思うと当時の力でよく実装できたなーという気持ちです (ただし1ヶ月かかりましたが...)

こんな感じで自分なりにコードを書いていた時期がありました。
成績自体は下の下の... でしたが、プログラミングのいろはというか、if, for, 配列... をゴリゴリ使った手続き的な処理は、 CS学科の中でも中程度には書けるようになってたんじゃないかなーと思います[要出典]。
この頃の自分にAtCoderをやらせたら推定茶色ぐらいかなーと思っています。(実装は遅かったので...)


(推定) 緑色になるまで

なんだかんだで就職しました。このセクションもAtCoderに出会う前のことです

ソフトウェアエンジニアとして実務経験を積んだ

これは競プロ力とはあまり直結しないのですが、単純に趣味でゆるーくコードを書いていたところから、お仕事で毎日8時間3 向き合うようになったので、単純にプログラムに触れる時間が増えました。
また、実務の中で、先輩にレビューしてもらう中で効率の良いコードのまとめ方なんかは身に着けられたかもしれません。

Project Euler を90問ぐらい解いた

ある半年~1年の間ぐらい、 Project Euler 埋めにはまっていたのを思い出しました。
最初のころは完全自力で解くのを目指していましたが30問解いた辺りから辛くなったので、どうしても分からなかったらググって色んな人の解法を見るようになりました。今の精進方法と同じ!
今思うと、累積和や簡単なDPのような解法は自力で発明していたように思います (当時はそれが名前のついた定跡であると知りませんでした)
ただ、競プロのように正解までの早さを競うわけではないので、めっちゃ(ものによっては1週間とか)考えて編み出したりしていました
にぶたん(二分探索・バイナリサーチ) は知っていました。

素因数分解させたり、素数を列挙させる問題がやたらと多かった4 ので、競プロでよくある整数問題に対する考え方もこのときに多少磨かれた気がします。
あとはLU分解を調べて実装して、任意の有理数が係数になっているn元連立一次方程式を解けるようになって感動した記憶があります(これは競プロで出なさそう?)

90問ぐらい解いたところで行き詰って、それから熱が冷めてしまったのですが、思い出したのでまた久々に再開しようかな ^^

CODE VS 5.0 に出た

2016年3月ごろの、CODE VS 5.0予選に出ました5
同僚がたまたま話題に出していたので、いっちょやってやるか!という気持ちで出てみました。
このとき、キャラクターを動かす場所の候補を探すのに、初めて幅優先探索を書いた記憶があります。
最終日にヒューリスティックなパラメータを怪しくいじったのが意外と善戦して、全参加者の真ん中ぐらいの順位にはなれました。
CODE VSはリアルタイムで他のユーザーと対戦できて、対戦のようすがグラフィカルに表示されるので、やたらと楽しかった記憶が強いです。
6.0があるとしたら有給を何日か使ってでもやりたいなーと思っています6

AtCoderと出会うまではこんな様子でした。
この頃の自分にAtCoderをやらせたら推定緑色ぐらいかなーと思っています。


AtCoderとの出会い~水色になるまで

AtCoderと出会って、人生が変わりました

初回参加

忘れもしない、初めて参加した時のことを書きます。初参加は2017年5月、ABC062でした
この頃の私は、井の中の蛙だったので、プログラミング力には多少の自信をつけていました。
そして、AtCoderBeginners」 Contest だと思って舐めていました。
言語は、当時一番慣れていたJavaではなく、独学で少し触ってみただけのPythonで挑みました。(心境的には舐めプに近いです)
結果は、4問中の2完で、これほどまでに通用しないのか、と凹みました (全部解けて当然とぐらいに思っていたので)
が、同時に 俺はこんなもんじゃねぇ~~!! という、熱い気持ちが沸き上がってきました
これが、私に火をつけたきっかけになり、以降は毎週のAtCoderコンテストでレートを上げることを目標にしました。

ABC全完を目指し、ABC埋めをした

とりあえず、AtCoder Problems を参考に、手当たり次第に過去問をやりました。
言語は、引き続きPython を使いました7
ABCのA~C問題は絶対解くつもりで解いて、解けたらD問題にも挑戦していました。
CやDには自力で解けない問題も多かったので、逐一解説を見たりしては、身に着けていました。
それをがむしゃらに、日によっては2セットや3セットや4セットやりました。(多分、この時期が一番新規ACを稼いでいた)
公式のEditorial が数学的な記述や グラフ理論の言葉を使った記述が多くて、読み解くのに苦労していました。(これは今は多少慣れてきましたが今でも苦労します^^;)
こんなとき先人の書いてくれたブログ記事たちはとても理解の助けになりました。
初めて全完できたときの達成感、気持ちよさは今でも覚えています。

蟻本を買った

プログラミングコンテストチャレンジブック (通称:蟻本) は競プロerのバイブルだと知って、購入しました。
1ページ1ページに情報が凝縮されているので、理解するのに1時間以上かかるページも存在しました。
2017年8月頃にちまちま読み進めて、水色になる前に初級編は読了したと思います。8

水色になるまでに学習したアルゴリズム、考え方

  • 計算量・オーダーに関する感覚
  • list, set, dict, deque(双方向キュー), heap(優先度付きキュー) を使いこなす
  • グラフ理論の基礎
  • ソートして貪欲
  • ソートして二分探索
  • しゃくとり法
  • 累積和、いもす法
  • DFS、BFS
  • ダイクストラ、ワーシャルフロイド、ベルマンフォード
  • DP
  • Union-Find, クラスカル
  • 二項係数のmod 1e9+7 を求めるかわりにmodの逆元を繰り返し二乗法で求めるやつ
  • (Pythonの) itertoolsの便利そうなやつを抑えておく (permutation, combination, product, ...)

青色になるまで

水色~青までの時代は長かったので、時系列通りに書いてません。(書けません)

このブログを始めた

何か学習した知見をアウトプットしようと思いこのブログを始めました。
しかし記事にまとめるのって物凄く大変だと分かって、あまり記事を書かずに長らく放置しちゃいました。
今後も思い立った時に書こうと思います。。

Twitterを始めた

DDCC2017の決勝に進めたのがきっかけで、Twitter を始めました。
畏れ多くも1000名を超える方にフォローいただいています。ありがとうございます。9
特にコンテスト後に解法に関する議論が活発に行われているのを知って、軽い情報収集の目的がありました。
後述しますが、Twitterがきっかけでリアルの交流も多く生まれて、単なる情報収集にとどまらない、期待以上のものが得られたと感じています。

1日1ACを軸に、AtCoderの過去問を埋めていった

AtCoder Problems に、Streak という指標があります。
AtCoderの問題を連続で何日新規ACしたか を表すのですが、2018年1月3日~2018年12月30日現在まで、362日継続中です
この 「Current Streak を切らさない」を1つの方針として、2018年は精進していました。
この方針の精進方法については、向き不向きというか、賛否両論がある10 のですが、結果として私にとっては良かったと思います。
理由としては、常に頭の中に解きかけの問題をいくつか置いておけるというのがあります。
どういうことかというと、Streakを長く続けるためには意外と戦略的に考える必要があって、例えば時間的・体力的に厳しい日なんかは軽めの問題で繋ぎたいので、軽めの問題は温存しときたいという気持ちになります。
すると、普段はできるだけ軽めの問題以外に目を通すようになって、それらの解法を考える習慣が生まれます
大体私は、新しい過去問に目を通したときに「すぐ解けそう」「ちょっと考えれば解けそう」「かなり大変そう」の3つぐらいに分類しています
時間的・体力的に余裕のある日は「かなり大変そう」な問題に挑戦しますが、そうでない日のほうが普段は多いので、「すぐ解けそう」「ちょっと考えれば解けそう」の問題は割とストックしてあります11
その過程で多くの問題に目を通したり、実際にACしたり、「かなり大変そう」な問題の考察にチャレンジしたりしてきました。
このStreakという数字は今後もモチベーションを保つために生きる数字だと思っています。

PythonのLanguage Ownerになった

これは1日1AC以上... をコツコツやってきた結果の副産物ですが、2018年9月頃、「Pythonで一番AtCoderのAC数が多い人」になりました
(これまたAtCoder Problemsさんで言語別に集計されています12)

AtCoderの過去問は2000問以上あるうえ、「すぐ解けそう」に分類される問題も多く解いてきたので、個人的にはあまりすごい事と思っていないです。
でもこういう形で可視化されるのは非常にモチベーションになりました。

AtCoderコンテストには欠かさず出た

これは私ぐらいのモチベーションがあれば自然とそうなってしまうのですが、AtCoderのトップページ左側に「予定されたコンテスト」という一覧がありまして、 そこに表示されているコンテストには冠婚葬祭レベルの理由がない限り大体出ていました
何なら旅行中にも出ていました^^;
休日は基本AtCoderコンテストに被らないように行動します。
(競プロerと遊ぶときはこの辺は共通認識になってたりして面白いです 13)

AtCoder以外のコンテストにもできるだけ出ようとした

AtCoderは土曜または日曜の21時~ で、日本人が参加しやすい時間帯に開催されます。
TwitterのTLを眺めると、AtCoder以外のコンテストの情報も流れてきて、自分もやろうかなーという気持ちになります。

yukicoder

これは金曜の21時か22時頃に開かれるので、これまた日本人に参加しやすい時間帯になっています。
日本の方が運営しているのでもちろん日本語です!
TLで情報が流れてきた際には大体参加するようにしています。

Codeforces

ロシアで運営されているコンテストサイトです。
曜日が固定されていなくて、頻繁にコンテストが開かれている印象があります。
英語が分かりづらいという評判14もあります...
海外コンの中では一番参加回数が多いです

TopCoder

歴史あるコンテストサイトです。
1度だけSRM(するめ、短期型)と、2回マラソンに出ました。

CS Academy

最近あまり聞かなくなった気がしますが、教育的なコンテストサイトです。
UIが格好いいです。

GCJ

年に一度のGoogleが主催する世界的にも大規模なコンテストです。
2018年はqualは突破できたのですが、Round1A~Cはいずれも通過できませんでした。
2019年はRound2まで行ってみたいですね...

Paiza

これはコンテストとは違う形態ですが、日本語の問題が充実していて、いつでも参加できます。
ただ、ネタバレ禁止の特性上、分からなかったときに復習する手段がないのが難点です。。
水色がSランク相当という情報を得ていたので、Sランクは取りました。

ゴリラジオ体操を始めた

2018年5月頃から、AtCoder Virtual Contest さんをお借りして、ゴリラジオ体操 なる早朝バーチャルコンテストを定期開催しました。
実は4月頃、上述のCodeforcesやCSAといった海外コンに積極的に出ようとした結果、深夜のコンテストが多くて寝不足になり、体調を崩してしまいました。
そんな経緯があって、海外コンに出るのは基本諦め、その代わりに普段の生活の中で無理なく精進できる方法はないだろうかと考えた結果、ラジオ体操形式にして毎朝バーチャルコンテストをやるのはどうかと思いつきました。
実際それがうまいこと普段の生活の中に習慣化できて、2018年年末時点で157回 15、いまだにこの習慣が続けられています。

有り難いことに、一緒に精進してくれるゴリラジ勢がいらっしゃって、毎朝10~20人ぐらいの人たちが参加してくれています 16
めちゃめちゃ朝早い(今は6:25~開始) のに、この人数に参加してもらえるのはビビります。
心理的には、これだけの人たちが参加してくれているから、ここまで続けられたという側面もありますね。
いずれにしても皆さんに感謝です。

ゴリラジ以外にも不定期にバチャを立てたり、他の人が立てたバチャを見つけたらお邪魔しているので、水色時代に軽く200回以上はバチャをしています。

オンサイトのイベントにもできるだけ出た

モチベーションの源です。オンサイトコンテストの機会は何度でも行きたいです。

DDCC2017 決勝

初めてのオンサイトでめちゃめちゃモチベーションを得られました。
詳細レポ→ DDCC2017本戦に参加してきました!! - 30歳で競プロに目覚めた霊長類のブログ

RUPC2018

立命館大(滋賀県のキャンパス) に3日間、お邪魔しました。
年齢や所属の縛りがなかったので、社会人である私も参加できる貴重な機会でした。
(平日なので社会人は少なかったですが...) ICPC形式なので、3人1組のチームで問題を解きました。
これをきっかけにTwitterで接していた人たちと仲良くなったり色々出会いがありました。

ACPC2018

3日間会津大(福島県) にお邪魔しました。
RUPCと同様、年齢の縛りがないので私でも参加できました。
貴重な機会でとても刺激になりました。
RUPCのときは一人宿だったのですが、ACPCでは8人ぐらいで民泊しました。
また、この時もたくさんの出会い or 再会がありました。
帰りに温泉にも寄れて楽しかったです

Future Meets You Contest (ふみこん)

Future社にて、社会人限定のオンサイトコンテストがありました。
3時間でマラソン形式の問題を解くスタイルでした。
ラソン形式は慣れていないのですが、たまたま方針が良くて、20数名中4位の結果でした。
(賞金が3位からだったので惜しい)
懇親会でも交流させていただきました。
また、帰りにエントランスホールから皆でARCに参加したのもいい思い出です(笑)

競プロer達と交流した

交流の機会はできるだけ大事にしました!
競プロのモチベーションを得られる、人生の充実感を得られる... 等 様々な恩恵がありました

CombNaf, CombGig, CombMof

いずれも高校生が主催していて若い方が多く集まるLTイベントでしたが...
発表内容がどれもすごくて刺激になりました。
参加者がいずれも数十人規模で、二次会まで参加しています
GigとMofでは二次会の幹事をさせていただきました (自然とそんな流れになっていました)

ビアガーデン

企画としては初めての私主導だったので思い出深いです
Twitterで何気なく「ビアガーデン行きたいなー」と呟いたら、行きたい!という声が意外と上がったので決行の運びになりました

競プロキャンプ2018

8月末に、千葉へ競プロer達との交流キャンプに行ってきました。
これも外せない思い出の一つです。
競プロer達と泊ったのはこれが初めてでした。
たくさん交流できて良かったです。
何と2019年は私が幹事をやることになったので、うまく行きますよう、皆さんよろしくお願いします。

和歌山旅行

tatuyanさんが企画してくれました。
駅猫を見に行ったり、浜焼きバーベキューしたり、温泉入りまくったり... 素敵な思い出でした。
旅行の習慣がなかったのですごく新鮮で楽しかった!


...その他、書ききれませんが、勉強会、もくもく会、〇〇会、××会、その他たくさん交流の機会がありました
AtCoderを始める前はこんなに交友関係が広がるとは思いもしなかったので、(競プロのレートとは別の) 思わぬ収穫でした!!
2018年、(2017年も) 仲良くしてくださった皆さんありがとうございます。

ゴリラのぬいぐるみを買った

競プロキャンプ2018の行きにUSB扇風機を買おうと立ち寄ったドンキで出会いました
ゴリたろうと言います
競プロキャンプの後も何かと活躍してくれました。

青になるまでに学習したアルゴリズム、考え方

実は上のほうに挙げた、水色のときに学習したアルゴリズムたちで青色にはほぼ足りています
足りないのはスピードだとある時に認識して、毎朝のゴリラジオ体操で、早解き力を鍛えました。

以下は学んだけど類題を多く解いていないのであまり使いこなせていないかも (><)

  • 二部グラフの判定 →私の記事
  • 包除原理
  • LCA, ダブリング
  • 行列累乗
  • 最大流最小カット(フロー)
  • BIT, セグ木
  • 幾何いろいろ、文字列いろいろ

青色達成時のスナップショット色々

AtCoder Problems

AtCoder Problems

ABC-D, ARC-D(下の円グラフでB) がもうちょいなので埋めきりたかったです...
ARC-E(下の円グラフでC) をもっと解きます

f:id:prd_xxx:20181230225038p:plain
atcoder_problems

AtCoder Scores

AtCoder Scores

こちらも400を埋めきりたかったです...
500,600,700, それ以上... もまだ増やしていきたいです

f:id:prd_xxx:20181230225107p:plain
atcoder_scores

AtCoder Performances

ここ2ヶ月ぐらいは大きな失敗はなく、レートを上げることができました
今後は青パフォ、黄パフォの頻度を上げていきたいです。

AtCoder Performances

最後に

ここまで長々と書いてしまいましたが最後まで読んでいただきありがとうございました。

最後に2つメッセージがあります

灰色、茶色、緑色、水色で行き詰っている方へ

それぞれのステージで、違った大変さがあると思います。
そして私もそれをよく理解しています。
特に私は大学に入って最初の3年間はプログラミングで挫折していて、自分には向かないとさえ思っていました。
でも結局は好き、楽しいという気持ちが勝って、プログラミングを続けることができました。

私はレート上は、AtCoderと出会って4ヶ月で水色になれました。
よく「4ヶ月で水色ってすごいですね~」と言われます。
しかし、上で書いたように、(あるいは書ききれていないけど)、私には長い期間のバックグラウンドがあります。
実際に4ヶ月で水色になれる人は私から見て凄すぎる人です。

成長のペースは人ぞれぞれ違います。
これは持って生まれたものや、様々な置かれた環境が違うので、仕方ないことです。
ただ私は、今置かれた環境の中で手を尽くしたら、どこまで行けるだろう? というところに興味を持ちました。

どうか、他人の成長速度に惑わされることなく、自分のペースで精進を続けてください。
そして、プログラミングが好きだという気持ちを忘れないでください。

黄色、橙色、赤色、、、を達成された方へ

競技プログラミングを極められていて、とても尊敬・憧れの念を持っています。
そこに至るまでに、現在までの私の数倍、数十倍... の努力を重ねられてきたことも知っています。
私はどこまで追いつけるか分かりませんが、少しでも追いつけるように精進していくので、見守っていてください!


はぁ~~年を越す前に書き終わって良かった、ゴリ~~(><)
皆さん、良いお年を、お過ごしください!!


脚注:


  1. 当ブログ最初の薄っぺらい記事です。長らく(後編)が書かれていませんが、当エントリが(後編)の役目を果たすつもりで書きます

  2. 留年した超過分は私が全部負担する約束で、ついこの間全額完済しました

  3. ずっと実装だけさせてくれるというわけでは全然ないですけど

  4. 当時はエラトステネスのふるいを座圧して定数倍高速化して喜んでいました

  5. これは広義の競プロではあるので、30代になって競プロを始めたと宣言した気がしますが、厳密には嘘です (当時29歳) まあそんなことは置いといて、当時の順位表を今見ると知っている名前が多くて楽しいですね

  6. と思いつつ、ずっと開催されないので首を長くして待っています

  7. もともとLL言語をさくーっと書ける人に憧れがあったので独学でPythonを始めていて、毎週のAtCoderPythonに慣れることを最初は目的の一つと考えていました

  8. 初級編といっても、生半可な覚悟では読み切れない難しさですよね。。ちなみに青になった現在、中級編を読了していません。。2019年は全部読むぞ!!

  9. 皆さん、何にそんなに惹かれるんでしょう…?? というのは自意識過剰ですかね。。理由はどうあれ、フォローいただいているのはありがたいことです。

  10. 否定的な意見の例… Streakを繋ぐことを目的にしてしまうと精進強度の低いAC(虚無と呼ばれたりします) をすることになり必ずしも役に立たない、AC継続にとらわれてしまい他のことができない、等

  11. 実はそうでもなくて最近カツカツしてきたかもしれない

  12. 裏話があって、初期のころは訳合ってPython2系で提出していたので、Python2とPython3で分けて集計されていたらこうはなっていませんでした。合算してくれてありがたいです

  13. 急にコンテストが生えることもあるので、土日の夜に企画を立てづらいというのはちょっとあります。。「予定されたコンテスト」欄にはできるだけ早めに予定を掲示してほしい… (願望)

  14. “Read"forces なんて呼ばれてたりしますね… 私も何度も誤読で時間を溶かしています (ただこれは私の英語力の問題な可能性がある)

  15. 土日祝日は好きな時間に起きたいので途中ではずしました。平日に、出社前にやるのを習慣化しました。

  16. 最近10名を切るぐらいに減りつつあります。(寒くなったし朝オフトンから出られないのは無理もないです) (というか出てる人すごい)

DDCC2017本戦に参加してきました!!

本戦に出られたことは本当に奇跡でした →前回の記事

初のオンサイト大会であり、ひょっとしたら最後かもしれない。
私にとって、とても貴重な体験!!
超ーーー楽しくて、超ーーー刺激になった 1日だった!!


本戦開始まで

Twitterを眺めると、本当に全国から飛行機なり新幹線なりで集結していた。
改めて、規模の大きい大会なんだなってのを認識した。

さて、私はというと、新幹線はいらないまでも、会場まで片道2時間はある所に住んでいる。
余裕を持って、6時には家を出た。
よりによって前日緊張して眠れなかったので、とにかく眠かった。

会場近くのコンビニでカフェオレとお茶と板チョコを買い、準備万端。
コーヒーでなくカフェオレを選択したのは少しミスで眠気を覚ますには弱いと感じた。

集合時間の10分前ぐらいに、Disco社に潜入。
すでに50人ぐらいが蛇のように並んでいたかな。
若い人が多く、中には中高生くらいの見た目の方も何人かいた。

受付でTシャツと名札を受け取り、エレベーターに乗った。
名札の番号は、No.200!!
本当に最後の通過者だったみたい。

会場ではチョコレートと計算用紙が自由に取ってよかった。
(しまった。チョコレートが被ってしまった。。)
と思いながら何粒か確保。

着席し、wifiにつながるのを確認してからは、家でいつもコンテスト前にやるのと同じように、
手慣らしで簡単な問題を解き、あとは本番用のファイルをエディタで開き、深呼吸・精神統一していた。
開始の時刻が近づくと、"""あの"""chokudaiさんが登壇した。
始まるぞ!

ハプニング

今回のコンテストページのURLがスクリーンに映し出された。
ブラウザを開き、写経して...と。あれ、開けない。
URLは何度見ても正しい。
かつ、ネットには繋がってる。他のwebページは開けるし、AtCoderのサイトも開ける。
唯一、コンテストページだけが開かない。
周りの人は、問題なく表示されてそう。
自分だけが何故か今回のコンテストページを開けない。

chokudaiさんは「開けましたかー、開けてない人いませんかー」と言っている。
助け舟だ!すかさず挙手。スタッフの方が駆けつける。
状況を説明するも「おかしいですねぇ。」で原因分からず。
他にも手を上げてた方がいたようで、「また何かあったら呼んでください」と言って、走り去ってしまった。
うーん、いつもと違うのは何だ、と思った時に、このwifiかなあと思って、自分のスマホからのテザリングに切り替えてみた。
・・・。相変わらず、無が表示されている。

一方、chokudaiさんは「皆さーん、サーバの負荷を確認しますので、イッセーのせで、F5を押しましょう〜」とか言っている。
これ、オンサイト大会では恒例の儀式なのかな?
開始時刻も迫っていたのでイベントは進めないとね。
カウントダウンと共に皆F5押す。念のため自分も押す。・・・うむ。
「大丈夫ですね〜」と沸き起こる拍手。
こっちは大丈夫じゃないよ!

ふと思い立って、PCを再起動してみる。ものは試し。
こういう原因不明の事象には原始的な対処が良かったりする。
・・・あああー、良かった。
無事にコンテストページが表示されたのは、開始2分前だった。
ダッシュでトイレに行くと、息つく間もなく、本戦は始まった。
眠気?そんなものは、とうに吹き飛んでいた。


ちなみに、未だに原因はわからない。
ブラウザのタブを開きすぎてて、メモリが確保できなかったのを一番疑っているけど。。。
すごくパニックになった出来事でした。

本戦

簡単に感想など。

A: 正方形のチップ2

Submission #1733480 - DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦

去年の過去問を直前に見ていたのでデジャビュを感じた。
とりあえず、過去問のときと同じように、右上の領域について求めて、4倍すればいいなと思った。
しかしKが奇数のときの場合分けが案外面倒臭く、時間を取られた。結果として書けたコードも必死感あふれてる。
あとで解説を見ると、Kが小さいので、全ての格子点を調べて円に含まれるか判定するのが推奨されていた。
確かにそうすると場合分けいらないし、楽に書けるな〜と思った。

B: GCDロボット

Submission #1733480 - DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦

色々手元で実験してたら、GCDのLCMを求めるのが良さそうなのに気づいた。
LCMの求めかたは、わりと直近に類題を解いていたので、覚えてた。
LCM(a,b) = a * b / GCD(a,b)
私にしてはファインプレー。
問題を見てすぐに、素因数分解がいるだろ!と直感して素因数分解のコードを書き始めなければ、もうちょっと早く解けた。。(素因数分解はいらない)

C:グラフいじり

これは手も足も出なかった。。。
とりあえず閉路を検出しなきゃと思い、色々試してた。


というわけで、結果は2AC、42:38。
200人中、119位!!(実力・レートの割に、かなり上出来!)

ビュッフェ

本戦が終わったらビュッフェで昼食。
TABさんに思い切って声をかけ、北大の皆さんとご一緒させていただいた。
(TABさんは特に、今回私の出場のきっかけになったので、ご挨拶したかった)
競プロについてリアルで話せる人が私の周りにいないので、色々お話できたことでかなり刺激になった。
ICPCについて知らなかったけど、とてもアツイ世界があって、アツイ男たちがいるのを知った。

ビュッフェはピラフとパスタがあって、あとは揚げ物が多かった。
というか、人数が多すぎて、食べ物にたどり着くのに時間がかかった。
この界隈でよく聞く、人権とかハラスメントといった言葉が頭をよぎった。
(それはさておき、食べ物は美味しくいただいた。)
終了5分前にビュッフェに寿司が到着するハプニングもあった。(だがこれもすぐに売り切れた)

特別対談

ponanza開発者の山本さんと将棋棋士の西尾六段の対談。
これを、AtCoder社長のchokudaiさんの進行で進められた。
なんとも豪華。
しかも、私の席は舞台の真正面、前から3番目のすごくいい席だった(^^)

主な内容は、

  • 将棋AIが将棋界に与えた影響について
    • 古くからの戦法が否定されたり、逆に注目されたりしてる
    • 棋士の研究の仕方に大きな変化。(千田六段の手法を聞いちゃったけど、スゲ〜と思った)
  • AIが人間を上回っても結局人間は人間が好きという話
    • ニュースの注目度 (ponanzaが名人を倒す <<< 藤井四段フィーバー)
  • AIが競技プログラミングをやるとしたら?
    • というかすでにやってる(レート1000ぐらい←!!)

あとは、うん、メモを取りながら聞けばよかった...。
PCやメモ用紙やらクロークに預けたままだったのとても悔やまれる。

一応、Twitterの#DDCC2017 ハッシュタグで、質問や話してほしいことなどを受けつけるスタイルだった。

私もこんなことをポロっと書いたけど、実は、
競プロというのは、どちらかといえば AIに食われやすい 分野らしい。
ひぇー。意外。
入力と出力の形がお行儀良く決まっているからなのだとか。

すでにある競プロAIは、なんと、問題文を読んでないらしい。
出力のサンプルに合致する解法をゴリゴリ探索して、submitしまくるらしい。
それでレート1000なんて、驚き。
今後、問題文を解釈できるようになったら、確かにどんどん強くなりそう。

「AIの知能は指数的に成長するから、人間は油断しているといつの間にか抜かされている」
と、こんな話題があった。
将棋は電王戦という媒体があって、人間かコンピュータかみたいな構図が数年続いて、商業的にうまくいったけど、囲碁は抜きつ抜かれつのようなドラマをあまり見せることなく、気づいたら抜かされていた。

競プロも含め、多くの知的な分野で人間が敵わなくなるのは、確かに近い将来ありそう。

山本さんから、こんなメッセージがあった。
競技プログラミングだけではなく、他のチャンネルにも目を向けてほしい

これは確かにそう、で、肝に銘じている。

今は新しいアルゴリズムを身につけてどんどん問題が解けるようになるのが楽しくて、競プロをやっている。
そのうち、ここで身につけたことが、新しい何かを生み出す力になれば最高だと思う。
そこのレベルに行くには圧倒的に力が足りないので、今は精進するしかない。
でも、他のチャンネルにも目を向けるってのは、忘れずにいたい。

さて、少し脱線したけど、この対談もすごく刺激になったなあ。
面白かったから、どこかで放送してくれないだろうか。
(ディスカバリーチャンネルさん有料メディアだっけ?)

社内見学

主催のDisco社さんのリクルーティングを兼ねたイベントだったので、Disco社の紹介などがあった。
私は社会人だけど、せっかくの機会だしで、一緒に見て回った。
自社ビルにプール、ジム、仮眠室、食堂、社員寮…があって、福利厚生すげーと思った。

懇親会

このタイミングで結果発表があり、入賞者の表彰が行われた。
なんというか、皆さん独特なコメントが面白かった。

またも、お寿司が登場!
そして、今度はなんとビールももらえた。 キンッキンに冷えてやがら...なかったけど、ありがてぇ。。

ミーハーな一面のある私は、山本さんや西尾六段とお話しできるかなーと少し期待した。けどさすがにいらっしゃらなかった。
chokudaiさんはやっぱり、常に人気だった。
私が元々お顔を知っていたのがchokudaiさんだけだったので、もっと色々な人に話しかけていけなかったのが少し悔やまれた。(誰が誰だかわからない)
ネームプレート、どーんとでっかくユーザーネーム書いて欲しかった。。

終わりに参加者で集合写真を撮った。
男だらけで人口密度が満員電車レベルだったので、とても暑苦しかった

解散後

私はあるチャンスを伺っていた。
またとない機会なので、chokudaiさんに絡みに行こう、と。

まあ、同じことを考える人はたくさんいて、
本にサインをねだる人、ツーショット写真をねだる人がいた。
よし、これになろう!と思った。

chokudaiさんが他の参加者と歓談しているちょっとの隙をみて、「お疲れ様です〜」と話しかけて行った。
「よろしければお写真撮ってもらっていいですか〜」と。
自己紹介もせずに、我ながら図々しい男だ。

にもかかわらず、素敵な笑顔で応じてくれた。
ほんとは写真を撮ってもらった後に少しお話ししたかったけれど、ちょうど別の人が横で話したそうにしていたので、譲ってしまった。

今更ながら、自分だけ顔を隠して、勝手にchokudaiさんのお顔をアップロードしてしまったので、失礼でないかと思ってる。
(しかもツイート内容も興奮のあまり、chokudaiさんをパネル呼ばわりする超失礼なジョークが添えてある)
ご本人からいいねを頂いたので、寛大な心で許して頂いたと捉えてるけど。。
失礼がありましたらすみません。。

まとめ

長々とまとまりのない文章を書いてしまったが、、、読んでいただいてありがとうございます。

何度か書いたけど、イベント全般を通じて、とてもいい刺激を受けた。
私自身、冴えない人生を送るんだろうな、と感じたこともあったけれど、こういう強いプラスの刺激があると、人生が一転、華やかになるというか、まだまだ楽しいことがあるな、と感じた。
それと同時に、もっと競プロを頑張りたい!という思いが強くなった。

あとは、参加してみて思ったのは、競プロで出会った人たち、若いなって思った。
年齢的なことはもちろんあるのだけど、それ以上に、目がキラキラしてて、心から競プロを楽しんでいるのが伝わってきた。
私と違って、彼らは若さを有効活用できているので、この先も充実した人生を送れるだろうと信じて疑わない。
私も肉体的には中年になりつつあるのは仕方ないけど、精神的な若さは見習っていきたい! !

素敵な機会をありがとう、AtCoderさん、Discoさん、ディスカバリーチャンネルさん!!
次回もあったら、ぜひまた強くなって参加したい!!

運を引き寄せた話。(DDCC2017予選通過!)

DDCC2017の本戦に、出場できることになりました!!

Twitterアカウントを急遽作ったのでよろしければフォローお願いします。


今日書きたいことは上のツイートに割と凝縮されていて、私がアクションを起こさなければ、本戦のチャンスを逃していたということになる。

幻の切符

出場枠は、2019卒100名、その他一般枠100名。
少し就活生に有利になっている。(企業がやってるから、それはそうよね)
むしろ、就活生以外に100人も枠をもらえるなんて、かなり太っ腹だと思う。

2019卒とその他の人口比は分からないけど、仮に2:8だとしたら、一般枠のボーダーはだいたい125位ぐらいかな、と思ってた。
つまり、私の222位という順位では、2019卒除いて80人ぐらい辞退してくれないと回ってこない、絶望的な遠さだった。
私が本戦に出れることになったのは、これだけでも相当な奇跡だとわかる。
実質、回ってくることはないだろうと、諦めていた。

Web予選から2週間後くらい、たまたまTwitter上で「DDCCのボーダーラインがかなり繰り上がっている」という話題を目にした。
(Twitterアカウントは当時なかったけど、コンテストのたびに検索したりして勉強させてもらってた)
そこで、DDCCでさらに検索すると、一般枠は221位まで通過しているらしいとの情報を得た。
あれ、自分、何位だっけ?と順位表を見て、心臓が飛び出た。

祈った日々、悶々とした日、踏み込んだ日

当然それからというもの、通過メールが来てないか、敏感になる。
仕事から帰っても正直過去問を解くどころではなかった。

そしてその日はきた。でも、こなかった。

223位の方が、Twitterで通過報告をしていた。
思わずガッツポーズが出た。

でも、私のメールボックスには来ていない。
もちろん、Twitterで何人かが注意していたプロモーションタブも見たし、念のため持ってるGmailアカウントは全部みた。
まあ、明日になれば大丈夫だよね、のノリでその日は寝た。

翌日、やっぱり連絡は来ていない。
何かがおかしい。ざわ... ざわ...

色々と疑心暗鬼になってしまう。
もちろん仕事は集中できない。
私も通過メールを受け取って、ヨッシャー!と歓喜し、本戦対策に入りたいのに。

いざ問い合わせようと思ったとき、窓口は電話しかなく、平日の10-17時だけだったことを知った。
時刻は19時。なんたる不覚。

翌日。昼休み、やっぱり通過メールは来ていないことを確認し、運営へ電話。

まずは「本戦通過の状況について確認したい」と伝えた。
「19卒はまた繰り上げ者が出たところだが、一般枠100人はすでに出場者が決定した」の情報を得た。
ワオ!そんなこと、あってはならない。

ボーダーラインについても聞くと、一般枠は220位までの人にご案内しましたとのこと。
(あれ、持ってる情報と違うぞ??)

はあ、そうですか。。
(いや、そうじゃない!根暗サーチで仕入れたネタをぶつけるとき!)

「私は予選222位のprd_xxxですが、Twitterで223位の方が通過報告しているのを見ました 。順位の入れ違い等起こってないでしょうか?」
「本当に220位までで終了、なら納得できるのですが。本当のボーダーラインはどこでしょうか」

申し訳ありません、調べて折り返します、とのこと。
クソ!と思ったが、同時にしてやったりという気持ちに少しなった。

だがまだ安心はできない。
やはり仕事は集中できない。
疑心暗鬼になりすぎて、自分という存在がもみ消されるのではないかとも思った。

17時前、電話がきた。
とても低姿勢な話しぶりの女性に説明を受けた。
「『手違い』がございまして、通過の連絡を差し上げたつもりが、行き届いていませんでした」
「prd_xxx様に本戦に出場していただきたく思います」

やった!2回目の本当のガッツポーズでた。

自分がクレーマーだったら、
「なぜ手違いが起こったのか」「なぜ折り返しの連絡に時間がかかったのか」等、追求してたかもしれない。
でも、DDCC本戦に出られることの喜びに比べたら、どうでもよくなった。
なお、本当のボーダーラインは、やはり223位とのことだった。

予選は終わっていたので成績は変えられないけど、執念で運命を変えた

何もしなければ本戦に出られなかった世界線に落ちるところだったけど、それを捻じ曲げて自分の行きたい世界線を引き寄せた

夢が現実になるって、こんな感じなのか。

不思議な縁

前の記事でもさらっと触れたのだけど、講演がかなり楽しみ。

3者とも、画面の向こうでしか見ない、凄すぎる人!!
凄すぎて凄さがわからないレベルを凌駕した凄さ
いや、表現できる語彙がない。ヤバイ。

私は2012年あたりから、観る将棋ファンになった。
電王戦がはじまって、米長永世棋聖ボンクラーズが戦った頃から。
コンピュータvs棋士の構図を通じて、棋士のひたむきな姿勢に惹かれていった。

コンピュータ将棋プログラムはだいぶ昔にBonanzaのソースを読もうとしたことがあったけど全然解読できなかった。
私のような挫折だらけのプログラマからしたら、山本さんみたいにコンピュータ将棋で世界一になって維持し続けるなんて、想像もつかない。

西尾先生も、YouTube四間飛車講座がわかりやすくて、お世話になった。
棋士の時点で凄すぎるのだけど、棋士の中でも研究熱心と慕われてる上に、ギター極めたりとかしてる。

そして言わずと知れたchokudaiさん。AtCoder作ってる神。
競技プログラマの憧れ。

もちろん、本戦の大会も楽しみ!(こっちがメイン)
というか、明日、いつも順位表でしか眺めない猛者達と同じ舞台に立てる(座れる?)ってのが、本当にヤバい。
自分がこの中に混ざっていいのだろうか、という気持ち。

いやー本当に楽しみ!
エンジョイ勢(?)なりに、いつも通りの力を出せるように頑張りたい!
奇跡に感謝。


以上、拙文・長文でしたが、読んでいただきありがとうございます。
それでは明日よろしくお願いします!!

CODE FESTIVAL 2017 qual C

3日ぐらい前のやつ。

ところで、先日のDDCCの本戦、辞退者が多くてどんどんボーダーラインが繰り上がってる、と風の噂。
行けたらぜひ本戦行きたいので、かな〜り気になってる。
ちなみに10/26 1:00現在、予選222位の私には連絡なし(´・ω・`)

結果

A,B,Cの3完。タイム19:43。395位。
パフォーマンス1782(highest!)、レート1303→1367(highest!)(+64)

A,Bで少しモタついてしまい600位ぐらい → Cで冷静に挽回できて300位ぐらい。
あとはDの700が難しく、あまり順位が下がらず救われた。(救われてはいけない)
どうも、あるレベル(400-500点?)より難しい問題だと、手も思考もフリーズしてしまうのをなんとかしたい。

A - Can you get AC?

A - Can you get AC?

2〜5文字までの入力があって、文字列'AC'を含むかどうか。

S = input()
print('Yes' if 'AC' in S else 'No')

はい。
なんだけど、pythoninのイディオムが咄嗟に思い出せずにググった。。
ゴリゴリとforループ回した方が早かったかも。
ど忘れコワイよー。

B - Similar Arrays

B - Similar Arrays

整数の数列が入力として与えられて、各項が±1の範囲の整数になってる数列を「似ている」数列と呼ぶとき、
似ている数列の中で、全ての項の積が偶数になるものがいくつあるか。

これ、最近の200点にしては難しかったので、焦った。 体感300点ぐらい。

N = int(input())
src = list(map(int,input().split()))
 
whole = 3**N
even = 0
for i in range(N):
    if src[i]%2 == 0: even += 1
 
print(whole - 2**even)

コード自体は、一言で言うと、
偶数の数を数えて、3^Nから2^[偶数の個数]を引いてるだけ。

なぜそうなるのか。プチ解説

各項、+1,±0,-1の3通りが許されるので、「似ている」数列は全部で 3^N 通りある。
この問題は偶奇だけを考えれば良いので、似ている数列では、
「奇・偶・奇」または、「偶・奇・偶」がN個並んでいることになる。
内訳は、数列に偶数がe個あったとすると、
「奇・偶・奇」がe個、「偶・奇・偶」が(N-e)個になる。

整数どうしの積は、
奇数同士はいくら掛けても奇数 ↔︎ 偶数が1つでも含まれていれば偶数
という性質がある。
これを使って、全体から「奇数のみからなる数列の個数」を引く と良さそう。

「似ている」数列の中から、奇数のみからなる数列を作るには、

  • (N-e)個の「偶・奇・偶」については、真ん中の奇数を取るしかない。1通り。
  • N個の「奇・偶・奇」については、どちらかの奇数が選べるので、2通り。

奇数のみからなる数列は、
1^(N-e) * 2^e = 2^e 個。
つまり、答えは全体から引いて
(3^N - 2^e) 個。

ちなみに、Nが10と小さいので、3^Nを全探索しても良い、という問題でした。

C - Inserting 'x'

C - Inserting 'x'

文字列が与えられて、'x'と言う文字を何回か挿入して回文になるなら、その最小回数を出力し、回文にならなければ-1を出力する問題。

これはB問題とは逆に、400点にしては少し簡単に感じた。
むしろBより楽だったかも。

S = input()
l = 0
r = len(S)-1
cnt = 0
while l < r:
    if S[l] == S[r]:
        l += 1
        r -= 1
    elif S[l] == 'x':
        l += 1
        cnt += 1
    elif S[r] == 'x':
        r -= 1
        cnt += 1
    else:
        cnt = -1
        break
print(cnt)

コード見てもらえばわかると思うけど、lrの添字を文字列の頭とお尻に設定して、そこから挟み討ちのようにlは増やし、rは減らしていく方針
途中、lまたはrのうち一方が'x'だったら、'x'のカウントを1増やして、'x'だったほうの添字を進める。
lrが異なっててどちらも'x'でないときは、いくら'x'を挿入しても回文になり得ないので、-1

whileの終了条件が少し不安なままsubmitしてしまったのはちょっと秘密。
実際はもしl==rだとしても同じ文字を参照するから変にカウントは増えない。大丈夫。

ところで、これはしゃくとり法の一種なのかな?

よくあるしゃくとり法って、 頭をr、お尻をlって決めて、しゃくとり虫みたいにlrを進めていくイメージ。
今回のやつは、
ビヨーンと最大に伸びきったしゃくとり虫が、縮んでいって最後には無になるイメージ。

しゃくとり法は単純な割に、実はO(N)と知って、あなどれないと思った。
この手の問題のときには優先的に思い浮かべることにしてる。

Atcoder Beginner Contest 075

5日ぐらい前のやつです。

結果

A,B,Cの3完。タイム23:33。302位。
レート変動なし。

感想

水色コーダーになってから初めてのABC。
これから青コーダーを目指すにあたってサクッと全完する... つもりが、
D問題で迷宮に陥り、時間切れ。
精進しなきゃ。。

A One out of Three

A - One out of Three

素直にif-elseする問題。(説明になってない)

A,B,C = map(int,input().split())
if A == B: print(C)
elif B == C: print(A)
else: print(B)

すごいと思ったのが、if文を使わずにXOR演算で print(A^B^C) みたいに解いた人がいたらしい。
確かに、同じ数を偶数回XORするとその数は消えるから、答えが残るね。
絶対に思いつかないな〜。

B Minesweeper

B - Minesweeper

いわゆるマインスイーパの爆弾の位置が与えられて、空きマスについて、8近傍に爆弾がいくつあるかを求める問題。

これも基本的なif-elseとfor文が使えればできそう。
でもABCのBにしては実装量が少し多い。

H,W = map(int,input().split())
src = [input() for i in range(H)]
 
ans = []
for row in src:
    ans.append(list(row))
 
dxy = [(-1,-1),(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1)]
for y in range(H):
    for x in range(W):
        if src[y][x] == '#': continue
        c = 0
        for dx,dy in dxy:
            if x+dx < 0 or x+dx > W-1 or y+dy < 0 or y+dy > H-1: continue
            if src[y+dy][x+dx] == '#': c += 1
        ans[y][x] = c
 
for row in ans:
    print(''.join(list(map(str,row))))

2行目のsrcに文字列の配列を読み込んでいるけど、
Pythonだとsrc[0][1] = '1'みたいな文字列への代入ができなくて、
仕方なく答えを書き出す用のansという配列の配列を用意してる。
最終的にansを結合して出力してる。(なんか微妙な気が。。

あとは、8近傍の調べ方がいくつかテクがあるっぽい。
解説のソースコードを抜粋すると、↓の書き方だった。

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

でもこれ、うまく説明できないけど、なんかモヤっとする...。
dx[i]dy[i]はセットで意味をなすので、(dx[i],dy[i])みたいにまとめたいと思ってしまう。

というわけで、せめてもの抵抗として(笑) (dx[i],dy[i])とタプルでまとめたコードを貼り付けた。
でも、カッコで囲ってるぶん、タイプ数が少し多いような。
競プロは早さを競うのだからうだうだ言ってられませんがな。

次からは素直にdxdyでやるか。(ズコー

ちなみに、上で載せた私のコードは実はブログ用に書き直してて、本番でAC取ったのは愚直なif-elseの山。

(おまけ)ACは取ったけど載せるのをためらったコードは↓
Submission #1682548 - AtCoder Beginner Contest 075

C Bridge

C - Bridge

二重辺や自己ループのない無向連結グラフがあって、取り除いたら連結じゃなくなる辺がいくつあるか。
以下私の回答。

N,M = map(int,input().split())
es = []
for i in range(M):
    a,b = map(int,input().split())
    a,b = a-1, b-1
    es.append((a,b))
 
parent = None
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def is_same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    parent[ra] = rb;
 
ans = 0
for i in range(M):
    parent = [k for k in range(N)]
    for j,e in enumerate(es):
        if j == i: continue
        a,b = e
        unite(a,b)
    a,b = es[i]
    if not is_same(a,b):
        ans += 1
print(ans)

Union-Findを使って解いた。
Union-Findは、競プロ歴5ヶ月の私が知ってる知識をざっくり説明すると、

  • グラフのある頂点とある頂点が繋がってるかどうか高速に判定するよ
  • 辺がない状態から、辺を追加しながら構築するよ。構築の途中でも判定できるよ
  • 判定も追加もほぼ定数時間(ちょうはやい)。アッカーマン関数(とてもでかい)の逆数だとか
  • 初期化するのだけO(N)かかるよ(N:頂点数)

上記コード中に出てきたroot()is_same()unite()がUnion-Findだけど、
スニペットに入れてたやつそのままなのでかなり楽できた。

あとは、全ての辺をループして、辺eを除いたグラフでUnion-Findを構築して、
辺eの両端が繋がってるかを判定していけばいい。

計算量は、辺ごとにUnion-Find初期化+構築でO(N+M)なので全体でO(M(N+M))かな?
NもMも小さいので大丈夫!

ちなみに、想定解ではUnion-FindじゃなくてDFSで解いてたみたい。
DFSは思いつかなかったので両方思いつくようになりたい。

2部グラフ判定問題

先日のコドフェで、2部グラフってのを扱う問題が出たので、勉強してみた。

2部グラフとは

(雑な説明、ご容赦ください)
いくつかの頂点があって、それらを辺で繋いで考えるモデルをグラフという。
棒グラフとか、円グラフとか、折れ線グラフとかのグラフではなくて、グラフ理論のはなし。

グラフ理論のグラフにも種類があって、2部グラフはその中の1つ。
どんな特徴があるかというと、頂点を2つのチームに分けたとき、「全ての辺が、自分チームと相手チームを結んでいる」ように分けることができる。

  • 2部グラフの例
    f:id:prd_xxx:20171020010001p:plain

  • 2部グラフじゃない例
    f:id:prd_xxx:20171020010013p:plain

例えば、男女の複雑な三角関係や四角関係(!?) を図に書いたとき、男女間でしか線が引かれていなければ2部グラフと言える。
男男間、女女間にも線が引かれていれば、2部グラフじゃないかもしれない。
かもしれないと言ったのは、別の何かしらの基準で(例えば右利きの人と左利きの人みたいに)チーム分けしたときに、「全ての辺が、自分チームと相手チームを結んでいる」ふうにできれば、2部グラフだから。

よく考えたら、三角関係が含まれていたら、2部グラフになり得ないっすね。^^;

2部グラフ判定問題の解き方

2部グラフ判定問題とは、与えられたグラフが2部グラフかどうか、という問題である。
「蟻本」の94ページに、C++のコードが載っていたので、意訳してpythonで書いてみた。

全ての辺において、一方が黒、もう一方が白となるように頂点を塗ることを考える。
2部グラフの場合、ある頂点の色が黒だとすると、そこに隣接している頂点は一意に白と決まる。
最初は適当に1箇所を黒で塗って、あとはDFS(深さ優先探索)で白、黒、白... とどんどん塗っていって、矛盾がなければ2部グラフ。

難しそうに思えて、意外と単純!

# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)

# 入力のつもり。esはよくある隣接リストで辺を表したもの。
N = 5
#es = [[1,2,3],[0,2],[0,1],[0,4],[3]] # False
es = [[1,3],[0,2],[1,3],[0,2,4],[3]] # True

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)] 

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

print(is_bipartite())

ちなみに、2部グラフは英語では、bipartite graph というみたい。
biは"2"、partiteは "partに分ける"ってことかな?(適当)
is_nibu() とかでもいいんだけど、なんかダサかったので(笑)

おまけで、再帰なし版も載せておきます。

# 入力のつもり。esはよくある隣接リストで辺を表したもの。
N = 5
#es = [[1,2,3],[0,2],[0,1],[0,4],[3]] # False
es = [[1,3],[0,2],[1,3],[0,2,4],[3]] # True

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    stack = [(0,1)] # (頂点、色)のタプルをスタックする。最初は(頂点0, 黒(1))
    while stack:
        #スタックから最後に追加された(頂点, 色)をpop
        v,color = stack.pop()
        #今いる点を着色
        colors[v] = color
        #今の頂点から行けるところをチェック
        for to in es[v]:
            #同じ色が隣接してしまったらFalse
            if colors[to] == color:
                 return False
            #未着色の頂点があったら反転した色と共にスタックに積む
            if colors[to] == 0:
                 stack.append((to, -color))
    #調べ終わったら矛盾がないのでTrue
    return True

print(is_bipartite())

DFSを初めて覚えたとき、再帰なしのコードで覚えたので、こっちのほうが個人的に馴染みがある。
再帰は深さとか気にしなきゃいけないし、動きをイメージしづらいし、デバッグしづらい、って意識があって、あんまり書きたくないと思ってた。
でもこうやって比較すると、なるほどこのDFSだと再帰のほうがコードがすっきりしてる。
(イメージのしづらさとかは置いといて)
引き出しは多いほうがいいから、両方書けるようになっておこうっと。

実践例

さて、これでようやく、先日のコドフェ予選BのC問題が解けるようになりました。
問題はこちらです。
C: 3 Steps - CODE FESTIVAL 2017 qual B | AtCoder

(意訳)
N <= 106 頂点を、M <= 106 の辺で結んでいる。
連結な無向グラフで、自己辺や多重ループはない。
3つの辺を経由してたどり着ける(=あいだに2頂点を経由する)2点を全て結ぶように辺を追加するとき、最大で何本の辺を追加できるか。


これ、解く方針がわかりませんでした。
N,M <= 106 のサイズがネックで、私の思いつく解法だとどうしても間に合わない。
(全ての頂点から伸びてる辺、のそのまた先の伸びてる辺、を調べるだけで、 O(NM) ぐらい?にはなってしまう気がした。)
小手先の工夫でゴリゴリやって倒せる相手じゃなかった。

解説を見たら、魔法みたいな解法がありました!
どうも、探索で解くというよりは、グラフの性質を使って解く模様。
より詳しくは、解説を見てね。(私レベルには若干わかりづらい)

まず、距離が3辺離れた点を繫ぐということは、距離3が1になり、
同様に距離が奇数離れた点の間は2ずつ縮めることができて、そのうち辺を繋げる!
なるほどなぁ。。気づかなかった。。

そして、ここで、2部グラフが登場する。
2部グラフの場合、自分チームと相手チームを結んでいる辺しか存在しない。
どの頂点からも、奇数個の辺をたどって行ける頂点は相手チームで、偶数個の辺をたどって行ける頂点は自分チーム。
もちろん1辺の両端は異なるチームだし、3辺離れた頂点同士も、異なるチームになる。
とすると、この問題のルールにおいては、同じチーム同士はどうやっても結べない!

反対に、2部グラフでなければ、どこかしらの2点間は
奇数個の辺をたどっていくルートと、偶数個の辺をたどっていくルートが存在する
ということだから、全ての辺は、いずれ繋ぐことができる!

なので、結論は

  • 2部グラフなら、黒・白と塗った頂点数をB,Wとして、B*W - M本。
  • 2部グラフでなければ、全頂点間が結ばれるので、 N(N-1)//2 - M本。

になるらしい。
すっごーい !!

早速、上で書いたコードをぺたりと貼り付けて、ACもらってきました!

import sys
sys.setrecursionlimit(10**7)
 
N,M = map(int,raw_input().split())
es = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,raw_input().split())
    a,b = a-1,b-1
        es[a].append(b)
        es[b].append(a)
 
colors = [0 for i in range(N)]
 
def dfs(v,color):
    colors[v] = color
    for to in es[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True
 
def is_bipartite():
    return dfs(0,1)
 
if is_bipartite():
    b = (sum(colors) + N) // 2
    w = N-b
    print(b*w - M)
else:
    all = N*(N-1) // 2
    print(all - M)

なお、2部グラフ判定のところ、再帰版ではAC取れたけど、
再帰なし版もsubmitしたら、テストケースが1つTLEだった。
ステップ数はさほど変わらないような気がするが、、ナゼだ。。
どなたか分かる方、ご教授ください。。。(考察放棄)

この問題のキモ

この問題、見抜かなきゃいけないことがたくさんありました。

  • N,M <= 106 のサイズは、工夫したところで、隣の隣の、、みたいな探索は到底できないこと。
  • グラフの性質を使って計算で解く問題ということ。
  • 奇数個離れた頂点なら、いずれ、全て結ぶことができること。
  • 2部グラフかどうかで答えの方針が変わること。

2部グラフを知っていなきゃ解けない問題だったのだけど、
知らなかったとしても、3番目のポイントまで見抜いていなければ、どのみち解けなかったという。

ぐぬぬ
精進します!

CODE FESTIVAL 2017 qual B

結果

A,Bの2完。タイム06:25。549位。
パフォーマンス1598、レート1259→1303(+44)

C,D問題、むずかった。。
そして全然できなかったのにレート上がっちゃった。
少し腑に落ちないと思ったけど、結局どちらも自力でできる内容じゃなかったので、ある意味実力通りか。
どうやったら、あの問題から、2部グラフなんて思いつくようになるんだろう。。。
というか、2部グラフってものは蟻本でさらっと出てきただけで存在を忘れてたし、使ったこともなかった。
次は絶対に解けるようにしとこう。

A XXFESTIVAL

A: XXFESTIVAL - CODE FESTIVAL 2017 qual B | AtCoder

末尾の8文字を除いてprint。

S = input()
print(S[:-8])

B Problem Set

B: Problem Set - CODE FESTIVAL 2017 qual B | AtCoder

N問の問題セットがあって、その中にM問の指定された難易度の問題が含まれているか。
以下、私の回答

import sys
from collections import Counter
 
N = int(input())
s1 = list(map(int,input().split()))
M = int(input())
s2 = list(map(int,input().split()))
 
c1 = Counter(s1)
c2 = Counter(s2)
 
for k,v in c2.items():
    if k in c1:
        if v > c1[k]:
            print('NO')
            sys.exit()
    else:
        print('NO')
        sys.exit()
print('YES')

pythonCounterモジュールを使った。(個人的によく使う)
l = [10,20,30,20] みたいなリストを、Counter(l)とかやると、
{10:1, 20:2, 30:1} みたいなdict型に集計してくれるすごいやつ。
key:valueのうち、keyの方がもともとの要素で、valueの方が集計した個数。(たまに、どっちか混乱する。)

c2.items() でM問の必要な方をループして、N問の用意してある問題セットに1つもないか、問題セットが足りなければNOを出力。
ループが最後まで行けばYESを出力。
こんな感じでしたー。