YNU.cpc

横浜国立大学競技プログラミング部 ( YNU.cpc )

活動日記 day 26

活動日記

活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest


コメント :
動的計画法が２問でましたね。

今回から簡単な解説を残しておこうかと思います。

A - 豆まき

ソートしてその値が何番目かを出力しました。

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
int main() {
  vector<int> vec(3), tmp;
  rep(i,3) cin >> vec[i];
  tmp = vec;
  sort(tmp.begin(),tmp.end());
  rep(i,3) cout << 3 - ( lower_bound(tmp.begin(),tmp.end(),vec[i]) - tmp.begin() ) << endl;
  return 0;
}

vector, sortやlower_boundは良く使うのでここで覚えておきましょう。

vectorは可変長の配列です。
配列と同じように使うことができます。
使用例を以下に示します。

#include<vector>
#include<iostream>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

int main() {
  vector<int> vec(10); // int vec[10]; みたいなものです。
  rep(i,10) vec[i] = i; // 配列と同様にアクセスすることができます。
  rep(i,10) cout << vec[i] << " "; puts(""); // 0 1 2 3 4 5 6 7 8 9 と出力されます。
  vec.push_back(10); // 後から要素を追加することができます。
  cout << vec.size() << endl; // vecのサイズを出力します。　ここでは 11 と出力されます。
  rep(i,(int)vec.size()) cout << vec[i] << " "; puts(""); // 0 1 2 3 4 5 6 7 8 9 10 と出力されます。
  vec.clear(); // vectorの中身をすべて消します。　
  rep(i,(int)vec.size()) cout << vec[i] << " "; puts(""); // 空の行が出力されます。

  vec.push_back(1); // vec[0] = 1 です。
  cout << -vec.size() << endl; // どうなるんでしょうね？
  return 0;
}

sortはその名の通りです。
使用例を以下に示します。

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

int main() {
  vector<int> vec = {5,1,4,2,3}; // C++11から int vec[] = {5,1,4,2,3}; みたいですね。
  sort(vec.begin(),vec.end());
  rep(i,(int)vec.size()) cout << vec[i] << " "; puts(""); // 1 2 3 4 5 と出力されます。
  sort(vec.begin(),vec.end(),greater<int>()); 
  rep(i,(int)vec.size()) cout << vec[i] << " "; puts(""); // 5 4 3 2 1 と出力されます。
  return 0;
}

最後にlower_boundの使用例を示します。
lower_boundは引数の配列の指定した範囲の中にある要素の中で、ある値以上のもののうちもっとも左にある要素の位置を返す関数です。

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

int main() {
  vector<int> vec = {10,1,5,2,3}; // C++11から
  sort(vec.begin(),vec.end()); // lower_bound は使う前にsortしておく必要があります。
  cout << *lower_bound(vec.begin(),vec.end(),1) << endl; // vecの中で、1以上であるような要素のうち最も左にある要素を出力します。　ここでは 1 が出力されます。
  cout << *lower_bound(vec.begin(),vec.end(),4) << endl; // 5 が出力されます。
  return 0;
}

B - 文字列の反転

文字列の長さ、操作の回数が高々100なので愚直にシミュレーションしてよさそうです。
( 文字列の長さ * 操作の回数 * １回の操作にかかる処理の回数 = 100 * 100 * 100 = 10^6 <= 10^8 なので 2sec あれば十分間に合います )
C++を使っているのであれば、string型を利用しましょう。

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
int main() {
  string s;
  cin >> s;
  int n;
  cin >> n;
  rep(i,n) {
    int a,b;
    cin >> a >> b;
    --a, --b;
    reverse(s.begin()+a,s.begin()+b+1); 
  }
  cout << s << endl;
  return 0;
}

reverseは指定した範囲をreverseする関数です。

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

