はやし屋

競技プログラミングのメモ きたない

ICPC 2015 アジア地区予選参加記

課題に追われてるのでまともに推敲していません.
いつか添削します.

この記事はTUT Advent Calendar 10日目の記事です.
前日12/9はayafmyさんの他系の単位の食べ方、そして他系の単位を食べることによるその効果。です.



はやしやと言います.現在はTUTのB1です.
競技プログラミングを高校の時にやってました.大学入学後も少しやっています.

今回はICPCという(競技)プログラミングコンテストについて書きたいと思います.
プログラミングコンテストにはいろんな種類がありますが,
ここで書くのは,簡単に言うと時間内に問題を多く速く正確に解くというものです.(chokudaiさんの記事がわかりやすい)
ICPCは10問ぐらいの問題をチームで5時間で解きます.結構長いです.

6月にあった国内予選にB3のfoldoriさん,arukukaさんと僕(hysy)でチームGO TO THE FUTUREとして参加し,
B枠(2012以降に予選通過していなかったチームに与えられる奨励枠)で通過しました.
TUTからは5年ぶりのアジア地区予選出場になります.

大会はこのようなスケジュールで行われました.

1日目

  • 会場に付き,手続きを済ませ入場する.
  • 久しぶりに高校の先輩であるsateさん,furuwさん,roxionさんに会う.
  • 開会式の後,お菓子を食べたり,参加賞を漁ったりする.
  • 大会専用PCの環境設定をする.右シフトが押しにくい.(文字キーと同じサイズのタイプ)
  • Practiceが始まる.3完する.
  • JavaChallengeが始まる.C++でも良いらしい.
  • 行路で見た問題と制約とかが違うので読みなおす.
  • 幅優先で次行けるマスを探していたりしていたが,提出時にDebugの出力を消すのを忘れる.
  • その後は筑波大学で歓迎会があり,いろんな人と話した.
  • 同学年で大学入ってから競技プログラミング始めて国内予選通過した人がいてビビる.
  • チームプレゼンで114514を連想させるチーム名があり,例のアレが流れる.



  • その後はsateさんの部屋にいろんな大学,高専の人が集まり雑談する.
  • 1:30ぐらいに寝る.

2日目

  • 6:30に起き,朝食を食べ,会場に向かう.
  • 会場につき,しばらくして中に入り,準備を終えたらすぐコンテストが始まる.


  • コンテスト開始 9:20~14:20
  • 順位表はこちら(チーム名をクリックするとTwitter名等表示される).
  • 全問題はこちら(pdf)
  • A問題をみんなで見る.
  • このルールで考えられる数字はそこまで大きくないので,ある程度の長さまで取ればいいんじゃないかと考える.
  • foldoriさんが実装する.
  • 37分: A問題Accept
  • この頃向かいの上海交通大学チームが爆速でFirst Acceptを連発し,Acceptすると貰える風船とFAすると貰える風船がたくさんあった.めちゃくちゃ怖かった.
  • A問題を実装している間arukukaさんと僕でB問題を見る.
  • 読んでみて二分探索と気付く.
  • 二人で解法を確認しながらarukukaさんが実装する.
  • なんとか書き終え,サンプルもあったので提出したが Time Limit Exceeded.
  • 二分探索でTLEって??って3人でDebugする.
  • 色々試したところ,探索終了の条件文のepsが1e-9(だった気がする)が小さすぎるので時間がかかったことに気づく.
  • 1e-8ぐらいにして提出.TLEは取れたがWrong Answer
  • ん~??と思いバグりそうなテストケースを試す.
  • 左からやって円柱を飛ばした時におかしくなったと気づく.(サンプルをよく確認していなかったかも知れない)
  • テストケースを再確認して提出.
  • 79分: B問題Accept
  • C問題をみんなで見る.
  • START,もしくはGOALから再帰的にやる,ループが存在するのでそこをうまくやって...(最大ケースが有向グラフかつ完全グラフだからつらそう)みたいなことを考えるが,解けず.
  • B問題を考えてたり,C問題を実装したりしている間,foldoriさんがD問題を考えていて実装できそうだったが,C問題の実装を残り30分までやって紙Debugに変えたので,D問題を解く時間が足りなかった.
  • コンテスト終了



  • どこが悪かったかをチームで相談したら,自分たちが時間内に解ける問題を見分け,実装していたらD問題ももしかしたら解けたかもしれなかったことが挙げられた.
  • もっと時間と力量を考えることが大切と思い,コンテスト慣れしなきゃと思った.
  • しばらくして別部屋に移動.コンテスト問題の解説が始まる.
  • E以降よくわからない.
  • JavaChallengeの結果が出る.
  • ニ日目に書いてある通り,Debugの出力が取れていなかったので全く期待してなかった.
  • 実際なんにも動かなかったが,なぜか準決勝にボーダー通過する.謎.
  • 優勝チームはサンプルコードを提出しただけだったので爆笑する.
  • 実装が2時間しか無いからこういうこともあるんだなあと思った.
  • 順位が発表される.終了30分前に凍結された順位表が表示され,下から順に順位表が更新されていく機能に感動した.
  • 自分たちの結果は変わらなかったが他のチームが変わるの見てて面白かった.
  • 上海交通大学チームが全完WA0FirstAcceptいっぱいで1位だった.圧倒的.
  • 閉会式後は懇親会が行われた.
  • いろんな企業ブースがあり,いろんなものをもらった.
  • TUTのOBでICPC(2007~2010)に出場していた人,JAG夏合宿であった人と話す.
  • 企業の人と話してたら,連日の寝不足で倒れそうになり心配される.
  • 問題を解くと景品がもらえるブースが多かったが頭が回らず解けない.
  • 最後に記念撮影をして終了.
  • 研修センターに戻る.
  • 到着し風呂に入った後寝ようと思ったけれど,なかなか寝付けなかったので,後半の問題みたり,参加記書いたり,Twitterみたりしていた.
  • 23:30ぐらいになるとTLにsateさんのクソツイートが流れ始める.予定調和.
  • これ好き.

  • お酒の力って怖いなあと思いながら寝る.

