1<2<3<4<5<6の順番に実装の時間が掛かったけど、1～4が(例年より)難しくて、難問が易化してた気がする。JOIは去年みたいな感じで、4番解けなくても実装力(と知識)ある人が5番解けるようにしているのだろうか。
見直し結構したので提出ミスはないはずだけど、それでも満点かどうかは怪しい。満点であってほしい。
問1.
それぞれ最小値更新しながらほげ。
#include <iostream> using namespace std; int main(){ ios_base::sync_with_stdio(false); int N = 999999; int M = 999999; for(int i = 0 ; i < 3 ; i++){ int in; cin >> in; N = min(in,N); } for(int i = 0 ; i < 2 ; i++){ int in; cin >> in; M = min(in,M); } cout << N + M - 50 << endl; }
問2.
去年より実装面倒くさいなと思った。ソートするだけだとO(log n)で済むが、面倒くさいのでO(n^2)で自分より点数高い相手の数数えた。
#include <iostream> using namespace std; int main(){ ios_base::sync_with_stdio(false); int n; int table[100]={0}; cin >> n; for(int i = 0 ; i < n * (n-1) / 2 ; i++){ int a,b,c,d; cin >> a >> b >> c >> d; a--,b--; if(c==d){ table[a]++; table[b]++; }else if(c>d){ table[a]+=3; }else{ table[b]+=3; } } for(int i = 0 ; i < n ; i++){ int weakness = 0; for(int j = 0 ; j < n ; j++){ if(i != j && table[j] > table[i]){ weakness++; } } cout << weakness + 1 << endl; } }
問3.
例えばトッピングをk個ふりふりする場合に、どういうトッピングを選べば嬉しいかというと、カロリーの高いものからk個ふりふりすれば嬉しい。
ってことは、ソートして高いものから優先的にふりふりしていくと解ける。
切り捨てるときの誤差恐かったのでEPS足したけどまあさすがに大丈夫らしい。
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ ios_base::sync_with_stdio(false); int n,A,B,C; cin >> n; cin >> A >> B >> C; vector<int> v; for(int i = 0 ; i < n ; i++){ int in; cin >> in; v.push_back(in); } sort(v.rbegin(),v.rend()); int price = A , cal = C; double maxCal = (double)cal / price; for(int i = 0 ; i < n ; i++){ price += B; cal += v[i]; maxCal = max( maxCal , (double)cal / price ) ; } cout << (int)(maxCal+1e-10) << endl; }
問4.
まあよくあるＤＰですが、去年より"状態"を理解してるかどうか問う感じだった。
- 何日目まで決定したか(今何日目見てるか)
- 直前２日のメニューは何だったか。
でＤＰ。当然メモ化で書けるならメモ化に逃げます。僕は。
(あとで気づいたけどそのメニューが何連続しているかでも解ける。ていうか3日固定じゃなくて、K日間hogeでK<=100とかならそっちじゃないと解けない。今回の場合はそうでないから良いが。)
なんか直前のやつを保持するのがとてつもなく面倒くさくその時は感じたので、
直前の2個でいいところを直前の3個と、あとdequeとmap使ってメモ化している。
多少遅くても一瞬なことには変わりないしエンバグしにくそうだったので。
正直3倍しながらmod取ったらいいよね・・・。
#include <map> #include <vector> #include <deque> #include <iostream> using namespace std; map< pair< int , deque<int> > , int > memo; int scheduled[100]; int n , m; int f(int pos,deque<int> prev){ deque<int> current = prev; if( memo.count(make_pair(pos,prev)) ) return memo[make_pair(pos,prev)]; if(prev.size() == 3 && count(prev.begin(),prev.end(),prev[0]) == 3 ) return 0; if(pos == n) return 1; if(prev.size() == 3) prev.pop_front(); int ans = 0; if(scheduled[pos] == -1){ for(int i = 1 ; i <= 3 ; i++){ prev.push_back(i); ans = ( ans + f(pos+1,prev) ) % 10000; prev.pop_back(); } }else{ prev.push_back(scheduled[pos]); ans = ( ans + f(pos+1,prev) ) % 10000; } return memo[make_pair(pos,current)] = ans; } int main(){ memset(scheduled,-1,sizeof(scheduled)); cin >> n >> m; for(int i = 0 ; i < m ; i++){ int a,b; cin >> a >> b; a--; scheduled[a] = b; } cout << f(0,deque<int>()) << endl; }
問5.
とても実装ゲーだったので手持ちのハニカム構造をペタっと貼り付けた。これがなかったら10分くらい時間つぶすのでよくない。
とりあえず外に余白つくるのは常套手段として、外からDFSなりBFSなりで空白マスを調べつつ、周りに壁が何箇所あるかをカウントしていくと解ける。
#include <iostream> using namespace std; // Example: dy[i%2][d] ( i is 0-indexed ) const int dx[2][6] = {{ 1,-1, 0, 0,-1,-1},{ 1,-1, 0, 0, 1, 1}}; const int dy[2][6] = {{ 0, 0, 1,-1,-1, 1},{ 0, 0, 1,-1,-1, 1}}; int W,H; int field[110][110]; int done[110][110]; int ok(int x,int y){ return x >= 0 && y < 110 && x < 110 && y >= 0; } int f(int x,int y){ if(field[y][x]) return 1; if(done[y][x]) return 0; done[y][x] = true; int ans = 0; for(int i = 0 ; i < 6 ; i++){ int tx = x+dx[(y+1)%2][i]; int ty = y+dy[(y+1)%2][i]; if(ok(tx,ty)) ans += f(tx,ty); } return ans; } int main(){ cin >> W >> H; for(int i = 0 ; i < H ; i++){ for(int j = 0 ; j < W ; j++){ cin >> field[i+2][j+2]; } } cout << f(0,0) << endl; }
問6.
これもＤＰ。去年、今年は一昨年以前に比べて言い換えとかのひねりがなかった感じ。個人的に、これは典型の詰め合わせだと思っている。しんどかった。
DPの仕方(?)
最上位桁から見ていくとして、
- 今何桁目を見ているか(500)
- 直前の桁は何だったか(10)
- 今の余りはいくつか(500)
- 今回はupするべきかdownするべきか(2)
- まあNを超えないようにDPしていくと、もう後の桁は何でもいいかどうかという情報が必要になるの(2)
O( 2 * 2 * 10 * M log N) くらいで解ける。(※log Nは桁数)
僕は最初に0を許しちゃうコードでずっとバグが取れなかったので、諦めて桁毎に求めるようにしたのでさらに500倍遅い。まあ予選だし4分くらいかかってもいいよね！
ところで、大きな数を小さい数Rで割った余り取るときに、でかい桁から順番に
- sum = ( sum * 10 + (今の見ている桁の値) ) % R
していって求めるのは有名ですよね。(オススメ:no title)
[A,B]にある数=([1,B]にある数) - ([1,A-1]にある数)って言い換えが可能なのでそうしたが、そのA-1を求めるために多倍長使っている。
#include <iostream> #include <sstream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; class bigInteger{ #define DIGITMAX (500) // 4 * n digit public: std::vector<int> value; bigInteger operator=(bigInteger b){ this->value = b.value; return *this; } /* O(n) */ bigInteger operator-(bigInteger b){ for(int i=0;i<DIGITMAX;i++){ b.value[i] = this->value[i] - b.value[i]; if(b.value[i]<0){ b.value[i] = 10000+b.value[i]; b.value[i+1]++; // b wo oome } } return b; } string str(){ char tmp[5]; string retVal = ""; for(int i=DIGITMAX-1;i>=0;i--){ sprintf(tmp,"%04d",value[i]); retVal += tmp; } while(retVal[0] == '0' && retVal.length()>=2)retVal = retVal.substr(1); return retVal; } bigInteger(){this->value.resize(DIGITMAX);} bigInteger(string init){ vector<int> vi; for(int i=init.length()-4;i>-4;i-=4){ vi.push_back( atoi(init.substr(max(i,0),4+(i<0?i:0)).c_str()) ); } this->value = vi; this->value.resize(DIGITMAX); } }; int M; int memo[512][16][512][2][2]; string limit; int f(int pos , int digit , int mod , int up , int free){ if(pos == -1) return (mod == 0); if(memo[pos][digit][mod][up][free] != -1) return memo[pos][digit][mod][up][free]; int ans = 0; if(up){ for(int i = digit+1 ; i <= (free?9:limit[pos]) ; i++){ ans += f(pos-1,i,(mod*10+i)%M,up^1,free||(i < limit[pos])); ans %= 10000; } }else{ for(int i = (free?digit-1:min((int)limit[pos],digit-1)) ; i >= 0 ; i--){ ans += f(pos-1,i,(mod*10+i)%M,up^1,free||(i < limit[pos])); ans %= 10000; } } return memo[pos][digit][mod][up][free] = ans; } int solve(string n){ int ans = 0; if(n.size() == 1){ for(int i = 1 ; i <= n[0] - '0' ; i++) if(i % M == 0) ans++; return ans; }else{ memset(memo,-1,sizeof(memo)); limit = n; reverse(limit.begin(),limit.end()); for(int i = 0 ; i < limit.size() ; i++) limit[i] -= '0'; for(int i = 1 ; i <= limit[limit.size()-1] ; i++){ ans += f((int)limit.size()-2,i,i%M,0, i < limit[limit.size()-1] ); ans += f((int)limit.size()-2,i,i%M,1, i < limit[limit.size()-1] ); ans %= 10000; } ans += solve(string(n.size()-1,'9')); ans %= 10000; } return ans; } int main(){ string A,B; cin >> A >> B >> M; bigInteger A_dec = bigInteger(A) - bigInteger("1"); A = A_dec.str(); cout << ( solve(B) - solve(A) + 1000000) % 10000 << endl; }
