2017-12-10

競技プログラミングの裏技！？　誰が解いたかの情報から問題の傾向は予想できるか？

ネタ

adventar.org
もうちょっといいネーミングは無かったのでしょうか。

おことわり

今回の記事にデータ源として登場する人は、新AtCoderのコンテストに20回以上参加した人のうち、だいたいレートが2700以上とかの人だけです。

赤にいかないうちは、典型も解けていないという証拠なのでどんな問題がでても文句を言わずに解きましょう
— rng_58 (@rng_58) 2017年10月12日

APIとかの使い方がわからないので、手作業で集められる範囲で許してください。

はじめに

ある程度プログラミングコンテストに出ていると、限界を感じます。具体的には典型を全部把握していて過去に見たことがあるような問題ならゼロ時間で解けるのに、ある程度典型から外れた瞬間全く解けなくなるというやつです。AGCやCode JamのRound 3以降で顕著です*1。
だいたいそこからできることというのは、爆速でコーディングを上げる能力と、ズルです。ただしAGCにおいてはコーディング量が元から少ないので、爆速でコーディングして変わる時間がほぼありません。困りました。残された道はズルです。

ズルと言ってもやってはいけないズルとそうでないズル、あとグレーゾーンなズルがあります。グレーゾーンなズルは白黒はっきりさせたくないのでここでは割愛します。やってはいけないズルというのは、他の人と解法を共有する・サブ垢を作ってACしたものだけを送ることでペナルティを解消する・ジャッジキューをつまらせて他の人を妨害して順位を上げる、などです。やってもいいズルというのは、戦略の中に収まるものから順に、証明しないで正しいと思う・順位表を見て解いている人の集合から問題ジャンルを予想する・定数倍改善・input解析(この二つは最近結構難しいです)・嘘だとわかっているがどうせ落とすデータはないだろうと思って提出する・OEISを見る・問題名やキーワードを検索し、同じ(部分)問題を探す、とかでしょうか。

嘘解法対策などは、昔に比べたらどこでもある程度対策されていると思われます。しかしながら未だに変なオーダーで解いたり、TLEした1ケースはどうせ○○だからあらかじめこのケースだけ埋め込んで置けばOKとか、変な解き方をすることは十分可能です。現に僕はAtCoderでよくtesterをしているのですが(これは言ってもいいよね)、tester中に思いついた変な解法を出すことで、「じゃあこういうケースを足してこれを落とそう」とか「問題設定をちょっと変えてOEISに出てこないようにしよう」といった改善がされることも多いです。

OEISについてだけは少し触れておきましょう。OEISは、使い方に慣れてないと見落としが多いかもしれません。たとえば、そのまま実験した結果だと検索しても出てこないけど2^nで割ったら出てくるとか、(2^n)(n!)で割ったら出てくるとかはよくあります。2変数の数列(さすがに(i≤j)となる(i,j)のペアにしか定義されないものがほとんどです)も実はOEISに相当数入っています。いろいろ割ったり足したり引いたり掛けたり差分を取ったり2変数のものを1次元に押しつぶしたりして、いろいろ検索を掛けてみることはとても大事です。

それでは本題に入りましょう。

本題

過去の「Aさんが問題Bを解けたかどうか」データから、特徴を見つけていきましょう。統計に弱いので*2、変な方法でもお許しください。生データは欲しい人がいたらあげます。

使ったもの

AGC001~019とMujin, Code Festivalの予選二年分の各問題に対し、AtCoderのレート上位で20回以上コンテストに参加した人が「開始1時間以内に解いた」「1時間経ってから解いた」「解けなかった」に分類したデータ
欠測値があるデータにおいて主成分分析するRのライブラリ
時間

結果の鑑賞

とりあえず鑑賞してください。

データシートの様子

f:id:tozangezan:20171209165032p:plain

PCA 1軸/2軸

f:id:tozangezan:20171209165252p:plain

さすがにわかると思いますが1軸はだいたい問題の難度に対応していて、これを見ることは今回の趣旨ではない上、問題についた配点をみればいいだけの話なので、この軸は無視しましょう。

PCA 2軸/3軸

f:id:tozangezan:20171210002122p:plain

よくわからん... 一部やたらと遠くに位置していることがわかると思いますが、なぜだかわかりません(antaさんはわかる気がする)。不思議ですねえ。
不安定感というか、独特の解き方になっている人が外側にいるのかもしれません。この人たちが解いているかどうかはあまり参考にできないということでしょうかね。

PCA 3軸/4軸

f:id:tozangezan:20171209165751p:plain

何か特徴があるのかないのか、よくわかりません。問題のほうの外れ値も調べてみればわかると思いますが、別に変な問題とは思えないものばかりでした。

クラスタリング人

PCAで出てきたうち2~6軸でWard法を使いました。こういうことって統計的に正しい操作なのかなあ

f:id:tozangezan:20171209165912p:plain

わりかしこれは、僕が順位表を眺めるときに使う戦略(この人が解いてたから自分も解けるはず)に近い気がします。真ん中の僕がいるあたりが低配点・典型系の安定性が高い人で、右側の人が高配点か非典型に強い感じですかねえ。左側の人たちはそれぞれの距離がかなりありますが、それもなんとなく納得いきます。

クラスタリング問題

同様のことを問題についてしました。

f:id:tozangezan:20171209170355p:plain

