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

2016-02-03

DISCO presents ディスカバリーチャンネルプログラミングコンテスト2016 予選 B問題ディスコ社内ツアー

コンテスト中に解法を思いつけなかったので、AtCoderの解説とTwitteを参考に解きました。

問題

B: ディスコ社内ツアー - DISCO presents ディスカバリーチャンネルプログラミングコンテスト2016 予選 | AtCoder
面白さがそれぞれA_iの部屋が環状にならんでいて、面白さが広義単調増加となるように部屋を回る。
1番目の部屋を出発点としたとき何周する必要があるかをもとめる。
みたいな問題

解法

実際にぐるぐるまわる単純なシュミレーションを書くとO(N^2)になり部分点の20点が得られます。

満点解法もぐるぐるまわるシュミレーションなのですが、面白さが等しい部屋をまとめて管理することで高速化でき、O(N)で解くことができます。

まわる部屋はかならず広義単調増加になっているため、面白さが等しい部屋は必ず続けて通ることになります(例 : 2 1 3 2 2 2 -> 1 2 2 2 2 3 )
これに注目し、キーを「面白さ」、値を「"その面白さである部屋のindex"をもつvector」のmapを使用して、面白さが等しい部屋をまとめて管理します。
このmapを利用してシュミレーションを行います。

基本的にはmapのキーが小さい順に舐めていくだけなのですが、今いる部屋の更新の際に工夫が必要になります。
説明を簡単にするため、「map[i]」と書いたときのiを、mapのキーの中でi番目に小さいものとします。
また、map[i]の値(vector)は昇順にソートされており、大きい値が格納されている方を右と呼ぶことにします。

現在いる部屋のindexをnowとし、はじめは-1に初期化しておきます。
すると次に向かう部屋は「map[0]の値(vector)のうち、nowのindexから右にたどっていき、はじめに見つかったもの(右端にくると左端にローテーションする)」となります。
その後、向かった部屋と同じ面白さの部屋を全てまわることになります。
つまり今いる部屋のindexをnowとすると、以下のようにnowの値を更新していくことができます。

next = upper_bound( map[i].begin(),map[i].end() , now ) - map[i].begin();
now = map[i][  (next - 1 + map[i].size()) % map[i].size()  ]

now==1の時の更新を図にするとこんな感じで、この例ではnowの値は1から0に更新されます。
f:id:Yazaten:20160203074018p:plain

よく読むとわかるのですが、「(next - 1 + map[i].size()) % map[i].size()」は基本的にはnext-1の結果と一致し、next==0のときにのみ「map[i].size()-1」となります。

面白さが等しい部屋の左端と右端だけを持つと今いる部屋の更新がうまく行かず、例えば「2 1 3 2 2 2」というケースに対して3と出力してしまう(正解は2)ので注意が必要です。

#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()
#define pb push_back

int main(){
    int n;
    cin>>n;
    vector<int> vec(n);
    map<int,vector<int>> mp;
    rep(i,n){
        cin>>vec[i];
        mp[vec[i]].pb(i);
    }
    
    int count=1,now=-1;
    for(auto itr = mp.begin();itr!=mp.end();itr++){
        vector<int> sec = itr->second;
        sort(all(sec));
        
        int p = lower_bound(all(sec),now)-sec.begin();
        if(  now>sec[  (p+sec.size()-1)%sec.size()  ]  )count++;
        now = sec[  (p+sec.size()-1)%sec.size()  ];
        
    }
    if(now == 0)count--;
    cout<<count<<endl;
}

2015-12-13

CODE FESTIVAL 2015 参加記まとめ

CODE FESTIVAL 2015 の参加記まとめが少し寂しかったので、僕が観測できた範囲の参加記をメモしておきます。

togetter版 -> CODE FESTIVAL 2015 参加記まとめ - Togetterまとめ

参加記

投稿日が新しい順に並んでいます。