あったこといろいろ

ほぼ自分用備忘録です。

ICPC引退を期に競技プログラミングに出会ってからの4年半を振り返る

この記事は、 「競プロ!!」 競技プログラミング Advent Calendar 2017 22日目 の記事です。公開が大幅に遅れてしまい申し訳ありませんでした。

はじめに

本記事は、「ICPCをきっかけに競技プログラミングに出会い、4年半の間ICPCに出場し続けた競技プログラマー」のポエムとなっております。この記事を読んでも、アルゴリズムの理解が深まったりだとか、プログラミングの有益テクニックが得られるということは残念ながらありませんが、読んだ方のモチベーションになれば幸いです。


読者のみなさんは、昨年のアドベントカレンダーで公開された「競技プログラミングを始めての10年間を振り返る( 前編, 後編 )」をご存知でしょうか?僕はこの記事を読み、当時の競技プログラミングを取り巻く環境や、skyさんの当時の気持ちを知ることができ大変興味深いと感じました。僕の実力は彼には遠く及びませんし、競技プログラミングに取り組んでいる時間も短いのですが、「プロじゃなくてもICPC引退を期にポエム書く権利くらいあるやろ」ということで、僕の競技プログラミングに出会ってからの4年半についてお話したいと思います。


書いてると結局ほとんど自分語りみたいになってしまったので、この先は「それでも良いよ」という方だけお読みください。


自己紹介

  • 現在修士課程1年生
  • 競技プログラミングに出会ってから約4年半が経過
  • 先日のICPCアジア地区つくば大会をもってICPCを引退
  • 2013年~2017年にかけてICPC国内予選に参加、うち2度アジア地区予選進出*1
  • AtCoderレート: 1895(max 1997)
  • TopCoderレート: 1515(max 1656)



2013年 ( 高専4年生 )

4月時点でのTopCoderレート: なし
競技プログラミングに出会った年です。ちなみに、高専*2の4年生は大学の学部1年生に相当します。

競技プログラミングとの出会い( ICPC2013国内予選参加 )

今となっては何の自慢にもならない話ですが、僕はいわゆる「クラスの中では比較的プログラミングができる」タイプの学生でした。そんな学生だった僕は、プログラミングの授業を受け持って下さっていた先生の誘いを受け、内容もよく知らないチーム戦コンテストに出場することを決めました。これがICPCと出会うきっかけでした。昨年もICPCに参加したという、プログラミングが得意な先輩2名とチームを組ませて頂き出場しました。

コンテスト開始までの時間は昨年出題されたA問題( ミレニアム | Aizu Online Judge )を解かせてもらっていて、もうすぐコンテストも始まろうかというタイミングでなんとかサンプルが合った*3のをよく覚えています。

コンテストの方はと言うと、先輩方が解法を思いつきA,B問題にそれぞれ取り組んでいたため、C問題( 階層民主主義 | Aizu Online Judge )を担当することになりました。結果から言うとC問題が解けることはありませんでしたが、「再帰的に計算することができる」や「複数ある選挙区のうち勝ちやすいものから貪欲に表を集めれば良い」といった考察を紙の上に並べながら悩む時間は案外楽しいものでした。

ICPC国内予選のメンバー探し&チーム練習

前回のICPCでの屈辱を晴らすべく、1月頃には次回のICPCに参加することを決めていました。去年通りなんの準備もなく挑んでもダメだと考えた僕は、早い段階でチームを組んでチーム練習をしておくことを考えました。
仲の良い友人2名に、「ICPC国内予選に一緒に出場してもらえないか」、「一緒に競技プログラミングを初めてくれないか」ということをお願いしました。彼らは快く受け入れてくれ、過去のICPC国内予選の問題を用いたチーム練習をしたりcodeforcesにそれぞれ出場してみたりといった活動を行いました。僕のワガママに付き合ってくれた友人には今でも心から感謝しています。

RUPC参加

