あったこといろいろ

ほぼ自分用備忘録です。

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

はじめに

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

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

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

半開区間とは

[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つの閉路を必ず含む。

橋・二重辺連結成分分解

この記事は、Competitive Programming Advent Calendar 2016の記事……ではなく、僕のAdCの記事を楽しむための予備知識として書かれた記事です。
ちなみに、僕の担当は明後日です。よろしくおねがいします。



グラフ上の「橋*1」となる辺を求め、これによりグラフを複数の「二重辺連結成分*2」に分解する方法を解説します。
補足を注釈に書いていたりするので、適宜参照して下さい。

アルゴリズム

前置き

橋は、imos法を用いた方法*3やlowlinkを使う方法*4で列挙することができ、橋を取り除いたグラフでDFSをすることで二重辺連結成分に分解できます。
一方ここでは、Spaghetti Sourceのコードに基づいた、DFSをしながら橋と二重辺連結成分をまとめて列挙する方法を解説します。

以下の説明では「DFS木」や「後退辺」といった用語の説明は省きます。
その辺りの知識が不安な場合、npcaの部誌(2014)のP25あたりを読むと良いと思います。(ちなみに、この部誌ではlowlinkを使った橋の列挙方法を解説しています。)

解説

与えられたグラフ上の適当な頂点からDFSを行い、DFS木を作成します。
この作業の途中に、辺(u,v)*5を辿った先がusedである場合、この辺は後退辺であり、頂点u〜頂点vは同じ二重辺連結成分であることがわかります*6
この処理をDFSをしながら繰り返すことで、二重辺連結成分を列挙できます。また、二重辺連結成分に含まれていない辺は全て橋となっているため、橋を列挙できます。
f:id:Yazaten:20160726190852p:plain
u(8,5)が後退辺であるため、頂点5,7,8は同じ二重辺連結成分であることがわかります。

実装

アルゴリズム」の章では大まかな動作を解説しました。ここでは、具体的な実装を解説します。

はじめに、使用するデータ構造についての解説を以下に示します。

変数名 説明
vector<int> order 各頂点に訪れた順番
stack<int> S 既に訪れた頂点のうち、まだどの二重辺連結成分にも割り振られていない頂点の集合
vector<bool> inS 集合Sに各頂点が含まれているかどうかの情報
stack<int> roots 各二重辺連結成分を、DFS木の部分木として見た時の根の集合


適当な頂点を根としてDFSを開始します。
以下の解説では、現在訪れている頂点をcurと呼び、一つ前に訪れた頂点をprevと呼びます。

新しい頂点を訪れる度に以下の動作を行います。

  • order[cur]にorder[prev]+1を代入することで、その頂点に訪れた順番を記録
  • 集合Sにcurを追加し、curを追加したことをinSに記録
  • rootsにcurを追加


使おうとした辺(cur,to)が後退辺である場合(つまり「to!=prev && inS[to]」の場合 )、以下の動作を行います。

  • cur〜toまでの頂点(ただしtoは含まない)をrootsから捨てる


roots.top()の頂点より葉側の頂点の訪問が終了した場合(つまり「cur==roots.top()」の場合)、以下の動作を行います。
なお説明のため、roots.top()の頂点を以下ではnodeと呼びます。

  • nodeと、DFS木上でnodeより1つだけ根側にある頂点を橋として記録する(nodeが根である場合はなにもしない)
  • 一度目にnodeに訪問してから、nodeに戻ってくるまでに訪問した頂点をすべて同じ連結成分分解として記録する。(S.top()がnodeで無い間、topの値を記録し続けることで実現できる。)
  • rootsのtopの格納されている頂点をpopする


上記の動作を行うことによって最終的に、bridge関数の引数であるbrgに橋のリストが、each_bccに二重連結成分のリストが、cmpにある頂点がどの二重連結成分に含まれているかの情報が格納される。


*1:グラフから取り除いた時に連結成分が増える辺

*2:任意の辺を取り除いても連結であるような部分グラフ

*3:二重辺連結成分分解 ライブラリ - ゆらのふなびと

*4:二重辺連結成分分解 - コードを短く書く人のブログ

*5:DFS中木上で根に近い方の頂点をvとする

*6:DFS木上の任意の後退辺(u,v)を考えると、vは必ずuの親となります。

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

10/15~16 に行われたICPCつくば大会に、チームmiyazoy72で参加しました。


最終成績は45チーム中42位と、非常に悔しい結果となりました。

チーム練習としては会津さんがvirtual arenaで開いているコンテストに何度か出場していました。
LiveArchiveが壊れていて何を提出してもWAになった回が一番面白かったです。
575.cppはいつも強かったです。

1日目

受付開始30分前頃に会場に到着しました。
受付まではNAISTチーム、電通大チーム、会津大チームの方々とお話をしたりしていました。

周りを見渡すとコンテストの順位表でよく見かける方々ばかりで、このときから既に緊張していました。


プラクティスセッションでは用意していたemacsの設定を記述しましたが、思うように動きませんでした。
余った時間で一人一問を一応AC。
キーボードについては、配列は普段からUSなので問題はなかったものの、少し硬いかなぁという感想でした。
結局僕はあまり実装を担当しなかったので特に問題はありませんでしたが。


会場から筑波大学までは距離があるらしく、バスに乗って移動しました。
歓迎会では他の参加者と交流していました。

ホテルへ移動後は、emacsの設定を調べて、正常に動作する確認をしてすぐ寝ました。


2日目

朝は6時頃に起きました 朝ごはんが美味しかったです。
これはチームメイトとのslackでのやりとりです。
f:id:Yazaten:20161028130849p:plain

会場へはNAISTチームと一緒に移動しました。
会場到着後、コンテスト開始までは特に何もしていませんでした。


コンテスト開始直後はemacs等の設定を記述しました。
前日夜の確認で問題点はわかっていた(フォルダ名を".emacs.d"とするところを".emacs"にしていた)ので気をつけて書きました。
A問題はすぐに書けそうとのことで設定記述中に交代していたので、この時点で1ACでした。

C問題の読解が終わっていたので聞きました。
ある倉庫にたどり着ける荷物の集合は区間で表せることには気づいたのですが、緊張からか考察がなかなか進まず。
嘘解法を noy72 に伝えてしまいWAをもらったりしていました。

ここでB問題が簡単そうと聞きそちらに合流、全探索で適切にやればよさそう。
lazymii に実装をお願いしましたが、サンプルが合わないらしく混乱していたため紙の上で解法を確認。
2時間ほど経ってなんとかAC。時間がかかりすぎてしまった…

C問題は、合流した lazymii が解法を思いついてくれたのでおまかせしました。
A~CまでACするまでに3時間以上かかっており、いつもの調子が出ていないどころの騒ぎじゃないなと思っていました。

ここで選択肢としてはDかEのどちらかを解くというところでしたが、四則演算構文解析やったことなしだったのでDに専念することにしました。
見た瞬間ローリングハッシュだと思ったのですが、多くのチームがWAを出していたり、夏合宿でロリハ問題を軽々とACしていた shora_kujira16 さんのいるチームも手間取っていたため別解法を考えていました。

結局最後まで何も思いつかなかったので、終了間際にハッシュ値を配列に格納しておくO(N^2 logN)のロリハ解をダメ元で提出しました。
配列に格納する都合上MODを10^6にしていたため当然ハッシュが衝突してWAが返ってきました。


冒頭に書いたとおり、結果は 42位 / 45チーム でした。
問題文はほとんどチームメイトが読んでくれたため、その点はほとんど障害になりませんでした。
敗因はハッシュの理解の浅さと緊張だったと思っています。
チームメイトの協力に見合った活躍ができなかった…



コンテスト終了後は、1時間ほど余ったお菓子やドリンクに群がっていました。
コンテストは 8:45~13:45 の5時間開催だったので、とてもお腹が空きました。

その後の懇親会では協賛企業のブースが並んでおり賑やかでした。
司会の方が「あなた方のプログラミングスキルは非常に優秀で…」みたいなことを言っていて、「僕はそうでもないですよ」と思ったりしていました。


解散後は、n_vipさんが主催して下さった二次会に参加しました。
いくつかのチームは海外regionにも参加するらしく、海外チームの話などをしていました。
こういった話はなかなか聞けないので非常に面白かったです。


感想

  • 今まではICPCのアジア地区大会に "進出すること" を1つの目標として競プロを続けて来ましたが、出場チームの人々を見たり会場の空気を感じて、進出は通過点であることを体感しました。
  • ICPCには一応大学の代表として出場しているわけで、悔しいという気持ちとともに恥ずかしいという気持ちになったのが新鮮でした。
  • ICPCに出場できるのは来年で最後になります。NAISTからアジア地区に進出し、今年のNAISTチーム(chasen_no_sato)の取った26位という順位を超えられるよう、今から精進を続けていきます。