はじめに
この記事は東京高専プロコンゼミ② Advent Calender 2019 9日目の記事です。
昨日(12/9)の13:00-16:00にJOI2019/2020の二次予選が開催されました。私は本選参加資格がないのですが、一次予選に参加して通過したため、他の参加者と同様に予選を受ける事ができました。(つくばには行けませんが・・・)
結果は全完で500点でした。
当日の動きについて
ぼくはコンテストが開始される13:00時点でラーメンを食べていたので、問題文だけ先に読んで後で(適当な場所を探して)コーディングをする予定でした。
C問題
300点辺りがJOI予選突破ボーダー辺りだと考えていたので、いい感じの難易度っぽい3問目を最初に読みました。
最初5分ぐらいは解法が分からず、Nから逆に辿ればいいじゃんみたいな事を考えてすぐ捨てるみたいな事をしていましたが、思いつけばおわりです。逆辺張ってBFSすればおわりだと思ったのですが、実際は逆辺を張るまでもなく、桁和を足した先に値を加算すればおわりでした。スマホコーディングができるぐらいので軽実装で終わったのでよかったです。
コンテスト後のTLにUnionFindを貼って遷移先とマージしてNの含まれる集合の要素数を出力するみたいな解法が生えていて、めっちゃ頭がいいな〜となりました。(UFを貼って解けるの、かなり好きです)
#include <bits/stdc++.h>
using namespace std;
using i64 = long;
signed main() {
int n;
cin>>n;
vector<int> val(n+1,1);
for(int i=1;i<n;++i){int c=0;
int j=i;while(j){c+=j%10;j/=10;}if(i+c<=n)val[i+c]+=val[i];
}
cout<<val[n]<<endl;
}
D問題
dist[mod mでの値][現在指してるマス]で適当にダイクストラをします。JOIっぽくて割と楽しいな〜っていいながら解いてました(辺情報のソースコード埋め込みをしたのですが、それが間違ってないかが怖かった)
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
signed main(){
int n, r;
cin >> n >> r;
vector<vector<int>> v{
{0, 1},
{1, 2},
{2, 3},
{4, 5},
{5, 6},
{7, 8},
{8, 9},
{1, 4},
{2, 5},
{3, 6},
{4, 7},
{5, 8},
{6, 9},
};
vector<vector<int>> edges(10);
for(auto &p : v){
edges[p[0]].emplace_back(p[1]);
edges[p[1]].emplace_back(p[0]);
}
vector<int> dist(n * 10, 1e9);
dist[0] = 0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> que;
que.emplace(0, 0);
while(!que.empty()){
int d, p, val, pos;
tie(d, p) = que.top();
que.pop();
if(d != dist[p])
continue;
val = p / 10;
pos = p % 10;
for(auto& t : edges[pos]){
if(dist[val * 10 + t] > d + 1){
dist[val * 10 + t] = d + 1;
que.emplace(dist[val * 10 + t], val * 10 + t);
}
}
int nex = (val * 10 + pos) % n;
if(dist[nex * 10 + pos] > d + 1){
dist[nex * 10 + pos] = d + 1;
que.emplace(dist[nex * 10 + pos], nex * 10 + pos);
}
}
int ans = 1e9;
for(int i = 0; i < 10; ++i)
ans = min(ans, dist[r * 10 + i]);
cout << ans << endl;
}
E問題
問題を見てびっくりしました。まさか予選でBNF表記の構文解析が出るとは思わなかった・・・
考察要素はあまりなくて、あなたは実装ができますかみたいな問題なんですが、やっぱり構文解析は重めで辛いです。じゃんけんの勝敗情報の埋め込みとか、バグる予感しかしなくて大変でした。
カラオケで適当に書いてたら自然と左結合になって厳しかったです。ただ、演算が全部可換で2文字以上のトークンが存在しないので、入力対象のstringをそのままreverseしたら通りました。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
const i64 MOD = 1000000007;
template <i64 mod = MOD>
struct ModInt{
i64 p;
ModInt() : p(0){}
ModInt(i64 x){p = x >= 0 ? x % mod : x + (-x + mod - 1) / mod * mod;}
ModInt& operator+=(const ModInt& y){p = p + *y - ((p + *y) >= mod ? mod : 0); return *this;}
ModInt& operator-=(const ModInt& y){p = p - *y + (p - *y < 0 ? mod : 0); return *this;}
ModInt& operator*=(const ModInt& y){p = (p * *y) % mod; return *this;}
ModInt& operator%=(const ModInt& y){if(y)p %= *y; return *this;}
ModInt operator+(const ModInt& y) const{ModInt x = *this; return x += y;}
ModInt operator-(const ModInt& y) const{ModInt x = *this; return x -= y;}
ModInt operator*(const ModInt& y) const{ModInt x = *this; return x *= y;}
ModInt operator%(const ModInt& y) const{ModInt x = *this; return x %= y;}
friend ostream& operator<<(ostream& stream, const ModInt<mod>& x){
stream << *x;
return stream;
}
friend ostream& operator>>(ostream& stream, const ModInt<mod>& x){
stream >> *x;
return stream;
}
ModInt& operator++(){p = (p + 1) % mod; return *this;}
ModInt& operator--(){p = (p - 1 + mod) % mod; return *this;}
bool operator==(const ModInt& y) const{return p == *y;}
bool operator!=(const ModInt& y) const{return p != *y;}
const i64& operator*() const{return p;}
i64& operator*(){return p;}
};
using mint = ModInt<>;
signed main(){
int n;
string s;
char tmp;
cin >> n >> s >> tmp;
string p = "RSP";
int target = p.find(tmp);
reverse(s.begin(), s.end());
s += ";";
int c = 0;
struct Block{
array<mint, 3> res;
int r;
};
auto merge_plus = [&](Block& l, Block& r){
vector<vector<int>> magic{
{0, 0, 2},
{0, 1, 1},
{2, 1, 2}
};
array<mint, 3> m{mint(0), mint(0), mint(0)};
for(int i = 0; i < 3; ++i)
for(int j = 0; j < 3; ++j)
m[magic[i][j]] += l.res[i] * r.res[j];
return m;
};
auto merge_minus = [&](Block& l, Block& r){
vector<vector<int>> magic{
{0, 1, 0},
{1, 1, 2},
{0, 2, 2}
};
array<mint, 3> m{mint(0), mint(0), mint(0)};
for(int i = 0; i < 3; ++i)
for(int j = 0; j < 3; ++j)
m[magic[i][j]] += l.res[i] * r.res[j];
return m;
};
auto merge_mul = [&](Block& l, Block& r){
vector<vector<int>> magic{
{0, 2, 1},
{2, 1, 0},
{1, 0, 2}
};
array<mint, 3> m{mint(0), mint(0), mint(0)};
for(int i = 0; i < 3; ++i)
for(int j = 0; j < 3; ++j)
m[magic[i][j]] += l.res[i] * r.res[j];
return m;
};
function<Block(int)> expr, term, factor;
expr = [&](int l){
auto res = term(l);
if(s[res.r] == '+'){
Block ret;
auto res2 = expr(res.r + 1);
ret.r = res2.r;
TODO
ret.res = merge_plus(res, res2);
return ret;
}
else if(s[res.r] == '-'){
Block ret;
auto res2 = expr(res.r + 1);
ret.r = res2.r;
TODO
ret.res = merge_minus(res, res2);
return ret;
}
else
return res;
};
term = [&](int l){
auto res = factor(l);
if(s[res.r] == '*'){
Block ret;
auto res2 = term(res.r + 1);
ret.r = res2.r;
ret.res = merge_mul(res, res2);
TODO
return ret;
}
return res;
};
factor = [&](int l){
Block ret;
assert(l < n);
ret.r = l + 1;
if(s[l] == 'R')
ret.res = {mint(1), mint(0), mint(0)};
else if(s[l] == 'S')
ret.res = {mint(0), mint(1), mint(0)};
else if(s[l] == 'P')
ret.res = {mint(0), mint(0), mint(1)};
else if(s[l] == '?')
ret.res = {mint(1), mint(1), mint(1)};
else{
ret = expr(l + 1);
++ret.r;
}
return ret;
};
auto res = expr(0);
assert(res.r == n);
cout << res.res[target] << endl;
}
A問題
電車で帰宅中にスマホコーディングをします。90度回転がめんどいな〜って感じだったんですが、問題文をよく見るとどうやって解けばいいかが書いてあったので解けました。
#include <bits/stdc++.h>
using namespace std;
using i64 = long;
signed main() {
int n;cin>>n;
vector<string> s(n),t(n);
for(int i=0;i<n;++i)cin>>s[i];
for(int i=0;i<n;++i)cin>>t[i];
int ans=1e9;auto f=[&](int c){int k=0;for(int i=0;i<n;++i)for(int j=0;j<n;++j)if(s[i][j]!=t[i][j])++k;ans=min(ans,k+c);
};
auto rotate=[&](){vector<string> tmp=s;
for(int i=0;i<n;++i)for(int j=0;j<n;++j)s[j][n-1-i]=tmp[i][j];};
f(0);
rotate();f(1);
rotate();f(2);
rotate();f(1);
cout<<ans<<endl;
}
B問題
「一番遠い場所から戻ってくるといい」みたいな事がサンプルに書いてあるので、それで書きます。考えるのが面倒なので電車内でスマホから脳死で二分探索をすると通りました。
#include <bits/stdc++.h>
using namespace std;
using i64 = long;
signed main() {
int n;cin>>n;
vector<pair<i64,i64>>a(n);
for(int i=0;i<n;++i)cin>>a[i].first>>a[i].second;
sort(a.begin(),a.end());
auto f=[&](i64 val){i64 time=a.back().first;for(int i=0;i<n;++i)if(val+(a.back().first-a[i].first)<a[i].second)return false;
return true;
};
i64 ok=1e18,ng=max(a.back().second,a.back().first)-1;while(ok-ng>1){i64 mid=(ok+ng)/2;(f(mid)?ok:ng)=mid;
}cout<<a.back().first+ok<<endl;}
おわりに
全完できてよかったです。終盤3問の難易度は5-7-8、ボーダーは340-370ぐらいだと思いました。