ここで注目して欲しいのは、複数回writerをやった人の回が、別に近い場所にいるわけではないということです。若干DEGwer回とsemiexp回がそれぞれの中でまとまっているようにも見えるのですが、気のせいの範囲だと思います。

参考 AGCを2回以上開いた人
sugim48: 2, 4, 6, 8, 16
DEGwer: 3, 9, 15
yutaka1999: 10, 14
semiexp: 11, 17
maroonrk: 13, 18

まとめ

仮説1. 「誰が」解いているのかを見る価値はあるだろう

僕のフィーリングでしかなく根拠は特にありませんがなんか変なことしたらきちんとした数値として出てくるかもしれません。上の結果だけでも、例えばクラスタリングの木で遠く離れた人が解いていても特に気にしない、とかには使えそうです。
現に個々人の「知識量」とか「実装の速度」とかを知ってると、この人が解いたから変な知識ゲーではない、とか、この人が一瞬で解いたから実装が少ない、とかはありそうです。なんどもコンテストに出ることで世界中の多くの人の問題の解き方データベースを貯めることにより、競プロ力も上がるかもしれません。これ以上書くと順位表非公開コンテストとか増えそうだからこれくらいにしておこう。

仮説2. writerと参加者の相性というのは、思っているほど大きくはない？ writerによりけりという可能性もある

writer によりけりという説を推していきます。少なくとも僕はDEGwerセットが苦手だと感じているし、semiexpセットとかsnukeセットとかは得意だと思います。
それに、明確にwriterが偏った問題ジャンルを出すこともあります。AGCでない例を挙げますが、tozangezanというwriterが難問枠で数え上げ以外を出したことがあったでしょうか。あったら教えてください。

おわりに

いかにも即席感溢れるAdvent Calendar記事なのは、3日後に控えた今年読んだ一番好きな論文2017 Advent Calendar 2017 - Adventar にも参加予定でこっちばっかり真面目にやってるからです。許してください。3日後に各記事はこれよりずっと中身がある記事だと思うので是非とも読んでくれたらと思います。投票とかあったら投票協力してね！(クズ)

データ

やっぱデータ置いとこ→ advent calendar - Google スプレッドシート
このレート帯でAGC皆勤賞が居ないのは、面白いかもしれません。

*1:TopCoderもTCOのR2,R3以降はそうかもしれません。少なくともSRMのMediumまではパターン系問題がごまんとあります。

*2:生態学やってて統計に弱いのはいかんでしょ

2017-11-04

DDCC 2017 決勝

Contest

ブログを最近書かなさすぎで変な広告まで登場する有様なので、渋々記事を書く。

A

まあこれは良いでしょう。

int main(){
	int a;scanf("%d",&a);
	int A=0;
	int B=0;
	for(int i=-100;i<100;i+=a){
		for(int j=-100;j<100;j+=a){
			if(i*i+j*j<=10000&&(i+a)*(i+a)+j*j<=10000&&i*i+(j+a)*(j+a)<=10000&&(i+a)*(i+a)+(j+a)*(j+a)<=10000)A++;
		}
	}
	for(int i=-150;i<150;i+=a){
		for(int j=-150;j<150;j+=a){
			if(i*i+j*j<=22500&&(i+a)*(i+a)+j*j<=22500&&i*i+(j+a)*(j+a)<=22500&&(i+a)*(i+a)+(j+a)*(j+a)<=22500)B++;
		}
	}
	
	printf("%d %d\n",A,B);
}

B

よく考えて解いてないのですが、制約から素因数分解ができないとわかるので、GCDとLCMに収まると思えばこのくらいしか選択肢がありません。

long long p[110000];
long long gcd(long long a,long long b){
	while(b){
		a%=b;
		swap(a,b);
	}return a;
}
int main(){
	int a;
	long long b;
	scanf("%d%lld",&a,&b);
	for(int i=0;i<a;i++)scanf("%lld",p+i);
	long long ret=1;
	for(int i=0;i<a;i++){
		long long g=gcd(b,p[i]);
		ret=ret/gcd(ret,g)*g;
	}
	printf("%lld\n",ret);
}

C

これについて何も書かないとこの記事の存在意義がないので、これについては何か書きます。

もし辺を編集することが全くできないのなら、この問題は簡単で、1回DFSをするだけで良いです。(ある頂点から始めて、今までにたどった重みの和を持ちながら辺をたどっていきます。辺の行く先がすでに通ったことがある頂点だったら、その頂点までの重みの和と今回の和が同じかどうかをチェックします。全部同じだったら全部の閉路について和が0です。)
辺を編集する場合ですが、基本的に編集する代わりにその辺を見なければいいです(全部の頂点に和が計算できていれば、そこの辺のコストは差で計算できます)。ただ、変なたどり方(毎回頂点1からDFSするとか)をすると、その辺が存在しないことで到達不可能な頂点が出てきてしまったりしてまずいので、必ずその見ない辺の行き先からDFSをスタートする必要があります。(行き先からDFSをスタートすると全頂点に値がつけられるというのは、強連結性のおかげです。)

さて、一番本質ですが、この同じ行き先の辺を消すパターン全てを1回にまとめて判定することができます。というのも、別に辺を消す処理が頂点までの和の値とかに影響を与えることはないので、実際にたどってみて「この辺が存在するとマズイ！」って時だけ消したことにすればいいからです。
で、消す辺がどれかとかが重要なのではなく、消す必要がある辺が1個以下であることが大事で、各頂点からDFSをしていき、消すべき辺が1個以下なことが1回でもあったらYESです。そうでなければNOです。

