TopCoder
方針 これは自力で解けたので嬉しかったです。コードはスマートではありませんが。。 出発点・到着点を含む円を半径の昇順でソートしたのですが、この処理はいらなかったですね。 出発点から到着点まで移動する間にまたぐ境界の数は各点のどちらかだけ含む円…
方針 直接の友達の数＋直接の友達でない人の中で友達に自分がいる人の数 を数えればOKというのに気付けませんでした。 友達の友達をすべて洗い出そうとしたのがよくなかったですね。それだと重複を除くのが大変です。 ソースコード using System; using Syst…
方針 DPで各マスに到達できる場合の数を数えていけばいいのですが、まだDPで解けばいいということに気付けません。。 この問題の答えはカタラン数になるそうです。 ソースコード using System; using System.Collections.Generic; using System.Text; public…
方針 DPで各マスに到達できる場合の数を数えていけばいいのですが、まだDPで解けばいいということに気付けません。。 ソースコード 私は盤面を再利用しましたが、三次元配列を使って履歴も保持した方がシンプルで不具合が出にくいかもしれませんね。 using S…
ソースコード DPの漸化式の立て方を間違えました。最初は dp[i] = Math.Max(dp[i - 1], dp[i - 2] + donations[i]); だと思ったんですが、２つ飛ばしても最大になる場合があるのでこれではだめですね。 最後の家から寄付をもらうケースをどう扱うかについて…
方針 元の文字列と、文字列を反転させたものを重ね合わせ、1文字ずつずらしていき一致したところまで ずらした数＋nが答えとなります。 こっちの方が簡単に実装できますね。ソースコード >|cs| using System; using System.Collections.Generic; using Syste…
問題の分析 与えられた文字列の後ろに文字列を追加して回文を作ります。 作成できる最短の回文の長さを求めなさい。 方針a 回文となっているかどうかを調べる範囲を正しくコーディングするのに手間取りました。 ソースコード using System; using System.Col…
問題の分析 n+m人の友人がいます。最初のn人は退屈しています。残りのm人はそうではありません。 j番目とb番目の友人を退屈させた場合、退屈している人の数を求めなさい。 方針 本当にやるだけの問題なので言うことがありません。 ソースコード using System…
問題の分析 int型配列rosesとliliesでroseとlilyの数がそれぞれ与えられます。 同じインデックスのroseとlilyはセットになっています。各セットのうちいくつかを購入してroseとlilyを矩形に並べます。 ただし、同じ種類の花が隣り合ってはいけません。 矩形…
問題の分析 与えられた文字列の配列から、与えられた各文字列prefix（前方一致）, suffix（後方一致）, substring（部分一致）にマッチする文字列の数を求めなさい。 方針 前方一致、後方一致はStartsWith, EndsWithメソッドを使えば判定できます。 部分一致…
問題の分析 "HH:MM"形式で時刻を表す文字列の配列が与えられる。"AA:BB", "AB:AB", "AB:BA"のようになっている文字列の数を求めなさい。 方針 ただ条件に合う文字列を数えるだけです。 ソースコード >cs| using System; using System.Collections.Generic; u…
問題の分析 次の条件を満たすさいころは何種類あるかを求めなさい。NとKは引数として与えられる。 ・使っていい数字は1からN ・同じ数字を二度使ってはならない ・すべての面について反対側の面との合計が同じ値になる ・ある面と反対側の面の合計がK以下 ・…
問題の分析 与えられた数字のうち、1文字を書き換えて作れる数字のうち、最も小さいものを求めなさい。 方針 与えられた数字が0の場合は1を返し、それ以外の場合は最も大きい桁の数字を0にすればOKです。 0が与えられた場合を例外的に扱わないといけないこと…
問題の分析 N本の一直線に並んだ木があり、それぞれの高さheightと間隔distanceが与えられます。 各木の高さは自由に縮められます。整数でなくてもよいです。 各木の頂点を一直線に並べるために必要な、木を縮める操作の回数の最小値を求めなさい。 方針 木…
問題の分析 N本のワインがあり、どれか一本を熟成させ、どれか一本を若返らせます。i番目のワインを熟成させるとprofit[i]の利益が得られ、 i番目のワインを若返らせるとdecay[i]の損失が生じます。 得られる最大の利益を求めなさい。 方針 利益の最大値−損…
問題の分析 N×MのテーブルがAntimatterとMatterで埋められています。 Antimatterの上に1×Kの大きさのアメーバを配置する方法は全部で何通りあるかを答えなさい。 アメーバはテーブルからはみ出したり、アメーバの下にMatterがきたりしてはいけません。 制約…
問題の分析 N×MのテーブルがAntimatterとMatterで埋められています。 Antimatterの上に1×Kの大きさのアメーバを配置する方法は全部で何通りあるかを答えなさい。 アメーバはテーブルからはみ出したり、アメーバの下にMatterがきたりしてはいけません。 制約…
問題 RとBからなる文字列が与えられるので、 1からNまでの自然数を使って以下の条件を満たす数列を作れ。 ・Rの位置には素数を当てはめる ・Bの位置には非素数を当てはめる ・左から右へ単調増加する ただし、ある位置が複数の数字を取り得る場合は、-1とす…
シミュレーションするだけですが、indexをforループの外で宣言しているのを忘れて初期化忘れの不具合が出てしまいました。 using System; using System.Collections.Generic; using System.Text; public class CarrotBoxesEasy { public int theIndex(int[] …
TopCoder Statistics - Problem Statement 問題文 キャンバスの各点ごとに白のままとしておくべきところ、黒く塗るべきところを指示される。 指示通りに塗ることができる最大の正方形の大きさを求めなさい。 方針 DPを使って各点を最も右下とする最大の正方…
http://www.topcoder.com/stat?c=problem_statement&pm=11293&rd=14425 珠玉のプログラミングか何かの本でほぼ同じ問題を見た記憶があります。 横にソートした後、UniqしてやればOK。 下記では縦にソートして異なる文字列の数を数えています。 横方向にソー…
問題 白紙の画用紙に絵を描きます。青色(B)のペンは縦に塗ることしかできず、赤色(R)のペンは横に塗ることしかできません。 青色のペンと赤色のペンで両方塗ると緑色(G)になります。 与えられた絵を描きたい時に、必要な塗る回数を答えなさい。 ただし、一直…
http://www.topcoder.com/stat?c=problem_statement&pm=8681&rd=14426 問題の分析 与えられた文字列を「真ん中から前半・後半に分けたときに前半と後半が同じとなる文字列」に編集する場合の最小編集距離を求めなさい。 方針 任意の二つの文字列の最小編集距…
Div2 Medium 問題の分析 数列の大小関係を表す文字列が渡されるので、その大小関係を満たすよう１〜Nの数字を並べなさい。 複数答えがある場合は、辞書順で最も小さいものを返しなさい。 方針 １からNまで順に並べた状態から処理をスタートする。 頭からsign…
TopCoderのSRM497に参加してみました。結果はEasyは解けたけど、Medium解いてる間に時間切れ。。 まだまだですな。 解いた結果をのせてみます。Div2 Easy 問題の分析 あなたはフィルタを作る技術者です。 指定されたサイズのモノを通す、あるいは通さないフ…
http://www.topcoder.com/stat?c=problem_statement&pm=11121 これは割と簡単で、解けたときにAHA体験ができる良問だと思います。 式変形をしていくと最終的にnumListの合計÷numList.Lengthで答えがでてしまう。 計算量O(n)！すご！
