2023-11-25

[JOI精進録] 難易度6「Relay」(JOIG2021/2022 春合宿A)

JOI精進録

問題リンク

問題概要

$N$ 人の人 $i$ ( $1 \le i \le N$ )がいて、それぞれに $A_i$ 、 $B_i$ が定められている。
この中から3人 $i,j,k$ ( $1 \le i,j,k \le N$ )を選び、 $A_i + A_k + A_j + max(B_i,B_k) + max(B_k,B_j)$ を最小化してください。

解説

AC解法 (100/100点)

$1 \le j$ < $k$ < $i \le N$ として選ぶことで2つの $B$ の最大値の和を最小化することができます。今後はこの制約で選ぶことを考えます。
$k$ を全探索します。
$j$ は $A_j$ が最小になる $j$ 、 $i$ は $A_i+B_i$ が最小になる $i$ を選ぶのが最適です。
これは累積minを使って前計算 $O(N)$ 、クエリ $O(1)$ で求められ、全探索に $O(N)$ かかるので全体 $O(N)$ でこの問題を解くことができました。

ACコード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n,r(numeric_limits<int>::max()); cin >> n;
  vector<pair<int,int>> A(n); for (auto& [b,a]:A) cin >> a >> b;
  sort(A.begin(),A.end());
  vector<int> acc(n+1,r); for (int i(n-1);i > -1;--i) acc[i]=min(acc[i+1],A[i].first+A[i].second); int mn(A[0].second);
  for (int i(1);i < n-1;++i){
    r=min(r,A[i].first+A[i].second+mn+acc[i+1]);
    mn=min(mn,A[i].second);
  }
  cout << r << endl;
}

提出結果

atcoder.jp

2023-11-25

[JOI精進録] 難易度7「最悪の記者」(第6回日本情報オリンピック本選D)

問題リンク

atcoder.jp

問題概要

大会が開催され、一部の試合の結果が渡される。
この結果には引き分けはなく、全てのチームに異なる順位が付き、どの試合でも順位が上のチームが勝利した。
この試合結果に矛盾しない順位表を一つ出力し、また考えられる順位表は一つだけか判定しなさい。

解説

AC解法 (20/20点)

トポロジカルソートをすればよいです。
トポロジカルソートは入次数が0になっている頂点を順にqueに追加、探索すれば作成できます。
このときqueに入っている要素の数は0もしくは1の場合は他の選択肢がないですが、それ以外の場合はそちらを選択することも可能です。
そのためqueのサイズを監視することで判定が可能です。

ACコード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n,m,r(0); cin >> n >> m;
  vector<vector<int>> G(n); vector<int> B(n),R;
  for (int i(0),a,b;i < m;++i) (cin>>a>>b),G[a-1].emplace_back(b-1),++B[b-1];
  queue<int> que;
  for (int i(0);i < n;++i) if (B[i]==0) que.emplace(i);
  while(!que.empty()){
    auto x = que.front(); que.pop();
    if (!que.empty()) r=1;
    R.emplace_back(x+1);
    for (auto a:G[x]){
      --B[a];
      if (B[a]==0) que.emplace(a);
    }
  }
  for (auto a:R) cout << a << '\n';
  cout << r << endl;
}

提出結果

atcoder.jp

2023-11-23

[JOI精進録] 難易度7「美術展」(JOI2017/2018 本選B)

問題リンク

atcoder.jp

問題概要

$N$ 個の品物 $i$ ( $1 \le i \le N$ )があり、それぞれに大きさ $A_i$ と価値 $B_i$ が定められている。
この中からいくつかの品物を選び、価値の総和-(大きさの最大値-大きさの最小値)を最大化してください。

解説

AC解法(100/100点)

価値の総和を $v$ 、大きさの最大値を $x$ 、最小値を $y$ とします。
$v-(x-y)$
$v-x+y$
$v+y-x$
$v$ はどの $y$ でも同じように増えていくので、最大値を全探索して今までの $v+y$ の最大値と現在探索中の値を比較更新していけばよいです。

