SRM648参加しました。

今回は、日本時間では21時開始で時間的には参加やすい時間での開催でしたが、個人的には修論締め切り前なので、単純に日程的に厳しい状況での参加だったりしてます…

(rating: 905 -> 968)

• 250 : AC
• 500 : AC
• 1000 : no submit
• Challenge AC : 250*1

250 : KitayutaMart2

問題概要

i個目の値段が、(2^(i-1))Kのリンゴが売られている。

合計金額Tが与えられるので、買った個数を求めよ。

解法

値の上限はそれほど大きくないので、貪欲に解くことができます。

K,2K,4K…と合計値からその値段分の値を引いていき、0になった時の個数が答えとなります。

コード

class KitayutaMart2 {
    public:
    int numBought(int K, int T) {
      int cnt=0;
      for (int i=1; T>0; i*=2) {
	T-=i*K;
	cnt++;
      }
      return cnt;
    }
};KitayutaMart2.cpp

500 :  Fragile2

問題概要

文字列graphで無向グラフの隣接リストが与えられる。

graph[i][j]=‘Y’の時、iとjのノードをつなぐエッジが存在する。この無向グラフの2点を削除した時、元のグラフよりも連結成分が増加するペアの個数を答えよ。

解法

この問題は、グラフの最大ノード数が20なので、削除する点を全探索可能です。最初に与えられたグラフの連結成分の個数を求めた後、2点を削除した隣接リストを作成して、その連結成分の個数が元のグラフの個数を超えていればカウントして、全てのパターンについてチェックした際のカウント数が答えとなります。

コード

class Fragile2 {
    public:
    int countgroup(vector<string> graph) {
	bool flag[21];
	memset(flag,true,sizeof(flag));
	int n_size=0;
	for(int i=0;i<graph.size();i++)
	  {
	    if(flag[i])
	      {
		queue<int> qu;
		flag[i]=false;
		n_size++;
		qu.push(i);
		while(!qu.empty())
		  {
		    int now=qu.front();
		    qu.pop();
		    for(int j=0;j<graph[now].size();j++)
		    {
		      if(flag[j]&&graph[now][j]=='Y')
			{
			  flag[j]=false;
			  qu.push(j);
			}
		    }
		  }
	      }
	  }
	return n_size;
      }

    int countPairs(vector<string> graph) {
      int cnt=0;
      int n_size=countgroup(graph);
      for(int i=0;i<graph.size();i++)
	for(int j=i+1;j<graph.size();j++)
	  {
	    vector<string> tmp=graph;
	    for(int ii=0;ii<graph.size();ii++)
	      for(int jj=0;jj<graph.size();jj++)
		{
		  if(ii==i || jj==j ||
		     ii==j || jj==i)
		    tmp[ii][jj]='N';
		}
	  if(n_size<countgroup(tmp)-2)
	    cnt++;
	}
      return cnt;

    }

};Fragile2.cpp

この実装では、候補のペアのノードを削除せずにそこにつながるエッジのみ削除しているため、独立したノードがそ削除ノード分増えています。そのため、最後に2を引いてチェックしています。

1000 : ABC

問題概要

以下の条件を満たす文字列が存在するかを判定する。文字列が存在するときはその文字列を返し、存在しない時は空の文字列を返す。

• 文字列の長さはN
• 文字列の文字は’A’,‘B’,‘C’のみで構成される
• i < j において s[i]< s[j] となる i,j のペアがK個存在する。

解法

時間内に解けませんでした。DPでそこまでの条件を満たす個数と文字列を保持して探索する等考えましたが、実装まで出来なかったため、不明です。