下の実装ではよく整理していないせいで逆辺を辿っていますが、上に書いた解法と何ら変わりありません。辺の向きを全部逆にしただけだと思います。

vector<pair<int,int> > g[310];
vector<pair<int,int> > rev[310];
long long deg[310];
int v[310];
int T;
bool dame=false;
int cnt=0;
void dfs(int a){
	v[a]=1;
	for(int i=0;i<rev[a].size();i++){
		int to=rev[a][i].first;
		if(v[to]){
			if(to!=T&&deg[a]+rev[a][i].second!=deg[to])dame=true;
			else if(deg[a]+rev[a][i].second!=deg[to])cnt++;
			continue;
		}
		deg[to]=deg[a]+rev[a][i].second;
		dfs(to);
	}
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q,r;
		scanf("%d%d%d",&p,&q,&r);p--;q--;
		g[p].push_back(make_pair(q,r));
		rev[q].push_back(make_pair(p,r));
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++)deg[j]=v[j]=0;
		T=i;
		dame=false;
		cnt=0;
		dfs(i);
		if(!dame&&cnt<=1){
			printf("Yes\n");return 0;
		}
	//	printf("\n");
	}
	printf("No\n");
}

まとめ

まあこんなんで3位で10万円分のパソコンが買えるというのは不思議だと思っているのですが、後から振り返ってみるとCの思考の分量というのは決してやるだけ、無ということはなくて、ただやるべきことが瞬時に見えていた感じがします。Div1Easyみたいな難しくないものを高速で解くのは昔から得意なんですが、それが如実に結果に反映される問題セットでしたね。
Dみたいなのは日本人はみんな苦手でかつ難易度を過小評価されがちな問題なので、セットとしての解かれなさもよく分かります。

それより、何か10万円強くらいのパソコンでおすすめのものがあったら教えてください。切実。

2017-07-24

todo

memo

hogloidの個人的良問リスト - hogloidのブログを解いたら消していく
解いた日付
難度 (1)~(5)
面白さ [1]~[5]
他に良問まとめがあったらコメントしてくれると助かります

2017-07-16

ICPC2017 国内予選参加記

ネタ

f:id:tozangezan:20170716111237p:plain

気がついたら年齢的にもICPCの参加リミットを超えてしまった。年を重ねるにつれ、目標を達成してしまうし、目標になるものも減ってきてしまうのが、競技プログラミング(に限らないけど)の難しいところ。

その昔、こんな目標を持っていた。

IOIに参加してメダルを取る
ICPCに参加してメダルを取る
海外オンサイトに参加する

もちろんIOIは2012年の時にまあなんとかして代表になって銀メダルを取ったし、ICPCですら2014年の時に運もあって銀メダルを取ったし、この二つは年齢的にも引退なのでもう仕方がない。海外オンサイトはいつまでも出られるので、これは目標にできるか？と思いきや、FHC2015、DCJ2016ときてまたDCJ2017でも進出し、やはり数回出場すると目標としていまいちインパクトに欠けて、やる気が出ない。これだけのために必死に問題解き続けられるかと言われるとそんなことはないと思う。

じゃあここまでくると目標というのはどういうものが考えられるかと言うと、

TopCoder target
Codeforces LGM
AtCoder 3200
海外オンサイトで入賞

とかなんだけども、TopCoderは廃れて目も当てられないし、Codeforcesはゴミみたいなセットが増えすぎでいちいちやる気を削いでくるし、AtCoderは過去問練習で上位に来た無能を真っ向から潰しにかかってくるセットばっかりだし、海外オンサイトで入賞は有名人たちの争いだし、なんか以前の目標に比べて遠すぎる。

もっと現実的かつ練習が要求されて見返りも結構ある目標が立てられるといいんだけどもなあ。赤中上位だけどtargetには届かない、そんな人たちを集めてリーグ戦とかやって欲しい。chokudaiさんお願いします。

関係ないけどOpenCupのおかげで今もチーム戦に参加できるのは嬉しい。制限なしのチーム戦の真面目なコンテストとか出てきてくれないかなとも思ってる(ロシアにはあるよね)。

2017-06-21

純粋培養競技プログラマが基本情報技術者試験を解いてみた話

ネタ

参考:
d.hatena.ne.jp

こんにちは。たまには有機的な投稿をします、tozangezanです。

twitterで基本情報技術者試験、というものが話題に上がっていたので、過去問を解いてみることにしました。

筆者紹介

大学4年。中学2年のときに競技プログラミングを始める。インターンに行ったことがある。競技プログラミング以外の用途でもプログラムを書く(研究でシミュレーションをするため)。
パソコンの中のことやネットワークのことについて勉強したことはなし。離散最適化に興味なし。

DEGwerと違い、理学も工学も専攻していません(ポイント)

使用した問題

http://www.fe-siken.com/kakomon/29_haru/
ここに上がっている、平成29年度春の午前試験を解きました。

結果

46問正解/80問 です。ボーダーが6割らしいので、ぎりぎり不合格です。

感想

