はまやんはまやんはまやん

hamayanhamayan's blog

Swaps [NIKKEI Programming Contest 2019-2 C]

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_c

解説

https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8373471

TLで見つけたスーパーコーナーケース

4  
2 1 4 3  
1 2 3 4  

なるほど、という言葉しか出てこない。
解説に移ろう。

まずは、自明な所から攻めていく。
AとBをソートしたものをA2,B2とする。
このとき、A2[i]≦B2[i]が満たされている必要がある。
そうでないならNo
swapを使ってのソートはN-1回swapが必要である。
しかし今回はN-2回までしかswapが使えないので、どうしようかとなる。
そのため、自分は本番では、A[i]≦B[i]を満たすA[i],B[i]以外のA,Bをソートして、
A2[i]≦B2[i]が全て満たされているかを判定すればいいと考えた。
この方針ではスーパーコーナーケースに阻まれる。

スーパーコーナーケースから知見を得ることにする。
A = {2 1 4 3}であり、A2 = {1 2 3 4}であるが、これはA[0]がA2[1]へ、A[1]がA2[0]へ移動している。
これを遷移と考えると、なもりグラフになる。
実際はもっと違う性質を持っていて、入次辺と出次辺が全て1なので、ループのみの連結成分が1つ以上あるグラフになっている。
ループが1つであれば、N-1回のswapが必要であるが、スーパーコーナーケースのようにループが2つなら、
swapを1回減らすことができる。
実際にはBもソートされているので、A2[i]=B2[j]であるiからjに有向辺を引いてループの個数を調べよう。
ループが2つ以上あればyesである。
ループ検出はdfsでもUnionFindでもいい。
知見としてはei1333さんが言っていた「N-1回交換が必要→閉路グラフ」これに集約されそう。

これでもまだ通らない。

4  
2 3 4 1  
5 6 6 7  

これがNoになっちゃうはず。
A2が{1,2,3,4}なので、1->2->3->4->1で1つのループになる。
だが、今回はA2として{2,1,3,4}のようにしても問題ない。
つまり、ソート済み+1回のswapでもOKなら、ループが1つであってもswapにより2つになるので、yesとなる。
これは一番可能性が高いのは隣り合う要素となるので、隣合う要素を確認して、swapしても問題ないならyesとなる。
ここまでやって、やっとAC

int N, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
pair<int, int> A2[101010], B2[101010];
string solve() {
    rep(i, 0, N) A2[i] = { A[i], i };
    sort(A2, A2 + N);
    rep(i, 0, N) B2[i] = { B[i], i };
    sort(B2, B2 + N);

    // 前提条件チェック
    rep(i, 0, N) if (A2[i].first > B2[i].first) return no;

    // ループが2つ以上ならyes
    UnionFind uf(N);
    rep(i, 0, N) uf(A2[i].second, B2[i].second);
    int cnt = 0;
    rep(i, 0, N) if (uf[i] == i) cnt++;
    if (1 < cnt) return yes;
    
    // ラストコーナー対策
    rep(i, 0, N - 1) if (A2[i].first <= B2[i + 1].first and A2[i + 1].first <= B2[i].first) return yes;

    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
    cout << solve() << endl;
}

Shortest Path on a Line [NIKKEI Programming Contest 2019-2 D]

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_d

前提知識

解説

https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8371669

本家解答はダイクストラ
以下、セグメントツリーとDPによる解答を示す。

区間条件と最短経路といえば、Rを昇順に処理していって、DPをセグメントツリーで高速化テク。
この方針で考えていくと解けそうになってくる。
dp[i] := 頂点iに到着する為の最短経路
区間をR昇順でソートして、順番にDPを更新していく。
dp[R] = min(dp[R], min(dp[L], dp[L+1], ..., dp[R]) + C)
これで更新していけばいい。

更新先が頂点Rだけで良い理由を説明する。
区間[L1,R1]を使って移動した後に、区間[L2,R2]を使って移動するためには、
[L2,R2]の中にR1が入っているかだけを考えればいい。
よって、区間[L1,R1]を使って移動してきたという情報を頂点R1だけに伝播させれば、
直前の移動情報を正しく、かつ、まとめて保持しておくことができる。
それっぽく説明したけど、後付なので謎理論かも。

