ICPC2014 Domestic 参加記

参加記

5月某日

とか嘆いていたら

やったね！


というわけで7/11 16:30-19:30に開催されたICPC国内予選に参加してきました。

チームメンバーは
@negi_magnet さん(高専編入, B3)
@shimauma_zzz さん(高専編入, B3)
と私。

まとめ

Aを自分が通す。
このとき"各商品について消費税を計算する"ってのを見逃してて答えがズレたときは焦った

Bを@negi_magnetさんが通す。
途中バグあったので、Dの実装と平行してやる。

Cを@shimauma_zzzさんが「バグがああ」と叫んでました。

Dを自分が通す。
全列挙だったので、時間どれくらいかかるか不安でしたが案外すぐでてきた。

Cの解法を見直し、@negi_magnetさんのアイデアでにぶたんによる実装へ変更することに。
@shimauma_zzzさんが実装している間、残った二人でE,Fの解法模索。

Eの解法を思いついた。
Cのバグが取れなかったので、Eの実装と平行して行うことに。

Eもバグる(迫真)
終わってから気づいたんですが、Eはそもそも解法合ってたのかわからないです。要検証

残り30分くらいになって、 CとEを入れ替えながらデバッグ。

しかし、結局デバッグは終わらず予選終了。

結果は3完50位
○○-○---

反省

AとDもうすこし早解きできればなと思いました。
問題の誤読とか、実装の曖昧さとかがあったので結構時間がかかってしまいました。

Cについては初見で「ｳｯ幾何だ」ってなってしまったの良くなかった。
解法をあんまり理解できてなかったので、デバッグに協力し切れなかった。

Eは、アレでよかったのかなぁ・・・。

来年への課題(実装力と思考力)が大量にできたので、頑張ろう。

University Tsukuba

今年度うちから出たチーム(5チーム)は全て50位以上に入っていました(祝)
最下位はうちのチームでしたが、TOPは3位に入り、もう1チームが国内突破していました！
おめでた。

来年へ向けて

やっぱり年齢差があるとつらいですね・・・。
固定した面々でチームを組んで、毎年ICPCに挑みたいと思っていましたが、どうも辛そうです。
今年チームを一緒させてもらった先輩方はB3で、短くてあと2年で卒業ですからね。

今からチーム固定は厳しいので、来年くらいまではサークルの先輩方にお世話になるかもしれません。
いつかメンバーを決めたいなぁ・・・。