DFSすら書けず「お前は一体何なら書けるんだ」という程度のレベルの僕でしたが、Twitterで見かけたRUPC( 立命館大学競技プログラミング合宿 )に果敢に参加しました。これは僕にとって初めてのオンサイト競技プログラミングイベントでした。日頃から競技プログラミングをしている人と、チームを組んだりお話をすることは非常に楽しかったです。実力問わず楽しめる本当に良い合宿だと思うので、興味のある人は是非物怖じせず参加してみることをオススメします*4。( 参考: 立命館合宿参加録 1日目 - あったこといろいろ, 立命館合宿参加録 2日目 - あったこといろいろ )


2014年 ( 高専5年生 )

4月時点でのTopCoderレート: 811
本格的に競技プログラミングにのめり込み初めた年です。競技プログラミング実質1年目程度にしてCODE FESTIVAL本戦進出などの目に見える成果が得られたのは、今にして思えば非常に幸運なことだったと思います。

AtCoder, codeforces, TopCoder出場

ICPC国内予選までに、AtCoderで50AC*5, codeforcesコンテストに3度参加*6, TopCoderコンテストに12回出場したようです。TopCoderで4月に行われたTCOのRound1を運良く通過できたことがモチベーションに繋がったことをよく覚えています( 今となってはTCOのRound1は0pt以下を除き全員通過しますが、昔はそうでもなかったんですよ! )。

ICPC2014国内予選参加

1月から3度のチーム練習をして国内予選に臨みました。が、僕がA問題で詰まってしまい、その上PCを占領し続けたため0完という結果に終わってしまいました*7。この経験が本当に悔しかったため、結果的に競技プログラミングに次第にのめり込んでいくことになります。( 参考: ぼくの二度目のICPC - あったこといろいろ )

CODE FESTIVAL 2014本戦出場

実力的には間違いなく予選落ちのはずだったのですが、偶然部分点を素早く取っていたため本戦に出場することができました。結果は196位*8だったので本当にギリギリ予選通過したという感じだったのですが、初めて予選を通過してオンサイトに出場できたことが大変うれしく、競技プログラマー人生を変えたイベントの一つだと思っています。ほとんど競技プログラミングを始めたての僕にとっては、iwiwiさんやchokudaiさんに直接会えたことや、トップレベルの人たちを間近で見ることができたのは非常に貴重な経験でした。( 参考: CODE FESTIVAL 参加記 - あったこといろいろ )


2015年 ( 学部3年生 )

4月時点でのTopCoderレート: 1049
高専卒業後はRiPProのある立命館大学へ進学し、本格的に競技プログラミングに取り組み始めました。すぐ近くに競技プログラミングに取り組んでいる人が居る環境は非常に良いものでした。

RiPProでの活動

RiPProは、競技プログラミングを専門としたプログラミングサークルです。数あるコンテストの中でも特にICPCに力を入れており、AOJでの練習を重視している点や、AOJ-ICPCを埋めたいという雰囲気が存在する点が大きな特徴ではないかと勝手に思っています*9。入部後は、AOJ virtual arena を利用した部内コンテストに毎週参加していました。入部前は気が向いた時以外に問題を解いていなかったことを考えると、格段に多くの問題を解くようになりました。また、幸運にも実力の近い人が部内にいたため、相手にAC数を抜かれまいとしてお互いかなりのスピードで問題を解くという良い循環も発生しました。

ICPC2015国内予選参加

昨年までとは打って変わって、日頃から競技プログラミングをしている人と参加することができました。当時TopCoder青コーダー上位だった tubo28 氏がチームにいた事や、模擬国内予選で予選通過圏内の順位を取れたことから、アジア地区進出の期待は非常に大きかったです。しかしD問題を解くことができず*10、結果は3完でした。2年越しの野望であったアジア地区大会進出がまたも叶わなかったことに当時非常にショックを受けました。

ICPC2015アジア地区台湾大会参加