アルゴリズムの問題が1桁問しかない！
全般的に知らない語彙が多すぎます。具体的にはパソコン系単語とビジネス系単語だと思います。DEGwerも言っていましたが、まだ英語をカタカナにしたものは意味が想像つくので(たとえばニッチャとか生まれて初めて見た4文字ですが、nicheに-erをつけただけだと思うし、nicheという単語は生態学を専攻している人が知らないわけがありません)、まだなんとかなります。問題は、技術に関する知識が文字どおり0(特にネットワーク関係は、「パソコンの右上か左上に扇のようなマークがあり、これを押すとネットにつながる」くらいの知識しかないので、どうすることもできません)なので、問題文から推測しようがありません。
特にDMZにネットワークを置く問題とか、なんで韓国と北朝鮮の国境地帯にサーバー(あのディスクが3枚つながったやつです)を置くのかしか頭に残りません。
ビジネス関連単語も、発音はできるが全く意味がわからない日本語で構成されており、正気を疑います。

採点してみる。なんか最初の方間違えまくってるやんけ！ → どれもこれも単語の説明問題でした(完)

面白かった問題

問30. 唯一解きがい(手の動かしがい？)がありました。

問69. ここまでくると、経済学の問題じゃないですかね。

結論

一般常識 + 最低限の英語力 + 競プロ風味の算数では通らないこともあります。多分わからない問題の乱択の結果のブレが、合否を分けるラインです。
じゃあ競技プログラミングは基本情報技術者試験の役に立たない？そんなことはないと思います(わずかだとは思いますが)。そんなことで一番伝えたいのは、
情報系専攻は基本情報の役に立つ。

回答

間違えた問題の回答には、・がついています。
え

い
あ
あ
い
う
え

え

う

え
あ

あ
う
あ
あ
い

う
う

い

い
あ

う

う
え
あ

え

う

う
い
あ

う

え

い

う
い

い
う
い
え
う
い
い
う
え
う

2017-06-16

四国フォトギャラリー

ネタ

2017年2月に四国に行きました。そのとき撮った写真のうち、見せたいものをただひたすら張り続けます。

f:id:tozangezan:20170220143959j:plain
番号が汚い

f:id:tozangezan:20170220151334j:plain
ラスボスがいそう

f:id:tozangezan:20170220181135j:plain
高松からは離島行きフェリーがたくさんある

f:id:tozangezan:20170220192413j:plain
セルフの醍醐味

f:id:tozangezan:20170221085950j:plain
さぬきうどん駅

f:id:tozangezan:20170221104443j:plain
徳島。駅の隣に山がある

f:id:tozangezan:20170221132720j:plain
f:id:tozangezan:20170221132810j:plain
サラダ

f:id:tozangezan:20170221133335j:plain
阿波池田。寂しすぎる

f:id:tozangezan:20170221142611j:plain
f:id:tozangezan:20170221143223j:plain
大歩危峡

f:id:tozangezan:20170221153217j:plain
ゆるして

f:id:tozangezan:20170221155818j:plain
日本一駅間が短い

f:id:tozangezan:20170221173917j:plain
はりまや橋

f:id:tozangezan:20170222090526j:plain
土佐湾

f:id:tozangezan:20170222092755j:plain
大都会予土線

f:id:tozangezan:20170222100512j:plain
f:id:tozangezan:20170222101938j:plain
四万十川

f:id:tozangezan:20170222102852j:plain
f:id:tozangezan:20170222102859j:plain
半家はげ

f:id:tozangezan:20170222165503j:plain
四国一箇所巡り

f:id:tozangezan:20170222183619j:plain
願い事

ごはん
f:id:tozangezan:20170220144959j:plain
f:id:tozangezan:20170220185253j:plain
f:id:tozangezan:20170221112257j:plain
f:id:tozangezan:20170221115627j:plain
f:id:tozangezan:20170221175540j:plain
f:id:tozangezan:20170221180045j:plain
f:id:tozangezan:20170222122930j:plain
f:id:tozangezan:20170222175746j:plain

おまけ

B: flagpoles
差を取ると本当に簡単。

long long p[11000000];
long long lf[210];
long long lv[210];
long long rf[210];
long long rv[210];
long long sv[210];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetNumFlagpoles();
	if(N<=2){
		if(I==0){
			printf("%d\n",N);
		}
		return 0;
	}
	N--;
	if(N<T){
		T=N;
		if(I>=T)return 0;
	}
	int L=(long long)N*I/T;
	int R=(long long)N*(I+1)/T;
	int n=R-L;
	long long now=GetHeight(L);
	for(int i=0;i<n;i++){
		long long tmp=GetHeight(i+1+L);
		p[i]=tmp-now;
		now=tmp;
	}
	long long left=0;
	long long right=0;
	for(int i=0;i<n;i++){
		if(p[i]==p[0])left++;
		else break;
	}
	for(int i=0;i<n;i++){
		if(p[n-1-i]==p[n-1])right++;
		else break;
	}
	long long ma=0;
	long long val=0;
	for(int i=0;i<n;i++){
		if(i==0||p[i]==p[i-1]){
			val++;
		}else{
			val=1;
		}
		ma=max(ma,val);
	}
	if(I==0){
		lf[0]=p[0];
		lv[0]=left;
		rf[0]=p[n-1];
		rv[0]=right;
		sv[0]=ma;
		for(int i=1;i<T;i++){
			Receive(i);
			lv[i]=GetLL(i);
			lf[i]=GetLL(i);
			rv[i]=GetLL(i);
			rf[i]=GetLL(i);
			sv[i]=GetLL(i);
		}
		long long ret=0;
		long long nc=0;
		long long nl=0;
		for(int i=0;i<T;i++){
			ret=max(ret,sv[i]);
			if(nc==lf[i]){
				ret=max(ret,nl+lv[i]);
			}else{
				nl=0;
				nc=rf[i];
			}
			long long TL=(long long)N*i/T;
			long long TR=(long long)N*(i+1)/T;
			if(TR-TL==lv[i]){
				nl+=lv[i];
			}else{
				nl=rv[i];
				nc=rf[i];
			}
			ret=max(ret,nl);
		}
		printf("%lld\n",ret+1);
	}else{
		PutLL(0,left);
		PutLL(0,p[0]);
		PutLL(0,right);
		PutLL(0,p[n-1]);
		PutLL(0,ma);
		Send(0);
	}
}