3日目

  • 適当に起きて,朝食をとる.
  • つくば研修センターを出発する.
  • 道中の景色は研究施設が必ず目に入ったので,研究学園都市すげーと思った.
  • 午前はサイバーダイン・スタジオというところに行く.
  • パワードスーツを作っているらしく,期待以上に面白かった(個人の感想).
  • 操作者がスーツを着て小さいロボットを遠隔操作するみたいなビデオを見る.
  • 「感度良すぎィ!!」みたいなセリフがあり,何を伝えたかったのかわからなかったけど面白かった.

f:id:Hayashiya:20151130142441j:plain

  • 量子力学がほげほげって言ってたが,大半は理解してないと思う.
  • その後はつくば駅に着き,解散.
  • 帰りは秋葉原でおみやげを買ったり,オタクショップに行って23:00ぐらいに寮に帰る,天伯臭が迎えてくれる.


内輪ネタやよくわからない単語が多かった気がします.許してください.
写真とか撮ろうとおもってたけど忘れていたので,文字ばかりの記事となってしまいました.許してください.

プログラミングコンテストは予選通過すると,いろんな企業の人,学生と話せたり,世界トップのコンテスト中の様子を見れたり,貴重な経験ができます.(交通費宿泊費もタダ)(インターンの募集とかやってた).

僕はだいぶ競技プログラミングから離れてましたが,今回のICPCでOBの方,先輩,企業の方等から,B1でプロコン知ってて,こういう経験をしているのはとても良いことだし,またやってみたら?と言われたので,またオンラインジャッジを埋めたり,コンテストに参加したり活発になりたいです,

大学に入ってから今年でNAPROCKやJAG夏合宿,ICPCに出れたので(ほとんど先輩たちのおかげ),楽しかったです.
また来年も出場できるように日頃から頑張りたいです.



明日12/11はShun_40さんによる 入院のすゝめ です.


TUTから学外院に行きたい人にとって参考になると思います.

AOJ 0215: Pachimon Creature

約二年ぶりに解きなおした.懐かしい.
属性ごとの座標を配列に保存して,
dp[今の属性][今の属性から伸びてる辺が何番目のものか] = 最短路;
みたいな感じでやりました.
きれいに書きたい.

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<map>
#include<cstring>
using namespace std;
 
int w , h;
struct Point {int y , x;};
 
vector < Point > el[5];
Point S , G;
int dp[5][1024];
int start_el;
 