国内のアジア地区大会に進出できなかった僕達は、台湾で開催されるアジア地区大会に参加しました。アジア地区大会は日本以外にも様々な国で開催されており、台湾や韓国、タイ等 近隣の国のアジア地区大会に予選なしで参加することができる仕組みが存在します*11。僕達はこの仕組みを利用して初のアジア地区大会に参加することになりました。コンテスト本番では掃き出し法や橋の検出など、僕の知らないアルゴリズムを次々と取り出す tubo28 氏の知識量に感動し、このあたりから少しづつアルゴリズム自体に興味を持つようになっていきました。


2016年 ( 学部4年生 )

4月時点でのTopCoderレート: 1229
RiPProに入部して1年間練習を続けたことで少しづつ実力が付いて来ました。ICPCアジア地区大会進出に次ぐ昔からの目標であった青コーダーになり、最もモチベーションが高かった年であったかもしれません。

ICPC2016国内予選参加

頼りになる先輩 tubo28 氏は卒業してしまったため、先輩Aと後輩Aにチームを組んでもらい出場することになりました。「RiPProの活動」の部分で述べた「実力の近い人」( ixmel 氏と T.M. 氏です )は別のチーム( SIMrit )で出場することを決めていたため、もし通過ラインを超える順位を取っても学内予選*12が発生する可能性がありました。お互いのチームメンバーのレーティングや模擬国内予選の結果を見る限り、順当に行けばアジア地区に進出するのはSIMritだろうなと思っていました。
しかし本番ではなんと、SIMritよりペナルティタイムが少なく4完したため、僕達のチームがアジア地区大会に進出できることが決まりました。A~Cまでのペナルティが僕達の方が大きく、4完直後も「この20分の間にSIMritが4問目を通せば逆転される」という状況になり、この時間が非常に長い時間に感じたことをよく覚えています。( 参考: ICPC2016 国内予選 参加記 - あったこといろいろ )

ICPC2016アジア地区つくば大会参加

大会本番では、あこがれのアジア地区大会に出られたことでかなり舞い上がっていました。他のオンサイトとは異なり名札にもチームプレート(?)にも大学名が記載されていたり、順位表にも大学名が大きく掲載されるのを見て、勝手に大学を背負っているような気分になったりしていました。
しかしコンテスト本番では緊張のためかかなり手こずってしまい、3完で下から4位という振るわない順位となりました*13。このとき、アジア地区大会は非常にレベルが高いものであり、2015年以前に偶然アジア地区大会に参加できていたとしても手も足も出なかっただろうなと強く感じました。( 参考: ICPC2016アジア地区つくば大会参加記 - あったこといろいろ )

2017年 ( 修士1年生 )

4月時点でのTopCoderレート: 1630
立命館大学とRiPProを卒業してNAIST*14に入学しました。

メンバー集め

入学を決めた当初はNAISTからICPCに競技プログラマーと一緒に出場することは叶わないだろうと思っており、名前を貸してくれる人を探さなければと思っていました。しかし、幸運にも ゆらふなさん が( ほぼ )同時期に入学したり、入学直後に声をかけた らてあ君 が競技プログラミングに興味を持ってくれたおかげで、なんと競技プログラマーが3人揃ってしまいました。本当に幸運だったと思います。

ICPC2017国内予選参加

A~Cが片付いてD問題に合流した時には ゆらふなさん がすでに解法を思いついていたこともあり、ほとんど何もしていないのにあっさり予選を通過できてしまったという印象があります。ちょうど一年前は予選を通過しただけでも大喜びしていたことを考えると不思議なものです。何はともあれ、国内予選を突破できずにICPC引退ということにはならずに済みひとまずホッとしました。( 参考: ICPC2017 国内予選 参加記 - あったこといろいろ )

ICPC2017アジア地区つくば大会参加

