Distributed Code Jam 2016 について

はじめに

Distributed Code Jam R1に参加して、環境構築とか環境構築とか辛かった人を散見したので記事を書くことにした。

Distributed Code Jam とは

Distributed Code Jam (DCJ) とは、Google Code Jam (GCJ) に併設された分散処理のコンテストです。ざっくり言うと、100並列で競技プログラミングをやるコンテスト。2016年はGCJのRound2進出者に参加権がありました。

環境について

普段の競技プログラミングとは異なるところもあるので、思いついたところのまとめ。Mac/C++で参加しました。

並列化用ライブラリ

MPIっぽい関数を実装したライブラリがコンテストの運営から配られます。コンテスタントはそれを使ってプログラムを実装します。基本型の送受信用キューへの追加/読み出しと、送受信用キューの内容の送受信程度でしょうか。ライブラリの詳しい仕様を把握しないまま書いたら書けてしまったので詳しい仕様は言えない。

言語

C++かJavaの二択。

入出力仕様

入力は関数を呼んで取得する。問題ごとに入力用の関数が用意されていて、入力用関数の仕様は問題文中で与えられる。problem_ name.h というヘッダファイルに実装されているので、それをインクルードする必要がある。ヘッダファイルはソースと同じディレクトリの中に置いてね。sample-inputをくれるヘッダファイルは問題文の下のほうにあるリンクからダウンロードできました。答えの出力はどこか一つのノードが標準出力に吐けばよい。

環境構築

Distributed Guideに書かれてある。

Linux || Mac

LinuxかMacがメイン環境の人は環境構築がしやすいから幸せだ。DCJ 用のテスト用ツールを Distributed Guide に書かれてあるリンクから落としてくる。.tar.bz になってるので、 コマンドラインで

tar jxvf dcj.tar.bz

とかやって展開する。あとはGoをインストールして、

cd src/parunner/
go build
cp parunner ../../executable/

とやると環境構築おわり。

config.jsonにどのコンパイラを使うかとかを指定するようになってるので、「コンパイラみつかんねーよ」と怒られたりしたらconfig.jsonを書き換えるといいかもしれない。sample-configsの中にいくつか設定例があったので、自分で書き換える必要が出てくることはないかも。テストを行うには、Distributed Guide に書かれてあるコマンドを打てばよい。

problem=prblem_name
srcfile=${problem}.cpp
${DCJ_UNPACK_DIR}/dcj.sh build --source=$srcfile

problem=prblem_name
runnable=${problem}
${DCJ_UNPACK_DIR}/dcj.sh run --executable=./${runnable} --nodes=100 --output=all

とか書いてスクリプトにまとめとくと便利。

Windows

Cygwinで環境構築しようとしたら失敗した。辛い。READMEとか読んだら「MinGWでやれｗ」って書かれてたから、MinGWでやったら上手く行くんじゃないかな。

提出

提出はGCJとは異なりソースコードのみを提出する。例によってsmallとlargeのデータセットがある。smallを提出すると、コンテストサイト側でテストが行われ2分後に結果が分かる。提出後の2分間は結果も分からないし、再提出することもできない。largeはsmallが通った場合に提出でき、コンテスト終了まで何度でも再提出できる。largeの採点はコンテスト終了後に行われる。

practiceについて

DCJは本番前にGCJR2進出者を対象にしてDCJ前にオンラインで練習会が開かれる。今年の場合、練習会の日時・URLはメールで告知され、コンテストスケジュールには載ってなかった。事前練習を行いたいひとはこまめなメールの確認を。

問題難易度

極端に難しい問題は出なかった印象。R2進出者であれば、シングルノード版の解法を書くことにはまず困らない。samllはシングルノードでも解ける程度の制約、largeは並列化しないと無理ゲーな制約。という印象をうけた。Distributedと名がつくだけあり、シングルノードでも解ける制約のsmallの配点がものすごく低い。

SRM501 div2 hard 1000pts : FoxAverageSequence 解説

はじめに

SRM501 div2 1000pts を解いたら計算量の落とし方がいい感じだった && 多くの人が自分よりひとつ悪いオーダーで通してて悔しかった ので解説記事を書いてみる

問題概要

美しい整数列Aは以下の制約を満たす。

• 要素数40以下
• 
• 
• となるiは存在しない

整数列seqが与えられる。seqの各項は-1以上40以下である。seqの-1の項を0以上40以下の任意の数に変えることが出来るとき、seqから得られる美しい整数列の総数を求めよ。

解法

