結構まとも
久しぶりに結構まともに精進出来た気がしますね。
ダーツなんだかんだちょこちょこカンニングしちゃいましたが(-_-;)
お、あした蟻本2版発売やん( ^∀^)
0125
書く
#include <cstdio> int y1, m1, d1, y2, m2, d2; int day[2][12]={ {31,28,31,30,31,30,31,31,30,31,30,31}, {31,29,31,30,31,30,31,31,30,31,30,31} }; bool uruu(int year) { if (year%400==0) return true; else if (year%100==0) return false; else if (year%4==0) return true; else return false; } int main() { while (scanf("%d%d%d%d%d%d",&y1,&m1,&d1,&y2,&m2,&d2)) { if (y1==-1&&m1==-1&&d1==-1&&y2==-1&&m2==-1&&d2==-1) break; long long res = 0, flag; if (y1==y2) { if (uruu(y1)) flag = 1; else flag = 0; if (m1==m2) res = d2-d1; else { for (int i=m1; i<m2-1; i++) res += day[flag][i]; res += day[flag][m1-1] - d1; res += d2; } } else { if (uruu(y1)) flag = 1; else flag = 0; for (int i=m1; i<12; i++) res += day[flag][i]; res += day[flag][m1-1] - d1; if (y1+1<y2) for (int i=y1+1; i<y2; i++) { if (uruu(i)) res += 366; else res += 365; } if (uruu(y2)) flag = 1; else flag = 0; for (int i=0; i<m2-1; i++) res += day[flag][i]; res += d2; } printf("%lld\n", res); } }
0127
変なアイデアで書く量減らすよりテーブル書いたほうがいいようです。
#include <iostream> using namespace std; char table[6][5] = { {'a','b','c','d','e'}, {'f','g','h','i','j'}, {'k','l','m','n','o'}, {'p','q','r','s','t'}, {'u','v','w','x','y'}, {'z','.','?','!',' '} }; int temp[2]; int main() { string mes; while (cin>>mes) { if (mes.length()%2!=0) cout << "NA" << endl; else { string res=""; bool flag=false; for (int i=0; i<mes.length(); i++) { if (i%2!=0) { temp[1] = mes[i] - '0'; if (temp[0]<1||temp[1]<1||temp[0]>6||temp[1]>5) { flag = true; break; } else { res += table[temp[0]-1][temp[1]-1]; } } else temp[0] = mes[i] - '0'; } if (flag) cout << "NA" << endl; else cout << res << endl; } } }
0529
結局かがみずさんのブログの2分探索という文字を事故で見てしまい、解いていくうちに蟻本のくじびきが写せることに気づき、なんでオーダー通らないんだろうとか言ってちょこっとJOIの解説を覗き、2分探索に変な先入観を持っていることに気づき、いろんな人に支えられてここまでやってきました←
はい、すいませんw
半分全列挙と2分探索でO(n^2 log n)です。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n, m; int p[1001]; int pp[1500000]; int main() { while (scanf("%d%d",&n,&m)) { if (!n&&!m) break; memset(p, 0, sizeof(p)); for (int i=0; i<n; i++) scanf("%d",&p[i]); sort(p, p+(++n)); for (int c=0; c<=n; c++) { for (int d=0; d<=n; d++) { pp[c*n+d]=p[c]+p[d]; } } sort(pp, pp+n*n); int res=0; for (int i=0; i<n*n; i++) { int temp = upper_bound(pp,pp+n*n,m-pp[i])-pp-1; if (pp[temp]+pp[i]<=m) res = max(res, pp[temp]+pp[i]); } printf("%d\n",res); } }
JOI 2011-2012 予選 5
予選時に勘違いしてたのではという錯覚に襲われたのですが妄想でした。
JOIの解説でマップのまわりに一行追加するという定番のアイデアを見てしまい、とりあえずBFSで解きました。
自力だったのかどうなのかは知りません。
int w, h; int field[200][200]; int d1[6][2] = {{-1,-1},{-1,0},{0,1},{1,0},{1,-1},{0,-1}}; int d2[6][2] = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{0,-1}}; void solve() { scanf("%d%d",&w,&h); memset(field, 0, sizeof(field)); int res=0; for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) scanf("%d",&field[i][j]); /* for (int i=0; i<=h+1; i++) { if (i%2) printf(" "); for (int j=0; j<=w+1; j++) { printf("%d%c",field[i][j],j==w+1?'\n':' '); } } */ queue<P> que; set<P> done; que.push(make_pair(0,0)); done.insert(make_pair(0,0)); while (!que.empty()) { P now=que.front(); que.pop(); if (now.first%2==0) { for (int i=0; i<6; i++) { int x=now.first+d1[i][0], y=now.second+d1[i][1]; if (x>=0&&x<=h+1&&y>=0&&y<=w+1&&field[x][y]==1) { res++; } else if (x>=0&&x<=h+1&&y>=0&&y<=w+1&&field[x][y]==0) { if (done.find(make_pair(x,y))==done.end()) { que.push(make_pair(x,y)); done.insert(make_pair(x,y)); } } } } else { for (int i=0; i<6; i++) { int x=now.first+d2[i][0], y=now.second+d2[i][1]; if (x>=0&&x<=h+1&&y>=0&&y<=w+1&&field[x][y]==1) { res++; } else if (x>=0&&x<=h+1&&y>=0&&y<=w+1&&field[x][y]==0) { if (done.find(make_pair(x,y))==done.end()) { que.push(make_pair(x,y)); done.insert(make_pair(x,y)); } } } } } printf("%d\n", res); } int main() { solve(); return 0; }
Facebook Hacker Cup 2012のAuctionは正解コード見たのですが、RMQやっているのはなんとなく分かっても大分コードが煩雑なのでいつの日か解説がみれることを祈ります。