kuretchi's blog

競技プログラミング初心者のブログです。

AtCoder Regular Contest 080: E - Young Maids

http://arc080.contest.atcoder.jp/tasks/arc080_c

概要

ある正の偶数 $N$ について、 $(1,2,\cdots,N)$ の順列 $p=(p_1,p_2,\cdots,p_N)$ が与えられる。 $p$ のうち隣り合う $2$ 項を取り、新しい数列 $q$ の先頭に追加する。これを $p$ が空になるまで ($N/2$ 回) 繰り返したとき、 $q$ は $(1,2,\cdots,N)$ の順列になっているが、このような $q$ のうち辞書順最小のものを求めよ。

解法

$q$ の初項にできるだけ小さい数を持って来たい。サンプル 3 を見てみよう。

$p=(4,6,3,2,8,5,7,1), q=(3,1,2,7,4,6,8,5)$

$q$ の初項は $3$ となっているが、これは $p$ の偶数番目の項の最小値であり、その次の $1$ は、 $p$ で $3$ より後ろの項のうち奇数番目の項の最小値である。すなわち、任意の数列について、同様の議論によって前から 2 つの項が決定可能であることが分かる。

$3,1$ を除くと、 $p$ が分割され $(4,6),(2,8,5,7)$ の 2 つの数列ができる ($1$ が末項でなければ 3 つ)。あとは、先程の議論に従って、それぞれの数列に対して、前から 2 つの項を再帰的に決定していけばよい。この場合、 $(4,6)$ より $(2,8,5,7)$ からの方が辞書順で小さい 2 項を取ることができるので、先にこちらを処理する。これは、各数列の偶数番目の項の最小値を比較すればよい。

以上を愚直にやると $O(N ^ 2)$ となり間に合わないため、適切なデータ構造を使って高速化しよう。数列のある区間における偶数 (奇数) 番目の項の最小値は、Segment 木を 2 つ用意しておけば $O(\log N)$ で求められる (更新の必要がないため、Sparse Table 等を用いてもよい)。分割された数列のうち次に処理すべき数列を決めるには、毎回、偶数番目の項の最小値をキーとして、数列を優先度付きキューに enqueue することで、処理すべき順序で数列が得られる ($O(\log N)$)。以上の工夫で、全体の計算量は $O(N \log N)$ となり十分高速。

実装

偶数 (奇数) 番目の要素のみを格納した Segment 木を作ってもよいが、インデックスが面倒くさいことになるので、例えば偶数番目の要素のみの Segment 木は奇数番目に $\infty$ を入れておけばよい。

また、最小値を取り出すときに一緒にそのインデックスも得られるようにしておく必要がある。

static void Solve(IO io)
{
    var n = io.I;
    var p = io.Is(n);

    var pi = new int[n + 1];
    for (var i = 0; i < n; i++) pi[p[i]] = i;

    var evenp = p.Select((x, i) => i % 2 == 0 ? x : Inf).ToArray();
    var oddp = p.Select((x, i) => i % 2 != 0 ? x : Inf).ToArray();
    var evenst = new SegmentTree<int>(evenp, Inf, Min);
    var oddst = new SegmentTree<int>(oddp, Inf, Min);

    var xmin = Inf;
    var xmini = 0;
    var ymin = Inf;
    var ymini = n - 1;

    var pq = new PriorityQueue<Pair>();
    pq.Enqueue(new Pair(xmini, ymini, evenst[xmini, ymini]));

    while (pq.Any())
    {
        var pair = pq.Dequeue();

        xmin = pair.X % 2 == 0 ?
            evenst[pair.X, pair.Y] : oddst[pair.X, pair.Y];
        xmini = pi[xmin];
        ymin = pair.X % 2 == 0 ?
            oddst[xmini + 1, pair.Y] : evenst[xmini + 1, pair.Y];
        ymini = pi[ymin];

        if (xmini > pair.X)
        {
            var tl = pair.X;
            var tr = xmini - 1;
            var min = pair.X % 2 == 0 ? evenst[tl, tr] : oddst[tl, tr];

            pq.Enqueue(new Pair(tl, tr, min));
        }

        if (ymini - xmini > 1)
        {
            var tl = xmini + 1;
            var tr = ymini - 1;
            var min = pair.X % 2 == 0 ? oddst[tl, tr] : evenst[tl, tr];

            pq.Enqueue(new Pair(tl, tr, min));
        }

        if (ymini < pair.Y)
        {
            var tl = ymini + 1;
            var tr = pair.Y;
            var min = pair.X % 2 == 0 ? evenst[tl, tr] : oddst[tl, tr];

            pq.Enqueue(new Pair(tl, tr, min));
        }

        Write(xmin + " " + ymin + " ");
    }
}

