解いた問題のソースコードと解説など。


文字列処理

POJ 2341 Spell Checker

問題 アルファベットと.,;:-!?とスペースからなる文章が与えられる.文の区切りは.か!か?である.文章中の不整合な箇所の個数を答えよ. ただし不整合なケースとは以下の2種類を指す. 文頭が大文字でない 単語の途中に大文字がある やりかた 文意を正確に汲…

POJ 3510 A Tale from the Dark Side of the Moon

問題 文字列が一行ずつ与えられる。一行ごとに以下の処理を行って出力せよ。 アルファベット小文字とスペース以外は削除 "dd"という文字列があったら"p"に変換("ddd"という入力はないものとする) "ei"という文字列があったら"ie"に変換(ただし直前の文字…

POJ 1917 Automatic Poetry

問題 "s1<s2>s3<s4>s5" という形式の文字列が与えられる。もう一つ "s..." という形式の文字列が与えられる。元の文字列からカッコを取り除いた文字列と、もう一つの文字列を "ss4s3s2s5" という形式に直したものを出力せよ。 やりかた Javaであれば正規表現を使える</s4></s2>…

POJ 1107 W's Cipher

問題 アルファベットとアンダーバーからなる文字種を[a-i]、[j-r]、[s-zと_]の3グループに分ける。 文字置換による文章の暗号化を行いたい。暗号化の方法は平文の文字を一つずつ見ていき、その文字がグループiに属する時、その文字の右側を見ていって、グル…

POJ 2121 Inglish-Number Translator

問題 アルファベット表記された数字を英数字に変換して表示せよ。 やりかた 数字をthousand未満、thousandの桁、millionの桁に分けて各桁を英数字に直して、桁の数字をかけて足し合わせた。以下ソース。 int main(int argc, char **argv){ map<string, int> p; p["negativ</string,>…

POJ 2295 A DP Problem

問題 'x'を変数とする1次方程式が文字列形式で与えられる。この方程式をxについて解き、解を床関数にかけたものを出力せよ。ただし解が不定の場合は"IDENTITY"を、不能の場合は"IMPOSSIBLE"を出力せよ。なお入力文字列は空白を含まない。 やりかた 単にやる…

SRM 417 Div1 Medium CubeNets

問題 1x1x1のサイズの立方体の展開図が文字列として与えられる。'#'はそこが1x1のサイズの面であることを表し、'.'は面ではないことを表す。 この展開図は正しい展開図であるとは限らない。そこで文字列が与えられた時、正しい展開図となっているかを返せ。 …

SRM 405 Div1 Medium AllCycleLengths

問題 連結な有向グラフが与えられる。ある頂点から再びその頂点に戻るような長さxのパスが存在するときxはvacation friendlyであるという。途中で頂点に一度戻るようなパスも可とする。 xを1から無限まで調査し、vacation friendlyなら1、そうでないなら0と…

SRM 368 Div1 Medium PolylineUnion

問題 折れ線グラフが以下の形式で1つ以上与えられる。互いに交差している折れ線グラフを1つの集合と数えると、いくつの集合になるか。1つの折れ線は1つ以上の線分からなり、点同士は'-'で区切られ、点は','で区切られる2つの非負整数で表現される。' 'で区切…

SRM375 DateFieldCorrection

問題 QWERTYキーボードにおいてキーとキーの距離とは隣接するキーをいくつ隔てて到達できるかによる。ただしスペースキーと隣接するキーとの距離は3と数える。(詳細は問題文中の図)"month day"という形式で日付が与えられる。この日付はミスタイプされてい…

SRM 330 Div1 Medium PrefixFreeSubsets

問題 どの要素も互いの接頭辞にならないような文字列の集合をprefixfreeな集合と言う。与えられた文字列の集合のうちprefixfreeとなるような部分集合の数を求めよ。空集合も含める。 やりかた メモ化再帰による。 文字列をソートするとprefixfreeとならない…

SRM 320 Div1 Easy ExtraordinarilyLarge

問題 数字xとyがあたえられる。数字には0個以上の!がついており、これは階乗演算を表す。x,yの大小比較をせよ。 やりかた たとえば100!!!と1000!!を比較するとき、!の多いほうが、少ない方と同じになるまで階乗計算を行えばあとは数字の部分を比較するだけで…

SRM 542 Div2 Hard StrangeDictionary

問題 http://apps.topcoder.com/wiki/display/tc/SRM+542 長さが等しい文字列が複数与えられる。文字列中のランダムな2箇所を置換するのをランダムな回数行う処理をすべての文字列について行う。処理後の文字列をソートした時に当初の文字列が何番目に置かれ…

SRM 526.5 Div2 Hard MagicNaming

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11674&rd=14762 文字列がn個存在し、これらを辞書式最小になるように結合したものがSとなる。このnを最大化せよ。 やりかた DP。 dp[j][i] := (文字列Sのj文字目まででS[i...j]を1つの文字列と…

SRM 516 Div2 Hard NetworkXMessageRecovery

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11239&rd=14541 文字列message[i]を部分列として持つような最短の文字列を返せ。複数ある場合は辞書式最小のものを返せ。なお各message[i]の文字はすべて異なる。 やりかた Editorialを参考にし…

SRM 499 Div2 Hard PalindromeGame

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11331&rd=14428vector string が与えられる。各文字列の長さは等しい。各文字列には点数が割り当てられており、この文字列から複数を取り出してそれらを任意の順で結合した文字列がもし回文とな…

SRM 497 Div2 Hard MakeSquare

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=8681&rd=14426同じ文字列を2つ結合してできた文字列をSquareな文字列という。文字列Sから好きな文字を取り除く、変更する、挿入するという操作を行うことでSquareな文字列にするための最小の操…

SRM 496 Div2 Hard PalindromefulString

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11296&rd=14425大文字アルファベットからなる長さNの文字列を想定する。この文字列中に回文となる長さMの部分文字列がK個以上あるとき、この文字列をPalindromefulな文字列という。N、M、Kが与え…

SRM 476 Div2 Hard SubAnagrams

問題 http://apps.topcoder.com/wiki/display/tc/SRM+476YのあるsubstringのアナグラムがXになるとき文字列Xが文字列Yのsubanagramであるという。いくつかの文字列がvector stringで与えられる。これらの文字列を結合した文字列Sをn個に分割したい。ただしS1…

Get up! 明日のSUPER ST@R!