2020-06-23

AtCoder Beginner Contest 170 E - Smart Infants

実装がかなり重かった上に定数倍がきつそうな感じがしたけど、よく見ると制限3.5secだったのでギリギリ間に合った。

実装

こういう問題はまず与えられた情報をとりあえず書いてみると思い浮かんだりする。とりあえずこの2つはすぐわかる。

幼児からレートを検索するための配列rating
幼児から所属幼稚園を検索するための配列belongs

val belongs = IntArray(N + 1)
val rating = IntArray(N + 1)

次に、各クエリにおいて

最高レートが更新される可能性のある園は最高2つまで
毎回最小値を求める必要がある

これは一点更新区間取得なので、それを処理するためのSegmentTreeを用意する。演算はmin()、単位元はInt.MAX_VALUE。 ratingInKinderの説明はあとで。

val st = IntSegTree(
    ratingInKinder.map { if (it.isEmpty()) Int.MAX_VALUE else it.lastKey() }.toIntArray(),
    { i1, i2 -> min(i1, i2) },
    Int.MAX_VALUE
)

ここからこのSegmentTreeを更新するために必要な情報はなにかを考える。最高レートが変化する場合や、園から一人もいなくなる場合など、色々な場合を考える。すると、以下のような情報があれば更新できると思いつく。

その園に存在するレーティングと、その人数
その園に存在するレーティングの降順のSet

これは、いわゆる順序付き多重集合というもので保持できる。C++にはこのためのmultisetがあるらしいが、kotlinには無いためTreeMap(keyが自動ソートされたMap)を使って、valueとして人数を保持する。

//初期化
val ratingInKinder = Array(2 * 100000 + 1) { TreeMap<Int, Int>() }
//Ai Biの情報から最初に更新する処理
ratingInKinder[B][A] = (ratingInKinder[B][A] ?: 0) + 1

持っていないといけない情報が多いが、これでクエリを処理することができる。実際に書いたコードでは、わかりやすさのために前の所属先と次の所属先の最高レートの情報を毎回更新している。
そのレートの幼児がいなくなる場合にremoveすることや、園に一人もいなくなる場合にセグ木をMAXで更新する処理を忘れないように注意。

val child = // Ci
val before = belongs[child]
val after = // Di

//前の所属先に関する処理
if (ratingInKinder[before][rating[child]]!! == 1) {
    ratingInKinder[before].remove(rating[child])
} else {
    ratingInKinder[before][rating[child]] = ratingInKinder[before][rating[child]]!! - 1
}
if (ratingInKinder[before].isEmpty()) {
    st.update(before, Int.MAX_VALUE)
} else {
    st.update(before, ratingInKinder[before].lastKey())
}

//次の所属先に関する処理
if (!ratingInKinder[after].containsKey(rating[child])) {
    ratingInKinder[after].put(rating[child], 1)
} else {
    ratingInKinder[after][rating[child]] = ratingInKinder[after][rating[child]]!! + 1
}
st.update(after, ratingInKinder[after].lastKey())

belongs[child] = after
ans[i] = st.getOp(1, ratingInKinder.size)

最後に答えを出力。java/kotlinはprintlnが遅いので一回で出力したほうがいい。

println(ans.joinToString(separator = "\n"))

ソースコード

2020-06-23

AtCoder Beginner Contest 170 D - Not Divisible

ABC 競技プログラミング atcoder

考え方

エラトステネスの篩が思い浮かべばほぼ勝ち。こういうときはAiから考えがちではあるが、Ajから考えるとよい。

(1 <= j <= N)について、Ajを除くAjの倍数はダメ
それぞれの数について、2個以上含まれている場合はダメ

これらを、与えられた数列の各要素においてチェックする。

実装

制約を見るとAi <= 10⁶なため、予めBooleanArray(A_max)を用意してチェックを行うことができる。また、同じ数を2回チェックしたことを検出するためにもう一つBooleanArrayを用意する。

val dp = BooleanArray(max + 1) { true } //1つ目の条件用配列
val searched = BooleanArray(max + 1) { false } //2つ目の条件用配列

各要素Aiのチェック時に、

その数を除いた倍数をA_maxを超えるまでdpをfalseに
一回目のチェックでsearchedをtrueに、2回目以降にチェックした場合はその数のdpをfalseに

という感じ。

 A.forEach { it ->
    val a = it
    if (searched[a]) {
        dp[a] = false
        return@forEach
    }
    searched[a] = true
    var i = a * 2
    while (i <= max) {
        dp[i] = false
        i += a
    }
}

最後にdpがtrueの要素を数える

A.filter { a ->
    dp[a]
}.size.let {
    println(it)
}

ソースコード

2020-06-08

