勢いで埋めてた
DEGwerさんがやるだけ埋めてたせいで、StatusDiffみたいなことしてたら時間をとってしまったんよ〜←
あ、別にDEGwerさんはなんにも悪くないんだけどねっ
ARC C
やった。全ての可能性を単純に調べていく
#include <cstdio> #include <iostream> #include <vector> #include <algorithm> using namespace std; bool ok=true; vector<string> mp(8); int row[8], col[8], dia[2][15]; void dfs(int c) { if (ok&&c==8) { for (int i=0; i<8; i++) cout<<mp[i]<<endl; ok=false; return; } if (col[c]>0) { dfs(c+1); return; } col[c]++; for (int i=0; i<8; i++) { if (row[i]>0||dia[0][c-i+7]>0||dia[1][c+i]>0) continue; mp[c][i]='Q'; row[i]++; dia[0][c-i+7]++; dia[1][c+i]++; dfs(c+1); mp[c][i]='.'; row[i]--; dia[0][c-i+7]--; dia[1][c+i]--; } col[c]--; return; } int main() { for (int i=0; i<8; i++) { cin>>mp[i]; for (int j=0; j<8; j++) if (mp[i][j]=='Q') { row[j]++; col[i]++; dia[0][i-j+7]++; dia[1][j+i]++; } } for (int i=0; i<8; i++) if (row[i]>1||col[i]>1) { puts("No Answer"); return 0; } for (int i=0; i<15; i++) if (dia[0][i]>1||dia[1][i]>1) { puts("No Answer"); return 0; } dfs(0); if (ok) puts("No Answer"); }
Dは適度に難しいのでまだです。
AOJ
1085
ループを工夫して実際の計算量をへらす。
#include <cstdio> #include <algorithm> using namespace std; int r[20001]; int main() { int n, s; while (scanf("%d%d",&n,&s)) { if (!n&&!s) break; for (int i=0; i<n; i++) scanf("%d",&r[i]); sort(r, r+n); int cnt=0; for (int i=n-1; i>0; i--) { if (r[i]>=s) cnt+=i; else { for (int j=i-1; j>=0; j--) { if (r[i]+r[j]<=s) break; cnt++; } } } printf("%d\n",cnt); } }
1084
全探索、何か最初は最大値の計算みすってた
#include <cstdio> #include <algorithm> using namespace std; int c[100]; int calc(int n, int k) { int s=0, mt=0; for (int i=0; i<=n-k; i++) { int temp=1; for (int j=0; j<k; j++) temp*=c[i+j]; mt=max(mt, temp); } return mt; } int main() { int n, k; while (scanf("%d%d",&n,&k)) { if (!n&&!k) break; for (int i=0; i<n; i++) scanf("%d",&c[i]); int mt=calc(n,k), res=0; for (int i=0; i<n; i++) { for (int j=i+1; j<n; j++) { swap(c[i],c[j]); res=max(res, calc(n,k)); swap(c[i],c[j]); } } // printf("%d %d\n",res, mt); if (res<mt) puts("NO GAME"); else printf("%d\n",res-mt); } }
1074
時間に名前突っ込んでごにょごにょ
#include <iostream> #include <vector> #include <map> #include <algorithm> #include <cstdio> using namespace std; typedef pair<int, string> P; bool comp(const P& a, const P& b) { if (a.first!=b.first) return a.first<b.first; return a.second<b.second; } int main() { int n; while (scanf("%d",&n)) { if (!n) break; vector<string> cnt[31]; map<string, int> mp; P po[n]; for (int i=0; i<n; i++) { string name; cin>>name; po[i]=P(0,name); mp[name]=i; int m; scanf("%d",&m); for (int j=0; j<m; j++) { int d; scanf("%d",&d); cnt[d].push_back(name); } } for (int i=0; i<31; i++) { int sz=cnt[i].size(); int x=n-sz+1; for (int j=0; j<sz; j++) { po[mp[cnt[i][j]]].first+=x; } } sort(po, po+n, comp); cout<<po[0].first<<" "<<po[0].second<<endl; } }
以上!!勉強にもどります(しろめ)