dp(i,j,k,l)を、i個目までの和がj、i個目の要素がkで、i個目の要素がi-1個目の要素から{ l=0 : 減少していない, l=1 : 減少している}として、

• 
• 

に従って更新すればとりあえず答えは求まる。
但し、dp(i,j,k,l)はseqのi個目の要素が-1で無くseqのi個目の要素がkでない場合0である。また、k * i ≤ j - kを満たさない場合もdp(i,j,k,l)=0とする。

これを愚直に計算しようとすると、時間計算量はseqの要素数nとseqの各要素が取りうる値の最大値mを用いてとなり微妙に怪しい*1。

ということで、よく使う例の方法で計算量を落としにかかかる。

同じ要領で、2番目の式

を変形すると

となる。

これでdp表の更新にかかるオーダーが減り、全体のオーダーは無事に落ちたのだが、seqのi個目の要素が-1で無い場合のdp表の更新を上の漸化式に従って行うと間違う。なぜならば、を計算する場合を例にとれば、 のつもりで書いている が、k-1とseqのi+1番目の要素が異なる場合、 になるためである。

seqのi番目の要素が-1で無い場合、dp(i,j,k,l)はseqのi番目の要素とkが一致した場合には

• 
• 

を使って更新し、そうでない場合は0にすればよい。各(i,j,l)の組に対しての更新が回と、の更新が回しか呼ばれないのだから、DP全体の計算量はに収まる。

実装

バグの箇所がなかなか見つからずにつらかった。書き直す気はない。ぺたり。

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <utility>
#include <cassert>
using namespace std;

#define all(x) ((x).begin()),((x).end())
#define pb push_back
#define mkp make_pair
#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;

const int mod = 1e9+7;
int dp[50][50*50][50][2];
vector<int> S;

int solve(int i, int j, int k, int l) {
	if(i < 0 || j < 0 || j > 40*40|| k < 0 || k > 40)
		return 0;
	if(dp[i][j][k][l] + 1)
		return dp[i][j][k][l];
	if(k * i > j - k)
		return dp[i][j][k][l] = 0;

	if(S[i] + 1) {
		if(S[i] != k)
			return dp[i][j][k][l] = 0;
		dp[i][j][k][l] = 0;
		for(int k_ = k + l; 0 <= k_ && k_ <= 40; k_ = k_ + (l == 0 ? -1 : 1)) {
			dp[i][j][k][l] = (dp[i][j][k][l] + solve(i-1,j-k,k_,0)) % mod;
			if(l == 0)
				dp[i][j][k][l] = (dp[i][j][k][l] + solve(i-1,j-k,k_,1)) % mod;
		}
	}
	else {
		dp[i][j][k][l] = 0;
		if(l == 0) {
			for(int l_ = 0; l_ < 2; l_++)
				dp[i][j][k][l] = (dp[i][j][k][l] + solve(i-1,j-k,k,l_)) % mod;
			dp[i][j][k][l] = (dp[i][j][k][l] + solve(i,j-1,k-1,0)) % mod;
		}
		else {
			dp[i][j][k][l] = (dp[i][j][k][l] + solve(i-1,j-k,k+1,0)) % mod;
			dp[i][j][k][l] = (dp[i][j][k][l] + solve(i,j+1,k+1,1)) % mod;
		}
	}
	return dp[i][j][k][l];
}

class FoxAverageSequence {
	public:
	int theCount(vector <int> seq) {
		S = seq;
		for(int i = 0; i < 50; i++)
			for(int j = 0; j < 50*50; j++)
				for(int k = 0; k < 50; k++)
					dp[i][j][k][0] = dp[i][j][k][1] = -1;
		for(int i = 0; i < 50*50; i++)
			for(int j = 0; j < 50; j++)
				dp[0][i][j][0] = dp[0][i][j][1] = 0;
		if(S[0] == -1) {
			for(int i = 0; i <= 40; i++) {
				dp[0][i][i][0] = 1;
			}
		}
		else
			dp[0][S[0]][S[0]][0] = 1;

		ll res = 0;
		for(int i = 0; i <= 40 * 40; i++) {
			for(int j = 0; j <= 40; j++) {
				for(int k = 0; k < 2; k++) {
					res = (res + solve(seq.size()-1,i,j,k)) % mod;
				}
			}
		}
		/*
		cout << endl;
		for(int i = 0; i < 5; i++) {
			for(int j = 0; j < 20; j++) {
				for(int k = 0; k < 50; k++) {
					cout << dp[i][j][k][0] << "," << dp[i][j][k][1] << " ";
				}
				cout << endl;
			}
			cout << endl;
		}
		// */
		return res;
	}
};