2度目のアジア地区つくば大会であり、昨年ほどの緊張はありませんでした。結果は4完で順位は30位/50位でした。もう少し時間があればもう1問解けそうではあったのですが、もっと上を目指すならばそもそもB,C問題あたりのレベルの問題はサッと解けて当然にしておかなければならなかったのかもしれません。こうしてあっさりと最後のICPCが終わりました。
コンテスト後の懇親会では、同年代の選手やコーチをしている知り合い等、昔からの知り合いとばかり話していました。最近の競技プログラマーの方や、彼らの使う構文にだんだん疎くなってきたことを考えると、そろそろ引退すべき頃合いなのかもしれないと妙に納得したりしていました。


まとめ

僕はICPCアジア地区大会出場を最も大きなモチベーションとして競技プログラミングを続けてきました。僕はアジア地区大会に出場できるようになるまで3年間もかかりましたが、悔しいことは多くても苦しいことはそれほど多くありませんでした。競技プログラミングが役に立つかどうかはよくわかりませんが、一つのことにこれだけ長い期間熱意を持って取り組み続けられたことは自分にとって良い経験になったと思います。これまで競技プログラミングを続けられて本当に良かったです。
「引退です」と何度も言ってはいますが、AtCoderを始めとするオンラインコンテストにはこれからも出場し続けたいと思っているので、これからもよろしくお願いします。


おわりに

こういうのなんか恥ずかしいし需要があるか謎なんですが、skyさんの記事以外にも数年を振り返るタイプの記事があっても面白いかなと思って書いてみました。あとは自己満足です。記事に書いた他にも様々なコンテストやオンサイトに出場し、それぞれで自分の考えに影響を与える事柄や競技プログラマーとの出会いがありました。ここに書いたものはごく一部に過ぎませんので、もしもさらに興味がある方がいれば、直接会ったときなどに気軽に聞いて頂けると喜んでお話します。

最後までお読み頂きありがとうございました。

*1:後述のアジア地区台湾regional除く

*2:高等専門学校。中学卒業後に入学し、基本的には5年間通う。

*3:submitはしていませんがサンプルが親切な問題だったのでおそらくACでした。つまり僕の初ACはこれです

*4:余談ですが、この時同じくB1だった怒髪さんと知り合いました。B1の3月にして「これは蟻本のNimに帰着できるのでは?」と発言する彼の姿が強く印象に残っており、ひっそり尊敬し続けています。

*5:コンテスト出場回数はよくわからず

*6:なぜわざわざこどふぉに出たのかは謎です。ちなみにその後2年半の間こどふぉに出ることは一度もありませんでした。

*7: 税率変更 ゆるすまじ……

*8:kenkooooさんと仲良く2完 :)

*9:AtCoderでの練習環境が整った影響で最近のRiPProはそうでもないような気がしますが、実際のところは僕はよく知りません。

*10:500円玉貯金 ゆるすまじ……

*11:交通費や宿泊費などは参加者負担です。幸いサークルへの助成金等を利用することができたので、僕達の場合大きな負担にはなりませんでした。

*12:一応補足しておくと、一つの大学から2チーム出ることは結構難しいので、多くの場合学内1位のチームのみがICPCに進出します( いくつかの強豪大学は例外 )。

*13:「今年は全チームが3完以上でした」というアナウンスを聞き、「もしも3完できていなかったら…」と震えていました

*14:奈良先端科学技術大学院大学

ICPC2017 国内予選 参加記

ゆらふなさん( @yurahuna )とらてあくん( @ratetion )と、「sparsely_populated_regions」というチーム名で参加しました。
チーム名は限界集落の英語表記*1で、口に出して読むと575っぽくなっているのがポイントです。
結果はABCDの4完 35位で、アジア地区にはなんとか進出できそうで一安心です。

国内予選以前

LiveArchiveなどの問題を使って3時間セットを5回ほど解いたり、模擬地区予選に参加したりしていました*2。また、ICPCの1週間前にはメンバー3人でDPC*3出場を兼ねた広島旅行に行って親睦を深めたりしていました(?)

コンテスト

他のNAISTチームとともに会議室を借りて出場しました。しょらーさんとめんふぃむさんが手伝いに来てくれたので、印刷物を運んでもらったりしました。以下コンテスト中の様子。