ソートと要素のインデックス

ここらへんでハマってとてもつらかったので書いておきます。

ソート後のインデックスから、ソート前のインデックスを知りたい

f:id:Kuretchi:20170728115804p:plain:w600

方法1

インデックスとのペアのコレクションを作り、要素をキーとしてソートする。

char arr[5] = { 'D', 'A', 'C', 'E', 'B' };

pair<char, int> arridx[5];
for (int i = 0; i < 5; i++) arridx[i] = make_pair(arr[i], i);
// arridx => { (D, 0), (A, 1), (C, 2), (E, 3), (B, 4) }

sort(begin(arridx), end(arridx),
    [](pair<char, int>& a, pair<char, int>& b) {
        return a.first < b.first; });
// arridx => { (A, 1), (B, 4), (C, 2), (D, 0), (E, 3) }

方法2

インデックスだけのコレクションを作り、ソートしたいコレクションの対応する要素をキーとしてソートする。

char arr[5] = { 'D', 'A', 'C', 'E', 'B' };

int idx[5];
for (int i = 0; i < 5; i++) idx[i] = i;
// idx => { 0, 1, 2, 3, 4 }

sort(begin(idx), end(idx),
    [&arr](int& a, int& b) { return arr[a] < arr[b]; });
// idx => { 1, 4, 2, 0, 3 }

このソートされたインデックスを使って、ソートされた順番で要素にアクセスできる。

for (int i = 0; i < 5; i++) cout << arr[idx[i]] << " ";
// => "A B C D E "

ソート前のインデックスから、ソート後のインデックスを知りたい

f:id:Kuretchi:20170728115811p:plain:w600

コレクションが与えられた後、そのインデックスがクエリとして与えられるが、事前に元のコレクションをソートしておく必要がある場合など。上図では、例えば要素 D について、ソート前のインデックス 0 からソート後のインデックス 3 を得ることができる。

前述の、ソートされたインデックスのコレクションから生成する。

方法1

int after_idx[5];
for (int i = 0; i < 5; i++) after_idx[arridx[i].second] = i;
// after_idx => { 3, 0, 2, 4, 1 }

方法2

int after_idx[5];
for (int i = 0; i < 5; i++) after_idx[idx[i]] = i;
// after_idx => { 3, 0, 2, 4, 1 }

AtCoder Beginner Contest 064

http://abc064.contest.atcoder.jp/

  • Rank: 394th
  • Performance: 1287
  • Rating: 1027 (+39) (Highest!)

全完だが早解き失敗。C が酷すぎた。

A: RGB Cards

解法

$(100r+10g+b) \bmod 4 = 0$ なら YES。

B: Traveling AtCoDeer Problem

解法

$max(a_1, a_2, \dots , a_N) - min(a_1, a_2, \dots , a_N)$ が答え。

所感

サンプルにつられて、ソートして先頭と末尾を見ていたが、よく考えたらソートする必要はなかった。

C: Colorful Leaderboard

以下、色を選べないレートの人を趣味、色を選べるレートの人をプロと呼ぶ。

解法

レートの色数を最小にするには、プロ全員が趣味の任意の色にすればよい。逆に最大にするには、プロ全員が異なる色、かつ趣味の色と被らない色にすればよい。

