静かで孤独な日記

のんびりたまに

yukicoder No.592 括弧の対応(2)

  • 何かと括弧ってスタックって言うデータ構造と相性が良い気がするんですよ。
  • なので、括弧の問題を考える時はまずゆっくりスタックの性質を考えながら解いていくと良い気がします。(僕も経験が浅いので大きい事は言えませんが)
  • あと、類似した問題を2個程見たことがあるのでやったことが無い人は挑戦してみてね(そんなに複雑じゃないよ)

A - STring

D - Insertion


#include<bits/stdc++.h>
using namespace std;

int n;
string s;
int a[200001];
int ans[200001];

int main(){
  cin>>n>>s;
  for(int i=0;i<n;i++)a[i]=i+1;
  stack<int> st;
  for(int i=0;i<n;i++){
    if(s[i]==')'){
      int temp=st.top();
      ans[i]=temp;
      ans[temp-1]=i+1;
      st.pop();
    }else{
      st.push(i+1);
    }
  }
  for(int i=0;i<n;i++)cout<<ans[i]<<"\n";
  return 0;
}

yukicoder No.609 Noelちゃんと星々

  • 中央値に集めるのが最適なんて知らないし、考えもしなかった人は三分探索を思いついたよね。
  • 三分探索知らない人はGoogle先生に問い合わせてみよう。(わかりやすい記事があったはず)
  • 俺スゲー賢いとか思った僕は解説読んで知識増やしていこうね
  • 因みに以下のコードは三分探索の書き方を忘れた人間が苦し紛れに書いたものなので、もっと短くて読みやすいコードを提出一覧から見つける事をオススメします!
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int n;
int a[100001];

inline bool check(ll m1,ll m2){
  ll sum1=0,sum2=0;
  for(int i=0;i<n;i++){
    sum1+=abs(m1-a[i]);
    sum2+=abs(m2-a[i]);
  }
  if(sum1>=sum2)return 1;
  else return 0;
}

int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  int cont=0;
  ll l=-1000000000,r=1000000000;
  while(cont<80){
    ll mid1=(r+2*l)/3;
    ll mid2=(l+2*r)/3;
    //cerr<<mid1<<" "<<mid2<<endl;
    if(check(mid1,mid2)){
      l=mid1;
    }else{
      r=mid2;
    }
    cont++;
  }
  ll ans=(ll)1e15;
  for(int i=l;i<=r;i++){
    ll nowsum=0;
    for(int j=0;j<n;j++){
      nowsum+=abs(i-a[j]);
    }
    ans=min(ans,nowsum);
  }
  cout<<ans<<endl;
  return 0;
}

yukicoder No.604 誕生日のお小遣い

  • 二分探索やるんですよ。
  • 予め、何年か指定したらいくら貰えてるか計算しやすいし。(check関数のこと)
  • 算数が苦手な人でもこっちならいけるんじゃない?(僕のことです)
  • あとはlong long だとオーバフローします。(unsignedつけようね)僕はミスしました。
#include<bits/stdc++.h>
#define ll unsigned long long int
using namespace std;

ll a,b,c;

inline bool check(ll m){
  ll sum=m/a*b+m-m/a;
  if(sum>=c)return 1;
  else return 0;
}

int main(){
  cin>>a>>b>>c;
  ll ng=0,ok=c;
  while(ok-ng>1){
    ll mid=(ok+ng)/2;
    cerr<<mid<<endl;
    if(check(mid)){
      ok=mid;
    }else{
      ng=mid;
    }
  }
  cout<<ok<<endl;
  return 0;
}

POJ-1742

  • problem

1742 -- Coins

  • code
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <cstdio>
#include <cmath>
#include <utility>
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
using namespace std;

template<class T>inline string toString(T x){
        ostringstream sout; sout<<x; return sout.str();
}
const ll MOD=1e9+7;
const int inf=(ll)1e9;
const double PI=acos(-1.0);

