2015年 競技プログラミングの進捗

今年の競技プログラミングの進捗です。

ICPC

チーム l-_-..-_-..-_-lJJJJJJ として参加。
国内予選37位。アジア地区予選進出ならず。
今年は自分自身の実力もメンバーの実力も去年より上だったので今年こそはアジア地区予選に行けると思っていただけに悔しかった。
ICPCは来年で引退なので、来年こそはアジア地区予選に出場したいです。

TopCoder

rating: 1448 -> 1524 (+76)
rating(highest): -> 1448 -> 1580 (+132)

div1easy が安定してきて黄色にはなれたものの、この先維持できるかどうか不安なところ。
今年のratingの上げ幅が微妙だったのと、来年でICPC最後なので難しい目標ではあるけども highest 1800 と黄色安定を目指したい。

Codeforces

rating: unrated -> 1849
rating(highest): unrated -> 1913

今年の9月からcodeforcesにも出るようになりました。
来年はd2Dまで安定できる実力をつけてd1に定着したい。

matplotlibで棒グラフ

matplotlib を使って棒グラフを描こうとしたら罠にはまったので忘れないうちに。

欲しかったグラフ

書かなければいけなかったコード

import matplotlib.pyplot as plt
import numpy as np
import random

width=0.4
x = [i for i in range(10)]
sftx = [i+width for i in x]
l = ["one", "two", "three", "four", "five",
	"six", "seven", "eight", "nine", "ten"]

y1 = [random.random() * 8e12 for i in range(10)]
y2 = [random.random() * 8e9  for i in range(10)]

fig, ax = plt.subplots()

ax2 = ax.twinx()
p1 = ax.bar(x,y1,width,label="hoge")
ax.set_ylim(0,1e13)
p2 = ax2.bar(sftx,y2,width,color="red",label="fuga")
ax2.set_ylim(0,1e10)
ax.set_xticks(sftx)
ax.set_xticklabels(l,rotation = 30)
p = [p1,p2]
ax.legend(p,[i.get_label() for i in p])
plt.show()

欲しくなかったグラフひとつめ。

凡例がひとつしか表示されてません。legendを単純に呼ぶだけではいけません。このへんを参考にしてコードを描こうとすると罠に落ちる。
pylab_examples example code: barchart_demo.py — Matplotlib 1.5.0 documentation
subplots_axes_and_figures example code: fahrenheit_celsius_scales.py — Matplotlib 1.5.0 documentation

書いてしまったコード

import matplotlib.pyplot as plt
import numpy as np
import random

width=0.4
x = [i for i in range(10)]
sftx = [i+width for i in x]
l = ["one", "two", "three", "four", "five",
	"six", "seven", "eight", "nine", "ten"]

y1 = [random.random() * 8e12 for i in range(10)]
y2 = [random.random() * 8e9  for i in range(10)]

fig, ax = plt.subplots()

ax2 = ax.twinx()
ax.bar(x,y1,width,label="hoge")
ax.set_ylim(0,1e13)
ax2.bar(sftx,y2,width,color="red",label="fuga")
ax2.set_ylim(0,1e10)
ax.set_xticks(sftx)
ax.set_xticklabels(l,rotation = 30)
ax.legend()
plt.show()

欲しくなかったグラフふたつめ

x軸に表示させてるそれぞれの棒につけた名前が斜めに表示されてない。この辺を参考にしてコードを描こうとすると罠に落ちる。
ticks_and_spines example code: ticklabels_demo_rotation.py — Matplotlib 1.5.0 documentation
axes_grid example code: demo_parasite_axes2.py — Matplotlib 1.5.0 documentation

書いてしまったコードその二

import matplotlib.pyplot as plt
import numpy as np
import random
from mpl_toolkits.axes_grid1 import host_subplot
import mpl_toolkits.axisartist as AA

width=0.4
x = [i for i in range(10)]
sftx = [i+width for i in x]
l = ["one", "two", "three", "four", "five",
	"six", "seven", "eight", "nine", "ten"]

y1 = [random.random() * 8e12 for i in range(10)]
y2 = [random.random() * 8e9  for i in range(10)]

host = host_subplot(111,axes_class=AA.Axes)

ax2 = host.twinx()
p1 = host.bar(x,y1,width,label="hoge")
host.set_ylim(0,1e13)
p2 = ax2.bar(sftx,y2,width,color="red",label="fuga")
ax2.set_ylim(0,1e10)
host.set_xticks(sftx)
host.set_xticklabels(l,rotation = 30)
p = [p1,p2]
host.legend(p,[i.get_label() for i in p])
plt.show()

欲しくなかったグラフみっつめ。

グラフの右肩に乗っかって欲しい1e10が左肩に乗っかっている。この辺を参考にしようとして、「これでいいやろ～」とかヘラヘラしながら書くとこんなコードを書いてしまう。
axes_grid example code: demo_parasite_axes2.py — Matplotlib 1.5.0 documentation

