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

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

回文

AtCoder AGC 001 D - Arrays and Palindrome (1000 点)

楽しかった。 回文系の問題。「〜な条件だと結局全部一緒になる」という問題の雰囲気がどことなく数オリっぽい。 必要条件を頑張って列挙したら実は十分な感じもまた、数オリっぽさと AGC っぽさの両方がある感じ。 問題へのリンク 問題概要 総和が 、長さが…

AtCoder AGC 021 D - Reversed LCS (900 点)

面白かった 問題へのリンク 問題概要 文字列 が与えられる。あらかじめ文字列の中の 文字を自由に変更することができる。 こうして得られた文字列と、それを反転した文字列の LCS (最長共通部分列) の長さとして考えられる最大値を求めよ。 制約 考えたこと …

Educational Codeforces 62 E - Palindrome-less Arrays

楽しかった 問題へのリンク 問題概要 未完成の数列 が与えられる。未完成部分には が書かれている。完成部分には 以上 以下の整数が書かれている。 のところを 以上 以下の整数を埋める方法であって、整数列が奇数長の回文を含まないものは何通りあるか? 制…

早稲田大学プログラミングコンテスト WUPC 2019 E - Artist

回文な問題リストに!!! 問題へのリンク 問題概要 × のグリッドが与えられ、各セルには 0 か 1 の値が書かれている。 今、縦方向と横方向に切れ目を入れて、4 つの長方形に分けて、それぞれの長方形を 180 度回転させる操作を行う。 このときに、各行各列…

AOJ 2934 往復文字列 (RUPC 2019 day3-E)

ロリハの練習!!! 問題へのリンク 問題概要 長さ の文字列 T が与えられる。以下の条件を満たす最長の長さの文字列 S (反転したものを S' とする) を求めよ: S + S'.substr(1) + S.substr(1) + S'.substr(1) + S.substr(1) + ... の最初の 文字が と一致す…

全国統一プログラミング王決定戦 エキシビジョン G - 回文スコア (400 点)

比較的普通の問題っぽい 問題へのリンク 問題概要 文字列 が与えられる。 に含まれる文字をそれぞれ一度ずつ使い、何個かの回文を作ることを考えます。文字は自由な順序で使用することができ、 に複数回現れる文字は合計でその回数だけ使用します。 長さ の…

AtCoder ARC 064 F - Rotated Palindromes (1000 点)

約数系包除。かなり教育的要素の多い問題だと思った!!!!! 操作によって何通りできるのかを問う問題の取り組み方 約数系包除の考え方 問題へのリンク 問題概要 以上 以下の整数からなる数列のうち、以下のようにしてつくられるものは何通りあるか、10000…

AOJ 2895 回文部分列 (AUPC 2018 day3 G)

すごく大好きな問題! 部分列を走査する考え方をちゃんとわかっていれば自然に解くことができる。 問題へのリンク 問題概要 文字列 が与えられる。 の部分文字列のうち回文となっているものが何通りあるか、1000000007 で割ったあまりで求めよ。 制約 は英小…