整数を「10倍してaを足す」で捉える
面白かった！ 問題へのリンク 問題概要 整数 が与えられる。 整数 の十進法表記を 個 concat してできる整数を 998244353 で割った余りを求めよ。 制約 考えたこと まず、整数 が 桁だとしよう！ このとき、求めたい値は次のように表現できる。 よって、 と…
「十進法 → 二進法」変換。これも鉄則本公式解説とは異なる方法でやってみよう。 問題へのリンク editorial 問題概要 二進法で表記された整数 が与えられる。 整数 の十進法表記を求めよ。 解法 たとえば、二進法で表された整数 1101 は、十進法では、次のよ…
人目見て「頑張れば解けそう」と思えたので、コンテスト中になんとか頑張って通した！ 問題へのリンク 問題概要 "1+2*34" のような文字列が与えられる。 この文字列の連続する部分文字列をすべて考えて 数式として成立しているなら、その数式を計算した値 数…
整理するのが難しい！ 問題へのリンク 問題概要 3 個の 1 桁の整数 が与えられる。 このうちの 2 個を選んで並べて 2 桁の整数を作る。さらに、その残りの 1 個の整数をそれに足す。 こうしてできる整数の最大値を求めよ。 解法 たとえば、3 個の整数が のと…
久しぶりの、再帰関数を書きたくなるタイプの全探索！ 問題へのリンク 問題概要 各桁の数値が狭義単調減少になっている数を 321-like 数と呼ぶ。 番目の 321-like 数を求めよ。 制約 321-like 数の個数 解法 (1)：異常 10 重 for 文 この解法は本当に根性で…
これほどシンプルな問題がグラフ最短路問題になるのは感動的ですね！ 問題へのリンク 問題概要 の正の倍数をすべて考えたときの、各桁の和として考えられる最小値を求めてください。 制約 うまく数字を並べるゲームと捉える の倍数をひたすら試す方法をまず…
本選参加のボーダーとなった問題らしい！それにしても JOI は実装が重たい...！！！ 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 初期状態では下図のようなテンキーの「0」のところにカーソルがある。 上下左右への移動 ボタンを押す (315 …
よくある桁DPとはまた違うけれど、あまりを状態にもつ DP を試せる問題ですね！ 問題へのリンク 問題概要 "013?42???2??" のような、'?' と数値で構成された、長さ の文字列が与えられる。 この '?' を埋めて数値を作る方法のうち、13 で割ったあまりが 5 に…
この手の DFS、一時期全然見なかったけど、最近復活してきた！ 問題へのリンク 問題概要 1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。 番目に小さいルンルン数を求めよ。 制約 考えたこと さて、「 番目に小さ…
12 が 4 の倍数で、112 が 8 の倍数だから、1112 が 16 の倍数なんじゃないの...と迷走したりしていた。 問題へのリンク 問題概要 以下の条件を満たす整数 を 1 つ求めよ (というクエリに 回答えよ) 桁の整数である どの位の値も 0 ではない 各桁の話を とし…
RUPC 2018 の思い出。桁 DP。 問題へのリンク 問題概要 ごちうさ数とは、10 進法表記において「5?13」を含む正の整数のことである。? は 0〜9 のいずれでもよい。 以下の正の整数のうち、ごちうさ数が何個あるかを求めよ。 制約 解法 桁 DP。 一目、51?3 の…
AOJ-ICPC で無作為に問題を選んで実装する練習をした。あと、桁 DP でやってしまったけど、もっとずっとはるかに楽な方法があった。。。 問題へのリンク 問題概要 1 から順に FizzBuzz をやって得られる文字列を FizzBuzz 文字列と呼ぶ。 12Fizz4BuzzFizz78F…
きたまさ法によく似たタイプの DP ダブリング高速化！ ただかなり難しい問題だと思うので、004 まで順調に解いていた方が、この問題で挫折しないように注意！！！ 無理に解こうとせずに飛ばすのも一案だと思います...... 問題へのリンク editorial 問題概要 …