ACコード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n; cin >> n;
  map<long long,long long> M;
  long long t=0,r=0,a,b;
  while(n--) (cin>>a>>b),M[a]+=b;
  for (auto [a,b]:M) t = max(t,a),t += b,r = max(r,t-a);
  cout << r << endl;
}

提出結果

atcoder.jp

2023-10-21

[JOI精進録] 難易度7「IOI列車で行こう」(第12回日本情報オリンピック本選B)

JOI精進録

問題リンク

atcoder.jp

問題概要

2つの文字列 $S$ 、 $T$ がある。
文字列からそれぞれ先頭何文字かを無視し、その後の文字列について以下を考える。
・I、O、I、O、...、Iとなるように文字列の先頭から一文字ずつ取り出して構成していったときの最大の構成できる長さ
適切に無視する長さと取り出す順番を考えたとき、最大の長さを出力してください。

解説

AC解法 (100/100点)

$dp_{i,k,o} =$ $S$ の先頭 $i$ 文字、 $T$ の先頭 $k$ 文字を考えて最後の文字が $o$ になるように構成したときの最大の長さ
として、条件を満たすようにDPテーブルを更新していきます。

ACコード

#include <bits/stdc++.h>
using namespace std;
// dp[i][k][o] = Sから先頭iTから先頭kを待機または編成して最後がo[1:i 0:o]のときできる最大の編成長
int main(){
  int n, m, r(0); string s,t; cin >> n >> m >> s >> t;
  vector dp(n+1,vector(m+1,vector(2,0)));
  for (int i(0);i <= n;++i) for (int k(0);k <= m;++k){
    if (i==k&&i==0) continue;
    if (k!=0) dp[i][k][t[k-1]=='I']=max(dp[i][k][t[k-1]=='I'],dp[i][k-1][t[k-1]=='O']+max((bool)dp[i][k-1][t[k-1]=='O'],t[k-1]=='I'));
    if (k!=0&&t[k-1]=='I') r = max(r,dp[i][k][1]);
    if (i!=0) dp[i][k][s[i-1]=='I']=max(dp[i][k][s[i-1]=='I'],dp[i-1][k][s[i-1]=='O']+max((bool)dp[i-1][k][s[i-1]=='O'],s[i-1]=='I'));
    if (i!=0&&s[i-1]=='I') r = max(r,dp[i][k][1]);
  }
  cout << r << endl;
}

提出結果

atcoder.jp

2023-10-20

[JOI精進録] 難易度7「committee」(2008年日本情報オリンピック春合宿1-1)

JOI精進録

問題リンク

atcoder.jp

問題概要

N人の人がいて、上下関係の木とそれぞれのやる気が渡される。
直接の関係を持つ人同士でしか連絡が取れないため、何人かを通して(通さなくてもよい)連絡が取れる人物を1人以上選出する。
また連絡の際中継する人物も入れなければならない。やる気の総和を最大化してください。

解説

AC解法 (100/100点)

木DPです。DFSをして子が正の数なら足していき、自分自身のやる気を更に足して更新します。

ACコード

#include <bits/stdc++.h>
using namespace std;

int dfs(vector<vector<int>>& G,int d,vector<int>& A,int& r) noexcept {
  int dp = A[d],t;
  for (auto a:G[d]){
    t = dfs(G,a,A,r);
    if (t>0) dp+=t;
  }
  r = max(r,dp);
  return dp;
};

int main(){
  int r,n,a,b; cin >> n;
  vector<vector<int>> G(n); vector<int> A(n);
  for (int i(0);i < n;++i){
    (cin>>a>>b),A[i]=b;
    if (a==0) continue;
    G[a-1].emplace_back(i);
  }
  //assert(*max_element(A.begin(),A.end())>=0);
  r = *max_element(A.begin(),A.end());
  dfs(G,0,A,r);
  cout << r << endl;
}

提出結果

atcoder.jp

2023-10-12