int dp[2][100001];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(10);
    cout<<fixed;
    int n,m;
    while(cin>>n>>m){
    	if(n==0 && m==0)return 0;
    	int a[101],c[101];
    	for(int i=0;i<n;i++){
    		cin>>a[i];
    	}
    	for(int i=0;i<n;i++){
    		cin>>c[i];
    	}
    	for(int i=0;i<2;i++){
    		for(int j=0;j<100001;j++){
    			dp[i][j]=-1;
    		}
    	}
    	dp[0][0]=c[0];
    	for(int i=0;i<n;i++){
    		for(int j=0;j<=m;j++){
    			if(dp[i%2][j]>0 && j+a[i]<=m){
    				dp[i%2][j+a[i]]=max(dp[i%2][j]-1,dp[i%2][j+a[i]]);
    			}
    			if(dp[i%2][j]>=0){
    				dp[(i+1)%2][j]=c[i+1];
    			}else dp[(i+1)%2][j]=-1;
    		}
    	}
    	int ans=0;
    	//cerr<<"================"<<endl;
    	//for(int i=0;i<=n;i++){
    	//	for(int j=0;j<=m;j++){
    	//		cerr<<dp[i][j]<<" ";
    	//	}
    	//	cerr<<endl;
    	//}
    	for(int i=1;i<=m;i++){
    		if(dp[n%2][i]>=0)ans++;
    	}
    	cout<<ans<<endl;
    }
    return 0;
}
  • 感想

最初は配列の再利用せずに提出してMLE。
だから、自力でやったことがない配列の再利用を恐る恐る自力でやってみた。
結局は漸化式がiとi+1のところでしかやり取りしてないから2個しか用意してなくても使いまわせるじゃん?みたいな?感じなのかな?
よく分かってないから、そんな感じの認識。
にしても、案外学習が遅い自分なりには自力でACできてまあ良かった。

POJ-3280

  • problem

3280 -- Cheapest Palindrome

  • code
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <cstdio>
#include <cmath>
#include <utility>
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
using namespace std;

template<class T>inline string toString(T x){
        ostringstream sout; sout<<x; return sout.str();
}
const ll MOD=1e9+7;
const int inf=(ll)1e9;
const double PI=acos(-1.0);

int dp[2001][2001];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(10);
    cout<<fixed;
    int n,m;	
    cin>>n>>m;
	string s;cin>>s;
	int cost[30];
	for(int i=0;i<n;i++){
		char a;
		int b,c;
		cin>>a>>b>>c;
		cost[a-'a']=min(b,c);
	}
	//for(int i=0;i<m;i++)for(int j=0;j<m;j++)dp[i][j]=inf;
	//for(int i=0;i<m-1;i++){
	//	dp[i][i]=0;
	//	dp[i][i+1]=0;
	//}
	for(int i=m-1;i>=0;i--){
		for(int j=i+1;j<m;j++){
			dp[i][j]=min(dp[i+1][j]+cost[s[i]-'a'],dp[i][j-1]+cost[s[j]-'a']);
			if(s[i]==s[j]){
				dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
			}
		}
	}
	cout<<dp[0][m-1]<<endl;
    return 0;
}
  • 感想

正直よく分かってない。
典型らしいから、わからなきゃダメなんだろうけど。。
どうしてそういう考え方できるの?みたいな。
言ってることは分かるけど何か腑に落ちない。

POJ-1703

  • problem

1703 -- Find them, Catch them

  • code
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <cstdio>
#include <cmath>
#include <utility>
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
using namespace std;