void init(){
  for(int i = 0 ; i < 5 ; ++i)el[i].clear();
}
 
int dist(Point a , Point b){
  return abs(a.y-b.y) + abs(a.x-b.x);
}
 
//                      element idx 
int solve(int element , int idx , int fl){
  if(~dp[element][idx])return dp[element][idx];
  if((element+1)%5 == start_el)return dist(el[element][idx],G);
  int ret = 1 << 28 ;
  for(int i = 0 ; i < el[(element+1)%5].size() ; ++i){
    int d = solve((element+1)%5,i,fl|1);
    d += dist(fl ? el[element][idx] : S,el[(element+1)%5][i]);
    ret = min(ret,d);
  }
 
  return dp[element][idx] = ret;
}
 
int main(void){
  while(cin >> w >> h && h){
 
    init();
     
    for(int i = 0 ; i < h ; ++i){
      string s;cin >> s;
      for(int j = 0 ; j < s.size() ; ++j){
	if(isdigit(s[j]))el[s[j]-'1'].push_back((Point){i,j});
	if(s[j] == 'S')S = (Point){i,j};
	if(s[j] == 'G')G = (Point){i,j};
      }
    }
    int ret = 1 << 28 , ret_el = -1;
    for(int i = 0 ; i < 5 ; ++i){
      start_el = i;
      memset(dp,-1,sizeof(dp));
      int r = solve(i,0,0);
      if(r < ret){
	ret = r;
	ret_el = i;
      }
    }

    if(~ret_el)cout << ret_el + 1 << " " << ret << endl;
    else cout << "NA" << endl;

  }
  return 0 ;
}

AOJ 2585: 1 Day Passport

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2585

ICPCに出ることになったので,久々に競プロしました.
dijkstraは忘れていなかったのでよかった.
問題が長かった.構造体の使い方忘れてた.
徹夜明けでもありバグがひどく出た.1月半後のICPCまでには極力減らしたい.


問題概要は省略.

bitdp + dijkstraで解きました.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cstring>
 
using namespace std;
 
typedef long long ll;    
typedef pair < int , int > Pi;    
typedef pair < int , Pi > Pii; 
   
#define INF (1 << 28)    
#define sz(z) (int)((z).size())
#define fr first    
#define sc second
#define reps(i,j,n) for(int i = j ; i < n ; ++i)    
#define rep(i, n) reps(i,0,n)    
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;   

int N , M , H , K ;
int S , T , P;
int pass_corp[256],pass_cost[256];
int dp[256];
int min_cost[128][32];

struct Edge { int to , cost , time , corp ;}; 
vector < Edge > edge[128];


void init(){
  rep(i,128)edge[i].clear();
  rep(i,256)pass_corp[i] = 0;
  rep(i,256)dp[i] = INF;
}

int dijkstra(int pass){

  priority_queue < Pii ,vector < Pii > ,greater < Pii > > que;
  // cost, time , v
  que.push(make_pair(dp[pass],make_pair(0,S)));
  rep(i,128)rep(j,32)min_cost[i][j] = INF;

  while(!que.empty()){
    Pii tp = que.top();que.pop();
    int cost = tp.fr , time = tp.sc.fr , v = tp.sc.sc;
    if(v == T)return cost;
    rep(i,sz(edge[v])){
      Edge e = edge[v][i];
      int n_time = time + e.time;
      if(n_time > H)continue;
      int n_cost = (pass & (1 << e.corp)) ? cost : cost + e.cost;
      if(n_cost < min_cost[e.to][n_time]){
	min_cost[e.to][n_time] = n_cost;
	que.push(make_pair(n_cost,make_pair(n_time,e.to)));
      }      
    }
  }
  return INF;
}


void mk_table(){
  int ret = INF ;
  dp[0] = 0;
  rep(i,1<<K){
    if(dp[i] != INF){
      rep(j,P){
	dp[i|pass_corp[j]] = min(dp[i|pass_corp[j]],dp[i]+pass_cost[pass_corp[j]]);
      }
    }
  }
  return ;
}

