2016-09-21

JAG夏合宿2016参加記

9月の2日~5日にかけて開催されたJAG夏合宿に参加しました

1日目東京到着・ガイダンス

夜行バスで早朝に到着したので、yurahunaさん,37dbyeさん,T.M君と新宿のロッテリアでたむろしていました。

ガイダンスまでは時間があったので、模擬地区2012をyurahunaさんと一緒に解きました。
結局二人でDictionaryとMedian Treeを解き、Stack Mazeが解けず。

以下問題のネタバレなので白文字
「Median Treeは半信半疑で最小全域木を張ったら通ったのですが、解説を見るとキレイな証明が書いてあり面白い問題だと思いました。」

2日目 Central Europe Regional Contest 2014(CERC2014)

チームJag2015Mogichiku( @konjo_p + @nola_suz + @Yazaten )で出場しました。
CERCとはヨーロッパの激戦区の地区予選らしい。

寝坊でチーム決めにTLEしたのですが、2人で出場予定だったkonjo_pさんとnola_suzさんのところに入れてもらうことができました。

開始直後はA~Cをそれぞれ読む方針で僕はB問題を読む。
今いるところから見える一番近い山の斜面はどれですかみたいな問題だったけど斜面の数が結構多くて放置。
あとで聞くと実際ヤバい問題だったらしく良い判断だった。

その間に@konjo_pさんがC問題*1の解法を思いついたらしく書いてもらう。
なんか合わないらしく解法を確認していたが、実装のミスが見つかり無事AC。

その後H問題*2の概要をnola_suzさんに聞き、「なんか組み合わせをDFSで列挙して二分探索でホイみたいな感じですね」と言ったらnola_suzさんが実装をしてくれてAC。(実は列挙しても組み合わせは高々1000以下なので二分探索は不要だった。ごめんなさい。)

その後、僕がD問題*3、他の2人がI問題*4をAC。

この段階で解けそうな問題はF*5かL*6で、Fはチームメンバーが実装してくれそうな感じだったのでLを考える。
区間DPして欲しそうな制約だったがイマイチ区間の持ち方がわからず、いろんな貪欲とかを考えていた。

Lは結局わからないままコンテスト終了だったが、僕を除く2人が熱意でFをACしてくれたので8位といういい感じの順位を取れた

t9qmib + Yazaten - nikollson で参加して8位だった．
— 青 (@konjo_p) September 3, 2016

Lは距離と時間を要素にした二次元平面を考えると、「一番遠くで発生する攻撃は必ず打たなければならない」ことからその左側と右側の2つの区間に綺麗にわかれるのでいい感じに区間DPができたらしい。なるほどなぁ

3日目 JAG 模擬アジア地区予選2016

チームBlackSeven( @shora_kujira16 + @yurahuna + @Yazaten )で出場しました。
( 由来はしょらーさん(@shora_kujira16)の言った「NAのB棟7Fはブラック」というローカルネタ )
LINEさんのオフィスを借りての開催で楽しかったです。

LINEピラミッドできた pic.twitter.com/2fSI9xqeMT
— やざてん (@Yazaten) September 4, 2016

2日目同様、開始直後はA~Cをそれぞれ読む方針で僕はB問題*7を読む。
よくあるBFSなのですぐ解ける。A問題*8がACするのを待って連続AC。

C問題*9をyurahunaさんと考えている間にしょらーさんが「Eはこれハッシュでしょ」と言って提出。WAを食らったので諦め、D問題*10を考えてもらう。
するとここでE問題にリジャッジがかかり時間差AC。

D問題の条件を満たす括弧列には規則性があるらしく、いい感じに生成するプログラムをしょらーさんに書いてもらう。実装ミスでWAをもらいつつAC。

F問題以降はわからなかったのでC問題をセグ木を使ってyurahunaさんとペアプロ。
時間ギリギリに「サンプル通った！よっしゃいくぞ！」と提出したらめっちゃWAが出て終了♨

模擬地区は解説を聞くと「確かに〜〜」となるような問題が多く面白かったです。

4日目 2015-2016 XVI Open Cup

チームMILK_TEA( @osrehun + @satashun + @Yazaten )で出場しました。
( その辺にミルクティーのペットボトルがあったのでこうなった )
KLABさんのオフィスを借りての開催でした。大人の事情でラブライブの写真を取るのは禁止でした、残念。

