活動日記 day 27
活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest
コメント :
木の直径の求め方を覚えましょう。
A : 高橋くんと年齢
解法 1
実際にソートして真ん中を出力
#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() { int arr[3]; rep(i,3) cin >> arr[i]; sort(arr,arr+3); cout << arr[1] << endl; return 0; }
解法 2
総和 - 最大値 - 最小値
#include<bits/stdc++.h> using namespace std; int main() { int a,b,c; cin >> a >> b >> c; cout << ( a + b + c ) - max(a,max(b,c)) - min(a,min(b,c)) << endl; return 0; }
B: 高橋くんと文字列圧縮
その通りにシミュレーションしましょう。
#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; rep(i,(int)s.size()) { cout << s[i]; int cnt = 1; int sp = i; while( i+1 < (int)s.size() && s[sp] == s[i+1] ) { ++cnt, ++i; } cout << cnt; } puts(""); return 0; }
C: 高橋くんと魔法の箱
入力で与えられた各値について、2で割る限り割り続けます。
その後に残った値の種類の数が答えです。
#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; typedef long long ll; int n,a[100010]; int main() { cin >> n; rep(i,n) { cin >> a[i]; while( a[i] % 2 == 0 ) a[i] /= 2; } set<int> S; rep(i,n) S.insert(a[i]); cout << (int)S.size() << endl; return 0; }
D: 高橋くんと木の直径
木の直径の求め方をそのまま実行します。
木の直径の求め方は以下の通りです。
1. どこでも良いので1つノードを選んでそこから最も遠いノードxを求めます。
2. 先ほど求めたノードxから最も遠いノードyを求めます。
xとyの距離が木の直径です。
詳細はあり本に蟻ます。
#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; typedef long long ll; int main() { int n,v; cin >> n; vector<int> dist1; dist1.push_back(0); REP(i,1,n) { cout << "? 1 " << i+1 << endl; cin >> v; dist1.push_back(v); } int next_sp = 0; REP(i,1,n) { if( dist1[next_sp] < dist1[i] ) next_sp = i; } int maxi = 0; rep(i,n) { if( i != next_sp ) { cout << "? " << next_sp+1 << " " << i+1 << endl; cin >> v; maxi = max(maxi,v); } } cout << "! " << maxi << endl; return 0; }
活動日記 day 26
活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest
コメント :
動的計画法が2問でましたね。
今回から簡単な解説を残しておこうかと思います。
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なので愚直にシミュレーションしてよさそうです。
( 文字列の長さ * 操作の回数 * 1回の操作にかかる処理の回数 = 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)で行うことができれま解けそうです。
可能でしょうか?
動的計画法を使えば可能です。
動的計画法を用いて、そこのマスに菱形の一番下の部分がくるように菱形を置いたときの長さの最長を求めます。
詳しくは以下の記事を参考にしてください。(時間ができたらあとで解説を書き直します)
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 25
活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest
コメント :
動的計画法と半分全列挙、尺取り法がでましたね。
復習しておきましょう。
活動日記 day 23
活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest
コメント :
動的計画法が2問ありました。
活動日記 day 22
活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest
活動日記 day 21
活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest
コメント :
個人練習になりました。
連絡が遅れてしまい申し訳ありませんでした。
#
良い機会なのでダブリングを勉強しましょう。