C: number_bases
事前にくり上がりがある場合ない場合どっちも用意しておく。

int X[1100000];
int Y[1100000];
int Z[1100000];
int LL[210][2];
int RR[210][2];
int DD[210][2];
int KK[210][2];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetLength();
	if(N<T){
		T=N;
		if(I>=T)return 0;
	}
	int L=(long long)N*I/T;
	int R=(long long)N*(I+1)/T;
	int n=R-L;
	for(int i=0;i<n;i++){
		X[i]=GetDigitX(i+L);
		Y[i]=GetDigitY(i+L);
		Z[i]=GetDigitZ(i+L);
	}
	int DL=0;
	int DR=-1;
	int dame=0;
	int KR=0;
	for(int i=0;i<n;i++){
		DL=max(max(DL,Z[i]+1),max(X[i]+1,Y[i]+1));
		if(KR+X[i]+Y[i]>Z[i]){
			int nr=KR+X[i]+Y[i]-Z[i];
			if(DR==-1||DR==nr){
				DR=nr;
			}else{
				dame=1;
			}
			KR=1;
		}else if(KR+X[i]+Y[i]==Z[i]){
			KR=0;
		}else{	
			dame=1;
		}
	}
	if(DR!=-1&&DR<DL)dame=1;
	LL[I][0]=DL;
	RR[I][0]=DR;
	DD[I][0]=dame;
	KK[I][0]=KR;
	DL=0;
	DR=-1;
	dame=0;
	KR=1;
	for(int i=0;i<n;i++){
		DL=max(max(DL,Z[i]+1),max(X[i]+1,Y[i]+1));
		if(KR+X[i]+Y[i]>Z[i]){
			int nr=KR+X[i]+Y[i]-Z[i];
			if(DR==-1||DR==nr){
				DR=nr;
			}else{
				dame=1;
			}
			KR=1;
		}else if(KR+X[i]+Y[i]==Z[i]){
			KR=0;
		}else{	
			dame=1;
		}
	}
	if(DR!=-1&&DR<DL)dame=1;
	LL[I][1]=DL;
	RR[I][1]=DR;
	DD[I][1]=dame;
	KK[I][1]=KR;
	if(I==0){
	//	printf("%d: %d %d %d %d\n",0,LL[I][0],RR[I][0],DD[I][0],KK[I][0]);
		//printf("%d: %d %d %d %d\n",1,LL[I][1],RR[I][1],DD[I][1],KK[I][1]);
	//	fflush(stdout);
		for(int i=1;i<T;i++){
			Receive(i);
			for(int j=0;j<2;j++){
				LL[i][j]=GetInt(i);
				RR[i][j]=GetInt(i);
				DD[i][j]=GetInt(i);
				KK[i][j]=GetInt(i);
			}
		}
		bool ok=true;
		int dl=0;
		int dr=-1;
		int kr=0;
		for(int i=0;i<T;i++){
			if(DD[i][kr]){
				ok=false;break;
			}
			dl=max(dl,LL[i][kr]);
			if(dr!=-1&&dr!=RR[i][kr]&&RR[i][kr]!=-1){
				ok=false;
			}else if(RR[i][kr]!=-1)dr=RR[i][kr];
			kr=KK[i][kr];
		}
		if(kr)ok=false;
		if(dr!=-1&&dl>dr)ok=false;
		if(!ok){
			printf("IMPOSSIBLE\n");
		}else{
			if(dr==-1)printf("NON-UNIQUE\n");
			else printf("%d\n",dr);
		}
	}else{
		for(int i=0;i<2;i++){
		//	printf("%d: %d %d %d %d\n",i,LL[I][i],RR[I][i],DD[I][i],KK[I][i]);
			//fflush(stdout);
			PutInt(0,LL[I][i]);
			PutInt(0,RR[I][i]);
			PutInt(0,DD[I][i]);
			PutInt(0,KK[I][i]);
		}
		Send(0);
	}
}

D: broken_memory
落ちた。不必要にデータを送りすぎた。(700回ですむところを調子に乗って送りまくってしまった)

E: nanobots
smallは分割統治であることは有名。largeはたくさんスライスしてランダムに割り振ってsmallと同じことをする。

