ごりちゃんがゆく

競プロをするゴリラの精進記録

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部グラフ判定問題

(2024/03/14 更新) 本記事で扱われているコードの上位互換となるコードを書きましたのでご確認ください
グラフの各連結成分が二部グラフかどうか解析するモジュールを書いた - ごりちゃんがゆく


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

2部グラフとは

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

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

  • 2部グラフの例

  • 2部グラフじゃない例

例えば、男女の複雑な三角関係や四角関係(!?) を図に書いたとき、男女間でしか線が引かれていなければ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

(意訳)
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を出力。
こんな感じでしたー。

DISCO presents ディスカバリーチャンネル コードコンテスト 2017 予選

概要

2019卒枠が100人と、その他の100人が本戦に進めるコンテスト。
本戦の告知(DDCC | ディスカバリーチャンネル)を見たら、イベントがすごく豪華。
特に対談のメンバーがすごい。皆憧れの人ばかり。
(将棋界と将棋プログラムのトピックは、ここ何年か、個人的に追いかけているので)
厳しいだろうけど、何としても本戦出たい!って思いで参加しました。

結果

A,B,C の3完。タイム10:20。222位。
C問題までは自分的にベストなパフォーマンスだった。
D問題は1submitしたけど、考察力が足りずWA+TLE。
その他枠の人、100人ぐらい辞退してくれないかな〜??。。
まあ、そんな訳ないので、来年までに力をつけてリベンジするか。。

A,B問題

特に難しいポイントがないので省略。
ダースの12倍がグロス、その12倍がグレートグロスという単位があるのを初めて知った。

以下、 私の回答
A - DDCC型文字列
http://ddcc2017-qual.contest.atcoder.jp/submissions/1656175

B 鉛筆
http://ddcc2017-qual.contest.atcoder.jp/submissions/1656644

C 収納

C: 収納 - DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選 | AtCoder

N <= 100000 本の棒があって、長さCのケースに収納していくとき、ケースの最小数を求める。
ケースには1本か2本入れられて、2本入れる場合は[2本の和 + 1]の長さが必要。

以下、私の回答

N,C = map(int,input().split())
src = [int(input()) for i in range(N)]
src.sort()
 
l = 0
r = N-1
ans = 0
while l <= r:
    if src[l] + src[r] + 1 <= C:
        l += 1
    ans += 1
    r -= 1
print(ans)

ソートして左右から貪欲でいけた。
一番長いのを一番短いのと一緒に詰めることができれば、2本しまう。
そうでなければ、一番長いのを1本しまう。

例として、入力例1の C=10, L=[2,8,4,5]の場合。

  • ソートする。L=[2,4,5,8]
  • 2+8+1 > 10 で、8は単独で入れるしかないので、8をしまう。ans=1, L=[2,4,5]
  • 2+5+1 <= 10で、2と5が両方入るので、両方しまう。ans=2, L=[4]
  • 最後に4をしまう。ans=3

こんな感じ。

実際は、lとrの2つのインデックスを操作すれば、配列の要素を消すことなく、シミュレーションできる!
計算量は、

  • ソートにO(NlogN)
  • 貪欲なシミュレーションがO(N)

O(NlogN) なので大丈夫!

最後にちょっと脱線

このブログについて、本当は勉強したことをまとめていって自分用のノートにするつもりだったけど、気づいたら競プロの参加記になってた件。

まとめたいネタはいくつかあるんだけど、どうも、人が見て分かるような体裁にまとめるのが苦手というか、意外と骨が折れることが分かった。
記事にまとめるのより、過去問にチャレンジした方が楽しい ^^;。

まあ、無理せず、自分のペースでやればいっか。