int main(void){
  while(cin >> N >> M >> H >> K &&N){
    init();
    rep(i,M){
      int a , b , cost , time , corp;
      cin >> a >> b >> cost >> time >> corp;      
      a-- , b-- , corp--;
      edge[a].push_back((Edge){b,cost,time,corp});
      edge[b].push_back((Edge){a,cost,time,corp});
    }

    cin >> S >> T ;
    cin >> P;
    S--,T--;
    rep(i,P){
      int corp_num , corp_cost;
      cin >> corp_num >> corp_cost;
      rep(j,corp_num){
	int corp;
	cin >> corp; corp--;
	pass_corp[i] |= 1 << corp;
      }
      pass_cost[pass_corp[i]] = corp_cost;
    }

    mk_table();

    int ret = INF;
    rep(i,1<<K)if(dp[i] != INF)ret = min(ret,dijkstra(i));
    if(ret != INF)cout << ret << endl;
    else cout << -1 << endl;
  }
  return 0;
}

pku : 3252 Round Numbers

pkuかpojかどっちなんですかね...
http://poj.org/problem?id=3252

問題は

整数S,F(1 ≤ S < F ≤ 2,000,000,000)が与えられて

S以上F以下の Round Number の個数を求める問題です。

Round Numberというものは、
整数を二進数に直したときに、

"たっているビット数" <= "たっていないビット数"

であるような数です。

具体的には
1001 とか 10001 とか 100101 とか 100011001 です。


解法はZigZagと同じように桁でやりました。もっと簡単で効率的な解法が多分ある。

少しバグらせたけどデバッグうまくできてよかったです!

int dp[64][64][64][2][2];

int solve(const vector <int>&v,int idx,int n0,int n1,bool free,bool begin){

  if(idx == -1)return n0>=n1;

  if(~dp[idx][n0][n1][free][begin])return dp[idx][n0][n1][free][begin];

  int r = !free?v[idx]:1;
  int ret = 0 ;
  for(int i = 0 ; i <= r ; ++i){
    bool ch = !(r==i);
    if(begin){
      if(i==0){
	ret += solve(v,idx-1,0,0,free|ch,true); 
      } else {
	ret += solve(v,idx-1,n0,n1+1,free|ch,false);
      }
    } else {
      ret += solve(v,idx-1,n0+(i==0),n1+(i==1),free|ch,false);
    }
  }

  return dp[idx][n0][n1][free][begin] = ret;
}

int getNum(int x){
  vector < int > v;
  while(x){
    v.pb(x&1);
    x >>= 1;
  }
  return solve(v,v.size()-1,0,0,false,true);
}

int main(){
  memset(dp,-1,sizeof(dp));
  int a , b;
  cin >> a >> b;
  cout << (getNum(b)-getNum(a-1)) << endl;
  return 0;
}

AOJ 2022: Princess, a Cryptanalyst

後ろにつなげていくイメージのbitdp
INF足りなくてWAした~~~~~~~~~~~
""でもよかったような

#include<iostream>
#include<algorithm>
using namespace std ;
int n ;

string s[11];
string G[11][11];
string dp[11][1<<11];

const string INF = "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";

string MIN(string a , string b){
  return a.size()==b.size()?min(a,b):a.size()<b.size()?a:b;
}

string solve(int u , int v){
  if(u == (1<<n)-1)return "";
  if(dp[v][u] != INF)return dp[v][u];
  string ret = INF;
  for(int i = 0 ; i < n ; ++i){
    if(!(u&(1<<i)))ret = MIN(ret,G[v][i]+solve(u|1<<i,i));
  }
  return dp[v][u] = ret;
}

int main(){
  while(cin >> n && n){
    for(int i = 0 ; i < n ; ++i)cin >> s[i];

    int u = 0 ;
    for(int i = 0 ; i < 10 ; ++i){
      for(int j = 0 ; j < 1 << 10 ; ++j){
	dp[i][j] = INF;
      }
    }

    for(int i = 0 ; i < n ; ++i){
      for(int j = 0 ; j < n ; ++j){
	if(i == j)continue;
	if(!(u&(1<<j)) && !(u&(1<<i))){
	  if(~s[i].find(s[j])){
	    u |= 1 << j;
	  }
	}
      }
    }

    for(int i = 0 ; i < n ; ++i){
      for(int j = 0 ; j < n ; ++j){
	if(i == j)continue;
	G[i][j] = s[j];
	if(!(u&(1<<j)) && !(u&(1<<i))){
	  for(int k = 0 ; k < s[i].size() ; ++k){
	    string cut = s[i].substr(k);
	    int Idx = s[j].find(cut);
	    if(Idx == 0){
	      string in = s[j].substr(cut.size());
	      G[i][j] = in;break;
	    }
	  }
	}
      }
    }

    string ret = INF;
    for(int i = 0 ; i < n ; ++i){
      if(!(u&(1<<i)))ret = MIN(ret,s[i]+solve(u|(1<<i),i));
    }
    cout << ret << endl;
  }
  return 0;
}

