Chokudai SpeedRun 001 を一通り解いたので、解き方やコードを載せます。
このコンテストは、私がAtCoderで過去に行われたコンテストを色々漁っているうちに見つけました。開かれた経緯が不明（有識者求む）の謎のコンテストですが、問題セットが典型問題で構成されています。そのため、私のような競プロ初心者には、典型解法の確認やライブラリの整理に使えました。問題を解く際の注意点ですが、他のコンテストと違い、共通の制約がコンテストのトップページに書かれていて、問題文に書かれていないので、合わせて読まないと罠にはまる可能性があります。最後ですが、もっといい解法があれば連絡いただけると助かります。
A 最大値
for文を使い、入力を受け取るたびに、最大値を更新するだけ。for文を使うのが面倒でなら、$n$の上界が100しかないので、入力を全て受け取って、ソートして端を取り出すのもあると思います。私は、Goには int の max関数はないので以下を定義し、max(a...) で呼び出しました。
func max(arg ...int) int {
max := arg[0]
for _, x := range arg {
if max < x {
max = x
}
}
return max
}
B 和
Aと同様にfor文を回すだけです。オーバーフローの心配もありません。
C カンマ区切り
Goでは、以下の関数を使って文字列スライス($s$)を受け取って、カンマ区切りの文字列を求めることができます。
この関数を使うため、入力を数値ではなく文字列として受け取るのがポイントと思います。
strings.Join(s, ",")
D ソート
ソート自体はpackage sortのsort.Intsでお手軽に昇順ソートができます。
面倒なのは、それをスペース区切りで表示しないといけないところで、もう既に数値として受け取っているため、C問題のような方法は使えないです。素直にfor文を回す必要があります。順位表の上から何人かのC++のコードを眺めたところスペース区切りを出力する関数を定義して呼び出す人はいらっしゃらず、for文で丁寧に出力していました。以下のように、最初にスペースを出力するかの条件文を書くのがよさそうです。
for i := 0; i < n; i++ {
if i > 0 {
fmt.Fprintf(writer, " ")
}
fmt.Fprintf(writer, "%v", a[i])
}
fmt.Fprintf(writer, "\n")
E 1は何番目？
他の問題と同様に、for文を回すだけです。1が複数現れるパターンはトップページの共通制約($i\ne j \Rightarrow a_i\ne a_j$)により存在しないため、「最初に見つかった位置+1」 を返せばいいです。
F 見える数
ここから、制約を意識する必要があり、かつ問題文が難解であるため、急に難化した印象を受けます。
問題文が難解ですが、要するに数列のある位置にある数値が、それより左にある全ての数値より大きければ１カウントします。合計何カウントですか、という問題です。最初の入力例 3 1 5 4 2 なら 3(左に数がない) と 5(左にある3,1より大きい) で答えは2になります。
各iに対してjを見ていくと、$O(n^2)$になり、TLE(Time Limit Exceeded)します。そのため、計算量を落とすための前処理として、左から各位置での累積max $c$を計算します。$c$を計算後、各$a_i$ごとに$c_{i-1}$を比較して、$a_i$がほうが大きいときをカウントすることで $O(n)$で答えを求めることができます。
c := make([]int, n)
copy(c, a)
for i := 1; i < n; i++ {
c[i] = max(c[i], c[i-1])
}
ans := 0
for i := 0; i < n; i++ {
if i == 0 {
ans++
continue
}
if c[i-1] < a[i] {
ans++
}
}
G あまり
連結した整数の桁数は $n = 20$ で 30桁程度あり, int型で扱える整数は高々19桁であるため簡単にオーバーフローします。
そのため、以下の手順で答えを求めます。
- 入力を文字列で受け取り、連結した整数を文字列で表す
19 11 10 7 8 9 -> "191110789" - それらを桁ごとに分解し、整数型スライスで管理
"19110789" -> []int{1,9,1,1,0,7,8,9} - 桁ごとに、各桁の数字 * powMod(10, 何桁目か)を求め合計する。
手順が煩雑ですが、要は巨大な数の余りは直接求めることはできないので、余りの加算乗算は自由に行えることを利用して、桁ごとに分解して($321$ なら $3*10^{2}+2*10^{1}+1*10^{0}$)、各桁の余りを求め、加算して余りを求めます。powMod は冪剰余を求める関数で、単純な累乗では当初の問題と同様にオーバーフローしてしまうため、使用しています。
func powMod(a, x, d int) int {
var r int = 1
for x > 0 {
if x&1 == 1 {
r = r * a % d
}
a = a * a % d
x >>= 1
}
return r
}
H LIS
最長増加部分列の文字数を求める問題であり、蟻本にもある有名な典型問題です。
ライブラリにしているものをそのまま使用しました。
以下の実装は、典型90 を借用し、Goで書き換えたコードですが、INF値を使わなくていい点や、追加される一文字ごとのLISの文字数が求まり、応用しやすい点で気に入ってます。
func lis(a []int) (lis []int) {
lis = make([]int, len(a))
b := make([]int, 0)
for i := 0; i < len(a); i++ {
cnt := sort.Search(len(b), func(j int) bool { return a[i] < b[j] })
if cnt == len(b) {
b = append(b, a[i])
} else {
b[cnt] = a[i]
}
lis[i] = cnt + 1
}
return
}
I 和がNの区間
区間の和がN以下を真とした、しゃくとり法が使えます。
実装は以下を参考にし、queue を用いています。
https://qiita.com/keroru/items/6e0a22e8c9bf2a24dc68
q := queue{}
ans := 0
sum := 0
for i := 0; i < n; i++ {
q.push(a[i])
sum += a[i]
for !q.empty() && sum > n {
sum -= q.pop()
}
if sum == n {
ans++
}
}
fmt.Fprintf(writer, "%v\n", ans)
type queue []int
func (q *queue) push(n int) {
*q = append(*q, n)
}
func (q *queue) pop() int {
v := (*q)[0]
(*q) = (*q)[1:]
return v
}
func (q *queue) front() int {
return (*q)[0]
}
func (q *queue) empty() bool {
return len(*q) == 0
}
J 転倒数
バブルソートでソートするのに必要なスワップ数と転倒数は同値です。
その転倒数の求め方ですが、以下が詳しいです。
https://scrapbox.io/pocala-kyopro/%E8%BB%A2%E5%80%92%E6%95%B0
私はBITの実装を持っていなかったのでセグ木を区間の加算を求めるものにして代用しました。
余談ですが、バブルソート自体は最悪$O(n^2)$に対して、スワップ数は$O(nlog(n))$で求まるのは面白いですね。
type RMQ struct {
n int
x []int
unit int
op func(x ...int) int
}
func add(arg ...int) (sum int) {
for i := range arg {
sum += arg[i]
}
return
}
func (rmq *RMQ) Create(seq []int) {
rmq.n = len(seq)
rmq.x = make([]int, len(seq)*2)
rmq.unit = 0
rmq.op = add
for i := range rmq.x {
rmq.x[i] = rmq.unit
}
for i, x := range seq {
rmq.x[i+len(seq)] = x
}
for i := len(seq) - 1; i > 0; i-- {
rmq.x[i] = rmq.op(rmq.x[i<<1], rmq.x[i<<1|1])
}
}
// i 番目の要素をxに更新。O(log(n))
func (rmq *RMQ) Update(i, x int) {
i += rmq.n
rmq.x[i] = x
for i > 1 {
i >>= 1
rmq.x[i] = rmq.op(rmq.x[i<<1], rmq.x[i<<1|1])
}
}
// [l,r) での最小の要素を取得。O(log(n))
func (rmq *RMQ) Query(l, r int) int {
l += rmq.n
r += rmq.n
vl := rmq.unit
vr := rmq.unit
for l < r {
if l&1 > 0 {
vl = rmq.op(vl, rmq.x[l])
l += 1
}
if r&1 > 0 {
r -= 1
vr = rmq.op(rmq.x[r], vr)
}
l >>= 1
r >>= 1
}
return rmq.op(vl, vr)
}
tree := RMQ{}
tree.Create(make([]int, n))
ans := 0
for i := 0; i < n; i++ {
ans += tree.Query(a[i]-1, n)
tree.Update(a[i]-1, 1)
}
fmt.Fprintf(writer, "%v\n", ans)
K 辞書順で何番目？
入力例1で説明します。31542が辞書順で何番目にくるかを最小の12345から初めて、左から順に数を固定する感じで数え上げていきます。
3xxxx になるまえに、1xxxx, 2xxxx のパターンがあるためそれらを数えると 2 * 4! 通り
31xxx は 1より小さい数字がないため、1通り
315xx になるまえに、312xx, 314xx のパターンがあるためそれらを数えると 2 * 2! 通り
3154x になるまえに、3152x のパターンがあるため、1 * 1 通り
よって答えは54通りになります。これをどうプログラミングするかですが、上記から、右に進むたびに固定した数字と固定する予定の数字は使えないことがわかります。固定する予定の数字は自分自身であるため考えないとして、この固定された数字の個数をどう求めるかですが、前問の転倒数の数え方がヒントになっています。つまり、右に進むたびにBITやセグ木で固定した数字を記録し、必要になるたびに固定した数字の個数を求めればいいです。これで $O(nlog(n))$ で問題を解くことができます。また、階乗計算ですが、何度も計算をやり直すと 右に進むたびに、$O(n)$かかってしまうため、初歩的なDPで一度計算した結果をメモするといいです。
factMod := make([]int, n)
factMod[0] = 0
factMod[1] = 1
for i := 2; i < n; i++ {
factMod[i] = i * factMod[i-1] % mod
}
ans := 0
for i := 0; i < n; i++ {
used := tree.Query(0, a[i]) + 1
tree.Update(a[i]-1, 1)
ans += (a[i] - used) * factMod[n-i-1]
ans %= mod
}
ans++ // 辞書順x番目は 1-indexed
fmt.Fprintf(writer, "%v\n", ans)
L N回スワップ
Jの問題と違い、任意の２つの要素のスワップの問題です。隣り合う２つの要素のスワップの問題ではないです。
ちなみに、そう勘違いして転倒数を求めて解いても何故かACできます。（最初そうやってACしました...)
以下のように、スワップ数($c$)を求めていきます。１回スワップするたびに、少なくとも１つの数が正しい位置に移動するため
$c$は高々$n$回ですみます。$c=n$のとき、そのままYESを返し、$n$以下なら偶数回スワップしてn回スワップにできるので、$n-c$ の偶奇でYES/NOを返せばいいです。
cnt := 0
for i := 0; i < n; i++ {
for a[i] != i+1 {
a[i], a[a[i]-1] = a[a[i]-1], a[i]
cnt++
}
}