const long long mod=1000000007;
long long ret=0;
void count(long long L,long long R,long long lm,long long rm){
	if(L>=R)return;
	if(lm>rm)return;
//	printf("%lld %lld %lld %lld\n",L,R,lm,rm);
	if(Experiment(R-1,rm)=='T'){
		ret=(ret+((R-L)%mod)*((rm)%mod))%mod;
	//	printf("%lld %lld\n",R-1,rm);
		return;
	}
	if(Experiment(L,lm)=='E')return;
	long long M=(L+R)/2;
	long long left=lm-1;
	long long right=rm+1;
	while(left+1<right){
		long long mid=(left+right)/2;
		if(Experiment(M,mid)=='T'){
			left=mid;
		}else right=mid;
	}
	ret=(ret+left)%mod;
	//ret=(ret+(M-L)%mod*((left-lm+1)%mod))%mod;
	count(L,M,max(1LL,left),rm);
	count(M+1,R,lm,left);
}
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetNumNanobots();
	long long R=GetRange();
	int BK=min((long long)R,2000000LL);
	
	//count(1,R+1,1,R);
	srand(1145141919);
	for(int i=0;i<BK;i++){
		int tmp=rand();
		long long left=R*i/BK+1;
		long long right=R*(i+1)/BK+1;
		if(tmp%T==I){
			count(left,right,1,R);
		}
	}
	if(I==0){
		for(int i=1;i<T;i++){
			Receive(i);
			long long tmp=GetLL(i);
			ret=(ret+tmp)%mod;
		}
		
		printf("%lld\n",ret);
	}else{
		PutLL(0,ret);
		Send(0);
	}
}

21位。なんで通ったんだろう。アイルランドでも頑張ります。

2017-06-09

英単語の覚え方

ネタ

7000語くらい知ってる人(大学受験でそんなに苦労しないレベル)が15000～20000語くらい知ってる人になるための方法です。

自分の体験にしか基づいていないので、これが多くの人に適用可能かとかそういうことは一切考えてないのであしからず。

文脈で覚えるべきなのか単語リストとして覚えるべきなのか？英英で覚えるべきなのか英和で覚えるべきなのか？etc

以下、僕がやったことは単語リストで覚えて、多読で実際に触れることで実際の使用例を後から文脈で知るという方法をとりました。最初から文脈で覚えようとすると異常なほどに労力が必要でペースが落ちるので、非効率だと思います。特に高校生レベルの単語ならまだしも、それ以上になってくるとものすごい多義語とかは減ってくるわけで、和訳を見ただけでもう文脈も限られてくるようなものばかりです。(たとえば、sonnet (イタリアの14行詩) のような単語が、文脈で覚えないと情報量が落ちるかといわれると、そんなことはないと思います)。ただし、具体的なものの名称で、単語の説明だけ見ても想像が困難なものがあり、これは Google 画像検索によってイメージで覚えることが得策なこともあります。(僕が想像に苦労したのは、西洋の城に関する単語です。例えば portcullis という単語は「落とし格子」という意味ですが、城といえばまず鶴ヶ城を思い浮かべるような人には想像が難しいでしょう？)
英英で覚えるべきか英和で覚えるべきかに関しては、どちらも一長一短あるので好きなほうを選べばいいと思います。個人的には英和が(多くの場合)ストレスがないのでおすすめです。英和の良い点は、「パッと見で分かるので、単語を回すスピードが上がる」「訳語の意味を勘違いしていたせいで間違って覚える心配が少なめ(無いという事ではありません)」、英英の良い点は「説明が豊富でより的確」「GREレベルですら英和辞典に載ってない単語が意外とあるが、英英には必ず載ってる」ということでしょうか。
もう一つは媒体ですが、僕は紙で覚えようと思ったことはありません。格安で数千枚の単語カードが買えるなら考えなくもないのですが、本だと順番が固定されていたりする点、自分でカードを準備するには大変過ぎる点がネックでした。また、音声も付加して覚えるというのはすごく良いアイデアだと思います。しかし、これは自力で辞書と単語リストだけから環境を構築する場合はほぼ無理です。

覚えて思ったこと等

語幹を使って覚えるというのは、ある程度助けになります。例えば、mal-は悪いことですし、dys-は何かが壊れていたり失っていたりするものですし、arbo-は樹木に関しています。しかし、in-が特に厄介です。
単語と訳語の対応だけを覚えていると、実際に使えないというのは広く言われています。これは正しいです。例えば、infiltrate にはどのようなときにin/throughが付くのかとかは、infiltrateの意味が分かっていても全く知りません。
ただし、そのような難しい単語で、専門的な名詞や形容詞というわけでもないものを、作家でもないノンネイティブが使うときが来るのでしょうか？特にノンネイティブが使う複雑な動詞というのは、科学的な論文に登場しがちな単語だけな気がします。

厄介な外来語

mikanのGRE/TOEFLを終えて新しい単語リストを始めたとき、フランス語の単語を勉強しているような錯覚に囚われるほど、外来語が大量に登場しました。外来語は発音が意味不明で、複数形が意味不明で、語幹が全く通用しないものが多く、さらに意味がやけにマイナーなことが多いので、単語リストのため、試験のためだけに勉強しているような気分になります。特に感情が消えるフランス語由来の単語を並べてみます。発音してみましょう。

malapropos
maladroit
verdigris
cliche
raconteur
patois

実際、何をやったか

で、実際僕がやったことをまとめていきます。

