けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

整数を「10倍してaを足す」で捉える

JOI 二次予選 2020 D - テンキー (Tenkey)

本選参加のボーダーとなった問題らしい!それにしても JOI は実装が重たい...!!! 問題へのリンク 問題概要 初期状態では下図のようなテンキーの「0」のところにカーソルがある。 上下左右への移動 ボタンを押す (315 に 4 を押すと 3154 になる) を最小回…

AtCoder ABC 135 D - Digits Parade (400 点)

よくある桁DPとはまた違うけれど、桁DPの応用問題としてよくあるやつを試せる問題ですね! 問題へのリンク 問題概要 "013?42???2??" のような、'?' と数値で構成された、長さ の文字列が与えられる。 この '?' を埋めて数値を作る方法のうち、13 で割ったあ…

AtCoder ABC 161 D - Lunlun Number (400 点)

この手の DFS、一時期全然見なかったけど、最近復活してきた! 問題へのリンク 問題概要 1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。 番目に小さいルンルン数を求めよ。 制約 考えたこと さて、「 番目に小さ…

フォルシアゆるふわ競プロオンサイト #3 G - Digit Sum Multiple locked

12 が 4 の倍数で、112 が 8 の倍数だから、1112 が 16 の倍数なんじゃないの...と迷走したりしていた。 問題へのリンク 問題概要 以下の条件を満たす整数 を 1 つ求めよ (というクエリに 回答えよ) 桁の整数である どの位の値も 0 ではない 各桁の話を とし…

AOJ 2879 ごちうさ数

RUPC 2018 の思い出。桁 DP なん。 問題へのリンク 問題概要 ごちうさ数とは、10 進法表記において「5?13」を含む正の整数のことである。? は 0〜9 のいずれでもよい。 以下の正の整数のうち、ごちうさ数が何個あるかを求めよ。 制約 解法 桁 DP。 一目、51?…

AOJ 2441 FizzBuzz

AOJ-ICPC で無作為に問題を選んで実装する練習するなん。いや、つらいのんな^^; あと、桁 DP でやってしまったけど、もっとずっとはるかに楽な方法があったん。。。 問題へのリンク 問題概要 1 から順に FizzBuzz をやって得られる文字列を FizzBuzz 文字列…