コンテスト開始直後はらてあくんとゆらふなさんがディスプレイでそれぞれA,B問題を読み、僕はテンプレートの写経。その後は印刷されたC問題が来るまで暇なのでらてあくんの横で一緒に読んでいた。解法を確認するとよさそうなので「よし任せた」と言ったあたりでC問題が届き、ひと目でめんどくさそうなオーラを感じ取る。

よく読むと制約に甘えて池のサイズの決め打ち全探索をやれば良いことがわかり紙コーディングを開始する。紙コーディングが終わった頃にはちょうどA,B問題が通っていたので交代。Bでは僕のsplit関数ライブラリが役立ったらしくて嬉しい。

Cを写経してちょっと直すとサンプルが通ったので提出してAC。3完時点で経過時間は43分だったので「おっわりといい順位かな」と思って順位表を見るとそれでも30位くらいだった。みんな早すぎる。

先にD問題に取り掛かってくれていた二人に合流すると、すでに重要な考察であるところの「min(N,M)の値は高々22、全探索とbitDPを組み合わせれば解ける」がすでに出ていた。念のため検証すると問題無さそうだったので、全探索側を僕がbitDP側をゆらふなさんという分担で実装を開始。

確か20分くらいでお互い書きあがったものの両者ともサンプルが合わない。タイプミス・初期化ミス・ループ変数ミス等々を30分ほどかけて修正してAC。この時点でも30位くらいで、流石にここから10人に抜かれることはないかなあと、とりあえず一安心していた。

らてあくんがE,F問題を読んでおいてくれたのでとりあえずE問題を聞く。なんとなく構文解析をやりたかった&なんとなく解けそう だったのでE問題に取り掛かることに決める。ゆらふなさんに考察を任せ、僕はひとまず構文解析パートを書いていた。式を全列挙して良さそうという事と列挙の方針を聞き全体の実装を開始したが、結局サンプルを通すまでには至らずコンテスト終了。

反省点

  • 他のチームのコードを見ていると、C問題の池の容量を評価する部分でかなり冗長なコードを書いてしまっていました。
  • Dのバグで時間をかなり浪費してしまったのが痛かったです。入力形式や変数にそれぞれの流儀があるので、2人で1つの問題を解くというのも考えものですね。
  • 僕達の方針だとEの実装が結構大変だったので、E問題を後回しにしてF,Gを解く決断をすべきだったかもしれません。

全体的に実装パートが酷く結構な時間を無駄にしてしまったので、うまくやればもう1問解けたのかなあという後悔の残る結果となりました。

さいごに

ICPC国内予選は何度出ても本当に緊張するのですが、アジア地区大会進出をかけて熱くなれる大好きなコンテストです。
僕は今年で引退なので最後の国内予選でしたが、アジア地区で悔いを残さないために チーム練習・考察&実装練習 を頑張っていきたいと思います!

*1:ほんまか?

*2:結果は19位でした

*3:ディスコプログラミングコンテスト@広島2017

プログラミングにおける「半開区間」

はじめに

プログラム中では、区間は 閉区間 や 半開区間 など様々な方法で扱うことができます。
僕は閉区間派でしたが、最近半開区間派に鞍替えしました。
これにあたって半開区間の特徴をまとめたのが本記事です。

大したことは書かれていないので、半開区間の ①区間の長さ ②区間の分割方法 ③区間の包含判定 ④区間の交差判定 ⑤区間の隣接判定 がパッと書ける人にとっては無用な記事となっています。

※なおここでは整数値によって表現される区間を対象とします。

半開区間とは

[a,b)で表される区間を左閉右開区間(左閉半開区間)と言い、
(a,b]で表される区間を左開右閉区間(右閉半開区間)と言います。
これらを合わせて半開区間と呼びます。
※角括弧と丸括弧の意味の違いの説明はここでは省略します

この記事では、競技プログラミングにおいてもよく利用されている[a,b)(左閉右開区間)について扱います。

記号の定義