書いてしまったゴミ

import matplotlib.pyplot as plt
import numpy as np
import random
from mpl_toolkits.axes_grid1 import host_subplot
import mpl_toolkits.axisartist as AA

width=0.4
x = [i for i in range(10)]
sftx = [i+width for i in x]
l = ["one", "two", "three", "four", "five",
	"six", "seven", "eight", "nine", "ten"]

y1 = [random.random() * 8e12 for i in range(10)]
y2 = [random.random() * 8e9  for i in range(10)]

host = host_subplot(111)

ax2 = host.twinx()
p1 = host.bar(x,y1,width,label="hoge")
host.set_ylim(0,1e13)
p2 = ax2.bar(sftx,y2,width,color="red",label="fuga")
ax2.set_ylim(0,1e10)
host.set_xticks(sftx)
host.set_xticklabels(l,rotation = 30)
p = [p1,p2]
host.legend(p,[i.get_label() for i in p])
plt.show()

CODE FESTIVAL 2015 参加記

要約

長文・乱文になりそうなので要約を用意しました。

本戦41位。こどふぇ楽しかった。来年もあったら出たい。

記事の大部分は、どのコンテンツで何を考えてたかをだらだら書くだけです。

目次

CODE FESTIVAL 本戦以前

れじすたー

予選Aまで残り10日メールが来たので参加登録した。今年から前泊の基準が東京駅まで片道4時間になってる。早朝の時間帯に出発すると片道4時間ナントカ分掛かるものの、11時に会場に到着することのできる移動方法で最短のものは3時間40分程度らしい。4時間かかると言い張れなくはなかったが、4時間かからないと言って登録。

予選A

予選開始前、予選落ちの恐怖からガクガク震える。心拍数もだいぶ上がってた。予選Aの数日前のこどふぉで典型どころか定型のbitDP問を落としていたこともあり、予選落ちの不安が高まっていた。
結果は全完(45:48)で53位。自分にしては好成績である。しばらく勝ててなかった大学の同期たちに勝てて嬉しかった。
全完して予選通過確定したところで順位表の観測をはじめる。問題のレベルがレベルとはいえ、全完がこんなに出るとは思ってなかった。全完がボーダーが有り得ると思った。後日、全完した人は全員通過したらしいことがわかる。難易度調整すごい。

予選B

こどふぉd2onlyから予選Bへと休憩なしの2連戦。こどふぉで3問解いて撃墜まで済ませたあと、こどふぉ終了と同時に予選Bが始まる。D問題読んで「愚直に塗れば部分点もらえるよなー」と思って制約を見て絶望する。( 競プロサークルの一年生を3完+部分点の早解きで通そうと思ってたので、制約見てかなり厳しそうだと思った ) 5分ぐらい考えて区間で管理してマージすれば計算量的にも間に合うと気づく、辛い実装をやるだけの辛い問題だと分かって辛い気分になりながら実装した。100:18で全完して49位。同期や同じ大学の人より微妙に低い順位取ってて辛い気分になった。
予選Bでは3完部分点で遅くなければ一回目の連絡で通っていたらしい。辞退者が出たりして最終的に3完+部分点までは全員通ったらしく、素晴らしい難易度調整だった。

CODE FESTIVAL 前日まで

ゴルフ企画「短縮王」の問題が公開されて、元々手をつける気はなかったのだけど、twitter上でやってる人が多かったので手をつけた。1バイトを必死に削るのが面白く、ゴルフの魅力の一端に触れたような気がした。

CODE FESTIVAL 前日

研究室のゼミが長引いて研究室を出る時間が遅くなり、当日出発にしておいて正解だったと思った。荷造りをして眠ろうとしたが、眠れなかったのでコードを削ろうとした。削れたのは睡眠時間だけだった。

CODE FESTIVAL 1日目

移動

4:30起床。とれた睡眠時間は2時間程度。身支度をし、始発電車で空港へ向かう。自分が乗る予定だった飛行機が機材に不具合が見つかったため25分遅延する。某社のお金の力もあってANAの飛行機を取っていたのが良かった。これがLCCだったらもっと遅延してたんじゃないのかな。

9時頃羽田に到着。預けた荷物を受け取ってモノレールに乗るが、10時品川には間に合わないことに気づく。メールを送ってバスの乗車予定をキャンセルする。「当日出発にして正解だったな」とか言ってたのは嘘だった。品川駅には10時ちょっと過ぎに到着。さて、歩くかと言って会場の場所を確認したところで品川駅が会場の最寄りでないことに気づく。この時点で携帯の電池が切れたので、準備してあった路線図と地図を使って会場への経路を調べて移動する。JAG夏合宿の教訓が生きた。