mikan に出会う。mikan は本当に良いアプリです。ただし、ある程度覚えてからが本当に不便です。あと、四択クイズはいらないですね。やったことは、「とりあえず出来る限り早く全レベルを解禁し、学習済みにする」→「『全ての単語』モードからランダムを選び、150個カードをめくる」→「分からなかった単語が未学習に戻るが、それを全部学習済みに埋めなおす」を毎日やることです。3ヶ月くらいでGREを全部やり、次の3ヵ月くらいでTOEFLを全部やりました。これだけでもかなり十分だと思います。具体的には、Eragonシリーズはそこまで辞書に頼る必要がなくなります。

mikan の GRE/TOEFL 単語を9割以上覚えてしまったことと、覚えた単語が多いときの効率の悪さに不満を感じたので、自分でプログラムを作って今までmikanで毎日やってきたことがより効率的に出来るものを作りました。これが #1日150ShokubutsuランダムでおなじみのShokubutsuです。単語リストはネット上にあった難しめ(なかなか難しい！)のものを使いました。これが割りとできるようになるとEragonシリーズは10ページに1回くらいしか辞書を引かなくてよくなります。

やめたことは、Ankiに12000語レベルのものを大量にぶち込んでやったことです。これは単語リストの質が悪かった。(本当にどうでも良い単語ばかりな上和訳が変なのばっかりでした)

これ以降やるべきことは、小説や新聞で実際に出会った単語を覚えることと、気が向いた単語をthesaurusで引いて眺めることだと思いました。しかし、小説を読んで知らない単語に線を引くと、高確率でスラングなのが気がかりです。

おまけ

almost_sorted

区間をK伸ばしてソートするだけです。

#include<stdio.h>
#include<algorithm>
#include<message.h>
#include"almost_sorted.h"
using namespace std;

long long p[3100000];
const int mod=1<<20;
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=NumberOfFiles();
	int K=MaxDistance();
	int L=(long long)N*I/T;
	int R=(long long)N*(I+1)/T;
	int ans=0; 
	if(L==R){
		ans=0;
	}else{
		int left=max(0,L-K);
		int right=min(N,R+K);
		for(int i=left;i<right;i++){
			p[i-left]=Identifier(i);
		}
		std::sort(p,p+right-left);
		
		for(int i=L;i<R;i++){
			long long t=p[i-left]%mod*i%mod;
			ans=(ans+t)%mod;
		}
	}
	if(I==0){
		for(int i=1;i<T;i++){
			Receive(i);
			ans=(ans+GetInt(i))%mod;
		}
		printf("%d\n",ans);
	}else{
		PutInt(0,ans);
		Send(0);
	}
}

shhhh

中継点をランダムに決めることが本質です。ハッシュの計算を間違えました。

#include<stdio.h>
#include<algorithm>
#include<message.h>
#include<set>
#include<cassert>
#include"shhhh.h"
using namespace std;

int key[120];
int ha[110000];
int p[120];
int q[120];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetN();
	if(N<1000){
		if(I!=0)return 0;
		int ret=0;
		int at=0;
		while(1){
			int to=GetRightNeighbour(at);
			ret++;
			if(to==1)break;
			at=to;
		}
		int R=ret;
		int L=N-ret;
		if(L<R)printf("LEFT %d\n",L);
		else if(L>R)printf("RIGHT %d\n",R);
		else printf("WHATEVER %d\n",L);
		return 0;
	}
	srand(114514810);
	set<int>S;
	S.insert(0);
	S.insert(1);
	for(int i=0;i<100000;i++)ha[i]=-1;
	ha[0]=0;
	ha[1]=T;
	for(int i=1;i<T;i++){
		while(1){
			key[i]=rand()%N;
			if(!S.count(key[i]%100000)){
				ha[key[i]%100000]=i;
				S.insert(key[i]%100000);break;
			}
		}
	}
	//printf("%d: %d\n",I,key[I]);
	//fflush(stdout);
	int at=key[I];
	int dist=0;
	int nx=0;
	while(1){
		int to=GetRightNeighbour(at);
		//printf("%d: %d %d\n",I,at,to);
		//fflush(stdout);
		dist++;
		if(~ha[to%100000]&&(to==1||to==key[ha[to%100000]])){
			nx=ha[to%100000];
			break;
		}
		at=to;
	}
//	printf("%d: %d %d %d\n",I,key[I],nx,dist);
	//fflush(stdout);
	if(I==0){
		p[0]=nx;
		q[0]=dist;
		for(int i=1;i<T;i++){
			Receive(i);
			p[i]=GetInt(i);
			q[i]=GetInt(i);
		}
		int R=0;
		int L=0;
		int now=0;
		int cnt=0;
		while(1){
			int to=p[now];
			R+=q[now];
			cnt++;
			if(to==T){
				break;
			}
			now=to;
			if(cnt>T){
				assert(false);
			}
		}
		L=N-R;
		if(L<R)printf("LEFT %d\n",L);
		else if(L>R)printf("RIGHT %d\n",R);
		else printf("WHATEVER %d\n",L);
	}else{
		PutInt(0,nx);
		PutInt(0,dist);
		Send(0);
	}
}

load_balance

半分全列挙をどのスレッドでもやるのですが、条件を満たした結果(modとかで振り分ける)のみを各スレッドで考慮することにすると、log分もなんとかなります。
ただしこの解法はあんまり良くないようで、TLEぎりぎりです。(26個1があると26C13個の13を持つことになってそこがネック)