本記事では区間(segment)を {S} と表し、添字は識別子を表します。
区間の情報は [l,r) で表し、区間 {S_i} の情報は [{l_i, r_i}) です。

特徴

区間の長さ

区間 {S} の長さは r - l と等しくなります。

区間の分割

区間 [l,r) を、c-1とcの間を境界として分割すると、[l,c) と [c,r) の2つの区間ができます。
(閉区間で同様の事を行うと、[l,r-1] -> [l,c-1]と[c,r-1] となり少しややこしいです。)
f:id:Yazaten:20170519214614p:plain


区間の包含関係

{ l_1 \leq l_2 } かつ { r2 \leq r_1 }のとき、{S_2}{S_1}に包含されています。

区間の交差判定

{ l_1 \leq l_2 < r_1 } または {l_2 \leq l_1 < r_2 } のとき、{S_1}{S_2} は交差しています。

ある2区間 {S_1}{S_2} が隣接しているかの判定

{ l_1 = r_2 } または { l_2 = r_1 } のとき、{S_1}{S_2} は隣接しています。


まとめ

半開区間は、区間の長さを調べたり区間を分割するときに便利です。
二分探索でも多くの場合半開区間を用いているので、このあたりをおさらいしておくと何かの役に立つかもしれません。

AOJ 2527 MLE

解法

そのままソートすると時間計算量O(NlogN)でTLE、空間計算量O(N)でMLEする。
そこで、乱数列の各要素の上位16bitをキーにしたバケットソートみたいなことをする。
k 番目の値を調べる部分では、値が小さいキーから順に辿っていく。
バケットソートの結果だけではちょうど K 番目の値が見つからないので、その後境界になっているバケットの中身だけをvectorに入れて普通にソートする。
x0=0のときがコーナーケースで、生成される乱数列の値は全て0となるため0を出力するようにしておく。

詳細はソースコード参照

RUPC2017参加記

RUPC2017の運営・作問・参加をしました

1日目

卒業式がRUPCと被っていたため早朝に大学へ移動した。
会場ではなぜかn_vipさんが保護者席にいて "学部長のありがたい話" の実況をしていてシュールだった。
卒業しながらコンテストを開催するのは初めてだったので緊張した。

卒業が済んだので15時頃にRUPC会場に到着。
omu君達のチームにスーツ姿で風船を運んで威圧する。


今回の問題セットは、最終防衛問題みたいなのはなく中難易度以上の問題が沢山あるという感じだったのですが、お楽しみいただけたでしょうか?

2日目

drafearさん、omuさんと、チーム「caffe」で参加した
drafearさんが解法を吐いてそれを実装する みたいなことをしていて、結局僕はB,E,F,K問題に関わった。

B: lower_boundとupper_boundでえい
E: 蟻本とか「ABC-D食塩水」とかで見たやつ omuさんが実装してくれた
F: drafearさんから「解は高々2」と言われると後はわかったので書く(例に漏れずバグった)
K: drafearさんから「SCCすると木になるので後はDPするだけ」と聞いて解く
さて、優秀な読者のみなさんならお気づきかと思いますが、SCCして出来るグラフは木ではなくDAGになります😫
木だと思い込んだ*1僕がメモ化をサボってTLEを大量生産している間にコンテストは終了


オンサイト2位もとい1位を取ったので*2嬉しくはあったのだけど、あまり解かれていなかったG,Jを解いたのはdrafearさんだったので、プロだなあという気持ちの方が強かった。

順位表を見るとなんか偽物がいた*3
プロが居たおかげでチームとしては勝ったけど、僕より偽物の方が強いんだよな……


3日目