あとは、dp[N]が答え。

int N, M;
vector<pair<int, int>> Q[101010];
SegTree<ll, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int l, r, c; cin >> l >> r >> c;
        Q[r].push_back({ l, c });
    }

    st.update(1, 0);
    rep(r, 1, N + 1) {
        fore(p, Q[r]) {
            int l = p.first;
            int c = p.second;
            st.update(r, min(st[r], st.get(l, r) + c));
        }
    }
    ll ans = st[N];
    if (ans == infl) ans = -1;
    cout << ans << endl;
}

Counting of Trees [NIKKEI Programming Contest 2019-2 B]

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_b

解説

https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8371235

300点問題ではあるが、累乗を使う所があるので、そのライブラリを持っていないと厳しい。
mod上での掛け算は理解しているとして進める(かけてmodとるだけだけど)。
後、色々コーナーケースがあるので注意。

根から順番に組み合わせを確定させていくことを考える。
頂点1は根なのでD[0]=1である必要があり、かつ、ここだけである必要がある。
cnt[d] := D[i]=dである頂点の個数
以上のように置くと、cnt[0]=1である必要がある。

距離が1の頂点について考えると、これは全て根につなげるしか無い。
よって、1通り。

距離が2の頂点について考える。
その中の1つの頂点について考えると、これを距離が1の頂点のどれかにつなげると考えるとcnt[1]通りある。
他の頂点についても同様であるため、距離が2の頂点を距離が1の頂点につなげる組み合わせは、
cnt[1]^cnt[2]通りとなる。
この計算は、以下も同様となるので、求めたい答えはcnt[i]^cnt[i+1]の総積である。

あと、距離は0から順番に存在する必要がある。
距離3と5の頂点はあるけど、距離4の頂点は無いというのはありえない。

int N, D[101010];
//---------------------------------------------------------------------------------------------------
mint solve() {
    map<int, int> cnt;
    rep(i, 0, N) cnt[D[i]]++;

    int n = cnt.size();
    rep(i, 0, n) if (cnt[i] == 0) return 0;
    if (cnt[0] != 1) return 0;
    if (D[0] != 0) return 0;

    mint res = 1;
    rep(i, 1, n) res *= mint(cnt[i - 1]) ^ cnt[i];
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> D[i];
    cout << solve() << endl;
}

Non-triangular Triplets [NIKKEI Programming Contest 2019-2 E]

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_e

解説

https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8372437

yes/no判定だけでなく、構築結果も出せという問題なので、
単純なルールで構築が出せるのだろうとまずは仮定をする。
で、限界条件を頑張ってルール化すると、それっぽい構築法が出てくる。
その、それっぽい構築法を説明する。

a<b<cと仮定する。
加えて、小さい順からN個ずつ数を区切ったときにaが最初のグループ、
bが中のグループ、cが最後のグループに属すことになる。
これは実験により導いたが、正直これくらいの前提が無いと厳しいからなぁ・・・みたいな気持ちもある。

a[i]+b[i]≦c[i]であるが、この仮定により、総和を取ると嬉しい式が出てくる。
(NK + N(N-1)/2) + (NK + N(2N-1+N)/2) ≦ (NK + N(3N-1+2N)/2)
NK + (N2-N+3N2-N) / 2 ≦ (5N2-N) / 2
2NK + 4N2 - 2N ≦ 5N2 - N
2K + 4N - 2 ≦ 5N - 1
2K ≦ N + 1
K≦ (N + 1) / 2
ということで、この条件を満たすときに構築可能である。

N=4とかN=5とかでこの上限条件でのうまい構築ルールを考えると、思いつく。
1. (K, K+2N-1, K+2N-1+K)とする
2. (K+1, K+2N-3, K+2N-1+K-1)とする(bを-2して、cを-1する。すると差はK+1)になる
3. 2.をできる限り続ける(全部でK回行う)
4. (K+K, K+2N-1, K+3N-1)とする
5. (K+K+1, K+2N-1, K+3N-2)とする(b,cをまだ割りあたってない最大の数として割り当てていく)
なんか分からんけど、これで通る。

