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

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

逆問題

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

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

AOJ 2708 ABC Gene (JAG 夏合宿 2015 day2C)

こういうの好き。操作によって実現できるかどうかを問う問題は全体的に好き 問題へのリンク 問題概要 文字列 "ABC" に対して以下の操作を好きな回数だけ行うことで、所望の文字列 S に変形できるかどうかを判定せよ。 A, B, C のいずれかの文字を選び、文字…

AtCoder ABC 140 C - Maximal Value (300 点)

数学嫌いの方は問題文読んだ瞬間に一瞬敬遠心が生まれてしまうかもしれない...でも落ち着けば難しくはない 問題へのリンク 問題概要 長さ の数列 (具体的な値はわからない) に対して を満たす数列 が与えられます。 の総和として考えられる最大値を求めてく…

AtCoder AGC 006 B - Median Pyramid Easy (400 点)

これの Easy バージョン。すごく楽しくて好き!!!!! Easy:操作の結果が所望になる入力を求める逆問題 Hard:操作に入力を与えた結果を求める問題 という風になっていて、普通「操作の結果を求めるだけ」の問題の方が絶対簡単なことが多いのに、Easy と …

Codeforces 554 DIV2 E. Neko and Flashback (R2500)

面白かった 問題へのリンク 問題概要 (やや意訳) 長さ の数列 を復元したい。この数列に対し、ある並び替え順列 があって 隣り合う 2 要素の min をとってできる長さ の数列を で並び替えると となり 隣り合う 2 要素の max をとってできる長さ の数列を で…

AtCoder AGC 032 A - Limited Insertion (400 点)

好き!!!!!でも A 問題としてはかなり難しいね。 問題へのリンク 問題概要 数列 が空の状態から出発して以下の操作を 回行った結果が数列 と一致するようにできるかどうか判定せよ。 回目の操作においては 以上 以下の整数 を一つ選んで、数列の 番目に …

AOJ 2624 Graph Automata Player (AOJ-ICPC 550 点)

グラフに行列は付き物!!! 問題へのリンク 問題概要 頂点の有向グラフが与えられる。自己ループを含み得るが、多重辺は含まないことが保証される。 各頂点に 0 か 1 の値が割り振られている (が、その値がわからない)。以下の操作を 回行った後の各頂点の…