AOJ 0570: Zig-Zag Numbers

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0570

下手の横好きを参考にやりました。
こんなの初めてだq
頭いいなあ(感動のあまり死亡)
dp[今の桁][前の桁の数字][前の桁のupdown][前までのmod][今すべての数字を使えるか];
でやった

本番でときたいもんだなあ

#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<cstring>

using namespace std;

#define MOD 10000

vector < int > A , B; 
int M;

void sub1(vector < int >&q){
  for(int i = q.size()-1 ; i >= 0 ; --i){
    if(q[i] == 0){
      q[i] = 9;
    } else {
      q[i]--;
      return ;
    }
  }
  return ;
}

//     idx,prv,^v,mod,free
int dp[505][10][3][505][2];


// updown 増:0 減:1 0:2
int ZigZag(const vector < int > v , int idx , int prv , int updown , int mod , bool free)
{

  if(idx == v.size())return !mod;

  if(~dp[idx][prv][updown][mod][free])
    return dp[idx][prv][updown][mod][free];
  
  int r = (free ? 9 : v[idx]);
  int ret = 0;

  for(int i = 0 ; i <= r ; ++i,ret %= MOD){

    if(updown == 0 && prv <= i)continue;
 
    if(updown == 1 && prv >= i)continue;

    if(updown == 2 && prv && prv == i)continue;

    int u ;
    if(updown == 2){
      if(prv == 0){
	u = 2;
      } else if(prv > i){
	u = 1;
      } else {
	u = 0;
      }
    } else u = !updown;
    ret += ZigZag(v,idx+1,i,u,(mod*10+i)%M,free|(i!=v[idx]));
  }

  return dp[idx][prv][updown][mod][free] = ret % MOD;
}

int main(){
  string a , b ;cin >> a >> b >> M;
  for(int i = 0 ; i < a.size() ; ++i)
    A.push_back(a[i] - '0');
  for(int i = 0 ; i < b.size() ; ++i)
    B.push_back(b[i] - '0');

  sub1(A);

  memset(dp,-1,sizeof(dp));
  int ra = ZigZag(A,0,0,2,0,false);
  memset(dp,-1,sizeof(dp));
  int rb = ZigZag(B,0,0,2,0,false);

  int ret = (rb - ra + 10000)%10000; 

  cout << ret << endl;
  return 0;
}

AOJ 0540: Amidakuji

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0540

辿るとできる
面倒だった
無駄なくやるとよい

#include<algorithm>
#include<iostream>
#include<vector>
#include<map>

using namespace std;

int main(){
  int n , m , h , k;
  while(cin >> n >> m >> h >> k &&(n|m|h|k)){
    vector < int > wi[h];
    vector < int > point(n) , p(n);

    for(int i = 0 ; i < n ; ++i){
      cin >> point[i];
      p[i] = i;
    }

    for(int i = 0 ; i < m ; ++i){
      int a,b;
      cin >> a >> b;
      wi[b-1].push_back(a-1);
    }

    for(int i = h-1 ; i >= 0 ; --i){
      for(int j = 0 ; j < wi[i].size() ; ++j){
	int a = wi[i][j];
	swap(point[a],point[a+1]);
      }
    }


    int AL = 0 ;
    for(int i = 0 ; i < k ; ++i)AL += point[i];
    int ret = AL;

    for(int i = 0 ; i < h ; ++i){
      for(int j = 0 ; j < wi[i].size() ; ++j){
	int a = wi[i][j];
	int A = p[a];
	int B = p[a+1];
	swap(p[a],p[a+1]);
	if(A > B)swap(A,B);
	if(A < k && B >= k && point[A] > point[B]){
	  ret = min(ret,AL-point[A]+point[B]);
	}
      }
    }
    cout << ret << endl;
  }
  return 0;
}