int N, K;
//---------------------------------------------------------------------------------------------------
vector<vector<int>> solve() {
    if (K > (N + 1) / 2) return {};

    int a = K;
    int b = K + 2 * N - 1;
    int c = b + K;

    set<int> sa, sb, sc;
    vector<vector<int>> ans;
    while (K + N <= b and K + 2 * N <= c) {
        sa.insert(a);
        sb.insert(b);
        sc.insert(c);
        ans.push_back({ a, b, c });
        a++;
        b -= 2;
        c--;
    }

    b = K + 2 * N - 1;
    c = K + 3 * N - 1;
    while (sb.count(b)) b--;
    while (sc.count(c)) c--;
    while (a < K + N and K + N <= b and K + 2 * N <= c) {
        sa.insert(a);
        sb.insert(b);
        sc.insert(c);
        ans.push_back({ a, b, c });
        a++; b--; c--;
        while (sb.count(b)) b--;
        while (sa.count(c)) c--;
    }
    
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    auto ans = solve();
    if (ans.size() == 0) {
        cout << -1 << endl;
        return;
    }
    fore(v, ans) printf("%d %d %d\n", v[0], v[1], v[2]);
}

Sum of Two Integers [NIKKEI Programming Contest 2019-2 A]

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_a

解説

https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8370714

組み合わせを全探索してもいいが、計算だけでも解ける。
N=1+(N-1)=2+(N-2)=...=(N-1)+1
と考えると(N-1)通りある。
だが、順番は考えないので、組み合わせ数は半分になり、(N-1)/2が答え。
Nが偶数のときに相異なるに反するパターンもあったりするが、切り捨てしとくとうまいこと消える。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    int ans = (N - 1) / 2;
    cout << ans << endl;
}

日本情報オリンピック 予選の傾向と対策

自分は日本情報オリンピック出たこと無いし、運営という訳でもないので、参考程度にご覧ください。

はじめに

  • 概要と特徴
    • JOI: 日本情報オリンピック
    • 一人で実施する
    • 6問あり、全部100点満点であるが、部分点がある問題が多い
      • 部分点の付け方もJOI2017/2018を境に変わっている
      • それより前は入力データが5つあり、1つ20点として換算されてる?
    • JOI2017/2018から予選はAtCoderでやっているようで、フルフィードバックなんだろうか(要出典)
    • JOI2019/2020からも予選方式が変わり、1次2次という形になっているみたい
  • 目標
    • 予選突破の目標は3完+部分点。4完ならば、今の所突破できそう
    • 年々難しくなってる

対策

傾向

  • 前半3つ
    • 全探索、シミュレーション、貪欲法が中心
    • 特殊なアルゴリズムをあまり要求しないが、実装がちょっと大変なものもある
    • 全探索対象を探して、しっかり全探索する
    • ABCならCまで通していきたい。Dレベルも。
  • 後半3つ

年別統計

JOI2018/2019

# 題名 配点 要求(白塗りしてあるので選択で見て) 解説
A 40/60 ソーシャルゲーム 全探索、シミュレーション 解説
B 100 すごろくと駒 シミュレーション 解説
C 100 マルバツスタンプ 貪欲法(hamayanhamayan解説解法はDPだけどいらない) 解説
D 7/8/85 日本沈没 シミュレーション、座標圧縮 解説
E 10/30/30/30 イルミネーション 解説
F 6/14/80 座席 組み合わせ問題、高次元DP 解説

3完+部分点全部くらいがボーダー(391点)

JOI2017/2018

# 題名 配点 要求(白塗りしてあるので選択で見て) 解説
A 100 鉛筆 基本計算 解説
B 100 双六 全探索+シミュレーション(hamayanhamayan解説では幅優先探索してるけどいらない) 解説
C 10/90 幹線道路 全探索 解説
D 10/27/63 水ようかん 小課題は状態全列挙、完答も全探索 解説
E 15/28/57 森林伐採 3次元でのDP 解説
F 6/33/61 L番目のK番目の数 二分探索,累積和 解説

3完+部分点1つ目+部分点どれかの2つ目がボーダー(334点以上)

