ブログ名

競技プログラミングやお歌のお話をする高菜です。

AOJ/AtCoder-JOI 難易度 6

f:id:ngtkana:20200902004457p:plain

かなり難しくなってきました。

1 / 27 アナグラム

https://atcoder.jp/contests/joisc2007/submissions/16450644

2 / 27 おせんべい

https://atcoder.jp/contests/joi2008yo/submissions/16451459

グリッドの回転・鏡映 7 通り、なんども使っていますから、ライブラリ化しました。(gridtools)

3 / 27 ダーツ

https://atcoder.jp/contests/joi2008ho/submissions/16451554

4 / 27 ナイルドットコム

https://atcoder.jp/contests/joisc2008/submissions/16452228

けっこう大変でした。 真面目に遷移すると間に合わいませんから、遷移の順番を工夫してオーダーレベル高速化です。

結局使いませんでしたが、一瞬よぎった Sparse table もライブラリ化しました。私の好みの都合で、Argmin 専用のものが爆誕してしまいました。汎用バージョンもまた作りましょう。

5 / 27 折り紙

https://atcoder.jp/contests/joisc2008/submissions/16471418

苦戦しました。n = 5000 で 1 秒というのはかなり微妙な制約です。

まずは 1 度目のチャレンジです

普通に座標圧縮 → TLE & MLE (10000 × 10000 のマス目ができますから、それはそうでした……)

さて、2 度目のチャレンジです

ここで本質制約に気づきました。

貼り絵に用いる折り紙の辺の長さは 20 cm 以下である.

そこで天才的なひらめきをした私は、折り紙を全探索して、その中身 20 × 20 マスそれぞれを重複度を、これまた折り紙を全探索して累積和で計算します。→ メモリは大丈夫でしたが、TLE です。(実行時間は縮んでいないですからね。)

難しくありませんか!? 座標圧縮もそれなりに高度なテクですし、2 つ目の方法もかなり天才だと思ったのですが。

くじけず 3 度目のチャレンジです。

折り紙を全探索 & そのなかのマスを全列挙してあとで重複度を数えると良いです。

なんともあっけない答えでした。これ一問に平日まる一日を持っていかれてしまいました。むーん……

6 / 27 連鎖

https://atcoder.jp/contests/joi2009yo/submissions/16471711

どこの色を変えるかを全探索します。

その一つ一つは最悪 Θ( N ) の時間がかかるのですが、連鎖の範囲がほとんど重ならないので全体でも Θ( N ) しかかからないという、面白い問題でした。

7 / 27 ピザ

https://atcoder.jp/contests/joi2009ho/submissions/16471806

折り紙で苦戦させられたのもあり、あまりの簡単さに、え、これあっていますか? 誤読ですか!? と読み直してしまいました。

8 / 27 通勤経路

https://atcoder.jp/contests/joi2010yo/submissions/16471935

基本的には前二手を記憶する 5 状態 DP で、二乗時間を達成です。

9 / 27 つらら

https://atcoder.jp/contests/joi2010ho/submissions/16507315

どのつららがいつ落ちるのかを、時刻順に決めていきます。あるつららが落ちることで落ち始めるのは隣のつららだけなので、queue で管理してがんばります。けっこう難しいですね……

10 / 27 階段

https://atcoder.jp/contests/joisc2010/submissions/16507647

動的な累積和で DP を高速化するテク、いつも混乱してしまいます。

...というわけで、作ってしまいました。PrefixSum です。

let n = buf.usize();
let jump = buf.u64();
let mut a = vec![0; n + 1];
for i in 0..n {
    a[i + 1] = a[i] + buf.u64();
}
let n = a.len();
let mut dp = prefix_sum::PrefixSum::with_zero(Mint::zero());
dp.push(Mint::one());
let mut i = 0;
for j in 1..n {
    while a[i] + jump < a[j] {
        i += 1;
    }
    dp.push(dp.sum(i..));
}
let ans = dp.get(n - 1);
println!("{}", ans);

それはそうと、そろそろ modint も釣り直したいところですね。

11 / 27 横断幕

https://atcoder.jp/contests/joisc2011/submissions/16514104

行の組み合わせを全探索して、それぞれを Θ( W ) で解きましょう。 今までにどんなセルの組をいくつ見たのかを、8 種類の(実際には 1, 2, 3, 4, 5, 6 の 6 種類のみ) のbit 集合で管理です。すると、今見ているところと合わせて 7 になるようなものに関して足すをするとよいです。

ここで注意が 2 つです。まず、毎回 8 個全部イテレートするとおそらく無理でしょう。(もともと私は 9 状態 { 0, 1, 2 } × { 0, 1, 2 } で遷移も全探索で書いていたら TLE をしました。)

