hogecoder

tsutaj 競技プログラミングの記録

数え上げ

Advent Calendar Contest 2020 18 日目: 塗るめた

Advent Calendar Contest 2020 の 18 日目として、ecasdqina さん作の問題の tester を担当しました。tester 解は、writer 解と少しアプローチが異なっていたので紹介したいと思います。また、コンテスタントの提出を見て発見した、形式的べき級数を一切使用…

AtCoder Grand Contest 030 F: Permutation and Minimum

問題概要 日本語があるので原文参照 → F - Permutation and Minimum 解説 と の順序は答えにあまり関係ないので、数列を 2 個のブロックに区切って考えていき、ブロックの中は (左の値) < (右の値) という関係が常に成り立つものとする。ブロックの状態とし…

AOJ 2436: Card

同じ方針でやっている人があまりいなさそうなので一応書きます。 問題概要 日本語なので原文を参照してください → Card | Aizu Online Judge 解説 整数を組み合わせて最終的に という数を作ったとします。与えられるそれぞれの整数について、その整数の 1 の…

AtCoder Regular Contest 043 B: 難易度

ARC043 B問題、データ構造で殴ってしまったけど、明らかに想定解法より楽な方法だと思うのでいちおう紹介。 問題概要 問題原文 → B: 難易度 - AtCoder Regular Contest 043 | AtCoder 長さ の数列が与えられる。この数列から、( 番目に取った数 ) ( 番目に取…

AOJ 1335: Equal Sum Sets

たとえ簡単な DP でも一発で通ると嬉しいよね。 問題概要 原文 → Equal Sum Sets | Aizu Online Judge 以下の相異なる自然数 個の合計が となる組み合わせの総数を求めよ。 解説 以下の各数字 について、 を使うときと使わないときを考えてみます。 を使うと…

AtCoder Regular Contest 009 C: 高橋君、24歳

問題概要 原文 → C: 高橋君、24歳 - AtCoder Regular Contest 009 | AtCoder 長さの順列を並び替えたとき、 (1-indexed)となる要素が個になる組み合わせは何通りか。1,777,777,777 (素数) で割った余りを出力せよ。 解説 まず、となる要素をどこにするかを決…

AOJ 0096: Sum of 4 Integers II

今日もAOJを埋めるだけの簡単なお仕事 (簡単とは言ってない) 問題概要 原文 → 4つの整数の和 | Aizu Online Judge 4000以下の正の整数が与えられる。0から1000までの範囲の整数の組でを満たす組み合わせの数を出力せよ。 解説 ナイーブ解法だと4重ループで…

AtCoder Beginner Contest 029 D: 1

問題概要 原文 → D: 1 - AtCoder Beginner Contest 029 | AtCoder である十進表記の自然数Nが与えられる。1からNまで書きくだす時、1という数字を何回書いたかを求めよ。 数学解法 解説 ナイーブな解法(部分点解法)はここで解説してもしょうがないので略。 …