読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

AtCoder Beginner Contest #041 (Nim-langの練習帳)

bitDP AtCoder

いつも通り、Nim-langでABCに出た
Nim-lang: index - Nim Programming Language
Nim-lang Tutorial: Nim Tutorial (Part I)
Nim Standard Library: Nim Standard Library

abc041.contest.atcoder.jp

A - 添字

echo(s[i-1])

B - 直方体

A*Bしたあとに一度modを取らないと1<<63を超えるので注意(pythonで解こう!)
A*B mod 10^9+7 * C mod 10^9+7

C - 背の順

(高さ, 出席番号)でソートして高さの降順に出席番号を出す。
出力するものが多すぎて、codeforcesだとprintfを使わないとTLEする問題。

D - 徒競走

bitDP
dp[state] := (stateの1が立っているところを既にゴールしたうさぎとしたときの、うさぎの着順の組合せ)
とすると、うさぎvがまだゴールしていない、かつ、vより先にゴールするべきうさぎが全てゴールしている場合、dp[state | v] += dp[state]とできる。

制約から解法を思いつくタイプの問題。