飛行機乗り遅れそうになって得た教訓は、 ・新宿駅を経由する時は1時間迷うことを想定して行動しなさい ・東京で行動するときは複数の鉄道会社の路線図が一枚に描かれているようなものを持ち歩いたほうが良い ・携帯はいざという時電池がやばい（←これは知ってた） という三つ。

— 136_紺青 (@konjo_p) September 14, 2015

10時45分に受付に到着した。なんとか間に合った。

受付 - 本戦前

受付を済ませてTシャツとリストバンドを受け取る。Tシャツ配ってる場所の近くにしょらーさん(@shora_kujira16)が居たのでお話する。ツカサさん(@tsukasa_diary)も居たのでお話しする。JAGの夏合宿以来である。kyos(@kyos1704)さんとかYazaten(@Yazaten)さんとかとお話したのも本戦前だったっけな。

席番は136。斜め前の隣ぐらいにzerokugi(@zerokugi)さんが居た。あとから気づいたのだけど、斜め前がhogloid(@hogloid)さんで自分が座ってた島にプロが2人も居た。

今年のパーカーラインが5完であると言われる。パーカーはばら撒くが、問題の難易度落とす気は無いということか。5完なら余裕かなーとか思いつつ、去年はなんとか5完したものの、1問詰まると5完危うい感じだったことを思い出しパーカー取れない可能性もあるなと思う。

本戦

こどふぇがこどふぉる。45分の遅延。略称がCF同士だし、妥当なのだろうか。延期にはこどふぉで慣れたので何の問題も無い。安心感さえある。ネットワークの不調が原因での遅延だったが、去年の備えをGIZMODOの記事で見ていたので大きな問題にはならないだろうと安心していた。

A,B,Cはやるだけ。
D問題は一瞬セグ木か何かかと思ったが、累積和で解けることに気づく。まあやるだけ。
E問題は考察つめたら数えるだけになったのでAC。

!	0か非ゼロかを反転する。これが登場すると入力の数が何だったかという情報と符号が何だったかという情報が落ちる。
-	符号を反転する。入力の数の情報は保存される。

ということに気づけば、'!'の数と入力された文字列で最初に登場する'-'の数を数えればいいだけと分かる。

E問題参考

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main() {
	string s;
	int a, b;
	bool flg = true;
	cin >> s;
	a = b = 0;
	for(int i = 0; i < s.size(); i++) {
		if(s[i] == '-') {
			a += flg;
		}
		if(s[i] == '!') {
			b++;
			flg = false;
		}
	}
 
	cout << (a%2 ? "-" : "" ) << (b%2 ? "!" : (b?"!!":"")) << endl;
}

この時点でパーカーが確定し、気が楽になる。

とりあえずF問題を解きに行く。
難しい。6問目以降はさすがにこのレベルの問題を並べてくるか。
しばらく6問目を考えた後、順位表を見に行くとFとGのACがほぼ半々であることが分かり、G問題を読みに行く。林作って掛けるだけだけだと思って実装を始めるが、実装の途中で誤読があることが分かり、残り時間を使ってF問題を考えることを決める。

• 無限の鍵盤だし、隣にしか移動できないし、ループっぽいグラフは書くよね。
• 入力は頂点の次数だね。
• オイラー閉路が作れるかどうか判定すればいいね。
• ある場所の辺の数を決め打ちすると、できるグラフの形が分かるし上手くいくよね。

まで考察が詰まったので、張る辺の数で二分探できないか考えてみる方針が立つ。

• フロー流す要領で辺の数を伝えていけば上手く判定できるんじゃね？

と思ったので実装して、オイラーグラフであるかどうかの判定部分をごにょごにょしたら通った。6完。
あとから考えたらこれ二分探必要なさそうなことに気づく。でも通れば勝ちなのでナントカ。

F問題参考

#include <iostream>
#include <vector>
using namespace std;
 
typedef long long ll;
 
int main() {
	vector<ll> C;
	C.resize(7);
	for(int i = 0; i < C.size(); i++) cin >> C[i];
	C[0]--;
	ll l, r, m;
	r = C[0]*2;
	l = 0;
	bool res = false;
	while(l <= r) {
		m = (l+r)/2;
		ll use = m;
		bool flg = true;
		int zero_cnt = m?0:1;
		for(int i = 1; i < C.size(); i++) {
			ll tmp;
			tmp = C[i] * 2 - use;
			if(tmp < 0)  flg = false;
			if(use > 0 && tmp == 0) zero_cnt++;
			use = tmp;
		}
 
		if(flg && m+use==C[0]*2 && zero_cnt <= 1) {
//				cout << m << " " << use << endl;
//				cout << m+use << "," << C[0]*2 << endl;
			res = true;
			break;
		}
		if(m+use>C[0]*2)
			r = m-1;
		else
			l = m+1;
	}
 
	cout << (res ? "YES" : "NO") << endl;
}

