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

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

回文

AtCoder ABC 070 A - Palindromic Number (灰色, 100 点)

を文字列として受け取るのが楽だと思う! 問題へのリンク 問題概要 3 桁の整数 が与えられる。 が回文数であるかどうかを判定せよ。 解法 を整数ではなく、文字列として受け取ろう。そうすれば 「先頭の文字と末尾の文字が等しいかどうか」 を判定すれば OK…

AtCoder ABC 320 B - Longest Palindrome (灰色, 200 点)

最長回文を求める問題! 問題へのリンク 問題概要 文字列 が与えられる。 の連続する部分文字列のうち、回文であるものについて、最長の長さを求めよ。 考えたこと この問題は次の 2 ステップに分かれている。 の連続する部分文字列を全種類抜き取る それら…

ウクーニャたんお誕生日コンテスト D - ukuku

ネタコンテストなのかと思いきや、問題面白くて、この D 問題は勉強になった。答え決め打ちの二分探索! 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 この文字列について 回のクエリに答えたい。 各クエリでは整数値 が与えられ…

AtCoder ABC 286 C - Rotate and Palindrome (茶色, 300 点)

慣れれば解ける問題だけど、最初は「固定する」という考え方が難しいかもしれない。 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返すことで回文にしたい。 先頭の文字を末尾に移動する (コスト ) 文字を 1 つ…

AtCoder ABC 206 D - KAIBUNsyo (緑色, 400 点)

今や Union-Find やるだけだと茶色 diff (下手したら灰色 diff) だけど、ちゃんと考察要素を入れるとやっぱり緑色 diff になるのね。 問題へのリンク 問題概要 正の整数からなる整数列 が与えられる。以下の操作を好きなだけ行うことによって、 個の値がすべ…

Codeforces Round #557 (Div. 1) D. Palindrome XOR (R2400)

面白かった。重み付き Union-Find を使った。 問題へのリンク 問題概要 0 と 1 と ? のみからなる長さ の文字列 が与えられる。先頭の文字が 1 であることが保証されている。 以下の条件を満たす整数の組 () の個数を求めよ。 はともに回文数である (11 や 1…

AOJ 3174 No Palindromes (HUPC 2020 day3-C)

これ楽しい! 問題へのリンク 問題概要 長さ の英小文字のみからなる文字列 が与えられます。 の文字を入れ替えることによって、次の条件を満たす文字列 を作ることができるかどうかを判定してください (可能ならば具体例を 1 つ挙げてください)。 のどの長…

AtCoder ABC 175 F - Making Palindrome (橙色, 600 点)

こういう重たい実装を確実にこなせるように...なりたい! 問題へのリンク 問題概要 個の文字列 が与えられる。これらを好きな順序で好きな回数だけ concat して回文を作りたい。ただし 番目の文字列を使用するコストは 1 回あたり である。 回文を作れるかど…

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning (黄色, 700 点)

遷移先を絞れる系の DP 問題へのリンク 問題概要 長さ の文字列 が与えられる。これを以下の条件を満たすように最小個数の区間に分割したい。最小個数を求めよ。 どの区間についても、区間内の文字を適切に並び替えると回文になる 制約 考えたこと まず「文…

CODE FESTIVAL 2017 qual C C - Inserting 'x' (緑色, 400 点)

少しでも実装を楽にしたい 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。以下の操作を最小回数行って回文にしたい。その最小回数を求めよ。不可能な場合は -1 を出力せよ。 のどこかに 'x' を挿入する 制約 考えたこと まず可…

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

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

AtCoder AGC 021 D - Reversed LCS (黄色, 900 点)

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

Educational Codeforces 62 E - Palindrome-less Arrays (R2200)

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

早稲田大学プログラミングコンテスト 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 で割ったあまりで求めよ。 制約 は英小…