ABC195に参加しました - 名もなき未知

2年ぶりくらいにコンテストに参加しました。まあ気が向いたのと、たまたま時間が空いたので（ただ、しばらく今後も土日のこの時間予定が入ってて参加できなさそう）、参加してみました。

当日は4完でしたが、できたものを考えるともっと早く解けないといけないかなという感じですね…。

Fは無理そうでしたが、時間があればEは惜しいところまで行けたんじゃないかなと思います（解けるとは言っていない）

A問題

剰余を取ります。提出は 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はなんかすきだけど、マラソンはいまだに手を出そうという気になれていないという課題感を最近思いました）。

過去問ちょいちょい解いて水色には戻したいですね（希望的観測）。