残り30分無いくらいで、残りの問題の考察詰めて実装を行うことはほぼ無理だと思ったので、本戦後の解説に向けて読んでいなかった問題を読んだ。

コンテスト結果は6完158:53で40位タイだった。提出IDが自分のほうが遅かったらしく、実質41位。1秒以下の差で負けるのは悔しい。とは言っても実力的に40位台はなかなか取れないので嬉しかった。睡眠時間足りてなくて眠い感じで出場したためにいつものSRMっぽさが出たのが良かったか。

このレベルの問題を解けたことが多くはないので、そろそろ壁を一枚超えることができるのではないかという自信につながった。

本戦後

しょらーさんの近くに行ったら知ってる人が集まってたので本戦の問題についておしゃべりをする。

解説

遅延の影響だろうか、あって無いような解説だった。スライド読もう。

夕食

寿司・肉巻きおにぎり・生春雨・ジェラートを選択。ピザは何処。

LayCurseさんトークライブ

LayCurseさんのトークライブを聞きに行く。が、睡眠不足が祟って半分ぐらいのところから記憶が飛んでる。折角LayCurseさん(自称レアキャラ)のお話を聞ける機会だったのに勿体無かった。

エキシビジョン

りんごさんがエキシビジョンに出ると聞いて、りんごさんのコーディング画面の前に張り付いてた。コーディングしていた時間よりも問題の画面を開いていた時間のほうが長かったように感じる。デバッグも怪しいところを出力して確認するといったようなことはせず、ソースコードと問題文の間を行ったり来たりしているようだった。凄いんだけど全然参考にならない。

チームリレーの顔合わせ

hogloidさんチームだった。名前を奪われた人(@hadrori)の提案により、チーム名がFCCPCに決定。本戦順位で同率40位だったうどんさん(@kw_udon_)とも同じチームだった。顔合わせでtsuburin(@tsubu_taiyaki)さんに話しかけてもらったよ、やったね(自分から声を掛けるのはなかなかハードルが高い)。前日に顔合わせて、少ししゃべりやすくなる制度いいなーと思った。

ホテルにて短縮王

会場からも短縮王A問題に提出していたのだけど、WAが出て通らない。こんな単純な問題が通らないなんておかしい！と思ってたら、出力する文字列を間違えていただけだった。

後日談

短縮王のA問題。事前公開では"Pass"と"Fall"の出力だったのに、本番では"Pass"と"Fail"の出力に変更されてたのは意地悪だなーと思いました。

— 136_紺青 (@konjo_p) November 16, 2015

@konjo_p それ多分変更じゃなくてフォントの問題…

— くりんぺっと (@climpet) November 16, 2015

@climpet 本当ですね。。。事前公開の問題文のほうではちゃんとFailになってる。。。

— 136_紺青 (@konjo_p) November 16, 2015

CODE FESTIVAL 2日目

会場まで

起床成功。が、眠い。チェックアウトし、バスに乗って会場へ。

あさプロ

今年はhard(1st - 30th), middle(31st - 100th), easy(101st - 200th)の3クラスだった。hardとmiddleの境界は妥当だと思うけども、middleとeasyの境界は昨年どおりでよかったのではないだろうか。
あさプロmiddleに参加。今年のコンテストページに asa! の文字列が無かったのは残念。A,B,Cをやるだけやるだけと言いながら解く。が、C問題でバグにはまってやるだけ感を出せずに辛い思いをした。3完69:57で46位。参加者のレベルが抑えられてるのに前日の本戦より悪い順位というダメな結果だった。
コンテスト終了後にmiddle D (hard B) について言及したツイートでヒストグラムの奴と言ってるのを見かけて頭いいなーと思った。

chokudaiさんトークライブ

chokudaiさんがお話しするというので聴きに行く。chokudaiさんにクソリプを送って許される貴重な機会だったのでここぞとばかりにクソリプを送る。競プロ界で最も有名な素数は1e9+7と1e9+9はちょっと言い過ぎではないだろうか。2と3だと思うんだけど。問題に対する典型的なアプローチのお話とか聞けて面白かった。

昼ごはん

西京焼き弁当を選択。りんごさんトークライブを聞きに行きたかったので急いで詰め込もうとしたがTLEした。

りんごさんトークライブ

人だかりができていて遠目に見ることしかできなかった。目が悪くて回答者の顔が分からない。。。。

書道コーディング

再帰版のgcdとlcmを書いた。1行でシンプルに書けて気に入ってる。

チームリレー

前日顔合わせがあったので、極端に緊張することは無かった。問題の担当は順位順で、順位がいい感じに離れてる人とペアを組んで方針に誤りが無いかを確認してやることになった。自分のペアはyumaさん。H問題の担当になったが、自分の実力でこの難易度の問題が解けるのかどうか不安になる。

