ヘクトのメモ

なんとなくいろいろ書いていくと思います.

ICPC 2015 国内予選

チームnocowとして今年は参加しました.(記号制限でチーム名変更)

チームメンバー
@osrehun
@icchyr
@xthexworldx

結果から書くと3完39位でした.

最後の1分で同じ大学のチームに4完されたので,今年もICPCアジア地区には行けず...

以下詳細なタイムスケジュールと感想


0:00

まず,チームメイトがAを読みながら,スクリプトとテンプレートなどを書く.

その間にBを読むとやるだけなので紙コーディングをすぐにする.

Aがバグったぽいので少し見る.GAPの更新を忘れていただけ.

修正して A AC

その後に,紙コーディングしてあったBをすぐに移して B AC

その間にチームメイトがCを読んで方針が立ったということでCを任せる.

そして,Fを読む.MSTみたいで辺の制約が600からクラスカルを何度もやるのだと考える.

ただ,Fで2種類の辺をうまく使う方法が分からないので飛ばす.

Hを見る.3次元はヤバいのではとスキップすることにした.

1:00 その間にC AC

その後ににチームメイトと共にD,Eを読む.Eはこうすればよいということを教えてくれるが実装方針が思いついていない.少し,考えるが難しそうということでパス.

Dは制約を見て,まあDPじゃないですかということでチームメイトに任せる.

そして,チームメイトがGを読むとこれは頂点を選んで折り返すだけと教えてくれる.
ここから泥沼に... Convex_cutをライブラリとして持っていたので多角形を選んだ2点の垂直二等分線で切る.
ここから,点を反射させるという部分まで実装.そして,周長を求めるという点で少しずつ議論していく.
ここで,方針が詰め切れていないので二転三転して時間が過ぎていく.

一方,引き続きDを考えてもらうもチームメイトが詰んでしまう...

2:30

ここで,Gを実装してしまっているので方針を変えずにそのまま行いタイムアップ

3:00

感想

最初の1時間は3問すんなり通って,そこからいろいろな問題の可能性を検討できたのは良かったけど,解ける問題を確実に探して集中して解くという点が弱かった.
特に解法を考えるチームメイトが詰んでしまい,2人の実装が怪しい2:30の時点で3人で1問に取り組むでも良かったかもしれない.
また,解法に確信が持てないけど,実装できる方針と実装出来ない方針には大きな差があり,そこを考慮すべきだったなと反省点はいくつか.

なにより,国内予選終わった後にまともにDを読めていなかったので,しっかり読んでみたら20分で実装できて本番のデータセットで通ってしまった...

ただ,練習を積み重ねてチームの特徴を把握すれば,強くなる余地はあるので,夏合宿への参加とかして,チームとしての経験を積んで再チャレンジですかね.
(あと研究が忙しくなければ)

大学のサークルとしては,今年は去年より1チーム増えて3チーム参加となり,1年生も1完はしてくれました.
(ちなみに,毎年ここぞという時に力を発揮するライバルチームは強いなと)

実装したDのソースコードを載せておきます.

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

int n;
int d[110];

const int vmax=499*100+1;
int dp[110][vmax];
int dp2[110][vmax];

int main(void){
	while(cin >> n,n){
		rep(i,n) cin >> d[i];
		rep(i,n+1)rep(j,vmax) dp[i][j]=-1,dp2[0][0]=0;
		dp[0][0]=0;
		rep(i,n)rep(j,vmax){
			if(dp[i][j]==-1) continue;
			if(dp[i+1][j]<dp[i][j]||(dp[i][j]==dp[i+1][j]&&dp2[i][j]<dp2[i+1][j])){
				dp[i+1][j]=dp[i][j];
				dp2[i+1][j]=dp2[i][j];
			}
			int next=dp[i][j];
			int next2=dp2[i][j]+d[i];
			int change=(5000-d[i])%1000;
			int nj=j+change;
			if(nj>=500) next++,nj-=500;
			if(dp[i+1][nj]<next||(next==dp[i+1][nj]&&next2<dp2[i+1][nj])){
				dp[i+1][nj]=next;
				dp2[i+1][nj]=next2;
			}
		}
		int ans=0,ans2=0;
		rep(j,vmax){
			if(ans<dp[n][j]||(dp[n][j]==ans&&dp2[n][j]<ans2)){
				ans=dp[n][j];
				ans2=dp2[n][j];
			}
		}
		cout << ans << " " << ans2 << endl;
	}
}