動的計画法のアルゴリズムは以下の通り。 最適解の構造を特徴づける 最適解の値を再帰的に定義する ボトムアップに最適解の値を求める 最適解を構成する １．最適解の構造を特徴づける 問題がより小さい問題に分けることができ、問題の最適解に小さく分けた…

Problem Statement A string S is called a square if there is some string T such that S = T + T. For example, the strings "", aabaab" and "xxxx" are squares, but "a", "aabb" and "aabbaa" are not. You are given a String s. Find the longest sq…

Problem Statement When dealing with long names and phrases, we sometimes use the initial letters of words to form its acronym. For example, we use "JFK" instead of "John Fitzgerald Kennedy", "lgtm" instead of "looks good to me", and so on.…

Target Coding Phase：SRM 698 DIV2のEasy問題を正答すること ⇒ 達成 Challenge Phase：今回は特に目標を設けない ⇒ N/A Result Not Rated ⇒ 1157（↑） Green Coder Easy(250)：Passed System Test Medium(500)：Opened Hard(1000)：Unopened Implessions Ea…

Problem Statement An out-of-control robot is placed on a plane, and it takes n random steps. At each step, the robot chooses one of four directions randomly and moves one unit in that direction. The probabilities of the robot choosing nort…

探索における手法に深さ優先探索と幅優先探索がある。 最強最速アルゴリズマー養成講座によると、問題を解答するにあたって、どちらの探索手法を使えばよいかの指針は以下の通り。 ※どちらを使ってもよい場合もあるので注意すること。 深さ優先探索を使うケ…

TopCoderに参戦している人の中ではおそらく常識なのだろうが、PracticeでSystem Testを実施する方法を発見。 これまではPracticeでSystem Testを実施する方法がわからず、EclipseCoderで自動生成されるテスト（問題中のExamples）を通しているだけだったので…

いよいよ9/18のSRM 698にてTopCoderに初参戦する予定です。 ここでは初参戦に向けた目標と現状、参戦までに取り組むことをまとめておきます。 目標 Coding Phase：SRM 698 DIV2のEasy問題を正答すること Challenge Phase：今回は特に目標を設けない 現状 最…

解くには解けたが、かなり遠回りなコードを書いてしまった。 考えた全探索のロジックは以下の通り。 探索対象を1人決める（= friends[i]） 探索対象の友達を検索（= friends[i].charAt(j)がYとなる人） 探索対象の2で抽出した友達以外の友達を検索（= friend…

回文を作る最小の文字列長を求める問題。 Problem Statement John and Brus are studying string theory at the university. Brus likes palindromes very much. A palindrome is a word that reads the same forward and backward. John would like to surp…

SRM 150 DIV2 Medium(500) - InterestingDigitsを解いたので、ついでにEasy問題も解いてみた。 この問題は、前日までの積み残し（rest）と当日到着分(arrivals[i]）の合計が当日処理可能分（numPerDay）を超えるかどうかを考慮すればOK。 前日までの積み残し…

初のMedium問題。さすがにこれまでの問題とは違って難しく感じた。4桁未満のチェックでOKという問題文の設定を見落としていて、実装の方針がたたずギブアップ。解説を読んで4桁未満でokということに気づき、何とか実装をこなした。 Problem Statement The di…

この問題は読んだ瞬間に一番小さい数を+1した場合は最大になることが直感的に分かった。 したがって、実装もそれに沿った形で行った。 これぐらいの難易度であれば解けそうな雰囲気。簡単そうな問題を選んでくれているのだろうけれど・・・。 Problem Statem…

SRMで少しでも時間を有効に使うためにEclipseCoderというEclipseのSRM用Pluginを使用しています。 操作は非常に簡単で、クラス、メソッドのシグニチャからExampleのテストケースまで自動で生成してくれとても重宝しています。 が、本日このEclipseCoderからA…

引き続き、最強最速アルゴリズマー養成講座から。 こちらの問題もMapを知っていれば簡単に実装が可能。このレベルならきっちり1問解くことができそう。 Problem Statement Mr. White is a very versatile person - absolutely everything is interesting to …

TopCoderに参戦するにあたって、まずは雰囲気をつかむため最強最速アルゴリズマー養成講座を読んで第4章の一番最初に取り上げられているSRM 478 DIV2 Easy(250)のコードを書いてみた。この問題なら確かに著者の高橋直大さんが書いている通り、何か特別な知識…