ペアを組んだ人が円周率のあの問題を引き当てた。円周率30桁ぐらいなら一応暗記しているものの、不安があるのでその他の方針を考える。が、結局「産医師異国に向こう産後厄無く産婦みやしろに虫散々闇に鳴く頃にや」と有名な語呂合わせを唱えて円周率を書き出す。

自分の担当のH問題を読む。「色が9色... 盤面の大きさが最大で500 * 500 ... 」あれ、これやばい奴では？と思い出力するものを見て問題の解釈が終わったところで数分考える。考えた結果dijkstraやるだけだと思ったが、結構不安だったので2-3人のメンバーと方針を確認する。dijkstraで大丈夫そうだという結論になった。

他の人の問題の方針を聞いたりしながらワイワイやる。

自分のコーディングの時間が廻ってきたが、10分程度消費してしまう。しかもRE吐いてる。配列外参照してるところも無さそうだし、謎。するとresize(H)とすべきところをresize(W)としていると指摘が飛んだので、そこを修正してACした。

その後うどんさんがI通して、yumaさんが円周率の問題通して、hogloidさんがJ問題を通したところで、チームメンバー全員で残ったG問題のデバッグに取り組む。あれじゃないかこれじゃないかとバグがありそうな箇所の指摘が飛ぶ。最後はhogloidさんがredcoderの撃墜力を見せ付けて全完した。

自分がペアプロ好きなほうなのでかなり楽しめた。前日にはチームメンバーが分かっているというのも良かった。

ハッピーアワー

1時間ぐらい時間を取ってしゃべれる時間。と思ってたら表彰もこの枠でやるのね。直前にコンテストがあるとコンテストの問題をネタにおしゃべりできるのでコミュ障の多いコミュニティ的には良かった。

閉会式

まとめ映像流して写真撮って解散。ドローンでの写真撮影だった。あと、カメラマンさんが写真撮ってた。「心をオープンソース」で吹き出す競技プログラマたち。撮影後に心がオープンソースになった場合のライセンスについての雑談がなされる。このあたりは競技プログラマとはいえどプログラマのコミュニティか。

移動

面白かったなーと思いながら帰る。解散が始まったのが17:30頃だったので、帰りの飛行機の19:55には間に合うなーと思いつつ、迷ったら最悪帰れなくなるからと思い遠方特権を発動してblue_jamさん(@blue_jam)と一緒に会場を出る。会場の出口にトイレ5個さん(@chako0407)が居た。

会場に来る時にバスに乗らなかった(というより乗れなかった)おかげで駅までは迷わずに着く。駅のホームドアの高さに圧倒される(福岡の地下鉄のホームドアは胸ぐらいの高さ)。麻布十番で乗り換えて、さらに浜松町で乗り換えてからモノレールだと思っていたが、どういうわけか麻布十番で下りたら都営地下鉄から京急線へ乗り換えなしで行けてそれが羽田空港までつながっていた。で、ちょっとしたトラブル。

昨日帰り道で僕がやらかしたこと一覧 ・一回出た駅のホームにもう一回戻ろうとする ・国内線ターミナルを国際線ターミナルと勘違いし折り返してしまう ・Dijkstraもろくに書けないのかと後輩に煽られる ・焼き鯖寿司を買い忘れる

— 頭がない大学院生 (@blue_jam) November 16, 2015

福岡へ帰る人々とご飯を食べて、荷物を預けたら出発時刻ぎりぎりになってしまった。遠方特権発動しといてよかった。

福岡空港に着くと荷物の受け取り台のところでclimpet(@climpet)さんと会った。ショートコーディングの話になったので、自分の提出したコードを見せると「あと4バイトは縮みます」と言われた。exit(0)の代わりにグローバル変数に0を代入することでexit statusを0にできることがあるとのこと。試してみたら本当に通った。

これ(89B)が

i,a,b;main(n){for(;~scanf("%d",&n);b+=2*a-n+1)a+=n*!~i--;exit(!puts(b>1?"Pass":"Fail"));}

こう(85B)

i,a,b;main(n){for(;~scanf("%d",&n);b+=2*a-n+1)a+=n*!~i--;a=!puts(b>1?"Pass":"Fail");}

まとめ

CODE FESTIVAL 楽しかった。運営の皆様ありがとうございました。また来年あれば参加したいです。

にぶたんについて

二分探索が話題になってたので二分探について書いてみる。

kujira16.hateblo.jp