感想

解で解いた人がTLEせずにACしてるのが悔しかった*2。計算量の落とし方としては良くある方法*3だが、seqのi番目の要素が-1でないときにループを回してdp表を更新しても全体的な計算量が悪くならないという点がお洒落だと思った。

*1:通るらしいんだなぁ。。。これが。

*2:40^5 が大体 1e8 なので落ちても良さそう

*3:和をdp表のどっかから持ってきて計算量を落とす方法

SRM356 div2 medium 500pts : AverageProblem 解説

はじめに

SRM356 div2 500pts を部内の練習で解いたところ、面白い問題だった && 人々が辛そうにしてた && 日本語の解説記事が見つからなかったので解説記事を書いてみることにした。

問題概要

0 以上 10 以下の範囲の整数で評価する、評価項目が 1 つ以上あるアンケートを 1 つ 以上とった。各アンケート毎に、そのアンケートの評価項目毎の評価の平均を小数第4位で切り捨てたものが与えられる。アンケートに回答した回答者の人数としてありうる人数の最小値を求めよ。

• 1 ≤ アンケート数 ≤ 50
• 1 ≤ アンケート毎の項目数 ≤ 50

解法

アンケートの回答者を1人から順に調べ、その人数でアンケートを回答したとき、入力として与えられた平均となるような回答の方法があるかどうかを調べればよい。アンケートの項目ごとにどのような判定を行うべきかを解説する。

判定法

アンケートの回答者を人、各人のアンケート項目への評価をとすると、アンケートの評価の平均は、

入力として与えられる平均は小数点以下3桁まででそれ以下の値は切り捨てられている。切り捨てられた値をとして、と表せる。 上の式は

と変形でき、右辺を整数にできるか否かを判定する問題となる*1。今回の場合、左辺の値が具体的に何になるかを考慮する必要は無い。右辺を整数にするためには、入力として与えられる平均が表現できる最小の値が*2、アンケートの参加人数が人(定数)であったとき、半開区間に整数があればよい。がの範囲の値を取るためである。

計算量

アンケートの数を、アンケートの項目数を、与えられる平均が表現できる最小の値をとすると、時間計算量は

実装

上で書いたことを実装すればよい。誤差対策として入力として与えれれる値を1000倍して持っておくとよい。整数であれば剰余演算子を用いれるので、判定を行う部分の実装も楽になる。

#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <sstream>
#include <list>
#include <deque>
using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<long,long> pll;

class AverageProblem {
	public:
	int numberOfParticipants(vector <string> marks) {
		vector<int> ave;
		
		// 入力の受け取り部
		for(int i = 0; i < marks.size(); i++) {
			stringstream sstr(marks[i]);
			string s;
			while(sstr >> s) {
				// 入力を1000倍して, ave に追加する
				int a = 0;
				for(int j = 0; j < s.size(); j++) {
					if(s[j] != '.') {
						a *= 10;
						a += s[j] - '0';
					}
				}
				ave.push_back(a);
			}
		}

		// resはアンケートに答えた人の人数の候補
		int res = 1;
		// このループは1000回を超えて回ることはない
		while(1) {
			bool flg = true;
			for(int i = 0; i < ave.size() && flg; i++) {
				// diff は ave[i] * res 以上の最小の整数との差
				int diff = (1000 - (ave[i] * res) % 1000) % 1000;

				if(diff < res) // 条件成立
					;
				else
					flg = false; // 条件不成立
			}

			// ave のすべての要素に対して条件が成立していれば, その res が答え
			if(flg)
				return res;
			// そうでなければresを増やしてまた調べる
			res++;
		}
	}
};

感想

素直な問題で解いていて面白かった。計算量の見積もりや、アンケートの回答者がN人のとき入力として与えられた平均にできるか否かの判定など、div2med(500pts)の問題としては難しいように感じた。この難易度なら最近のdiv1easy(250pts)でも通用するのではないだろうか。切り捨てた値を適当な文字で表して式変形を進めるという考えに至れれば解け、行う式変形も分母を払う程度で難しくないため、その発想に至れるかどうかが勝負の分かれ目のよう。

無視した値を適当な文字で表すというアイデアに関しては、例えば電気系であれば抵抗の誤差を適当な変数として表して、最終的にどの程度誤差が現れるかを調べるなどの応用が利くので押さえておきたい。

*1:右辺が整数になりさえすれば, 左辺は右辺と一致するように選ぶことができる

*2:うまく表現できてる気がしないが、つまりはの精度のこと。今回は0.001

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;
}