駆け出しでも良いので、チーム組みたい！って人いたら声かけてください:;(∩´﹏`∩);:

あとは精進をします。来年までの目標は

・今まで解いた問題にプラスしてあと1000問以上解く

・Topcoderの色を黄色く安定させる(現状Div2)

頑張るぞー！！！！

SRM 626 div2

競プロ

250

class SumOfPower {
public:

	int findSum( vector <int> array ) {
		vi v(array);

		int sum = 0;
		for(int i=1;i<=v.size();i++){
			for(int k=0;k<v.size();k++){
				if(k+i > v.size())continue;
				for(int j=k;j<k+i;j++){
					sum += v[j];
				}
			}
		}

		DUMP(sum);
		return sum;
	}
};

500

class FixedDiceGameDiv2 {
public:
	double getExpectation( int a, int b ) {
		int sums = 0;
		for(int i=1;i<=a;i++){
			for(int j=1;j<=b;j++){
				if(i>j)sums++;
				else break;
			}
		}

		double ret = 0;
		for(int i=1;i<=a;i++){
			int cnt = 0;
			for(int j=1;j<=b;j++){
				if(i>j)cnt++;
				else break;
			}
			ret += (double)i * ((double)cnt/(double)sums);
		}
		return ret;
	}
};

1000

long long dp[1002][50];
int d[51][51];
class NegativeGraphDiv2 {
public:
  long long findMin( int N, vector <int> s, vector <int> t, vector <int> weight, int charges ) {

    for(int i=0;i<1000;i++){
      for(int j=0;j<50;j++){
	dp[i][j] = INF;
      }
    }
    for(int i=0;i<50;i++){
      d[i][i] = 0;
      for(int j=0;j<50;j++){
	if(i!=j)d[i][j] = INF;
      }
    }
    for(int i=0;i<s.size();i++){
      s[i]--;t[i]--;
      if(s[i]!=t[i])d[s[i]][t[i]] = weight[i];
    }
    for(int k=0;k<50;k++){
      for(int i=0;i<50;i++){
	for(int j=0;j<50;j++){
	  d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	}
      }
    }
    for(int i=0;i<N;i++)dp[0][i] = d[0][i];
    for(int k=1;k<=charges;k++){
      for(int i=0;i<s.size();i++){
	dp[k][t[i]] = min(dp[k][t[i]], dp[k-1][s[i]] - weight[i]);
      }
    }
    long long ans = INF;
    for(int i=0;i<=charges;i++)ans = min(ans, dp[i][N-1]);
    return ans;
  }
};

Competition

easy若干読めなかった。
midは期待値求めるの時間かかった。
結果：○○-

Practice

hardを解いた。

解法

  • easy

特に必要無いよね

  • mid

これも・・・必要ないよね。

  • hard

Warshall-Floydでchargesが0の場合を求めてから
chargesを使った場合に関してDP。
Warshall-Floydを使わない場合はDPにNのループが付随するらしい。
まぁでも、これのほうが早いと思います。

hard、div1だと行列累乗じゃないと解けないって聞いたけど、まださっぱりわからん。

AOJ 2200 Mr. Rito Post Office

競プロ

問題文

日本語なので省略
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2200

解法

動的計画法
dp[i][j] : i番目まで集配するとき、船をjに泊めていた場合にかかる最小のコスト
陸と海の距離に関してはWarshall-Floydで求めた。
ただ、Dijkstraでもできるらしい(知らん)

コード

//-------------include
#include<cstdio>
#include<string>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<vector>
#include<list>
#include<deque>
#include<functional>
#include<sstream>

//-------------define
#define ALL(a)  (a).begin(),(a).end()
#define PB push_back
#define MP make_pair
#define SORT(c) sort((c).begin(),(c).end())
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define CLR(a) memset((a), 0 ,sizeof(a))
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define fi first
#define se second
#define INF 1 << 28

//-------------namespace
using namespace std;

//-------------inline
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//-------------typedef
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;

//-------------var
int dx[]={0,-1,0,1,1,1,-1,-1};
int dy[]={1,0,-1,0,1,-1,1,-1};

int l[201][201];
int s[201][201];
int dp[1001][201];

int main()
{
  int n,m;
  while(cin >> n >> m,n){
    for(int i=0;i<200;i++){
      s[i][i] = l[i][i] = 0;
      for(int j=0;j<200;j++){
        if(i!=j)s[i][j] = l[i][j] = INF;
      }
    }

    for(int i=0;i<1000;i++){
      for(int j=0;j<200;j++){
        dp[i][j] = INF;
      }
    }

    for(int i=0;i<m;i++){
      int a,b,t;
      char p;
      cin >> a >> b >> t >> p;
      a--;b--;
      if(p=='S'){
        s[a][b] = s[b][a] = t;
      }else{
        l[a][b] = l[b][a] = t;
      }
    }

    for(int k=0;k<n;k++){
      for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
          s[i][j] = min(s[i][j], s[i][k] + s[k][j]);
          l[i][j] = min(l[i][j], l[i][k] + l[k][j]);
        }
      }
    }

    int r;
    cin >> r;

    vi v(r);
    for(int i=0;i<r;i++){
      cin >> v[i];
      v[i]--;
    }

    dp[0][v[0]] = 0;
    for(int i=1;i<r;i++){
      for(int j=0;j<n;j++){
        for(int k=0;k<n;k++){
          dp[i][k] = min(dp[i][k], dp[i-1][j] + l[v[i-1]][j] + s[j][k] + l[k][v[i]]);
        }
        dp[i][j] = min(dp[i][j], dp[i-1][j] + l[v[i-1]][v[i]]);
      }
    }

    int ans = INF;
    for(int i=0;i<n;i++){
      ans = min(ans, dp[r-1][i]);
    }
    cout << ans << endl;
  }
  return 0;
}