JOI本選 参戦記
まえがき
こんにちは、みちらからです。先週末に行われたJOI本選に参加したので参戦記を書いておきます。(緑コーダー 199点なのであまり参考にはならないと思います)
問題1
問題概要
色がたくさんある片方からしか置けない一次元オセロをやるから結果を出力してね
感想
これは結構簡単でした。方針は一瞬で思いついたので気合で実装しました。C++でmapやsetなどを使ったことがなかったので少し時間がかかってしまいましたが満点を取ることができたのでうれしかったです。
コード
int main(){ int n; cin>>n; vi a(n); vin(a); map<int,set<int>> m; rep(i,n){ m[a[i]].insert(i); } vi toout(n,0); int i=0; while(i<n){ auto it=m[a[i]].lower_bound(i); if(++it==m[a[i]].end()||*it==i+1){ toout[i]=a[i]; i++; continue; } reps(j,i,*it+1){ toout[j]=a[i]; } i=*it; } rep(i,n)cout<<toout[i]<<endl; }
問題2
問題概要
影響力が大きい人に本をあげるほど周りのひとが本を買うよ
全員が本を持つようにするために必要な本をあげる人をできるだけ少なくしてね
感想
さっそく結構難しかったです。
O(N2)貪欲で69点が取れました。むずくね！？
コード
本番59点コード
int main(){ int n; cin>>n; set<pair<int,int>> b;//eとx逆 rep(i,n){pair<int,int> tmp;cin>>tmp.second>>tmp.first;b.insert(tmp);} //ここでO(N^(N/2))? int cnt=0; while(b.size()>0){ cnt++; pair<int,int> ex; ex=*b.rbegin(); vector<pair<int,int>> er; for(pair<int,int>i:b){ if((ex.first-i.first)>=abs(ex.second-i.second))er.push_back(i); } for(pair<int,int>i:er){ b.erase(i); } } cout<<cnt<<endl; }
+10点コード
int main(){ int n; cin>>n; set<pair<int,int>> a; rep(i,n){ int x,y; cin>>x>>y; a.insert(make_pair(x,y)); } cout<<sz(a)<<endl; }
おまけ
upsolveした満点コード
int main(){ int n; cin>>n; vector<pair<int,int>> a(n); rep(i,n){ pair<int,int> tmp; cin>>tmp.first>>tmp.second; a[i]=tmp; } sort(all(a)); vector<pair<int,int>> stack; stack.push_back(a[0]); reps(i,1,n){ int x,e,nx,ne; x=stack[stack.size()-1].first,e=stack[stack.size()-1].second; nx=a[i].first,ne=a[i].second; while(ne-e>=abs(nx-x)&& stack.size()>0){ stack.pop_back(); x=stack[stack.size()-1].first,e=stack[stack.size()-1].second; nx=a[i].first,ne=a[i].second; } if(stack[stack.size()-1].second-a[i].second<abs(stack[stack.size()-1].first-a[i].first))stack.push_back(a[i]); } cout<<stack.size()<<endl; }
問題3
問題概要
Stronger Takahashiの壊すブロックの大きさが決められてないよ
がんばってね
感想
Stronger Takahashiをちょっとだけ変えて27点
解説見て思ったこと
- このへんからJOI本選のとてつもない実装量感が出てきた
コード
本番27点コード
けんちょんさんのブログからほぼコピペです
ここ
// 四方向への移動 const vector<int> dx = {1, 0, -1, 0}; const vector<int> dy = {0, 1, 0, -1}; // 無限大 const int INF = 1<<29; // マスを表す構造体 using pint = pair<int,int>; int main() { // 入力 int H, W,N,sx,sy,gx,gy; cin >> H >> W>>N>>sx>>sy>>gx>>gy; sx--;sy--;gx--;gy--; vector<string> fi(H); for (int i = 0; i < H; ++i) cin >> fi[i]; // deque deque<pint> que; vector<vector<int>> dp(H, vector<int>(W, INF)); que.push_back({sx, sy}); dp[sx][sy] = 0; // 0-1 BFS while (!que.empty()) { // que の先頭要素を取り出す auto [x, y] = que.front(); que.pop_front(); // 通路マスへの移動 for (int dir = 0; dir < 4; ++dir) { int nx = x + dx[dir], ny = y + dy[dir]; if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue; if (fi[nx][ny] == '#') continue; // 移動コストは 0 なので que の front に push if (dp[nx][ny] > dp[x][y]) { dp[nx][ny] = dp[x][y]; que.push_front({nx, ny}); } } // 魔法を唱えて移動 for (int nx = x - N; nx <= x + N; ++nx) { for (int ny = y - N; ny <= y + N; ++ny) { if (abs(nx - x) + abs(ny - y) == N*2) continue; if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue; // 壁だろうが通路だろうがコスト 1 の辺を張る // コスト 1 なので que の back に push if (dp[nx][ny] > dp[x][y] + 1) { dp[nx][ny] = dp[x][y] + 1; que.push_back({nx, ny}); } } } } cout << dp[gx][gy] << endl; }
問題4
時間足りねえ！！無理！！！
問題5
シンプルに無理！！！
まとめ
集中力のある序盤のうちに考察などをしておいた方がよかったかもしれない。
来年のこの時期は青コーダーになっている予定なので来年は春合宿行きます
あとJOI始まる前によく寝ておいた方がよいです。
途中で眠くなって集中が切れかけました。
今回は春合宿メンバーには入れませんでしたが、すごく楽しかったので来年も楽しんで頑張りたいです！
