3 重の for 文を書くのが楽だと思う 問題へのリンク 問題概要 3 種類の文字 .、|、* からなる、長さ の文字列 が与えられる。 には | がちょうど 2 つ、* がちょうど 1 つ含まれる。 * が 2 つの | に挟まれているかどうかを判定せよ。 考えたこと 色々な解…

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

至ってシンプルな構文解析問題。ただちょっと仕様が不明瞭なところがある気もする。 問題へのリンク 問題概要 次のように、何個かの計算式を表す文字列 が与えられるので計算結果を出力せよ。 2 4-2*3= 4*(8+4+3)= 式は数値、演算記号、かっこからなり、= で…

アドホックにも実装できそうだけど、構文解析ライブラリで殴った！ 問題へのリンク 問題概要 0 以上 9 以下の整数値に対して「+」「×」で連結して得られる長さ の文字列 が与えられる。たとえば以下のような文字列が与えられる。 1+2*3+4 また、Bob がこの式…

この問題のおかげで、構文解析力が上がった！ 問題へのリンク 問題概要 次のように、 の関数を表す式 が与えられる。基本的には「+」「*」「^」「log」で構成されるものである。 N*log(N^2)*log(N)+N+log(N^1+N)^2*N より正確には、次の BNF によって定義さ…

これは難しくないけど、少し面倒。。 問題へのリンク 問題概要 次のようなプレイヤーのレーティング情報が与えられる。 tourist 3858 ksun48 3679 Benq 3658 Um_nik 3648 apiad 3638 Stonefeang 3630 ecnerwala 3613 mnbvmar 3555 newbiedmy 3516 semiexp 34…

o......f...(.....)... のようなパターンで、(.....) の中身が消せるような場合を最初見落とした。 問題へのリンク 問題概要 長さ の文字列 に対して、次の操作を好きな回数だけ行える。操作後の文字列の長さとして考えられる最小値を求めよ。 が連続する部…

久しぶりに本当に簡単だと言える A 問題！ 問題へのリンク 問題概要 2 つの文字列 が与えられる (これは苗字と名前を表している)。 + " " + "san" を出力せよ。 コード 標準入力から文字列を受け取る技術があれば解ける問題。 を出力したあと、" san" を出力…

C 問題としてはかなりハードな問題であった。 問題へのリンク 問題概要 個の文字列 のうち、文字列 との編集距離が 1 以下であるものの個数を求めよ。 なお、文字列 と文字列 の編集距離が 1 以下であるとは、以下のいずれかが成り立つことを指す。 である …

問題を典型パーツに分解して考察を積み上げていく系の、とても教育的な問題！ 問題へのリンク 問題概要 個の文字列 と文字列 が与えられる。以下の条件を満たす の組の個数を求めよ。 と をこの順に連結してできる文字列から、いくつかの文字を選び、順序を…

Suffix Array 上をひたすら頑張って探索する感じ 問題へのリンク 問題概要 個の文字列 が与えられる (これらの文字列はすべて英小文字のみからなる)。 以下の条件を満たす文字列 の個数を求めよ。 英小文字のみからなる のうち、ちょうど 1 個の部分文字列で…

添字の偶奇によって処理を分岐する系 問題へのリンク 問題概要 0 と 1 のみからなる、16 文字の文字列 が与えられる。 の左から偶数番目の文字がすべて '0' であるかどうかを判定せよ。 コード 先頭が S[0] なので、S[1], S[3], ..., S[15] の中に 1 がある…

文字列の標準入力と、先頭の文字がわかっていれば解ける系 問題へのリンク 問題概要 "AtCoder s Contest" という形の文字列 が与えられる (s の部分は任意)。 たとえば、"AtCoder Beginner Contest" のような文字列が与えられる。これを "ABC" のように略し…

少し FizzBuzz チックな判定問題 問題へのリンク 問題概要 長さ の文字列 と、長さ の文字列 が与えられる。 であることが保証される。 が の prefix でも suffix でもあるとき：0 が の prefix であるが suffix ではないとき：1 が の prefix ではないが su…

「連続文字列」を処理する典型問題。 問題へのリンク 問題概要 文字 A, B, C のみからなる長さ の文字列 が与えられる。 文字列 に含まれる連続部分文字列 "ABC" のうち、それが始まる最小の添字を答えよ。"ABC" を含まない場合は -1 を出力せよ。 解法 (1)…

