Codeforces Beta Round #40 (Div2)

codeforces

参加はしてないですが、プラクティスで解いたので

A Translation

方針

回文になっているかどうか確かめる

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int main() {
  string s,t;
  cin>>s>>t;
  reverse(s.begin(),s.end());
  if(s == t) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}

B Martian Dollar

方針

明らかに2回以上取引することはないので、買う時と売る時の組み合わせを全部調べる

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
  int n,b,j,c,d;
  vector<int> a;
  cin>>n>>b;
  for(int i=0; i<n; ++i) {
    cin>>j;
    a.push_back(j);
  }

  int maxd = b;
  for(int i=0; i<n; ++i) {
    for(int j=i+1; j<n; ++j) {
      if(a[j] > a[i]) {
	int dol = b / a[i];
	int rem = b % a[i];
	maxd = max(maxd, dol*a[j] + rem);
      }
    }
  }

  cout<<maxd<<endl;
}

C Email address

方針

規則にしたがって置き換える

#include<iostream>
#include<string>
using namespace std;

int main() {
  string s;
  cin>>s;

  bool update = true;
  string next = string(1,s[0]);
  for(int i=1; i<s.length(); ++i) {
    if(i < s.length()-3 && s.substr(i,3) == "dot") {
      next += ".";
      i+=2;
    }else{
      next += string(1,s[i]);
    }
  }

  string nnext = string(1, next[0]);
  for(int i=1; i<next.length(); ++i) {
    if(i < next.length()-2 && next.substr(i,2) == "at") {
      nnext += "@";
      nnext += next.substr(i+2);
      break;
    }else{
      nnext += string(1,next[i]);
    }
  }

  cout<<nnext<<endl;
}

D Pawn

方針

位置とそこまでの和の(k+1)での余りの組み合わせでDPする

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

int chess[101][101];
int dp[11][101][101];
char trace[11][101][101];

int main() {
  int n,m,i,j,k,l;
  string s,tans = "";
  cin>>n>>m>>k;
  k++;

  memset(trace, 0, sizeof(trace));
  memset(dp, -1, sizeof(dp));
  rep(i,n) {
    cin>>s;
    rep(j,m) chess[i][j] = s[j] - '0';
  }

  rep(j,m) dp[(chess[n-1][j])%k][n-1][j] = chess[n-1][j];

  for(int i=n-1; i>0; --i) rep(j,m) rep(l,k) {
	if(dp[l][i][j] != -1) {
	  if(j > 0) {
	    int ts = chess[i-1][j-1] + dp[l][i][j];
	    if(dp[ts%k][i-1][j-1] < ts) {
	      dp[ts%k][i-1][j-1] = ts;
	      trace[ts%k][i-1][j-1] = 'L';
	    }
	  }
	  if(j < m-1) {
	    int ts = chess[i-1][j+1] + dp[l][i][j];
	    if(dp[ts%k][i-1][j+1] < ts) {
	      dp[ts%k][i-1][j+1] = ts;
	      trace[ts%k][i-1][j+1] = 'R';
	    }
	  }
	}
      }

  int ans = -1, di = 0, dj = 0, dl = 0;
  rep(j,m) if(ans < dp[0][0][j]) ans = max(ans, dp[0][0][j]),dj = j;

  cout<<ans<<endl;

  char c;
  if(ans >= 0) {
    while((c = trace[dl][di][dj]) != 0) {
      tans += string(1, c);
      dl = (dp[dl][di][dj] - chess[di][dj])%k;
      (c == 'L') ? dj++ : dj--;
      di++;
      if(di == n-1) break;
    }
    reverse(tans.begin(), tans.end());
    cout<<dj+1<<endl;
    cout<<tans<<endl;
  }
}

E 3-cycles

方針

k個の端点のグラフに対して、端点の次数の小さい方から閉路ができないように貪欲に辺を追加する
求めたいグラフはどうやら2部グラフになる気がする(嘘かもしれない) 

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

int used[100][100];
int deg[100];
int ans;

void add_edge(int p,int n) {
  int i,j;

  priority_queue<pair<int,int> ,vector<pair<int,int> >, greater<pair<int,int> > > Q;
  memset(deg, 0, sizeof(deg));
  rep(i,n) rep(j,n) if(used[i][j]) deg[i]++,deg[j]++;
  rep(i,p) Q.push(make_pair(deg[i],i));

  vector<pair<int,int> > pv;
  while(!Q.empty()) {
    pair<int,int> pi = Q.top(); Q.pop();
    bool isable = true;
    rep(j,p) if(used[j][pi.second] != 0 && used[p][j] != 0) isable = false;
    if(isable) used[p][pi.second] = used[pi.second][p] = 1,ans++;
  }
}

int main() {
  int n,i,j;
  ans = 0;
  cin>>n;
  memset(used, 0,sizeof(used));

  rep(i,n) add_edge(i,n);

  cout<<ans<<endl;
  rep(i,n) REP(j,i+1,n) if(used[i][j]) cout<<i+1<<" "<<j+1<<endl;
}