この記事を見て、二分探の形は人それぞれだと感じた。
自分の二分探はこんな感じです。

    #include <iostream>
    #include <vector>
    using namespace std;
     
    // find を超える最初の要素のインデックスを返す. vは昇順にソートされている.
    int my_upper_bound(vector<int> & v, int find) {
    	int right, left;
    	int res = -1; // 見つからない場合の戻り値
    	left = 0; right = (int)v.size()-1;
    	while(left <= right) {
    		int middle = (left + right) / 2;
     
    		if(find < v[middle]) {
    			// v[middle] は find を超える要素である. (答えの区間)
    			res = middle;
    			right = middle-1;
    		}
    		else {
    			// v[middle] は find 以下の要素である.
    			left = middle+1;
    		}
    	}
    	return res;
    }
     
    int main() {
    	// 引数の生成
    	vector<int> v;
    	for(int i = 0; i < 100; i++) {
    		v.push_back(i);
    	}
    	int res, find;
    	cin >> find;
     
    	res = my_upper_bound(v,find);
    	cout << "my_upper_bound(v," << find << ") returned : " << res << endl;
    	cout << "v[" << res << "] : " << v[res] << endl;
    	return 0;
    }

こういう感じの区間があって、

二分探をはじめる。
もし、middleの指してる要素が答えでなければ、middleの右のほうにleftを移動させる。

もし、middleの指してる要素が答えであれば、答えを仮の変数に格納して(ここ重要)middleの左のほうにrightを移動させる。

区間を狭めながら探索するだけ。left <= rightの間繰り返せばいい。

繰り返しごとに区間が狭まることは明らかな気がする。
二分探書いて無限ループにはまることが多かったのでこの書き方気に入ってます。

あと、for文使ってナントカ回まわす二分探も思いついたので書いて貼っておきます。
実装してたらバグらせた。辛かった。たぶんこんな感じのはず。

#include <iostream>
#include <vector>
using namespace std;

int my_upper_bound(vector<int> & v, int find) {
	int res = -1;
	int tmp = 0, i = 0;
	// 探索する範囲のサイズの二進表現で1の立っている最上位のビットを探索.
	while((int)v.size() > (1 << (i+1))-1) i++;
	// 区間を狭めながら二分探
	for(; i >= 0; i--) {
		if(((tmp | (1 << i)) < v.size())) {
			// middle の代わりが tmp | (1 << i) となる.
			if(find < v[tmp | (1 << i)]) {
				// 条件が成立しているならば答えを仮置き.
				// さらに左の区間を探索するので,tmpはいじらない.
				res = tmp | (1 << i);
			}
			else {
				// そうでないなら,右の区間を探索するようにする.
				tmp |= 1 << i;
			}
		}
	}
	// for文の最後の繰り返しで, 最下位ビットに1を立てて条件が満たされたケース対策.
	return (find < v[tmp]) ? tmp : res;
}

int main() {
	vector<int> v;
	for(int i = 0; i < 100; i++) {
		v.push_back(i);
	}
	int res, find;
	cin >> find;

	res = my_upper_bound(v,find);
	cout << "my_upper_bound(v," << find << ") returned : " << res << endl;
	cout << "v[" << res << "] : " << v[res] << endl;
	return 0;
}

CODE FESTIVAL 2015 予選A 予想問題

昨夜、会場までの移動時間が4時間かかるかからないがTLで話題になってたので、予選AのDぐらいにこういう問題来るんでないかなーと。

問題

tkhs君はCODE FESTIVALへの参加を考えている。CODE FESTIVALでは自宅から東京駅へ行くまでの所要時間がT分以上であると前泊の費用を主催者であるR社が負担してくれる。tkhs君は万全の状態でコンテストに臨むために前泊したいのだが、自宅から東京駅まで行くのにT分以上かかりそうもない。そこでtkhs君は歩く速さを調整することで自宅から東京駅に行くまでにかかる時間が最短でT分になるように調整するようにした。
tkhs君は電車または徒歩で移動する。歩く速さは体力の範囲内で自由に決められるが、CODE FESTIVALの参加規約上、東京駅までの経路は時間が最短になるような経路を選ばなくてはならない。電車はtkhs君が乗ると直ちに出発し、遅延は無いものとする。また、電車の乗降にかかる時間は無視してよい。

入力

N T E W V
ta_1 tb_1 tt_1
...
ta_E tb_E tt_E
wa_1 wb_1 wd_1
...
wa_W wb_W wd_W

一行目に自宅、東京駅、及び経由地点の合計の数 N、前泊が可能となる移動時間 T分、 電車の区間数 E、 徒歩で行動できる区関数 W、tkhs君の歩く最速の速さ V[m/min.] が与えられる。
各地点には0からN-1の番号が振られている。
自宅は番号0, 東京駅は番号 N-1の地点である。
続くT行に、電車で移動できる区間を表す情報が与えられる。ta_i, tb_i間 は電車で移動でき、その所要時間はtt_i分である。
続くW行に、徒歩で移動できる区間を表す情報が与えられる。wa_i, wb_i間 は徒歩で移動でき、その移動距離はwd_iメートルである。

出力

自宅から東京駅までの移動に最短でちょうどT分かかるような歩く速さ v [m/min.]を一行に出力せよ。
そのような v が存在しない場合、またはそのようなvが複数存在する場合は -1 を出力せよ。
期待される出力との差が10^{-6}以下であれば正解とみなされる。