#include<stdio.h>
#include<algorithm>
#include<message.h>
#include"load_balance.h"
using namespace std;

long long p[60];
int m[110];
const int mod=53461;
int bt[60000];
int L,R;
int I;
int ls;
int rs;
long long left[11000000];
long long right[11000000];

void dfs(int a,int b,int c,long long d){
	if(a==b){
		if(bt[c%mod]==I){
			if(b==L)left[ls++]=d;
			else right[rs++]=d;
		}
		return;
	}
	dfs(a+1,b,(c+p[a])%mod,d+p[a]);
	dfs(a+1,b,(c+mod-p[a]%mod)%mod,d-p[a]);
}
int main(){
	int T=NumberOfNodes();
	I=MyNodeId();
	int N=GetN();
	for(int i=0;i<N;i++)p[i]=GetWeight(i);
	srand(114514810);
	for(int i=0;i<mod;i++){
		bt[i]=rand()%T;
	}
	L=N/2;
	R=N-L;
	dfs(0,L,0,0LL);
	dfs(L,N,0,0LL);
//	std::sort(left,left+ls);
	std::sort(right,right+rs);
	int ok=0;
	for(int i=0;i<ls;i++){
		if(binary_search(right,right+rs,left[i]))ok=1;
	}
	
	if(I==0){
		bool ret=false;
		if(ok==1)ret=true;
		for(int i=1;i<T;i++){
			Receive(i);
			int tmp=GetInt(i);
			if(tmp==1)ret=true;
		}
		if(ret)printf("POSSIBLE\n");
		else printf("IMPOSSIBLE\n");
	}else{
		PutInt(0,ok);
		Send(0);
	}
}

kolakoski

最初に配列の種みたいなのを割り振っておき、順々に種から次の世代を発生させていきます。
発生のさせ方ですが、最初に長さと1/2が切り替わる回数がわかるので、それらを求め親ノードにこれを転送します。親ノードは子ノードの左から順にこれらを使うことで、その子ノードで1/2どちらから始まるか、オフセットがどこかというのを渡すことができるようになります。

デバッグがしにくいです。スレッド数を下げる(3とか)のがおすすめです。

#include<stdio.h>
#include<algorithm>
#include<message.h>
#include"kolakoski.h"
using namespace std;

char a[2000];
long long N;
int Get(long long i){
	if(i>=N)return 0;
	return GetMultiplier(i);
}
char p[2][41000000];
long long X[110];
long long Y[110];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	N=GetIndex();
	
	a[0]=1;
	a[1]=a[2]=2;
	int left=2;
	int right=3;
	while(right-left<T){
		if(a[left]==1){
			a[right++]=left%2+1;
			
		}else{
			a[right++]=left%2+1;a[right++]=left%2+1;
		}
		left++;
	}
	//if(I==0){for(int i=0;i<right;i++)printf("%d",a[i]);printf("\n");}
	if(I==T-1){
		long long ret=0;
		for(int i=0;i<right;i++){
			ret+=Get(i)*a[i];
	//		printf("%d",a[i]);
		}
	//	printf("\n");fflush(stdout);
		long long now=left;
		long long at=right;
		while(1){
			for(int i=0;i<T-1;i++){
				Receive(i);
				X[i]=GetLL(i);
				Y[i]=GetLL(i);
			}
			for(int i=0;i<T-1;i++){
				PutLL(i,now%2);
				PutLL(i,at);
				Send(i);
				now+=X[i];
				at+=Y[i];
			}
			bool end=false;
			for(int i=0;i<T-1;i++){
				Receive(i);
				long long tmp=GetLL(i);
				long long cnt=GetLL(i);
			
				ret+=tmp;
				if(cnt){
					end=true;
				}
			}
			if(end)break;
		}
		for(int i=0;i<T-1;i++){
				Receive(i);
				X[i]=GetLL(i);
				Y[i]=GetLL(i);
			}
			for(int i=0;i<T-1;i++){
				PutLL(i,-1);
				PutLL(i,-1);
				Send(i);
			}
		
		printf("%lld\n",ret);
	}else{
		int m=right-left;
		int L=m*I/(T-1)+left;
		int R=m*(I+1)/(T-1)+left;
		for(int i=L;i<R;i++){
			p[0][i-L]=a[i];
		}
		int ptr=0;
		int n=R-L;
		while(1){
			long long r1=0;
			for(int i=0;i<n;i++)r1+=p[ptr][i];
			PutLL(T-1,n);
			PutLL(T-1,r1);
			Send(T-1);
			Receive(T-1);
			int sc=GetLL(T-1);
			long long off=GetLL(T-1);
			if(sc<0)break;
			int nn=0;
			
			for(int i=0;i<n;i++){
				for(int j=0;j<p[ptr][i];j++){
					p[!ptr][nn++]=(sc+i)%2+1;
				}
			}
			long long res=0;
			long long end=0;
		//	printf("%d: ",off);
			for(int i=0;i<nn;i++){
				if(off+i>=N){end=1;break;}
				res+=Get(off+i)*p[!ptr][i];
		//		printf("%d",p[!ptr][i]);
			}
		//	printf("\n");fflush(stdout);
			PutLL(T-1,res);
			PutLL(T-1,end);
			Send(T-1);
			ptr=!ptr;
			n=nn;
		}
	}
}

DCJは、残り解法が分かってないのが4問あります。解法だけは読んでおこうかと思っています。