静かで孤独な日記

のんびりたまに

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'の前半と後半の和は独立に考えることが出来るところがポイントなのかなぁ。

ARC071 D - 井井井 / ###

  • 問題

arc071.contest.atcoder.jp

  • エディトリアル

https://atcoder.jp/img/arc071/editorial.pdf

  • 感想

O(n+m)なのは想像がついた。
だけど、解けなかった。
xのトータルの長さとyのトータルの長さを掛けて答えが出ることも分かった。
だからあとはそのトータルの長さをO(n)とO(m)で求めるのだけど、その求め方が分からずエディトリアルを見た。
まぁ、簡単に書いてあって、そっかーって気持ちに。
なので、自分で考えて実装。
トータルの求め方は少しエディトリアルと違ってるが本質的には同じ。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;

int n,m;
int x[100001],y[100001];
const ll MOD=(ll)1e9+7;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin);
    freopen("out","w",stdout);
#endif
  cin>>n>>m;
  for(int i=0;i<n;i++){
    cin>>x[i];
  }
  for(int i=0;i<m;i++){
    cin>>y[i];
  }
  ll xsum=0,ysum=0;
  ll now=n-1;//x[n-1]に付く係数
  for(int i=n-1;i>=0;i--){
    xsum+=now*x[i];
    now-=2;//xに付く係数は毎回-2すれば良い
  }
  now=m-1;//xの時と同じ
  for(int i=m-1;i>=0;i--){
    ysum+=now*y[i];
    now-=2;
  }
  cout<<((xsum%MOD)*(ysum%MOD))%MOD<<"\n";
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

ABC041_D 徒競走

  • muzukasii...




pakapa104.hatenablog.com

  • ↑wakarimiga hukai !!!

http://www-erato.ist.hokudai.ac.jp/docs/autumn2013/inoue.pdf

  • ↑naruhodo!!!

正直僕にはエディトリアルが何を言ってるのか分からなかった。
自分の頭はたしかに良くないのでググって調べてみたら、こんな僕にでもわかる記事があって助かりました。

以下コード

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;

int n,m;
ll dp[(1<<16)+10];
bool a[20][20];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin);
    freopen("out","w",stdout);
#endif
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int to,from;cin>>from>>to;
    from--;to--;
    a[to][from]=1;//from->to
  }
  dp[0]=1;
  for(int i=0;i<(1<<n);i++){
    bool b[20][20];
    for(int j=0;j<n;j++)for(int k=0;k<n;k++)b[j][k]=a[j][k];//copy
    for(int j=0;j<n;j++){
      if(i&(1<<j)){
        for(int k=0;k<n;k++){
          b[k][j]=0;//j->kの入次数を消す
        }
      }
    }
    for(int j=0;j<n;j++){//iにない頂点から入次数が0のものを探す旅に出る
      if(i&(1<<j))continue;
      bool flag=1;
      for(int k=0;k<n;k++){
        if(b[j][k]){
          flag=0;
          break;
        }
      }
      if(flag)dp[i|(1<<j)]+=dp[i];
    }
  }
  cout<<dp[(1<<n)-1]<<"\n";
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

意識

まあなんていうか、何をするにしても意識することは必要かなと。

とはいいつつ、なかなかできない。

ただ、じゃあやらなくていいのかと言うとそんなことはない。

多くの人が言うのは、意識することが大切。

例えば、少ない変数が現れたとき意識することは、それぞれの変数が偶数か奇数かとか、少ない種類の色である箇所を塗るときは何の色で、または隣とどんな接し方をしているかとかとか。

自分が苦手だというのではなく、そういう考えをすることに慣れていないということ。

毎回問題の考察をするとき、その考え方を頭の中の候補として取り出せる状態にしてあるかが大事。

想定内のことにしか僕は対応できないのだから。

意識して、問題を考える。

そうすれば突破口は見えてくる。

そんなに難しい問題を考えてるわけじゃないんだから。