java/kotlinでAtcoderの解答を縦に出力する場合の注意点

競技プログラミング

　java/kotlinのSystem.out.println()/println()は早くないので、改行してN個の答えを出力する場合は注意。まとめてprintlnしたほうがよい。

例 - ABC113_C - ID
　処理部分の計算量はO(NlogN)なので本来は間に合うはず

普通に出した場合
提出
TLEでダメ
まとめてprintln()した場合
joinToStringで改行を入れて一回のprintln()で提出
提出
OK

2020-06-07

2値配列における転倒数の求め方(計算量O(n))

競技プログラミング

　AGC034_Bのような問題で、2値配列の転倒数を求めることがあったが、大抵解説では流されていることが多いためメモ。
　転倒数とはなにかはここ)。ここでは後の説明のために「バブルソートを行うときにswapを行う回数」としておく。

　転倒数を求める場合、多値配列ではBITやセグメントツリーなどを用いて計算するが、2値配列の場合はそんなに大掛かりなものは必要なくて、更に左から順番に見ることで O(n) でOKになる。
　用意するのは以下の2つの配列。

count[i] ・・・0からi番目までに、2値で比較が後ろ側になる値の数
inv[i] ・・・・0からi番目までの転倒数

　最終的に求めたいのはinv[n]で、この2つの配列を左から更新していく。

　まず0番目には何も無いとして count[0] = 0、inv[0] = 0 として初期化する。
　次に、元の配列のi番目が2値のどちらかで場合分けしてこの2つの配列を更新する。　　

元配列のi番目が2値のうち比較で後ろ側の場合
　この場合は転倒数は増加しない(一番うしろにあるため)ので inv[i] = inv[i - 1] 。
　countは1増えるため count[i] = count[i - 1] + 1 。
元配列のi番目が前に来る方の場合　countは増加しないため count[i] = count[i - 1]。
　ここで、i-1番目までの配列がすでにソートされている状態を考えると、i番目にある数をcount[i]分前に持っていかなければならない。そのため、更新は inv[i] = inv[i - 1] + count[i - 1] となる。

　あとはこの2つの場合をつかった更新を前から順番にnまで行えば答えが出る。計算量は普通に O(n)。

2020-06-07

第三回アルゴリズム実技検定(PAST)

atcoder PAST 競技プログラミング

76点で中級。茶色にしてはできたと思った。途中で飯食ったの今思うと完全に余計。80点惜しかったなぁと思う。
コンテストページ
 ソースコード

A - ケース・センシティブ

String.lowerCase()で一発、やるだけ。

B - ダイナミック・スコアリング

ある人が解けた問題の一覧と、ある問題を解いた人の人数を別で持っておいてそれぞれ計算。やるだけ。

C - 等比数列

公式を使えばいいけど数がでかすぎるのでBigDecimalでやった。その上でそれでも収まらない場合はBigDecimalから出る例外をキャッチする。

D - 電光掲示板

0, 1, 4, 7に関しては一箇所だけ見れば決まる場所があるので先に決める。残りはゴリ押し。

ここらへんで昼飯を食い始めてしまいロス、絶対にやめようね。

E - スプリンクラー

隣接リストでグラフを持って、色を保存する配列を1つ持ってその都度処理。

F - 回文行列

i行目とN - 1 - i行目に同じ文字が入ってるかどうかをaからzまで全探索。文字数が奇数な場合は真ん中はなんでもよい。

G - グリッド金移動

多分一番苦労した。無限にあるので幅優先でやると死にそうだけど範囲を-1000から1000程度に絞れば間に合う。実際は+1000して諸々を配列で保存できるようにしてやった。

H - ハードル走

普通に1次元でdpすると飛んでる途中で歩き出してもいい場合とかがわかんなくなったから最短時間を保存する配列とdpで記録する配列を分けてやった。

I - 行列操作

実際に行列を作る必要はもちろんない。行と列に関して何番目かを配列で持っておいて、行と列に対する操作が独立なことと2回転置すると元に戻ることを使って、転置した回数が奇数か偶数かで場合分けしてクエリを処理。

J - 回転寿司

順番に処理をしていくと、先頭の子供ほど寿司の価値の最高が高くなるので誰が食べるかを2分探索で探すことができる。探せなかったら食べる子供がいないので-1。

K - コンテナの移動

それぞれのコンテナに対して、その下にあるコンテナ/その上にあるコンテナ/その机にある一番下のコンテナ/その机にある一番上のコンテナの4種類の配列を用意して各クエリを処理。完全にゴリ押しなので絶対にもっといい回答があると思うけどもう時間がなかったのでそのままAC。

ここで時間切れ。次がある場合は80点目標にしたい。(次回があるかは知らない本当は有料なので)