AGC018
大爆散☆
http://agc018.contest.atcoder.jp/
AC：Aのみ300点
A
解法：鳩ノ巣応用
全ての数のGCDを取ってKがその数で割り切れればOKなのになんでこんな実装をしたのか自分でもこれが分からない
因みに実行時間1600ms超
#include <iostream> #include <deque> #include <vector> #include <cstdio> #include <cstring> #include <utility> #include <algorithm> #include <string> #include <cmath> #include <queue> #define i64 long long #define ui64 unsigned long long #define REP(i,n) for(int (i)=0;(i)<(n);i++) #define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++) #define MDIST(a,b) abs(a-b) #define DIST(a,b) sqrt((a)*(a)+(b)*(b)) #define ATCODER 1000000007 using namespace std; //////////////////////// /* a */ int d[10005]; int main(){ int n,k; cin >> n >> k; bool f=true; int a[n+1],m=0,m2=ATCODER; for(int i=0;i<n;i++){ cin >> a[i]; if(m<a[i])m=a[i]; if(a[i]==k)m2=a[i]; } if(m2==k); else if(k>m)f=false; else{ for(int i=0;i<n;i++){ if(!(a[i]%2)){ d[2]++; while(!(a[i]%2))a[i]/=2; } for(int j=3;j<=a[i]&&j<10005;j+=2){ if(!(a[i]%j)){ d[j]++; while(!(a[i]%j))a[i]/=j; } } } int c = 0; for(int i=2;i<10005;i++){ // cout << d[i] << " "; if(d[i]==n&&(k%i)){f=false;break;} } // cout << endl; } if(f)cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
ちゃんとGCDをとるとこう
実行時間50ms
#include <iostream> #include <deque> #include <vector> #include <cstdio> #include <cstring> #include <utility> #include <algorithm> #include <string> #include <cmath> #include <queue> #define i64 long long #define ui64 unsigned long long #define REP(i,n) for(int (i)=0;(i)<(n);i++) #define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++) #define MDIST(a,b) abs(a-b) #define DIST(a,b) sqrt((a)*(a)+(b)*(b)) #define ATCODER 1000000007 using namespace std; //////////////////////// /* a */ int d[10005]; int gcd(int l,int r){ int m; while(r){ m = r; r = l%r; l = m; } return l; } int main(){ int n,k; cin >> n >> k; int a[n+1],m=0,m2=ATCODER; for(int i=0;i<n;i++){ cin >> a[i]; if(m<a[i])m=a[i]; if(a[i]==k)m2=a[i]; } int t=gcd(a[0],a[1]); REP2(i,2,n){ t = gcd(t,a[i]); } if(k<=m&&!(k%t))cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
TOEICを無勉強で受けた結果
TOEICL&R受けるために昨日は何もせず
受けた感想：
・リスニングがむずい センターとは比べ物にならない
日本語でも聞き直すことが多い（）自分には辛いものでした
・一方でリーディングは簡単 センターほどの長文が出ず高々第5問程度…だが数が多い めちゃんこ多い でも斜め読みができて案外楽だった（明治大学の全学統一試験の英語を受けた経験からか）
まとめ：単語レベルは大体足りていたので問題はリスニング力
DPL_1_C
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C
制限なしナップサック
解法：漸化式に沿ってO(N*W)
漸化式の立て方は
こちらを参考にした。
なかなかこの漸化式に変形しきれないので今のうちは覚えておくほうが吉なのか
#include <iostream> using namespace std; int main(){ int n,mw; int v[1005],w[1005]; cin >> n >> mw; for(int i=0;i<n;i++){ cin >> v[i] >> w[i]; } int dp[mw+2][n]; fill(&dp[0][0],&dp[mw+1][n-1],0); for(int i=1;i<=mw;i++){ for(int j=0;j<n;j++){ dp[i][j] = i-w[j]>=0?max(dp[i][j-1],dp[i-w[j]][j]+v[j]):dp[i][j-1]; } } cout << dp[mw][n-1] << endl; }
AOJ2330
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2330
既視感ある問題。偽物の金貨を探すのが有名な気がする。
解法：O(logN)
要素数が等しい（もしくは差が1以下の）3個の集合に分けて2つを天秤にかける操作を繰り返すことで求まるので
N<=3^nとなる最小のnを探して終わり
#include <iostream> #include <cmath> using namespace std; int main(){ int n; cin >> n; int r=0; while(pow(3,r)<n)r++; cout << r << endl; return 0; }
AOJ2406
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2406
解法：割ったあまり考えるだけ O(n)
if文の中を書き間違えた結果1回WA
こういうのはホント減らしたい
#include <iostream> using namespace std; int main(){ int n,t,e; cin >> n >> t >> e; int a[n]; for(int i=0;i<n;i++){ cin >> a[i]; } for(int i=0;i<n;i++){ if((t%a[i])<=e||(t/a[i]*a[i]+a[i])<=(t+e)){ cout << i+1 << endl; return 0; } } cout << -1 << endl; return 0; }
AOJ2218
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2218
解法：場合分けして点数計算O(1)
とにかくinputが分厚い
デバッグが大変 おわり
結構な時間これに費やしたのでもうやりたくない一問
#include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <cstdlib> #include <utility> #include <algorithm> #include <string> #include <cmath> #include <queue> #define i64 long long #define ui64 unsigned long long using namespace std; int c_points[5][14]; int h_points[10]; struct card{ int num; int mark; card(char n_,char m_):num(),mark(){ switch(m_){ case 'S': mark = 0; break; case 'H': mark = 2; break; case 'D': mark = 3; break; case 'C': mark = 1; break; } if(('0'<=n_)&&(n_<='9'))num=n_-'0'; else{ switch(n_){ case 'T': num = 10; break; case 'J': num = 11; break; case 'Q': num = 12; break; case 'K': num = 13; break; case 'A': num = 1; break; } } } bool operator< (const card& a){ return num==a.num?mark<a.mark:num<a.num; } }; bool straight(vector<card>& hand){ for(int i=0;i<4;i++){ if((hand[i+1].num-hand[i].num==1)||\ ((!i)&&(hand[4].num==13&&hand[i].num==1))); else return false; } return true; } bool flush(vector<card>& hand){ for(int i=0;i<4;i++){ if(hand[i].mark!=hand[i+1].mark)return false; } return true; } bool no_pair(vector<card>& hand){ for(int i=0;i<4;i++){ if(hand[i].num==hand[i+1].num)return false; } return true; } bool one_pair(vector<card>& hand){ int p; for(int i=0;i<=4;i++){ if(i==4)return false; if(hand[i].num==hand[i+1].num){ p=i;break; } } for(int i=p+1;i<4;i++){ if(hand[i].num==hand[i+1].num)return false; } return true; } bool two_pair(vector<card>& hand){ int p; for(int i=0;i<=2;i++){ if(i==2)return false; if(hand[i].num==hand[i+1].num){ p=i;break; } } if(p==0){ return hand[2].num==hand[3].num?hand[3].num!=hand[4].num:hand[3].num==hand[4].num; } if(p==1){ return hand[3].num==hand[4].num; } } bool three_card(vector<card>& hand){ if(hand[0].num==hand[2].num&&hand[0].num!=hand[3].num)return true; if(hand[0].num!=hand[1].num&&hand[1].num==hand[3].num&&hand[3].num!=hand[4].num)return true; if(hand[0].num!=hand[1].num&&hand[1].num!=hand[2].num&&hand[2].num==hand[4].num)return true; return false; } bool fullhouse(vector<card>& hand){ int p; if(hand[1].num!=hand[2].num){ if(hand[0].num!=hand[1].num)return false; for(int i=2;i<4;i++){ if(hand[i].num!=hand[i+1].num)return false; } return true; }else{ if(hand[3].num!=hand[4].num)return false; for(int i=0;i<2;i++){ if(hand[i].num!=hand[i+1].num)return false; } return true; } } bool straight_flush(vector<card>& hand){ return straight(hand)&&flush(hand); } bool four_card(vector<card>& hand){ return hand[0].num==hand[3].num||hand[1].num==hand[4].num; } bool royal_straight_flush(vector<card>& hand){ if(straight_flush(hand)){ if(hand[0].num==1&&hand[4].num==13)return true; } return false; } i64 solve(vector<card>& hand){ sort(hand.begin(),hand.end()); i64 res=0LL; for(int i=0;i<5;i++){ int m_=hand[i].mark; int n_=hand[i].num; res+=(i64)c_points[m_][n_-1]; } if(royal_straight_flush(hand)){ res*=(i64)h_points[8]; return res; } if(straight_flush(hand)){ res*=(i64)h_points[7]; return res; } if(four_card(hand)){ res*=(i64)h_points[6]; return res; } if(straight(hand)){ res*=(i64)h_points[3]; return res; } if(flush(hand)){ res*=(i64)h_points[4]; return res; } if(fullhouse(hand)){ res*=(i64)h_points[5]; return res; } if(one_pair(hand)){ res*=(i64)h_points[0]; return res; } if(two_pair(hand)){ res*=(i64)h_points[1]; return res; } if(three_card(hand)){ res*=(i64)h_points[2]; return res; } if(no_pair(hand)){ return (i64)0; } return -1; } int main(){ int n; bool flag = false; while(1){ if(!flag){ cin >> n; if(cin.eof())return 0; flag=true; } fill(&c_points[0][0],&c_points[4][13],0); fill(&h_points[0],&h_points[9],0); for(int i=0;i<4;i++){ for(int k=0;k<13;k++){ cin >> c_points[i][k]; } } for(int i=0;i<9;i++){ cin >> h_points[i]; } char a[3]; vector<card> hands; for(int i=0;i<n;i++){ for(int k=0;k<5;k++){ cin >> a; hands.push_back(card(a[0],a[1])); } cout << solve(hands) << endl; hands.clear(); } if(flag){ cin >> n; if(cin.eof())return 0; else cout << endl; } } return 0; }
AOJ2501
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2501
解法：商と余のマンハッタン距離を求める
計算量：O(N)
サンプルを見ればなんとなく分かるだろうか。
図が丁寧に書かれているのが分かりやすい。
但し入力の数字をそれぞれ-1しないと余りがw=4の時の出力が合わない。（それを注視したケースもある）
#include <iostream> #include <cmath> using namespace std; int main(){ int n,a,b,c,d,p,q,res=10000; cin >> n >> a >> b >> c >> d; a--;b--;c--;d--; for(int w=1;w<=n;w++){ p = abs(a/w-b/w) + abs(a%w-b%w); q = abs(c/w-d/w) + abs(c%w-d%w); //cout << p <<" " << q << endl;; res = min(res,p+q); } cout << res << endl; }