[JOI精進録] 難易度7「fermat」(2007年日本情報オリンピック春合宿3-2)

JOI精進録

問題リンク

atcoder.jp

問題概要

$x^n+y^n \equiv z^n \pmod p$ を満たす $x,y,z$ $(0 \le x,y,z \le p-1)$ の組はいくつ考えられますか?

解説

AC解法1 (100/100点)

繰り返し二乗法を使って $O(p \; log \; n)$ で $n$ 乗の数を $p$ で割ったあまりを列挙し、
$A_i=$ $n$ 乗して $p$ で割ったあまりが $i$ になる $x$ の数
を数え上げます。
$x$ と $y$ について $A$ を全探索すると、 $z$ は定数時間で求められるため $O(P^2)$ で答えることができます。

ACコード1

#include <bits/stdc++.h>
using namespace std;

int main(){
  int p,n; cin >> p >> n;
  long long r(0);
  vector<int> A(p);
  for (int i(0);i < p;++i){
    int r = 1;
    for (int t = n,u = i;t;t>>=1,u*=u,u%=p) if ((t&1)) r*=u,r%=p;
    ++A[r];
  }
  for (int i(0);i < p;++i) for (int k(0);k < p;++k){
    r += A[i]*A[k]*A[(i+k)%p];
  }
  cout << r << endl;
}

提出結果1

atcoder.jp

AC解法2(1より高速) (100/100点)

$A$ を1では全探索したところでFFTです。ACLに定義されているのを使うと簡単に実装できます。

ACコード2

#include <bits/stdc++.h>
#include <atcoder/convolution>
using namespace std;

int main(){
#define int long long
  int p,n,r; cin >> p >> n;
  vector<int> A(p);
  for (int i(0);i < p;++i){
    r = 1;
    for (int t = n,u = i;t;t>>=1,u*=u,u%=p) if ((t&1)) r*=u,r%=p;
    ++A[r];
  }
  vector<int> B = atcoder::convolution_ll(A,A);
  for (int i(0);i < B.size();++i) B[i]*=A[i%p];
  cout << accumulate(B.begin(),B.end(),0ll) << endl;
}

提出結果2

atcoder.jp

2023-10-12

[JOI精進録] 難易度7「お菓子の分割」(第9回日本情報オリンピック本選B)

JOI精進録

問題リンク

atcoder.jp

問題概要

$N$ mmのお菓子がある。このお菓子を $N/2$ mmずつ2人で分ける。
このお菓子は切る場所によって違うコストがかかる。
このコストの総和の最小値を求めなさい。

解説

AC解法と同じ計算量だがMLEする解法 (12/20点)

$dp_{i,k} =$ 人1が $i$ mm、人2が $k$ mm分先頭から切り分けて配ったとき、コストの最小値
とする。更新は $i$ だけを変えて計算済みの場所のコストの最小値と $k$ だけを変えて計算済みの場所のコストの最小値の小さい方に今から切る分のコストを足したものとする。
累積minを取ることで $O((N/2)^2)$ で計算できる。
累積minは1次元+0次元、dp配列は2次元である。

AC解法 (20/20点)

dp配列は更新に累積minしか使わないので0次元のみでよい。
ということで計算量は同じで、dp配列を0次元にしたのでメモリの使用量が大幅に減る。

ACコード

このブログ書いてて配列外参照起こしてることに気づきました。以下は修正版のコード、提出結果です。

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n, acc1,t; cin >> n;
  vector<int> A(n-1),acc0(n/2+1,numeric_limits<int>::max()); for (int& a:A) cin >> a;
  A.emplace_back(0);
  for (int k(1);k <= n/2;++k) acc0[k] = A[k-1];
  for (int i(1);i <= n/2;++i){
    acc1 = A[i-1];
    for (int k(1);k <= n/2;++k){
      t = min(acc1,acc0[k])+A[i+k-1];
      acc0[k] = min(acc0[k],t),acc1 = min(acc1,t);
    }
  }
  cout << t << endl;
}

提出結果

atcoder.jp