まえがき
こんにちは、みちらからです。先週末に行われた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;
rep(i,n){pair<int,int> tmp;cin>>tmp.second>>tmp.first;b.insert(tmp);}
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<pint> que;
vector<vector<int>> dp(H, vector<int>(W, INF));
que.push_back({sx, sy});
dp[sx][sy] = 0;
while (!que.empty()) {
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;
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;
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始まる前によく寝ておいた方がよいです。
途中で眠くなって集中が切れかけました。
今回は春合宿メンバーには入れませんでしたが、すごく楽しかったので来年も楽しんで頑張りたいです！