JOI2016/2017 第16回日本情報オリンピック 予選

# 題名 配点 要求(白塗りしてあるので選択で見て) 解説
A 100 電子レンジ 場合分け、基本計算 解説
B 100 ポイントカード 貪欲法、ソート 解説
C 100 休憩スペース 全探索、(2次元累積和) 解説
D 100 ぬいぐるみの整理 bitDP、累積和 解説
E 100 尾根 幅優先探索 解説
F 100 ヘビのJOi君 拡張ダイクストラ 解説

3完+一部解答がボーダー(340点以上)

JOI2015/2016 第15回日本情報オリンピック 予選

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_b https://www.ioi-jp.org/joi/2015/2016-yo/index.html

# 題名 配点 要求(白塗りしてあるので選択で見て) 解説
A 100 科目選択 最大最小 解説
B 100 ゼッケンの交換 シミュレーション 解説
C 100 ロシアの旗 全探索 解説
D 100 JOI国のお散歩事情 事前計算 解説
E 100 ゾンビ島 複数始点BFS, ダイクストラ 解説
F 100 屋台 超多次元DP、大変な遷移 解説

JOI国のお散歩事情 (Walking in JOI Kingdom) [第15回日本情報オリンピック 予選(オンライン) D]

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_d

解説

https://atcoder.jp/contests/joi2016yo/submissions/8344299

それぞれの制約が大きく、制約から考えていくのは難しそう。
問題の弱点について考えていこう。
立ち止まる条件を考えると→←となってれば出会うので、時間が立つと立ち止まる。
あと、最左にある←は立ち止まることはない。
例えば、→→←←とかになってれば、この4つはある1点に集まる。
つまり、→←のグループに分割していってそれぞれに集まる時間が分かってくる。

これでとりあえず、ある1つの→←について考えていけば良くなった。
まず→←が出会う場所はここの中点になる。
→→→←←←となっていても、真ん中の→←の中点に全て集まる。
集まる場所がわかれば、そこにかかる時間もわかるので、その時間をそれぞれの場所について事前計算しておく。
その時間より前であれば、普通に動かして、後であれば、集まる場所に移動させる。
これを繰り返すことで、全ての場所について時間が立った後の場所がわかる。
最左の←と最右の→については集まる時間に制約がないので注意。

自分は実装のために、←を<、→の>として、文章にし、ランレングス圧縮をした上で操作している。
過実装ではあるが、用意してあるアルゴリズムが使えるのと、考えやすくなる。
あと、ちょっと見やすい。

int N; ll T; int Q;
ll A[101010]; int D[101010];
ll ans[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> T >> Q;
    rep(i, 0, N) cin >> A[i] >> D[i];

    string S = "";
    rep(i, 0, N) S += ((D[i] == 1) ? ">" : "<");
    auto rl = runLengthEncoding(S);
    int N_rl = rl.size();

    int cur = 0;
    int i_rl = 0;
    if (rl[0].first == '<') {
        rep(i, 0, rl[0].second) ans[i] = A[i] - T;
        cur += rl[0].second;
        i_rl++;
    }
    while (i_rl + 1 < N_rl) {
        ll cent = (A[cur + rl[i_rl].second - 1] + A[cur + rl[i_rl].second]) / 2;
        
        rep(d, 0, rl[i_rl].second) {
            ll limit = cent - A[cur + d];
            if (limit <= T) ans[cur + d] = cent;
            else ans[cur + d] = A[cur + d] + T;
        }
        cur += rl[i_rl].second;
        i_rl++;

        rep(d, 0, rl[i_rl].second) {
            ll limit = A[cur + d] - cent;
            if (limit <= T) ans[cur + d] = cent;
            else ans[cur + d] = A[cur + d] - T;
        }
        cur += rl[i_rl].second;
        i_rl++;
    }
    if (i_rl < N_rl) {
        rep(d, 0, rl[i_rl].second) ans[cur + d] = A[cur + d] + T;
        cur += rl[i_rl].second;
        i_rl++;
    }

    rep(i, 0, Q) {
        int x; cin >> x; x--;
        printf("%lld\n", ans[x]);
    }
}