前日hecさん(@osrehun)がTwitterで組む人を募集していたので一緒に出ることに。
あとは会場でのランダムマッチングでsatashunさんが加わり、プロ＆プロ＆僕(´･_･`)という感じになりました。

開始直後はC問題を読んだのですが英語がわからず結局satashunさんに助けてもらった(英語弱者感)
その後読んだF問題では閉路を列挙すればいいと一瞬思ったが、一般にグラフの閉路はめっちゃあるらしくて厳しいらしい。

C問題がいけそう、 D問題もRMQ書けばいけそうという感じでstashunさんとhecさんが取り掛かる。

Aが結構解かれていたので僕が考えていたが計算量を落とす工夫が思いつかない…。
結局hecさんに助けてもらいながらなんとかACしたものの、他の問題には全くと言っていいほど関われなくて申し訳なかった。

F問題の最短経路木を考えると良いと言うのが面白かったです。

おわりに

自分より強い方々とチームを組めたので、いい勉強になりました。
今回の合宿で、ICPC系のセットは「解法のわかりやすい問題をいかに高速に片付けられるか」が大事だと感じました。新しいアルゴリズムを覚えるのも大事ですが、解ける問題をしっかり解く練習もしていきたいです。
夏合宿でチームを組んでくださった方々ありがとうございました。おかげさまで楽しい合宿になりました！

おまけ

夏合宿9日目(家に帰るまでが夏合宿です)にマジカルミライ2016に行きました。
行くのは今年で2度目なんですが、今年も神イベントでした。
興味がある人には超オススメですが、ライブ以降テーマソングを聞くと泣きそうになるという弊害があるので要注意です。

*1:連続する整数の和がNになるような式を求めよみたいな問題

*2: 眠い人が携帯電話で数字を打つ問題

*3:一つの歯車を回すと他の隣接した歯車もまわるので、それぞれがどれくらいどちら向きに回転したかを答える問題

*4:x個の'B'とy個の'W'からなる文字列が与えられるので、'B'の個数:'W'の個数 = x:y となる部分文字列に分解する問題(?)

*5:'?'を含む文字列が3つ与えられるので、それらがsortedであるような'?'の組み合わせの総数を求める問題

*6:敵の攻撃がいっぱい来るのでビームで全部破壊して生き残る問題

*7:お姫様とそれを追う兵士がグリッド状にいて、姫は逃げ切れますか？という問題

*8:読んでない

*9:やる気上位20%しか働かない会社に人間が出たり入ったりする問題

*10:括弧をバランスさせるためにスワップがN解必要な括弧列のうち辞書順最小のものを答える問題

2016-07-16

NAIST受験記

NAIST 情報科学研究科第1回の試験を受験しました。

結果は合格で、学生宿舎優先入居の権利もいただきました。どの結果が功を奏したのかはわかりませんが、何かの参考になれば幸いです。

NAISTの試験は主に小論文・数学・英語・面接からなります。

小論文

A4用紙2枚で取り組みたいテーマを記述し、願書提出時に同封します。

大学での専攻がNAISTでの専攻とは異なるので、卒業研究を小論文用に書き換えることはしませんでした。テーマやアプローチは、スプリングセミナー参加時に志望研究室の学生や先生にお話を伺いながら考えました。

このように準備は春休み頃からしていましたが、実際に手を付けたのは願書提出の3週間ほど前でした。僕は言い回しなどの推敲に時間がかかるタイプなので、書き上がったのは願書提出の1週間ほど前でした。その後、志望研究室の博士後期課程の方のアドバイスを参考に修正し、提出しました。

評価はわかりませんが、納得のいく小論文を提出できたと思っています。

数学

解析・線形代数の分野から出題され、ホワイトボードを用いて口頭で解答します。

数学に今までまじめに取り組んでこなかったのでイチから勉強しなおしました。
使用した参考書はマセマの「微分積分」と「線形代数」です。勉強を始めたのは願書提出後でした。練習問題を解きつつ参考書の内容を理解し、確認のために演習を解くといった形で勉強を行いました。

本番では、arcsinの微分を参考書に載っていた公式を使って解くと微妙な顔をされたり、解析・線形代数ともに3つ目の小問が全く解けなかったりと、惨敗でした。
甘く見てもせいぜい60点という感じだと思います。

英語

TOEIC・TOEFLのどちらかを選択し、受験日当日にスコアを提出します。

英語に今までまじめに取り組んでこなかったのでイチから勉強しなおしました。
大学が開講している、TOEIC受験者向けの長期の講座に参加しました。講座参加前は350点ほどでしたが、5月の試験で最終的に600点台を取ることができたのでこれを提出しました。

面接

事前に提出した小論文や受験者の専攻に関する質問に、口頭で解答します。

恒例の3分間プレゼンの内容は、事前に作成し暗記して面接に望みました。どうしても説明したい背景なども含めると時間がギリギリになってしまいましたが、何度も練習をして制限時間を超えないよう心がけました。

プレゼン後の質問は、小論文の内容に関するものが多かったです。プレゼンの一部が正しく伝わっておらず再説明したり、学部の研究の内容や進捗について話をしたりしました。「質問に対してはまず解答を述べる」ことや「質問の意図を理解して簡潔に答える」ということを意識し、あとは自然体で受け答えを行いました。

面接官としっかりとコミュニケーションを取り、十分小論文の内容を伝えられたと思っています。

その他

前泊の必要がある場合、ゲストハウスせんたんを利用することをオススメします。比較的安価な上、綺麗で集中できました。
面接はポスターセッションでの発表と似ていると感じたので、そういった対策をしていくとやりやすいかもしれません。
大学への移動中にモバイルルータを紛失し、スマホを持っていない僕は丸一日インターネット難民を経験しました。貴重な体験でした。

2016-06-28

ICPC2016 国内予選コード置き場

ICPC2016 国内予選の問題を解いたコードを載せておきます。
解法の説明はざっくりです。

参加記はこっちです。
ICPC2016 国内予選参加記 - あったこといろいろ

問題文はこっちです。
All Problems

A問題

ソートして、隣り合う要素の差の最小値を出力

#include"bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(a) (a).begin(),(a).end()
#define INF 999999999

int main(){
	int n;
	while(cin>>n&&n){
		vector<int> data(n);
		rep(i,n)cin>>data[i];
		
		sort(all(data));
		int ans = INF;
		rep(i,n-1){
			ans = min(ans,data[i+1]-data[i]);
		}
		cout<<ans<<endl;
	}
}

B問題

毎回、暫定1位と2位の得票数を調べ、「1位の得票数 > 2位の得票数+残りの票数」を満たした時が当選確実。

#include"bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

int main(){
	int n;
	
	while(1){
		cin>>n;
		if(n == 0) break;
		
		int a[200] = {0};
		vector<string> v(n);
		
		bool f=false;
		
		rep(i, n){
			cin>>v[i];
			if(f)continue;

			a[v[i][0]]++;
			
			char ch='0';
			int count1 = 0, count2 = 0;
			for(int j='A';j<='Z';j++){
				if(a[j] > count1){ count2 = count1; count1 = a[j]; ch = (char)j; }
				else if(a[j] > count2) count2 = a[j];
			}
			
			if(count2 + n-i-1 < count1){cout<<ch<<" "<<i+1<<endl; f=true;}
		}
		if(!f)cout<<"TIE"<<endl;
	}
}

C問題

エラトステネスのふるいっぽく配列を埋めながらシュミレーション。
コードはチームメイトが書いたので、ここには貼りません。

D問題

状態 dp[i][j]

区間(i,j)で最適にブロックを取り除いた時の、取り除けるブロックの個数
そのとき、区間(i,j)に残っているブロックに書かれた数字の列

遷移

dp[i][j] = min( dp[i][k] + dp[k+1][j] - deleted , dp[i][j] )

区間(i,j)での最適な解は、区間(i,k) と区間(k+1,j) の組み合わせで求められる。
deletedは、dp[i][k]の数列の右端と dp[k+1][j]の数列の左端の差が1以下なら2、そうでなければ0。
kは区間(i,j)の間のどこを区切りに2つの区間に分けるかを表し、列 i+1 ~ j-1 の範囲で変化させる。
数字の列も適当にマージする

状態に数列を持っているので、コピーコストなどが原因で少し実行に時間がかかる。

#include"bits/stdc++.h"
using namespace std;
typedef pair<int,int> pii;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define INF 999999999

vector<int> w;
struct st{ int val; vector<int> elm; };

st dp[310][310];
st dfs(int left,int right){
	if(dp[left][right].val!=INF) return dp[left][right];
	if(left==right) return dp[left][right] = st{1,vector<int>(1,w[left])};

	int n = right-left+1;
	st mini = st{INF,vector<int>(0)};
	rep(i,n-1){
		st l = dfs(left,left+i);
		st r = dfs(left+i+1,right);
		int tmp = l.val+r.val;
		
		bool deleted=false;
		if( l.elm.size() && r.elm.size() ){
			if(  abs( l.elm[l.elm.size()-1] - r.elm[0] )<=1  ){
				tmp-=2;
				deleted=true;
			}
		}
		
		if(mini.val>tmp){
			vector<int> vec;
			vec.reserve(l.elm.size()+r.elm.size());
			copy(l.elm.begin()		,l.elm.end()-deleted    ,back_inserter(vec));
			copy(r.elm.begin()+deleted	,r.elm.end()		,back_inserter(vec));
			
			mini = st{tmp,vec};
		}
	}
	return dp[left][right] = mini;
}


int main(){
	int n;
	while(cin >> n&&n){
		w.resize(n);
		rep(i, n) cin >> w[i];
		rep(i,310)rep(j,310)dp[i][j]=st{INF,vector<int>(0)};
		st res = dfs(0,n-1);
		cout<<n-res.val<<endl;
	}
}

2016-06-25

ICPC2016 国内予選参加記

先輩( @LazyMii )と後輩と、「miyazoy72」というチーム名で参加し、33位でした。
恐らくアジア地区予選に出場できるのではないかと思います。

「SIMrit」という、熱意のある学内のライバルチームも参加していたので、学内1位の順位を取れたのは本当に運が良かったです。

(追記:地区予選進出が確定しました順位と結果 | ACM-ICPC 2016 Asia Tsukuba Regional)

国内予選当日まで

チームでは、模擬国内予選A・Bに参加したり、1度だけICPCの過去問題を通して解くといった練習をしました。
模擬国内予選Aでは3完早解きで46位、模擬国内予選Bでは普通の速度で3完して40位台*1でした。
この程度の順位では恐らくアジア地区予選に行くことはできず、また前述のSIMritは両模擬国内予選で僕達よりも1問多くACしていたので、本当に歯がゆい気持ちでした。
この時から、「学内一位を取るならば早解きで勝つしかない」と考えていました。

コンテスト

予選にはLazyMiiさんの研究室から参加しました*2。
広い机とプリンタがあったので、良い環境だったと思います。
コードや詳細な解法については別記事参照。
ICPC2016 国内予選コード置き場 - あったこといろいろ

A問題

問題文が短く、ABCのA問題かと思った。ついでにテンプレートを写しつつAC。

B問題

解法としては「得票数1位の人の票数 > (得票数2位の人の票数 + 残りの全票数)」を満たす、初めのタイミングが答えとなるという単純なもの。しかし、条件を満たしたタイミングでbreakしたため、入力を最後まで読まずプログラムが終了するバグが発生して20分ほど悩む。
早解きで勝とうと考えていた僕はこの時点でダメかもと思い始める。

C問題

パッと思いつくエラトステネスのふるい的な解法はTLEしそうに見えたが、一応LazyMiiさんに書いてもらいながら後輩と2人で考察。少しして前述のTLEしそうな解が問題なく通る。そんなんでええんか…

D問題

問題設定が単純でわかりやすかった。
「これに必勝法があるなら類題がいくらかありそうなものだし、どうせDPでいい感じに全探索やろ」とか思う。後輩にサンプルを解説してもらうと、区間で状態が持てそうなことに結構早く気づく。区間DPは、偶然参加していたSMR686で出題されており、pekempey先生の解説で理解していたので、本当に運が良かった。
この時はテンションが上がりすぎていて、ちょこちょこバグを出しながら*3メモ化再帰で書く。メモ化再帰恒例の、"dpテーブルは宣言したがメモ化を忘れるやつ"をやらかしながら、無事AC。

この辺でたしか2時間くらい経過していた気がする。SIMritはこのとき3完だが僕達よりもペナルティが小さかったため、僕達がACしてから20分以内にACされると逆転されるという状況だった。結果的にはこの20分の間に提出はなかったけれど、僕にとってほんとうにほんとうに長い20分だった。

👇pekempey先生の解説
TopCoder SRM 686 (Div. 1) Easy. BracketSequenceDiv1 - pekempeyのブログ

E問題

D問題をACしたテンションと疲れで僕が使い物にならなくなっていたので、考察を2人にまかせて少し休憩。休憩が終わって全員で話し合った結果、「完成する物体は連結」「完成する物体はドーナツ型かパス型」「一つの立方体と交差する立方体は高々8個？」という結論になった。スタートする立方体を一つ選び、そこからDFSみたいなことをする解法を書くが、いかんせん僕が使い物にならなくなっていて実装が遅い＆バグが出まくるという感じでヒドかった。LazyMiiさんに助けてもらいながら全体の40%くらい[要出典] 書いたところでコンテスト終了。

感想

Bのバグがなかなか取れなかった時は死を覚悟しましたが、Cの全探索をパッと書いてもらえたり、Dの解法がすぐに思い浮かんだのが功を奏しました。ある程度の難易度の問題に対して、早い段階で解法を思いつく能力を付けたいと思いました。
連続でコーディングしていると自分はすぐバテるらしいので、アジアに行けるならばそれまでにコーディングを分担できるようにしたいです。
競プロ引退気味だったLazyMiiさんが「また競プロやってみるかなぁ」*4と言ってくれたり、後輩が「僕も競プロ頑張りたいと思いました」*5と言ってくれたりしたので、本当に良かったです。ICPCは本当に偉大ですね。

たくさんお酒飲んでほえ〜なんですけども、多分ICPCアジア予選に出場できるんですよね。
うれしいなぁ
— やざてん (@Yazaten) June 24, 2016

*1:当日はメンバーの予定が合わず、後日集まって解いた結果なのでざっくりとした順位です

*2:快く承諾してくださった研究室の先生および学生に感謝します。

*3:LazyMiiさんが横でバグを潰してくれて本当に助かった。

*4:意訳

*5:意訳

2016-05-24

AOJ 2282: Problem B

Problem B | Aizu Online Judge
問題が長くてややこしいけれど、考察すると意外と簡単

考察・解法

問題文を素直に読むと自分より前の申請を考慮した場合分けが必要に見えるが、考えると実は不要であることがわかる。

申請の時点で自分が担当者にならない申請ができる場合、"B問題の担当者"から外れられることが確定する。"B問題の担当者"になり得ない人の作業時間は結果に影響しないので、Mを超えない最大の"難易度の倍数"の値を申請すると考えて良い。

申請の時点で自分が担当者にならない申請ができない場合、問題文通りMを超えない最大の"難易度の倍数"の値を申請する。

つまり、全ての人は前の人の状態にかかわらず、Mを超えない最大の"難易度の倍数"の値を申請すると考えることができる。

なお、申請が嘘かどうかの判定をする必要はない。
なぜならば、すべての人は作業時間を0と申請することが可能なので必ず嘘とバレない申請をできるからである。

あとは考察によって簡単になったシミュレーションを行い、pairの比較演算の特性を利用してソートすると意外とスッキリ解ける。

#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> pii;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(a)  (a).begin(),(a).end()

int under(int v,int m){
	int ret=0;
	while(ret+v<=m)ret+=v;
	return ret;
}

int main(){
	int n,m;
	while(cin>>n>>m&&(n||m)){
		vector<pair<pii,int>> vec;	//各人の 作業時間、問題難易度、識別番号を持つ
		vector<int> v(n);
		rep(i,n)cin>>v[i];
		
		rep(i,n){
			int time=under(v[i],m);	//i番目の人が申請する作業時間
			int diffi=v[i];		//i番目の人が担当した問題の難易度
			vec.push_back( make_pair(pii(time,diffi),i) );
		}
		sort(all(vec));
		if(vec[0].first==vec[1].first)cout<<n<<endl;	//time,difficultが最小の人が複数居た場合
		else cout<<vec[0].second+1<<endl;		//time,difficultが最小の人が一意に決まる場合
	}
}

2016-03-10

RUPC2016参加記

参加記です
問題の概要が雑であることなど、参加者でないと理解不能な内容があるのはご容赦ください

day1 立命館大学セット

B問題とD問題の作問を担当していました。
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=B
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=D

解説スライドはここです

RUPCに参加してくださった方ありがとうございます！Day1の解説スライドを公開しました https://t.co/MOfSf8WrP9 #rupc2016
— RiPPro (@PJ_RiPPro) 2016, 3月 8

day2 会津大学セット

@wanimaru さんと @kenkoooo さんと、チームyazamaruooooで参加しました

2日目はチーム yazamaruoooo (やざまるまるまるまるまる)
= @Yazaten + @wanimaru47 + @kenkoooo
で出ます！ #rupc2016
— 宇宙ツイッタラーX (@kenkoooo) March 7, 2016

僕はB問題とD問題を解きました

読むとなぜか rollman さんの顔が思い浮かぶB問題は、どう見てもバグらせると辛い系だったので慎重に紙コーディングしてから提出。紙から写経するときに'A'と'B'を打ち間違えて1WAを食らいながらAC。

D問題は @kenkoooo さんに「木を切ってパスグラフ2つになったらOK」みたいな概要を聞いて考察。「パスグラフ or T字グラフ or H字グラフに場合分けして、距離とか端点で場合分けして…」みたいなのが思い浮かんだ。

絶対バグを出す自身があったのでもうちょっと考えると、2人が同時に木を移動してゆくdfsが思い浮かんだので時間をかけて実装＆AC。

D問題、場合分けは嫌だと念じてたらDFS解が降ってきたので書いた
— やざてん (@Yazaten) March 7, 2016

チーム全体ではA,B,C,D,F,Gの6完と、まずまずかなぁという感じだった(終了後すぐに @kenkoooo さんがHをACしてて惜しかった)。

懇親会で、D問題は「肝試しで2人が神社をめぐる」みたいなストーリーがあったことを知ったけど
kenkooさん「木の上のノードを2つの点が移動します」
ぼく「OK、解きます」
みたいな感じでスルーしてしまったので、なんだか申し訳なかった

day3 北海道大学セット

かずさんと motxx さんと、チームekmnotで参加しました
競プロを始めたばかりという人もいたので各自問題を分担することはせず、チームでA,B,D問題を解きました

A問題は与えられる文字列の添字が逆順( 11,10,9, ... ,2,1,0 )に振られていて悪質
かずさんと一緒にバグらせながらAC

B問題は motxx さんが「周期Tは必ず数列長Nの約数」みたいなことを言ってくれたのでバーッと書いてすんなりAC

D問題はお菓子を食べてたら解法が湧いたので実装。気をつけていたつもりが一箇所オーバーフローで1WAを食らいながらAC。
解法の確認で「チームメイトに数列を決めてもらい、僕がクエリを投げながら数列を当てる」ということを実際にやったときに、「Yazatenさん、なんかメンタリストみたいっすね」と言われたのがめっちゃツボだった

Dを通した段階であまり時間が残っておらず、あとは余った問題文をみんなで読んでただけだった

おわりに

チーム戦は一人よりもたくさんの問題に触れられてやっぱり楽しいです。組んでくれたみなさんありがとうございました。
解けなかったりチームの別の人が解いた問題をしっかり復習して、今後は長時間セットで座ってるだけの時間を減らすことができるように頑張ります！

2016-02-16

AOJ 0151: Grid

Grid | Aizu Online Judge

実装が面倒なやるだけっぽいですが、DPで書くとさくっと解けました。

遷移

左から、左上から、上から、右上からの4パターン。

状態の持ち方

dp[i][j][0] = i 行目 j 列目まで見た時、横向きにいくつ連続しているか
dp[i][j][1] = i 行目 j 列目まで見た時、縦向きにいくつ連続しているか
dp[i][j][2] = i 行目 j 列目まで見た時、右ななめ下向きにいくつ連続しているか
dp[i][j][3] = i 行目 j 列目まで見た時、左ななめ下向きにいくつ連続しているか

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back

int n;
int main(){
    int n;
    while(cin>>n&&n){
        int dp[256][256][4];
        rep(i,256)rep(j,256)rep(k,4)dp[i][j][k] = 0;

        vector<string> data(n);
        rep(i,n)cin>>data[i];
        
        int maxi = 0;
        rep(i,n){
            rep(j,n){
                if(data[i][j]=='1'){
                    dp[i][j][0] = ( j-1>=0          )*dp[i  ][j-1][0] +1;
                    dp[i][j][1] = ( i-1>=0          )*dp[i-1][j  ][1] +1;
                    dp[i][j][2] = ( i-1>=0&&j-1>=0  )*dp[i-1][j-1][2] +1;
                    dp[i][j][3] = ( i-1>=0&&j+1<n   )*dp[i-1][j+1][3] +1;

                    rep(k,4) maxi = max(maxi,dp[i][j][k]);
                }
            }
        }
        cout<<maxi<<endl;
    }
}

1日目 東京到着・ガイダンス

2日目 Central Europe Regional Contest 2014(CERC2014)

3日目 JAG 模擬アジア地区予選2016

4日目 2015-2016 XVI Open Cup

おわりに

おまけ

小論文

数学

英語

面接

その他

A問題

B問題

C問題

D問題

状態 dp[i][j]

遷移

国内予選当日まで

コンテスト

A問題

B問題

C問題

D問題

E問題

感想

考察・解法

day1 立命館大学セット

day2 会津大学セット

day3 北海道大学セット

おわりに

遷移

状態の持ち方

1日目東京到着・ガイダンス