コンテスト
A問題
感想
$H+P_i$が$X$以上になる最小の$i$を求める。
コンテスト中提出コード
int main() {
ll n = in_ll();
ll h = in_ll();
ll x = in_ll();
vll p = in_vll(n);
ll t = -1;
ll pm = INF;
rep(i,n){
if(h+p[i] >= x) {
if(pm > (h+p[i])){
pm = p[i];
t = i+1;
}
}
}
print(t);
return 0;
}
B問題
感想
$A_i$をソートして、数が順番になっているか見ていく。
なくした整数が整数が一意に定まるようになっているので、最小の$A_i$から見ていけば良い。
コンテスト中提出コード
int main() {
ll n = in_ll();
vll a = in_vll(n);
sort(all(a));
dbg(a);
ll st = a[0];
rep(i,n){
if(st!=a[i]){
print(a[i]-1);
break;
} else{
st++;
}
}
return 0;
}
C問題
感想
コンテスト終了直前にACした。
最初、普通に全ての$i,j$間のdfsで解いていたが、最長経路を求める方法がわからず。
次に最大で$N=10$から全てのパターンの列挙をしようと思った。
next_permutationを使って、全てのパターンの順列を列挙したが、調べるべきパターンは順列だけではなく、1->3のようなパターも調べる必要があり、実装後、断念。
最後にdfsで列挙することを思いつきなんとかACした。
実装を始める前に入力例で実際に解けるかどうか、検討するべきだった。
コンテスト中提出コード
vector<bool> done;
vector<set<ll>> g;
vvll cost;
ll mdist;
void f(ll cur, ll cur_cost, ll target){
if(done[cur] == true){ return ; }
done[cur] = true;
fore(ad, g[cur]) {
if(ad==target){
chmax(mdist, cur_cost+cost[cur]);
}else{
f(ad,cur_cost+cost[cur],target);
}
}
done[cur] = false;
return;
}
int main() {
ll n = in_ll();
ll m = in_ll();
g.resize(n+1);
cost.resize(n,vll(n,INF));
rep(i,m){
ll a = in_ll();
ll b = in_ll();
ll c = in_ll();
g[a-1].insert(b-1);
g[b-1].insert(a-1);
cost[a-1][b-1] = c;
cost[b-1][a-1] = c;
}
mdist = 0;
rep(i,n){
reps(j,i+1,n){
done.resize(n,false);
f(i,0,j);
}
}
print(mdist);
return 0;
}
D問題
感想
コンテスト中に着手できなかったため、次の日に解説見ずにACした。
問題設定が複雑に感じた。
まず、現状の議席数を高橋君と青木君で分けてカウントする。
高橋君の獲得議席を$Z_t$、青木君の獲得議席を$Z_a$とする。
この時、$Z_t>Z_a$だったらすでに勝利しているので、0を出力して終わる。
$Z_a>Z_t$の時、議席を奪う必要がある。
奪う議席数を$t$として、$Z_a-t<Z_t+t$となれば、高橋君の勝ちになる。
変形すると$t>\frac{(Z_a-Z_t)}{2}$になれば良いとわかる。
よって、奪うべき議席は$\frac{(Z_a-Z_t+1)}{2}$となる。
これから青木君が勝っている選挙区から好きな個数選んで、$\frac{(Z_a-Z_t+1)}{2}$以上の議席にすることを目標とする。
dpを使って解くことにする。
dpは以下の定義にする。
$$dp[i][j]: 青木派の選挙区を集めてi番目まで見た時に、j議席獲得するとき、鞍替えさせるべき最小の人数$$
ある選挙区を高橋派が勝利するようにするには、鞍替えさせる人数をkとして、$Y[i]-k<X[i]+k$となれば良い。
議席の時と同様にして、ある選挙区を高橋派のものにするには$k=\frac{Y[i]-X[i]+1}{2}$人鞍替えさせれば良い。
kを使うとdpの遷移式は次のようになる。
$$dp[i+1][min(\frac{Z_a-Z_t+1}{2},j+k)] = \min(dp[i][j]+k),dp[i][min(\frac{Z_a-Z_t+1}{2},j+k)])$$
$$dp[i+1][j] = \min(dp[i+1][j]),dp[i][j])$$
ここで$min(\frac{Z_a-Z_t+1}{2},j+k)$としているのは、$\frac{Z_a-Z_t+1}{2}$以上ならどれだけ議席を獲得しても高橋君が勝利できるからである。
こうすることで、$dp[青木派の選挙区の個数][\frac{Z_a-Z_t+1}{2}]$が答えになる。
後日提出コード
E問題
感想
これもコンテスト中に着手できなかったため、次の日に解説みずにACした。
この問題は比較的わかりやすかった。
まず初めに「 >, v, <, ^」によって、見られている場所を’.’以外にマークする
その後BFSを行い最短距離を求める。
実装が少し長くなってし待ったがACできた。
初め、BFSでなくDFSを使ってしまったため、WAになってしまった。
後日提出コード
コメント