入力例

9 30 6 5 600
1 2 3
2 4 10
3 5 15
3 6 8
6 8 20
7 8 2
0 1 200
1 3 10000
3 4 3000
4 7 500
5 8 500

こんなんです

出力例

作る気力なかった

解法

にぶたん+dijkstraで解けるんでないかなーと思ってる。もっといい方法があると厳しめな制約つけれそう。

2015年 JAG夏合宿参加記

JAG 合宿参加記

JAG合宿に参加してきたので参加記を。タイポとか不正確な情報はそのうち修正します。気が向いたら何か追記するかもね。

合宿参加前

去年の夏合宿終わった後、「来年は黄色になってここに来てやる」「来年は国内通ってから来てやる」とか言ってた。 今年も国内予選落ちたし、黄色になったものの三日で青に落ちたりしたので何一つ達成できてない感じがあって辛かった。

合宿申し込んで参加確定する前の段階で投機的に飛行機のチケットを取った。おかげで今年は夜行バスで来るとかいう羽目にはならなかった。

1日目

懇親会で懇親できない勢だった。

2日目

地震で目が覚めた。寝坊しなくてラッキー。 臨時チーム編成所で筑波大logicmachineのzerokugiさんが作問で抜けた穴にマッチングされた。A,Bは通してもらった。Cを担当した。逆からやるだけだった。
アルゴリズム貰ってDも実装したけど、バグらせてバグらせて申し訳なかった。不甲斐ないじゃ済まない感じのアレ。 エッジ張ってる部分でバグってたのを指摘してもらったけど1ケースWAが出てた。巡回セールス問題解くbitDPみたいにDFSしたら通らないらしい。free solving sessionでBFSに書き直したら通った。つらい。

3日目

臨時チーム編成所で豊橋技科大 GO TO THE FUTURE の穴にマッチングされた。コンテスト開始と同時にJavaの環境を入れるところからスタート。
Bから読んだらやるだけだったので実装した。 H簡単らしいと聞いて読んだら誤読して二分マッチングっぽいと言ってしまう(実際マッチングだけどフローじゃ間に合わなさそう)。読み直したら微妙に問題の難易度上がったけど二部探やるだけで通るっぽいことにすぐ気づけたから実装した。バグにはまりまくって辛い思いをした。 15分毎ぐらいに「書けそうな問題ありますかー」と声は書けたものの、PC占領してて申し訳ない感じだった。 別の問題の概要説明うけてて「こどふぇのあれだー」ってなったものの、Hで時間消費しすぎてそれどころじゃなかった。

4日目

臨時チーム編成所で名工大splas_boomerangの穴にマッチングされた。
「エディタvimじゃないですよね？」「vimです」「まじかー」というやり取りの後、cygwinにvimを入れてもらうところからスタート。vim入れたら同時にgccやらなんやらもアップデートされたらしく、Eclipseが動かなくなったとのことで、急遽自分の環境でコンテスト参加することに。「emacsあれば大丈夫」とのことだったけど、自分のPCがMacでCtrlとAltの位置が違っていて大丈夫そうじゃなかった。
Aを通してもらってる間に先の問題を残りのメンバーで読み進める。D見るだけ見て「やばい」と直感する。先の方まで読んでみたけど、読んだ中ではBが一番とけそうな問題だった。実際ポインタ貼って回すだけだった。B実装開始時点で上位陣のB提出がなくて不安だったけども、上位陣がBをACしだして安心した。Bを無事ACしたら、Fの実装が始まった。他の問題読んでる間にメンバーがFのFA取ってた。プロ。この間にGの方針が固まってた。問題読んでたらGも通ってた。Dやばいと思っていたけど上位陣が通してたのでこれを考え出す。FのFA取った人はJを貪欲にやるだけっぽいと言ってJをやり始める(のちに誤読が判明)。自分たちが考えてたDは上位陣にとっては簡単だったけど、基礎知識足りてないと無理な問題だったらしい。結局4完。10位で合宿中の最高順位だった。

全体通して

去年もそうだったけど、強い人と会うといい刺激になっていい。コンテスト出る度に頭の悪さ自覚させられるけど、オンサイトだとさらに頭の悪さ自覚させられるのでとてもいい。3つのコンテストすべてで足を引っ張った感じになって辛かった。チームを組んでくださった皆様ごめんなさい。そしてありがとうございました。来年は国内予選通過してないと合宿参加資格がないので意地でも通過する。夏合宿div2の話が帰りがけにあったけど、境目がTCのレートで1800ぐらいになるのかなー。
JAGの皆様、参加者の皆様、ありがとうございました。

おまけ

地震

オリンピックセンターで地震にあうというレアな経験をした。地震あると放送入るのねー。

