GCJJ2011 予選
A-small,C-largeで人権は守りました。
A-small
シャッフル問題なのでsmallだけだと普通にシュミレーション
int solve(int m, int c, int w, int a[], int b[]) { int deck[m+1]; for (int i=1; i<=m; i++) deck[i]=i; for (int i=0; i<c; i++) { int temp[b[i]], npos=0; for (int j=a[i]; j<a[i]+b[i]; j++) { temp[npos++] = deck[j]; deck[j] = 0; } int ndeck[m+1]; for (int j=1; j<b[i]+1; j++) ndeck[j] = temp[j-1]; npos = b[i]+1; for (int j=1; j<m+1; j++) { if (deck[j]) { ndeck[npos++] = deck[j]; } } memcpy(deck, ndeck, sizeof(ndeck)); } return deck[w]; } int main() { int t;scanf("%d",&t); for (int ix=1; ix<=t; ix++) { int m, c, w; scanf("%d%d%d",&m,&c,&w); int a[c], b[c]; for (int i=0; i<c; i++) scanf("%d%d",&a[i],&b[i]); printf("Case #%d: %d\n", ix, solve(m,c,w,a,b)); } }
A-large
mが10^9まであるのでシュミレーションは不可能に。
ここからは色んな人から教えていただき、練習で通した。
解法 逆順に考える。wが操作を巻き戻した時、どこの位置にあったか? もともとwがあった場所の数字がwの位置にくるはずなのでそれで考える。 操作を巻き戻すときは、wが取り出す枚数以下なら取り出す始点+w-1がもとのwの位置。なぜならwは最後の操作で上に乗せられたものであるから。 そうじゃなくてwが終点より小さいならそれはシャッフルによって下にずれたものだからw-取り出す枚数の位置にあったことになる。
逆順って発想が思いつかず、普通の順で規則性を見つけ出そうとしてたのですが、無理でした(;・∀・)
なんとなく逆順じゃなくてもできそうな気もしますが・・・
struct rsf { int a, b;}; int solve(int m, int c, int w, rsf s[]) { // vector<rsf> ns; // int res = w; // for (int i=0; i<c; i++) { // if (ns.empty()) { // ns.push_back(s[i]); // } else { // bool flag = true; // for (int j=0; j<ns.size(); j++) { // if (ns[j] == s[i]) { // ns[j].c++; // flag = false; // } // } // if (flag) ns.push_back(s[i]); // } // } // for (int i=0; i<ns.size(); i++) { // } // return res; for (int i=c-1; i>=0; i--) { if (w<=s[i].b) { w = s[i].a + w - 1; } else if (w<=s[i].a+s[i].b-1) { w -= s[i].b; } } return w; } int main() { int t;scanf("%d",&t); for (int ix=1; ix<=t; ix++) { int m, c, w; scanf("%d%d%d",&m,&c,&w); rsf s[c]; for (int i=0; i<c; i++) scanf("%d%d",&s[i].a,&s[i].b); printf("Case #%d: %d\n", ix, solve(m,c,w,s)); } }
B
貪欲ですが、求められませんでした。
またまた教えてもらったもの。
解法 価値で降順ソートしたとき、消費期限-個数+1と1の大きい方が始点、消費期限が終点だとして、その期間そのコーヒーを飲めるのでこれを価値の大きい順に求めていく。 ただし、一度価値の大きいものを飲んだら、あとのコーヒーはそのコーヒーを飲んだ日に飲めないので、日数を調整する。
まぁあとはコードで。
struct c { ll c, t, s; }; class Comp { public: bool operator() (const c& a, const c& b) { return a.s > b.s; } }; ll solve(int n, int k, c coff[]) { // int res = 0; // sort(coff, coff+n, Comp()); // for (int i=0; i<n; i++) { // for (int j=i+1; j<n; j++) { // if (coff[i].t==coff[j].t&&coff[i].s>coff[j].s) { // swap(coff[i], coff[j]); // } // } // } // int days[k+1]; // for (int i=0; i<=k; i++) days[i] = 0; // for (int i=n-1; i>=0; i--) { // for (int j=coff[i].t; j>0&&coff[i].c>0; j--) { // if (days[j] < coff[i].s) { // days[j] = coff[i].s; // coff[i].c--; // } // } // } // for (int i=1; i<=k; i++) res += days[i]; // return res; ll res = 0; sort(coff,coff+n,Comp()); for (int i=0; i<n; i++) { int val = coff[i].s; if (coff[i].t==0) continue; ll begin=max(1LL, coff[i].t-coff[i].c+1); ll end=coff[i].t; res+=(end-begin+1)*val; for (int j=0; j<n; j++) { if (coff[j].t>end) { coff[j].t-=end-begin+1; } else { coff[j].t=min(coff[j].t,begin-1); } } } return res; } int main() { int t; scanf("%d", &t); for (int ix=1; ix<=t; ix++) { int n, k; scanf("%d%d",&n,&k); c coff[n]; for (int i=0; i<n; i++) { scanf("%lld%lld%lld",&coff[i].c,&coff[i].t,&coff[i].s); } printf("Case #%d: %lld\n", ix, solve(n,k,coff)); } }
Aも、Bも聞いてみると簡単なのですが、入力された変数をすべて使わないというのがネックすぎます。
その点があるかないかで考え方もそうとう変わってしまいますし・・・
C-small
ケースサイズ的に総当たり。
bitの1の数を調べるのはぐぐると出てくる。
int cntbit(ll bits) { bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f); bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff); return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff); } int solve(ll n) { int res = 0; for (int i=0; i<=n/2; i++) { ll a = i, b = n - i; res = max(res, cntbit(a)+cntbit(b)); } return res; } int main() { int t; scanf("%d", &t); for (int ix=1; ix<=t; ix++) { ll n; scanf("%lld", &n); printf("Case #%d: %d\n", ix, solve(n)); } }
C-large
総当りはできないので考えたら解法が思いつきました。
ちょっと楽して2進数文字列に直したいとかおもって色々しらべたけど結局自分で変換した。
解法 2進数を下の位から見ていく。それより下の位に0が現れていれば繰り上がりがあるとする。 繰り上がりがない状態のとき、0ならば、1+1なので二個カウント、1なら0+1なので一個カウントする。 繰り上がりがあるときは、0ならば、1+0なので一個カウント、1ならば1+1なので二個カウントする。 最終的にカウント数が答えになる。ただし、今のロジックの場合最後の位が繰り上がった1であると二個余分にカウントしてしまうので、それを引く。
コード
int solve(ll n) { int res = 0; ll bit=1; char buff[65]; for (int i=0; i<65; i++) { if (n&bit) buff[i]='1'; else buff[i]='0'; bit<<=1; } int c=64; while (buff[c]=='0'&&c>=0) c--; bool flag = false; for (int i=0; i<=c; i++) { if (flag) { if (buff[i]=='0') { res++; flag = true; } else if (buff[i]=='1') { res+=2; flag=true; } } else { if (buff[i]=='0') { res+=2; flag=true; } else if (buff[i]=='1') { res++; } } } if (flag) { res -= 2; } return res; } int main() { int t; scanf("%d", &t); for (int ix=1; ix<=t; ix++) { ll n; scanf("%lld", &n); printf("Case #%d: %d\n", ix, solve(n)); } }
Cの解法がDPか貪欲かで議論がありましたが、僕の解法だと明らかに貪欲だと思う・・・
というわけでばいちゃ(´・ω・`)