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

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

操作列を数え上げる問題

Codeforces Round #681 (Div. 1) B. Identify the Operations (R1800)

どんな風に操作しようとも、毎回「左右のうちの何個選べるか」が変わらない!! 問題へのリンク 問題概要 の順列 と、空の配列 が与えられる。これらに対して以下の操作を 回行うことで、配列 が に一致した状態にしたい。 そのような操作方法が何通りあるか…

AOJ ???? Counting Angels (KUPC 2020 G)

こういう条件を言い換えながら数え上げる問題好き! 問題へのリンク 問題概要 タプリスちゃんは現在、長さ 1 の数列 を持っている。 タプリスちゃんは に対して、以下のいずれかの操作を選んで行うことを 回繰り返すことにした。 の末尾に または を追加する…

CODE FESTIVAL 2016 Final F - Road of the King (橙色, 1000 点)

面白かった!!!DEGwer さんの pdf より。 問題へのリンク 問題概要 頂点のグラフが与えられる。初期状態では 1 本も辺が張られていない。 このグラフに、頂点 1 を始点とする長さ のウォークをとり、ウォークに沿って有向辺を張っていく。有向辺の張られた…

AOJ 3196 Increasing Sequence (AUPC 2020 day1-D)

in-place な DP にもっと慣れていきたい 問題へのリンク 問題概要 個の数列がある。 個目の数列は 個の要素からなる。 個目の数列の 番目の要素は と表す。 個目の数列から 1 個以下の要素を選び、選んだ要素を元の数列の順番通りに並べた数列を とする。 数…

AOJ 2378 SolveMe (JAG 冬合宿 2010 day3-J) (1200 点)

伝説の良難問。 現在でこそ AC 数 30 人で解説記事も豊富にあるが、当時は AC 数 3 人という状況で解説も無い中で、必死に 1 週間かけて通した想い出の問題。 問題へのリンク 問題概要 正の整数 と 以上の整数 が与えられる。 {} から {} への写像 の組であ…

AtCoder ARC 059 F - バイナリハック / Unhappy Hacking (橙色, 800 点)

面白かった 問題へのリンク 問題概要 長さ の '0' と '1' と 'B' からなる文字列 として、以下の条件を満たすものが何通りあるか、1000000007 で割ったあまりを求めよ。 空文字列に対し、 を左から順に見て、以下の操作を順に行ってえられる文字列が に一致…

第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion (青色, 500 点)

区間反転操作問題シリーズ!!! それにしてもいろんな見方ができる問題な気がする。 問題へのリンク 問題概要 長さ の 'B', 'W' からなる文字列 があたえられる。今この文字列に 回の操作を行う。 まだ選んでいない 2 マス を選んで区間 [ ] の 'B' と 'W' …

diverta 2019_2 E - Balanced Piles (橙色, 800 点)

最初は絶望感がヤバイタイプの問題。とても解ける問題には見えない。でも落ち着くと解ける。 こういう問題を作れるのはすごい。 問題へのリンク 問題概要 個のマスに積み木を重ねていく。最初はどのマスも 0 段である。以下の操作を繰り返して、最終的にすべ…

AOJ 2530 Reverse Game

ライツアウト系のいい感じの問題。そして bitset を用いたビットベクター高速化による高速化が求められる。 問題へのリンク 問題概要 × のグリッドがあって、各マスは白か黒に塗られている。今、何個かのマスを選んで 選んだマスから四方八方に伸ばして届く…