また、実は 400 は 4 乗するととてもおおきくて、u32 では収まりません。(ここで WA をいただくなどです。)しかし不思議です。実際には 4 分の 1 倍になりますから、1.6 × 10 ^ 10 です。u32 では 4 倍オーバーするだけなのですが、キラーケースが入っているのでしょう。

12 / 27 古本屋

https://atcoder.jp/contests/joi2011ho/submissions/16519364

ジャンルごとに、冊数を決めたら高い順に売ると良いですから、何冊売るといくらであるかを累積和で前計算です。 そのあと、ジャンルを順番に見て、そこまでのジャンルで何冊売ったらいくらであるかをナップザックで計算で、Θ ( K N ^ 2 ) です。

はじめ「一冊あたり」高くなるのではなく、合計額が T - 1 高くなるものと思っており、 これならばすべて 1 高くしておいてジャンルの数だけ安くなるのと同じですから、 ジャンルの集合を全探索してソートをするので、 Θ ( 2 ^ K N lg N ) となります。 こちらの方針にかなり引きづられてしまいました。

13 / 27 国際情報オリンピック

https://atcoder.jp/contests/joisc2011/submissions/16520461

やや添字ゲーの面倒な問題です。 自分に勝てるか負けるかなどで分岐が生じるのがやや厄介ですから、n = m のときには別で処理することにして n ≠ m を仮定しましょう。 また、簡単のため入力の得点 a[0], a[1], .. が降順にソートされているとみなしましょう。(unzip() で添字にサヨナラバイバイして人数だけ計算するのが便利です。)

強い順に、その人が確実に金メダルを取れるかチェックして、それができなくなる最初のものをを見つけると良いです。(take_while().count() がよいでしょう。)判定は、

  • ...j には負けるかもしれません
  • j... には確実に勝てるか引き分けかします。

を満たすような j を探して、(j - 1) * 12 < k (この -1 は自分自身です)であることでできます。この ji に関して単調ですから、尺取り法で計算ができます。

およそこのような感じです。

let mut j = 0;
(0..k)
    .take_while(|&i| {
        j = (j..k).find(|&j| a[j] + 100 * (n - m) <= a[i]).unwrap_or(k);
        (j - 1) * 12 < k
    })
    .count()

これを、「金メダルを取れるかもしれない」に関しても同じようなことをするとよいです。

14 / 27 イルミネーション

https://atcoder.jp/contests/joi2012yo/submissions/16524558

ひたすら実装六角グリッドです。 外側から到達可能なところにすべて印をつけておいて、falsetrue が隣接している箇所を数えます。 予め枠で囲っておくととても実装がしやすいです。

15 / 27 JOIポスター

https://atcoder.jp/contests/joisc2013-day1/submissions/16525659

はじめ N ≦ 1000 かと思ってうんうんいっていたのですが、なるほど N ≦ 50 ならば全探索やるだけです!

しかし解説によると Θ ( N ^ 3 ) でも解けるようですね。これだから解説というものはまほしきものなのです。(しかし思いつかずです。)

16 / 27 部活のスケジュール

https://atcoder.jp/contests/joi2014yo/submissions/16526186

鍵当番の条件は、どの隣接する 2 日についても参加メンバーに交叉があるということと同じです。 前日の参加メンバーの集合を保持する DP です。

17 / 27 JOI紋章

https://atcoder.jp/contests/joi2014ho/submissions/16527363

変える場所を全探索です。また、そこをどの文字にすると周り 4 箇所で何点入れられるかを計算するとよいです。 これにより、その点数計算でメインパートが正方形 4 つ × 7 箇所程度の二重配列アクセスとなります。

もともとこれよりかなり定数倍の重い方法を使っていて(、もとの文字 + 文字 3 通り= 4 通り) + 正方形 4 つを見ていて、イテレータchain などをもりもり使っていたら、TLE をしてしまいました。

定数倍を気にしながらきれいに書くのがちょっとめんどくさくなって、気合いをしてしまいました。

if (a[i - 1][j - 1], a[i - 1][j], a[i][j - 1]) == (b[0][0], b[0][1], b[1][0]) {
    score[b[1][1]] += 1;
}
if (a[i - 1][j], a[i - 1][j + 1], a[i][j + 1]) == (b[0][0], b[0][1], b[1][1]) {
    score[b[1][0]] += 1;
}
if (a[i][j - 1], a[i + 1][j - 1], a[i + 1][j]) == (b[0][0], b[1][0], b[1][1]) {
    score[b[0][1]] += 1;
}
if (a[i][j + 1], a[i + 1][j], a[i + 1][j + 1]) == (b[0][1], b[1][0], b[1][1]) {
    score[b[0][0]] += 1;
}

18 / 27 IOI 饅頭

https://atcoder.jp/contests/joi2014ho/submissions/16544732

ナップサックが苦手すぎて泣いています。