btkさん、treeoneさんと、チーム「daisotsu」で参加した*4
主にA~C問題を片付けたりしていて、結局僕はA,B,C,(E,G)問題に関わった。
A: codefightsで見た
B: treeoneさんがバグで苦しんでいたので、紙に擬似コードを書いたりして一緒に通す
C: 列の端にある数字を得られればOK treeoneさんに託す
E: btkさんが「遅延セグ木で解けるけど貼りたくなさすぎる〜」とか言っていて、btkさんの考察を聞いてあれこれ言っていたらsetで区間を持つ解法を生やしてくれた
G: こういう問題文を読むのは苦手。LISか?みたいな考察をしてbtkさんが解法らしいものを思いついてくれたが、誤読があったので嘘だったらしい


コンテスト後にA~Eを自力で解いてみたら結構バグったので、B,D,Eあたりを実装してくれたチームメイトに感謝。
木の同型判定を学びたいのでFも解いておきたい。

おわりに

  • ブランクのせいか、実装力が落ちていて困った
  • 知り合いばかりとチームを組んでしまったが、せっかくなので初めましての人とも組めばよかった
  • 運営などをしていて春休みが消滅したので、今後はICPC国内予選に向けて精進したい

*1:無向グラフの2重辺連結成分分解結果が木になるので正しいと思い込んでしまった

*2:チーム「btklatte」はon hotel & on 卒業式という扱いとのこと

*3: 実は結構嬉しかったんだけどうまく反応できなかった(>_<)

*4:btkさんもちょうど少し前に卒業を済ませたところだったので

AtCoder上で過去に提出したソースコードをローカルに保存する

この記事は、Competitive Programming Advent Calendar 2016(その2)の9日目の記事です。


ACしたソースコードは削除してしまう運用をしていましたが、ふと過去に提出したソースコードをローカルに保存したくなったので、プログラムを書きました。
同じ気持ちになった人は是非ご利用下さい。


以下プログラムの簡単な仕様です

  • 本プログラムを実行した階層に、「(コンテスト名)-(問題ID)_(submitID).cpp」という名称のファイルが大量に作成されます。(例:"abc001-A_582728.cpp")
  • 「ME='Yazaten'」という文のYazatenを自分のAtCoder IDに変更して使用して下さい。
  • ABC,ARC以外のコンテストに提出したソースコードについては対応していません。
  • およそ1秒あたり1ソースコードを取得する設計になっているので、「保存するソースコード数 * 1秒」以上の実行時間がかかります。

著作権の話

ソースコード著作権が少し気になってAtCoderの規約と著作権法を雑に読みました。

結論だけ話すと、自分のソースコードを取得することは問題無さそうです。
他人のソースコードを取得することが違法かどうかはよくわからない*1ので、非推奨としておきます。
( 間違っていればご指摘いただけるとありがたいです )

ソースコード

  • 本プログラムはpythonで書かれています。
  • python 2.7.9で動作することを確認しています。
  • 適当に書いたので冗長かもしれませんが、ご容赦ください。
  • skht777さんの作成したAPI( 元プログラムの作者はYSRKENさん? )を利用しています。


参考文献


明日、10日目の記事の担当は nanTosaka2 さんと ark_golgo さんです。

*1:著作権物の複製にあたるかもしれない

色々なアルゴリズムで「殴る」

この記事は、Competitive Programming Advent Calendar 2016 の7日目の記事です。


あなたは、一部の競プロ勢の間で使われている「セグ木で殴る」という言葉をご存知でしょうか?

priority_queueを使えば良いところをセグ木で解いてみたり*1、累積和を使えば良いところをセグ木で解いてみたり*2するアレです。

この「セグ木で殴る」は、「考察すればもっとスマートに書けるがめんどくさいのでセグ木で解いた」といった意味であり、ややネガティブな言葉でもあります*3
しかし競技プログラミングに限定すれば、バグさえ出さなければスマートに書く必要はありません。速さが正義です。
そこで本記事では、セグ木以外での「殴り方」をいくつか紹介したいと思います。

強連結成分分解で「殴る」

強連結成分分解は蟻本にも載っているアルゴリズムで、有向グラフ上の強連結成分を圧縮してDAGにするアルゴリズムです(ざっくり)。
知名度はそれなりですが、使う機会はあまり多くありません*4