template<class T>inline string toString(T x){
        ostringstream sout; sout<<x; return sout.str();
}
const ll MOD=1e9+7;
const int inf=(ll)1e9;
const double PI=acos(-1.0);
const int N=100000;
struct UF
{
	static const int n=100001;
	int par[2*100001];
	int Rank[2*100001];
	void init(){
		for(int i=0;i<2*n;i++){
			par[i]=i;
			Rank[i]=0;
		}
	}
	int find(int a){
		if(par[a]==a)return a;
		return par[a]=find(par[a]);
	}
	bool same(int a,int b){
		return find(a)==find(b);
	}
	void unite(int a,int b){
		int x=find(a);
		int y=find(b);
		if(x==y)return;
		if(Rank[x]>Rank[y]){
			par[y]=x;
		}else{
			par[x]=y;
			if(Rank[x]==Rank[y]){
				Rank[y]++;
			}
		}
	}
	void test(int size){
		cerr<<"=================="<<endl;
		for(int i=0;i<size;i++){
			cerr<<par[i]<<" ";
		}
		cerr<<"\n";
		for(int i=0;i<size;i++){
			cerr<<Rank[i]<<" ";
		}
		cerr<<"\n";
	}
	int judge(int a,int b){
		int x=find(a);
		int y=find(b);
		int z=find(a+N);
		int w=find(b+N);
		if(x==y)return 1;
		else if(x==w)return 0;
		else if(y==z)return 0;
		else if(w==z)return 1;
		else return -1;
	}
};

int t;

int main(){
    scanf("%d",&t);
    int cont=0;
    while(cont<t){
    	cont++;
    	int n,m;
    	scanf("%d %d\n",&n,&m);
    	UF uf;
    	uf.init();
    	for(int i=0;i<m;i++){
    		char a;
    		int b,c;
    		scanf("%c %d %d\n",&a,&b,&c);
    		b--;c--;
    		if(a=='A'){
    			int temp=uf.judge(b,c);
    			if(temp==1){
    				printf("In the same gang.\n");
    			}else if(temp==0){
    				printf("In different gangs.\n");
    			}else{
    				printf("Not sure yet.\n");
    			}
    		}else{
    			uf.unite(b,c+N);
    			uf.unite(c,b+N);
    		}
    	}
    }
    return 0;
}
  • 感想

こうゆうunion findの使い方したことなくて感動した。
でも、自力で使えるようになるのはまだ時間がかかりそう。

ABC062-D 3N Numbers

D - 3N Numbers


  • 考察

f:id:c6h4c12takamasa:20171227024049j:plain

  • code
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define show(x) cout<<#x<<"="<<x<<"\n"
using namespace std;

int n;
int a[3*100001];
ll lmax[100002];
ll rmin[100002];
const ll inf=(ll)1e18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout<<fixed;
#ifdef LOCAL_DEFINE
    FILE *stream1;
    //FILE *stream2;
    stream1=freopen("in","r",stdin);
    //stream2=freopen("out","w",stdout);
    if(stream1==NULL)return 0;
    //if(stream2==NULL)return 0;
#endif
    cin>>n;
    ll suml=0,sumr=0;
    for(int i=0;i<3*n;i++){
        cin>>a[i];
        if(i<n)suml+=a[i];
    }
    priority_queue<int> l;
    for(int i=0;i<n;i++){
        l.push(-a[i]);
    }
    lmax[0]=suml;
    for(int i=0;i<n;i++){
        l.push(-a[n+i]);
        suml+=a[n+i]+l.top();
        l.pop();
        lmax[i+1]=suml;
    }
    priority_queue<int> r;
    for(int i=0;i<n;i++){
        r.push(a[2*n+i]);
        sumr+=a[2*n+i];
    }
    rmin[n]=sumr;
    for(int i=0;i<n;i++){
        r.push(a[2*n-1-i]);
        sumr+=a[2*n-1-i]-r.top();
        r.pop();
        rmin[n-1-i]=sumr;
    }
    ll ans=-inf;
    for(int i=0;i<=n;i++){
        //cerr<<lmax[i]<<" "<<rmin[i]<<endl;
        ans=max(ans,lmax[i]-rmin[i]);
    }
    cout<<ans<<endl;
#ifdef LOCAL_DEFINE
    cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
    fclose(stream1);
    //fclose(stream2);
#endif
    return 0;
}
  • 感想

最近になってやっと問題はしっかり考察しようと思うようになった。
紙に書くことは大切だね。
今回はa'の前半と後半の和は独立に考えることが出来るところがポイントなのかなぁ。