入力を文字列として受け取ってしまうのが楽だと思う！ 問題へのリンク 問題概要 各桁の値が単調減少 (等しいはダメ) になっている数を 321-like 数と呼ぶことにする。 たとえば、971 や 5 は 321-like 数であるが、978 や 988 は 321-like 数ではない。 与え…

文字列の練習！ 問題へのリンク 問題概要 英大文字のみからなる、長さ の文字列 が与えられる。 の末尾の文字が 'G' 以外のとき： の末尾に文字 'G' を挿入して得られる文字列を の末尾の文字が 'G' であるとき： の末尾の文字 'G' を削除して得られる文字列…

アルファベットを戻す処理を書くのが最初は難しいかもしれない 問題へのリンク editorial 問題概要 シーザー暗号とは、文字列に対して、各文字を 3 つずつ進めたものに変換するものである。ただし、X, Y, Z はそれぞれ A, B, C となる。具体的には、次のよう…

Z-algorithm や Suffix Array が使える面白い文字列検索問題！ 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。次の条件を満たす文字列 の組が何個あるかを答えよ。 はいずれも空文字ではない である 制約 考えたこと この手の問…

こういうの詰めるの時間かかる。サンプルも弱いので、愚直シミュレーション解も実装して、それとの一致を確かめたりなどした！ 問題へのリンク 問題概要 '1'〜'9' のみからなる文字列 が与えられる。この文字列に対して文字列を返す関数 がある。 は次の操作…

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

フラグ変数を 3 個持ってもいいし、set 型を使ってもいい 問題へのリンク 問題概要 文字 'A', 'B', 'C' のみからなる、長さ の文字列 が与えられます。 S を左から 1 文字ずつ見ていったときに、はじめて「A, B, C がすべて 1 回以上出現している」という条…

少し前処理が面倒な DP。PCK の予選突破ライン上の問題のようですね！ 問題へのリンク 問題概要 個の整数 が黒板に書かれている (各整数は 100 桁までありうる)。 奇数の精と、偶数の精がいる。 奇数の精は、黒板に書かれている数字がすべて奇数となるように…

最小回数を求めるには BFS！！(素振り) 問題へのリンク 問題概要 黒板に整数値 が書かれています。次のいずれかの操作を最小回数繰り返すことによって、整数値 の値を にしたいとします。 を 倍して にする を十進法表記したときに、末尾の値を先頭に持って…

とてもいい感じの BFS の練習問題！ 問題へのリンク 問題概要 "atcoder" の並び替えである文字列 が与えられます。 文字列 に対して「隣接する 2 要素を swap する」という操作を繰り返すことで、"atcoder" となるようにしたいとします。 最小何回の操作で実…

メビウス関数を用いた約数系包除原理を使いこなそう！ 問題へのリンク 問題概要 (表現改) 文字 '.' と '#' のみからなる長さ の文字列 が与えられる。今、文字 '#' をいくつか '.' に書き換えることによって、文字列 が周期的文字列となるようにしたい。 な…

前から "PC" 詰めしていけば OK！！ 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 '.' か 'T' が書かれている。今、次の操作をできるだけ多く行いたいとする。 左右に 2 文字連続した "TT" を "PC" に置き換える 操作回数の最大化を目指…

ランレングス圧縮をする問題に一瞬見えるかもしれない。でもそんなことしないで、最初から最後まで綺麗に DP で殴れる！ 問題へのリンク 問題概要 文字 'a' と 'A' のみからなる長さ の文字列 が与えられる。 以下のキーボード操作を繰り返すことで、この文…

Suffix Array を用いる練習問題！ ACL practice contest にもある。 問題へのリンク 問題概要 長さが の文字列 が与えられる。 の連続する部分文字列の種類数を答えよ。 制約 考えたこと 実は、AtCoder Library Practice Contest に全く同じ問題がある！ drk…

「並び替え方」の全探索は、C++ なら next_permutation()、Python3 なら itertools.permutations() が使える！ 問題へのリンク 問題概要 個の長さ の文字列 が与えられる。 これらを並び替えて得られる文字列 であって、 「 と が 1 文字違いである」() とい…