int main() {
  string s = "0123456789";
  reverse(s.begin()+1,s.begin()+6); // [1,6)の範囲をreverseします。
  cout << s << endl; // 0543216789 と出力されます。

  vector<int> vec = {1,2,3,4,5};
  reverse(vec.begin()+1,vec.begin()+4); // [1,4)の範囲をreverseします。
  rep(i,(int)vec.size()) cout << vec[i] << " "; puts(""); // 1 4 3 2 5 と出力されます。
  return 0;
}

C - 菱型カウント

問題概要 :
R行C列の長方形領域があり、各マスには'o'か'x'が書いてあります。
一辺の長さがKであるような菱形を置けるマスは何箇所ありますか？
ただし、菱形の中に'x'があってはいけません。

一辺の長さが2の菱形
o*o
***
o*o

一辺の長さが3の菱形
oo*oo
o***o
*****
o***o
oo*oo

解法：
動的計画法で解きました。

愚直に計算していくことを考えます。
各マス(x,y)について、そこに長さKの菱形が置けるかどうかを判定するば良いです。
このとき計算量はO(R*C*K*K)なので、最悪の場合 500 * 500 * 500 * 500 = 62,500,000,000となり、2secでは終わりません。
ただ、この問題には部分点がついていて、それであれば R <= 50 かつ C <= 50 であるため最悪でも 50 * 50 * 50 * 50 = 6,250,000 <= 10^8 となり間に合います。
満点を取りたい場合はどうすれば良いのでしょうか。
各マスについて見ていくのはそのままで、そこのマスに菱形を置けるかどうかの判定をO(1)で行うことができれま解けそうです。
可能でしょうか？
動的計画法を使えば可能です。
動的計画法を用いて、そこのマスに菱形の一番下の部分がくるように菱形を置いたときの長さの最長を求めます。

詳しくは以下の記事を参考にしてください。（時間ができたらあとで解説を書き直します）

UVa 10593 : Kites - 土下座しながら探索中

D - バレンタインデー

解けた人は今年バレンタインデーのチョコがもらえるかもしれませんね。
私は解けたのでもらえるかもしれません。

以下解法の概略です。
女子の選び方を全て試します。
女子の選び方が決まったときの男子の選び方を動的計画法で求めます。 ( dp[i] := i人の男子を選んだときの幸福度の最大値 )
その中の最大値が答えです。

#include<iostream>
#include<cstdio>
#include<cassert>
#include<climits>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<sstream>
#include<vector>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<map>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
#define MAX 300
int N,M,P,Q,R,x[MAX*MAX],y[MAX*MAX],z[MAX*MAX];
int mat[MAX][MAX];
int popcount[1<<20];
 
int dp[20];
 
int score(int girls,int boy) {
  int ret = 0;
  rep(i,N) {
    if( (girls>>i) & 1 ) {
      ret += mat[i][boy];
    }
  }
  return ret;
}
 
void compute() {
  int maxi = 0;
  rep(i,(1<<N)) {
    if( popcount[i] != P ) continue;
    memset(dp,-1,sizeof dp);
    dp[0] = 0;
    rep(j,M) {
      for(int k=Q-1;k>=0;--k) {
	if( dp[k] == -1 ) continue;
	dp[k+1] = max(dp[k+1],
		      dp[k]+score(i,j));
      }
    }
    if( dp[Q] == -1 ) continue;
    maxi = max(maxi,dp[Q]);
  }
  cout << maxi << endl;
}
 
int main() {
  rep(i,(1<<20)) popcount[i] = __builtin_popcount(i);
  memset(mat,0,sizeof mat);
  cin >> N >> M >> P >> Q >> R;
  rep(i,R) {
    cin >> x[i] >> y[i] >> z[i];
    --x[i], --y[i];
    mat[x[i]][y[i]] = z[i];
  }
  compute();
 return 0;
}

活動日記 day 21

活動日記

活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest


コメント :
個人練習になりました。
連絡が遅れてしまい申し訳ありませんでした。
#
良い機会なのでダブリングを勉強しましょう。