早速殴っていきましょう。
今回、この強連結成分分解で殴られる問題はこちらです。(問題のネタバレを含みます)
abc030.contest.atcoder.jp


この問題を説く過程では、頂点をたどることによってたどり着く閉路に含まれる頂点数を求める処理が必要になる場面があります。
f:id:Yazaten:20161207125512p:plain

スマートに実装するならば「有向グラフを1頂点づつたどってゆき、usedの頂点とぶつかったときの深さ - usedの頂点の深さ が閉路の大きさ が答え」みたいな感じで求める方法が考えられます。
しかし、このアルゴリズムを考えるのが面倒だったり*5バグが怖いので書きたくないという気持ちになるかもしれません。

そこで、強連結成分分解で殴ってみることにしましょう。


強連結成分分解を適用する過程で、ある頂点を含む強連結成分の大きさ をO(1)で知ることができる配列を得ることができます。
そこで、「頂点をたどっていき今いる頂点を含む強連結成分の大きさを調べる。大きさが2以上であればそこが最終的にたどり着く閉路であり、その大きさは前述の配列を使って容易に求まる。」といった手順で目的の処理を実現することができます。


実際に強連結成分分解で解いたソースコードへのリンクを以下に貼っておきます。
Submission #961082 - AtCoder Beginner Contest 030 | AtCoder


二重辺連結成分分解で殴る

二重辺連結成分分解は蟻本には載っていませんが、僕の記事を初めいくつかの解説記事があります。無向グラフ上の二重辺連結成分を圧縮するアルゴリズムです(ざっくり)。知名度は強連結成分分解以上に低く、使う機会はかなり少ないです*6

どんどん殴っていきましょう。
今回、この二重辺連結成分分解で殴られる問題はこちらです。(問題のネタバレを含みます)
utpc2014.contest.atcoder.jp


この問題を解く過程で、N頂点N辺の連結なグラフ*7の持つ閉路に含まれる頂点数を求める処理が必要になる場面があります。
f:id:Yazaten:20161207125524p:plain

スマートに実装するならば「根つき木にして深さを持ったDFSをし、usedの頂点にぶつかった時の深さ - usedの頂点の深さが閉路の大きさ が答え」みたいな感じで求める方法が考えられます。

しかしここでは二重辺連結成分分解で殴ってみることにしましょう。


二重辺連結成分分解を適用する過程で、各二重辺連結成分に含まれる頂点の数とその要素を得ることができます。
N頂点N辺の連結なグラフはちょうど1つの閉路を持ち、閉路は二重辺連結成分の一種です。
そのため、「頂点数 = 辺数 かつ 連結な有向グラフ」に1つだけ含まれる閉路のサイズを容易に知ることができます。


実際に二重辺連結成分分解で解いたソースコードへのリンクを以下に貼っておきます。
Submission #1015041 - 東京大学プログラミングコンテスト2014 | AtCoder


「殴る」ことによるメリット・デメリット

メリット

  • ライブラリを貼るだけで良いので実装量が減る
  • Twitterで「C問題は◯◯で殴った」とか言える

デメリット

  • 可読性が低くなる
  • ソースコード長が無駄に長くなる(冗長な部分が増える)
  • 計算量が増加する場合がある

まとめ

競技プログラミングでこういうことをすると微妙な顔をされてしまう可能性があります。用法用量を守って正しくご使用下さい。


明日、8日目の記事はskyaozoraさんの「競プロを初めて10年になるので振り返ります」とyosupotさんの記事(内緒と書いてあった…)です。

*1:ワカサギ釣り | Aizu Online Judge

*2:B: ドキドキデート大作戦高橋君 - AtCoder Regular Contest 045 | AtCoder

*3:個人の感想です

*4:個人の感想です

*5:プロなら一瞬で思いつくぞー!という指摘は恐らく正しいです。

*6:個人の感想です

*7:なもりグラフやよすぽグラフとも呼ばれる。木に辺を一本追加したグラフであり、ちょうど1つの閉路を必ず含む。