AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

数え上げ

JOI難易度6 通勤経路

問題原文 atcoder.jp 問題要旨 縦 マス、横 マスのグリッドがある。 左上からスタートして、右か下への移動を繰り返して一番右下のマスを目指す。 曲がった直後に曲がることはできない という制約があるとき、一番右下のマスへたどりつく通り数はいくつある…

ABC154 E - Almost Everywhere Zero

問題原文 atcoder.jp 問題要旨 1以上 以下の整数であって、10進法で表した時に、0でない数字がちょうど 個あるようなものの個数を求めよ。 解法1:がんばる が高々3通りしか無い and 制約が小さい ので、頑張ればできます。 実装を見た方がいいと思うので…

ABC129 E - Sum Equals Xor

問題原文 atcoder.jp 問題要旨 非負整数からなる組 であって、以下の条件を満たすものの通り数を求めよ。 == 解法 ここから出てくる1111~とかは全部2進数です。 制約が桁dpをしろと言っている。。。 こういう場合には、「以下であることがまだ未確定にdpテ…

ABC150 E - Change a Little Bit

問題原文 atcoder.jp 問題要旨 長さ の、 0と1からなる相異なる数列 , を考える。また、長さ の数列 が与えられる。 に対して以下の操作を繰り返し行い、 にすることを考える。 のある項を0なら1に、1なら0に変える。この時コストとして、 (その時点で とな…

ABC143 D - Triangles

問題原文 atcoder.jp 問題要旨 互いに区別できる 本の棒がある。 番目の棒の長さは、 である。 これらの棒から3本の棒を使って、三角形を作る時、作れる三角形は何種類あるか。 ただし2つの三角形は、ある棒が一方にのみ使われているときに異なるとする。 …

ABC152 D - Handstand 2

問題原文 atcoder.jp 問題要旨 以下の正の整数の組 であって、 の末尾の桁が の先頭の桁に等しく、 の先頭の桁が の末尾に等しいようなものの個数を求めよ。 解法 とすると、 となる。(xは存在しないこともある) じゃあ を固定して、とりうる間のパターンを…

ABC135 D - Digits Parade

問題原文 atcoder.jp 問題要旨 数字と ? からなる文字列 が与えられる。 ? を好きな数字に置き換えてできる整数のうち、 13で割って5余る数はいくつあるか? ただし、先頭の0は許可される。 解法 すごいDPっぽいのでDPを考える。 まず「何番目までみたか?」…

第6回 ドワコン B - Fusing Slimes

問題原文 atcoder.jp 問題要旨 匹のスライムが一直線上に並んでいる。左から 番目のスライムは、座標 にいる。 ニワンゴ君は以下の操作を 回繰り返す。 番目(一番右)じゃないスライムの中からランダムに1匹選ぶ。 選ばれたスライムは、他のスライムにぶつ…

ABC132 D - Blue and Red Balls

問題原文 atcoder.jp 問題要旨 個の玉がある。そのうち 個が青い玉で、 個が青い玉である。 これら 個の玉を横一列に並べることを考える時、 を満たす全ての について、「青い玉が1個以上連続する区間がちょうど 個」であるような玉の並べ方の総数を求めよ…

ABC130 D - Enough Array

問題原文 atcoder.jp 問題要旨 長さ の正整数列 の連続する部分列であって、その総和が 以上となるものの個数を求めよ。 ただし、部分列が同じであっても取り出した位置が異なるなら別のものとして数えることとする。 解法 より、部分列の総和には単調性があ…

ABC147 D - Xor Sum 4

問題原文 atcoder.jp 問題要旨 を で割ったあまりを求めよ。 解法 XORは桁ごとに見るといいって言ってた。(というか制約の書き方ry) どちらかのbitが立っているときにのみ、XORでbitは立つので、「与式においてあるbitが何回数えられるか?」は「(あるbit…

ABC148 E - Double Factorial

問題原文 E - Double Factorial 問題要旨 の末尾に が何個続くか求めよ。 考えるべきこと が奇数の時には答えは0 はいくつかの奇数の積になるため、末尾が2で割り切れることはない。よって、末尾に0が続くことはない。 なので、 が偶数のパターンのみ考え…

三井住友信託銀行コン2019 E - Colorful Hats 2

問題原文 E - Colorful Hats 2 問題要旨 人の人が一列に並んでおり、それぞれ赤, 青, 緑 のいずれかの色の帽子を被っている。また各人は、「自分と同じ色の帽子を 被っている人が、前に 人いる」と主張している。これらの主張を全て満たすような帽子の色の組…

ABC145 F - Laminate

問題原文 F - Laminate 問題要旨 列のグリッドがあり、各列を下から [H_i] 行塗りつぶしたい。塗りつぶす時は、行方向に好きなだけ塗りつぶせる。 塗りつぶす前に、 個まで を好きな値に操作できる時、 実際に塗りつぶすのにかかる最小手数はいくつになるか…

ABC146 E - Rem of Sum is Num

問題原文 E - Rem of Sum is Num 問題要旨 長さ の整数列 と整数 が与えられる。の空でない連続する部分列であって、その和を で割ったあまりが部分列の要素数と等しくなるようなものの個数を求めよ。ただし、 つの部分列が列として同じでも、取り出す位置が…