以上より、最小値$=max(1,$趣味の人数$)$、最大値$=$プロの人数。

所感

最初、プロは趣味の色のどれかから選べると解釈していて、WA。

その後、趣味が 0 人のコーナーケースに気づかず、なんだかんだで 2WA。

にゃーん (色々な思いが込められた鳴き声)。

D: Insertion

解法

先頭に (、末尾に ) を必要十分な数だけ加えればよい (辞書順最小なので)。

サンプルの )))()) が分かりやすいので、これを例に考える。まず、真ん中あたりにある () については、正しい括弧列なので考える必要はない。これを除いてみると )))) が得られるので、先頭に ( を 4 つ加えればよいことが分かる。

うまく実装するには、カウンタを 0 で初期化し、先頭から見ていって ) なら +1、( なら -1 をすると、カウンタが取った最大値が追加すべき ( の数になる。

所感

yukicoder で似たような ★1 問題があった気がする。

yukicoder contest 166

http://yukicoder.me/contests/168

  • Rank: 24th

テスターを担当したBを含めて3完。

No.525 二度寝の季節

解法

入力を $h$ : $ m $ で受け取って、$ m $ に $5$ を足す。

  • $m \ge 60$ なら $h$ をインクリメント
  • $h = 24$ なら $h$ を $0$ にする

以上を処理し $h$ : $ m $ を出力。

別解1

分に直して計算した後、元に戻す。

別解2

時間を扱う標準ライブラリを使う。

No.526 フィボナッチ数列の第N項をMで割った余りを求める

テスターを担当した。

解法

mod を取りながら計算する。典型。

No.527 ナップサック容量問題

解法

まず $sum(v_1, v_2, \dots , v_i) = V$ のときは、$min = sum(w_1, w_2, \dots , w_i)$、$max = inf$ で終了。

容量 $c$ のナップサックについて 0-1 ナップサック問題を解く関数 $knapsack(c)$ を考える。この関数は典型的な DP で実装できる。

$knapsack(c)$ は単調増加関数なので、$knapsack(c) = V$ となる $c$ を二分探索で求められる。後は $x = c$ と置き $x$ をインクリメントしていくと、$knapsack(x) > V$ となる最小の $x$ が得られる。ここで $max = x - 1$。$min$ も同様に求められる。

所感

明らかに適当解法。ABC063 の D 問題があったので二分探索がすぐに思いついたが、二分探索にしてももうちょっと賢く使えないものか。想定解は、価値に対して重みを最小化する DP (あとで考えて追記します)。

余談

いつも使っているマクロの欠陥に気づけた。

AtCoder Beginner Contest 063

http://abc063.contest.atcoder.jp/

  • Rank: 118th
  • Performance: 1255
  • Rating: 988 (+42) (Highest)

3完。そろそろ水色が見えてきた気がする。多分気がするだけ。

A: Restricted

解法

#include <stdio.h>

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    if (a + b >= 10) puts("error");
    else printf("%d\n", a + b);
    return 0;
}

所感

58 秒。C と Haskell のどちらで書くか悩んで 5 秒、VSCode のスニペットがクソでさらに 5 秒ロス。LL 系の言語を早解き用に覚えようか悩んでいる。

B: Varied

解法

重複を取り除き、長さが変われば no

import Data.List (nub)
 
main :: IO ()
main = putStr . solve =<< getLine
 
solve :: String -> String
solve s = if length (nub s) == length s then "yes" else "no"

所感

1 分 27 秒。これくらいなら 1 分は切りたい。

C: Bugged

解法

合計が 10 の倍数のときは、10 の倍数でない配点のうち最小のものを引けばよい。配点がすべて 10 の倍数のときがコーナーで、0 になる。

所感

配点をソートし忘れたことが原因で 1WA。なお DP 解は思いつきはしたが実装が面倒くさかったのでスルー。

D: Widespread

以下、魔物 $i$ を中心に爆発を起こすことを、魔物 $i$ を爆発させるという。

方針

体力が一番大きい魔物を爆発させるのが常に最適であることは容易に分かる。ただし、愚直にシミュレートすると明らかに間に合わないので、少し工夫する。

TLE 解法

最大の体力を持つ魔物が変わるまでは同じ魔物を爆発させればよいので、そこだけ $O(1)$ にする。これだけだとサンプル 3 ($A = 2, B = 1, h_{max} = 10^{9}$) が TLE する。

WA 解法

爆発が $h_{max}/A$ 回以上必要なことは自明なので、その回数だけ先にシミュレートしておく:

  • $0 \leq i \leq N$ について、 $h_i-B\cdot(h_{max}/A) > 0$ であるような魔物 $i$ を爆発させる。
  • 爆発が $h_{max}/A$ 回起こるまで回す。

大して変わらなさそうだが、これで一応サンプル 3 が通る。ただし、TLE は取れないし WA が生えた (嘘解法?)。

AC 解法

ここから先は思いつかず。

$T$ 回以内の爆発で魔物を全滅させることが可能かどうかを返す関数 $f(T)$ を考えると、$f(t) = True$ であるような任意の $t$ に対して、 $f(u) = True\ (u > t)$ が常に成り立つ。というわけで、後は $f(T) = True$ となるような最小の $T$ を二分探索。

所感

明らかに研鑽が足りなかったが、これで今後の類似問題は多分解けるようになった。

yukicoder contest 164

http://yukicoder.me/contests/166

  • Rank: 26th

3完できた。★2が全部解けたのは嬉しい。

No.516 赤と青の風船

解法

RED をカウントし、2 以上なら RED。2 未満なら BLUE。

別解

ソートし、2 番目を出力。

所感

ソートするやつ綺麗だし、天才。プロはすごい。

No.517 壊れたアクセサリー

解法

ある文字を Key として、それに繋がる文字を Dictionary に投げておく。この時点で Dictionary の要素数が、アクセサリー文字列の長さ - 1 より小さい場合は復元不可能なので -1 を出力。あとは、Dictionary の適当なペアから Key -> Value を辿っていき文字列を復元していく。Key が見つからなくなった時点での文字列を一旦リストに投げ、また空文字列を用意し、適当な場所から Dictionary を辿って文字列に文字を足していく。最後に文字列のリストの後ろから繋げていけば完成。

所感

これはひどい (説明が)。

C# で書いたのだが、あまり綺麗に実装できなかった。ただ一発 AC したときは嬉しかった。

No.518 ローマ数字の和

解法

1 から 3999 までのローマ数字を埋め込み。 Int へデコードしてから和を求め、ローマ数字へエンコード

所感

後日きちんと解きます。

AtCoder Grand Contest 015

http://agc015.contest.atcoder.jp/

  • Rank: 664th
  • Performance: 1094
  • Rating: 946 (+21) (Highest)

2完。時間がかかりすぎた。

A: A+…+B Problem

解法

  • $A > B$ を満たす数列は存在しないので、$0$。
  • $N = 1$ かつ $A \neq B$ を満たす数列も存在しないので、$0$。
  • $A = B$ の場合は $A (= B)$ を $N$ 個持っているパターンしかないので $1$。

以上をフィルタした後、$(b - a)(n - 2) + 1$ が答え。

所感

サンプルが通ることをきちんと確認しなかったことが原因で気付かなかった実装ミスをこじらせ、2WA

B: Evilator

考察

制約の

  • $S_1$ は U である
  • $S_{|S|}$ は D である

より、任意の2階間を移動することができる。

ある階が U なら、それより上の階へ移動は明らかに1回で可能だが、下の階へ移動するときは、それより上の階に D である階が存在することが保証されているため、その階へ移動し、そこから目的の階へ移動することで高々2回で移動ができる。D の場合も同様。

解法

$S$ を前から見ていき、$S_i$ が

  • U なら $|S| - 1 - i$ + $2i$
  • D なら $2(|S| - 1 - i) + i$

をカウント。最後に総和を出力。

所感

#define int long long を書けば AC。