2年ぶりくらいにコンテストに参加しました。まあ気が向いたのと、たまたま時間が空いたので（ただ、しばらく今後も土日のこの時間予定が入ってて参加できなさそう）、参加してみました。
当日は4完でしたが、できたものを考えるともっと早く解けないといけないかなという感じですね…。
Fは無理そうでしたが、時間があればEは惜しいところまで行けたんじゃないかなと思います（解けるとは言っていない）
A問題
A - Health M Death
剰余を取ります。提出は Scala。
import java.util.Scanner
object Main extends App {
val sc = new Scanner(System.in)
val m = sc.nextInt
val h = sc.nextInt
println(if(h % m == 0) "Yes" else "No")
}
B問題
B - Many Oranges
答え見たら分析方法が違ったのであれですが…。
みかんの重さで表現しうるのはN個選んだ時に AN ～ BN になるので、その範囲にないときは問答無用で UNSATISFIABLE にしました（ AN～BN にしうる範囲では、起点を AN として、適当にミカンの重さを1gづつ調整できれば多分表現しうると考えたので）。
それ以外の場合は、まあ最小個数を math.floor(w.toDouble / a).toInt 、最大個数を math.ceil(w.toDouble / b).toInt として雑に出しました。
本当にこれでいいのかは不安だったので、かなり心配でした。想定解は N の全探索みたいですね。
提出は Scala。
import java.util.Scanner
object Main extends App {
val sc = new Scanner(System.in)
val a = sc.nextInt
val b = sc.nextInt
val w = sc.nextInt * 1000
def ok(a: Int, b: Int, w: Int): Boolean = {
val d = b - a
val t = w / a
if(a * t <= w && w <= (a + d) * t) true
else false
}
if(ok(a, b, w)) {
val f = math.floor(w.toDouble / a).toInt
val s = math.ceil(w.toDouble / b).toInt
println(s"${s} ${f}")
} else {
println("UNSATISFIABLE")
}
}
これ嘘解放じゃないか？大丈夫かな。
C問題
C - Comma
数え上げです。その数字以下の時は必ずコンマの数がこれだけあることが保証される、みたいな形になるので数え上げていきます。
解放では 1,000以上、1,000,000 以上みたいな形でうまく集計していましたが、僕は雑に 1,000 で割る、 1,000.000 で割る、を繰り返して一定の桁以上であれば全部買うと、そうでないならばそこまでの値をカウントする感じで書きました。
想定解がキレイなので、これは思いつきたかったな。提出はScala。
import java.util.Scanner
object Main extends App {
val sc = new Scanner(System.in)
var n = sc.nextLong
val t = Array.range(1, 6).map(i => Array(i, math.pow(10, 3 * i).toLong)).reverse
val l = math.pow(10, 3).toLong
var ans: Long = 0
for((e, ii) <- t.zipWithIndex) {
val i = e(0).toInt
val v = e(1)
val a: Long = n / v
if(a >= l) {
ans += (t(ii - 1)(1) - v) * i
} else if(a > 0) {
ans += (n - v + 1) * i
}
}
println(ans)
}
D問題
D - Shipping Center
あらかじめ入れるものをソートしておいて、使える箱のリストを毎回生成して、貪欲に入れる形でやっていました。
配列あれこれするのがめんどくさかったので提出は Python。配列の長さが短めなので、雑に作り直しても間に合うと思ってやったら案の定大丈夫でした。あんまりきれいなコードではない。
from copy import deepcopy
def run():
n, m, q = map(int, input().split())
wv = [[0 for i in range(2)] for i in range(n)]
for i in range(n):
w, v = map(int, input().split())
wv[i] = [w, v]
wv.sort(key=lambda t: (t[0], -t[1]))
x = [int(i) for i in input().split()]
for i in range(q):
r, l = map(int, input().split())
qx = x[:r - 1] + x[l:]
if(len(qx) == 0):
print(0)
else:
qx.sort()
qw = deepcopy(wv)
ans = 0
for j in qx:
tans, ti = -1, -1
for k in range(len(qw)):
if qw[k][0] > j:
break
if qw[k][1] > tans:
tans, ti = qw[k][1], k
if tans >= 0:
ans += tans
qw.pop(ti)
if len(qw) == 0:
break
print(ans)
if __name__ == "__main__":
run()
E問題
E - Lucky 7 Battle
ここからは復習。これは遷移をいい感じにDPに入れていって、最終結果から推定する問題でしたね。
後ろから見るのは思いついたんですが、時間切れだったのと、DPに保存すべき値がうまく思いつきませんでした。
なので解説見ながら書いた感じです。公式の解説読んで。提出は scala
import java.util.Scanner
object Main extends App {
val sc = new Scanner(System.in)
val n = sc.nextInt
val s = sc.next
val x = sc.next
var dp = Array.fill(n + 1, 7)(false)
dp(n)(0) = true
for(i <- (0 until n).reverse) {
val si = s(i) - '0'
val xi = x(i)
for(j <- 0 until 7) {
val f1 = (10 * j) % 7
val f2 = (10 * j + si) % 7
dp(i)(j) = xi match {
case 'A' => dp(i + 1)(f1) && dp(i + 1)(f2)
case 'T' => dp(i + 1)(f1) || dp(i + 1)(f2)
}
}
}
println(if(dp(0)(0)) "Takahashi" else "Aoki")
}
F問題
F - Coprime Present
BitDPらしいですね。素数の範囲がせいぜい72までに限定されるので、それをいい感じに数え上げられればよさそうです。
なお、数え上げパートが全く思いつかなかったのでユーザー解説のほうを参考に書いていきました。ありがとうございます。
Coprime Present ［パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195） F］ - はまやんはまやんはまやん
Scalaで書いたのですが、はまりポイントがあり
- どうやら Array の引数として渡せるのは Int 型が想定らしい、なぜか ( 1 << 20 ) を変数に入れてから Array に突っ込むと動く（これ想定されている挙動か？怪しい気がするが）
- DPを
int[n + 1][1 << 20] の形で定義するとメモリが足りなくなり、REとなる（MLEではないらしい）。今回はせいぜい、一つ前のものを見る程度だったので、変数を2つ使って表現し、更新する形にした。
あと isPrime をもっと楽に描く方法があったような気がするんですが（Javaのパッケージか何かにあったような）、探し出せなかったので雑に素数を出すコードを書いています。こういうのはライブラリみたいに使いまわせる形で用意しておいてもよいかも。
import java.util.Scanner
object Main extends App {
val sc = new Scanner(System.in)
def isPrime(a: Int): Boolean = {
for(i <- 2 to math.sqrt(a).toInt) {
if(a % i == 0) return false
}
true
}
val a, b = sc.nextLong
val d = (b - a + 1).toInt
val primes = (2 to 72).toArray.filter(isPrime)
val l = primes.length
val primesMap = (a to b).toArray.map(i => {
var r = 0
for(j <- 0 until l) {
if(i % primes(j) == 0) {
r |= (1 << j)
}
}
r
})
var dp = Array.ofDim[Int](1 << l)
dp(0) = 1
for(i <- a to b) {
var dp2 = Array.ofDim[Int](1 << l)
for(j <- 0 until (1 << l)) {
val t = (i - a).toInt
if((j & primesMap(t)) == 0) dp2(j | primesMap(t)) += dp(j)
dp2(j) += dp(j)
}
dp = dp2
}
println(dp.sum)
}
感想
めちゃくちゃ久々に参加しましたが、やっぱりやってて思ったのは
- 集中力落ちてない？（D問題の細かいロジックのバグを直すのに時間がかかった）
- 瞬発力も落ちてない？ とりあえず試す力が弱い（特に B 問題は、最初にこれ解ける？と思って怪しかったので飛ばしてC問題行って、考え直してたのでもったいなかった）
- タイピングが遅い（はい）
という感じなので、衰えを感じつつも、久々に出たのにレート変動なかったのは意外と元のコーディング能力は落ちてないのかなと思います。
逆に言えばまだまだ伸びる可能性は十分にあるので、今後も参加できるときは参加したい…（が、土日の21時は結構裏側に予定あったりして難しい）ですね。
（あとはどちらかといえば厳密解出すアルゴリズムのコンテストのほうが好きなのかもしれない、ISUCONはなんかすきだけど、マラソンはいまだに手を出そうという気になれていないという課題感を最近思いました）。
過去問ちょいちょい解いて水色には戻したいですね（希望的観測）。