競プロ勢とおしゃべり

積極的にお喋りできなかった。受け答えは大抵「ｱｯ､ﾊｲ…」。twitterでフォローしてる方とかいるんだけど、去年の合宿やこどふぇで知り合った人とか、それなりに絡んでる人とか、知ってる人としか話せなかった。twitterとかで積極的に絡んで行かないとああいう場に行って辛さを感じると思った。

SRM

このSRMは合宿中だし出れないなーと思ってたら、同部屋の人が出るというのでsoftbankが売ってる人権に課金して出場した。貪欲で落ちるケース見つけられずに貪欲したらゼロ完だった。合宿中にレート下がった。つらい。

ARC

ARC出てたらBバグらせた。大抵のテストケースでACしてたけど、間に合うコードでTLE出てて思考停止。バグが取れる前に回線が無くなった。バグの原因はオーバーフロー。そんなに大きな数こないだろと思ってintにしてた変数に1e5近く入ってた。C++のシフトを論理シフトだと勘違いしてて負の数が来て無限ループになってTLEとかいう可能性を見落としてた。

新宿駅被害者の会

合宿終わって神保町にでも遊びに行くかなーと思ったら新宿駅の中で迷った。危うく帰りの飛行機を逃すところだった。この時ほど「飛行機よ、遅延していてくれ」と思うことは後にも先にもないのではないだろうか。 新宿から神保町に行くには都営地下鉄の新宿線に乗ればいいという知識は持ち合わせてたので、新宿線を求めてさまよった。新宿駅西口を。都営地下鉄の駅に行けば案内が受けられると思って大江戸線の案内に従って駅へ。「ここからじゃ新宿線の駅まで10分ぐらいかかるから、このまま大江戸線で春日まで行って三田線に乗り換えて行きなさい」とのこと。 神保町から新宿に戻ってきて東口のコインロッカーに預けた荷物を取りに行くため、再び新宿駅をさまよった。南口の改札から見える案内には「こちらが東口」って出てるのに、いざ改札出ると東口への案内が一切無いのが罠。案内を求めてさまよった。 山手線で浜松町に行きたかったのだけど、＊＊方面という案内に浜松町方面とか羽田空港方面とかいう案内がない。改札くぐったら路線図もそう簡単には見当たらなかった。路線図を求めてさまよった。 結局空港には出発の25分前に着いた。20分前までに搭乗手続きを済ませる必要があったので間に合ったと思ったら自動チェックイン機でチェックインできない。有人カウンターまでお越しくださいの表示。有人カウンターに人が並んでいたが、どうにか21分前までには搭乗手続きを開始できた。保安検査場を通過したら搭乗口へダッシュ。どうにか飛行機に間に合った。神保町出発が飛行機の出発時刻の2時間前で大分余裕を持たせたはずなのにどうしてこうなった。研究室やプロコンサークルへのお土産を買い損ねた。お土産は前もって購入しましょう。

合宿来る時も新宿駅でちょっと迷ってた。JRの駅に貼ってある路線図みて参宮橋駅に行くにはどの路線に乗ればいいのかと必死になって参宮橋を探していた。小田急線はJRの路線じゃないとか余所者は知らないよ。。。

これ以上被害者を増やさぬために

飛行機乗り遅れそうになって得た教訓は、 ・新宿駅を経由する時は1時間迷うことを想定して行動しなさい ・東京で行動するときは複数の鉄道会社の路線図が一枚に描かれているようなものを持ち歩いたほうが良い ・携帯はいざという時電池がやばい（←これは知ってた） という三つ。

— 紺青 (@konjo_p) 2015, 9月 14

飛行機

始めてスカイマークの飛行機に乗った。某社事案のときはANAなりJALなり使えるのだけど、ANAは学生の自己負担で乗るにはきつい金額。ANAと比べると操縦が荒い感じはあった。羽田を飛び去るとき、機首を斜め上に向けて上昇されるという今までにしたことのない経験をした。きつい角度で上昇する時間も長かった気がする。薄雲越しに見た東京の夜景が綺麗だった。

合宿後

プロコン練習したい欲高まってるけど、目の前に積まれた論文に圧倒されてる。英語読みはじめたら1時間で睡魔に襲われるの本当にアレ。睡魔に負けてすいません。参加記書いてるのも現実逃避のゲフンゲフン

TopCoderで黄色くなれました

TopCoderのalgorithm部門で黄色くなれたので歓喜の報告記事。

TopCoderに登録してから2年と3ヶ月。青色になってから1年。ようやくyellow coderになることができました。TCOR2Aがratedになって本当に良かったです。

以前の記事に書いた今年の目標のうち、ARC3完・TopCoderAlgorithm部門でyellowになるという目標を達成できました。あとは今年度のICPCで2チーム目通過を決めたら立てた目標全達成ですね。がんばります。