内容 文字列が与えられるから、連続しない部分文字列(*1)は何個あるか数え上げたい。 ただし、部分文字列の内容が同じであれば重複して数え上げてはいけない。(*1) 連続しない部分文字列とは（自分で勝手に名付けたんだけど・・）、 以下のように、連続しな…

問題 TopCoder Statistics - Problem Statement 解法 区間dpる。 dp[L][R] := LからRまでの区間にて、シーケンスをcorrectにする消し方の場合の数 初期化 L == Rの場合、その一文字を消すしかcorrectにする方法はないので1 更新 Rのカッコに着目し、こいつを…

問題 TopCoder Statistics - Problem Statement 解法 A[i]の増加の仕方は2のべき乗ぐらいに凄く、A[90]ぐらいにはもうxの最大値である10^18を超える。 探索範囲は広くなさそうということで、枝刈り探索しました。 事後 Editorialを見ると、大きいものから順…

問題 TopCoder Statistics - Problem Statement 解法 こちらを参考にしましたm(_ _)m mayokoex.hatenablog.com参考先でも言っているように、開きカッコ閉じカッコのペアが成立しているものを取り除いていくと、最終的には「））））（（」とか「）（（（（（…

問題 TopCoder Statistics - Problem Statement 解法 それぞれの色の花において、その数がガーデンの幅（rowの長さ）を超えているものがあれば、どう配置しても隣り合ってしまうため配置不可となる。 逆にそうでない場合、以下のようにすれば必ず配置可能と…

問題 リンク無し！ 訳 狼のSotheと猫のSnukeがカードゲームで遊んでいる。このゲームはちょうど100枚のカードを使う。カードには1から100の数字が書かれている。ゲームの遊び方については以下の通り。 1. 初めに、猫のSnukeが1から100の中から数字のNを選び…

問題 TopCoder Statistics - Problem Statement 解法 下の記事を参考にしました。m(_ _)m kmjp.hatenablog.jp有効グラフで考えたときに、頂点を以下のように色分けする。 A・・・0,1どちらからも到達できる頂点 B・・・0からのみ到達できる頂点 C・・・1から…

問題 TopCoder Statistics - Problem Statement 解法(一番早かった人のをカンニング) 通過する辺の重みにて、下回ってはいけない最小値ラインを決め打ちする。 ↓ 辺それぞれの重みから、決め打ちした最小値を差し引く。 ↓ 0 -> 1へ移動するために通る最大の…

問題 TopCoder Statistics - Problem Statement 解法 w1[i]を消すとw2[i-1]とw2[i]が消せなくなり、w2[i]を消すとw1[i], w1[i+1], w2[i-1], w2[i+1]が消せなくなる。 で、w1とw2を交互に、iの小さいものから消すか？消さないかを順に考えていけば、 w1[1]->w…

問題 TopCoder Statistics - Problem Statement 解法 dpる。 dp[i] := i-1番目の人までの、番号の振り方の場合の数 初期化 まだ誰にも番号を振っていないときは１パターンなので、 dp[0] = 1; 更新 i番目の人に1からi+1までの番号を振って、それぞれの場合の…

問題 TopCoder Statistics - Problem Statement 解法 dpる。 まず全員をteam1に加入させておく。 それから、生徒ごとに着目していき、team2及びteam3に移籍させる場合を考えていく。 team2及びteam3それぞれのチーム力とすることが可能かどうか記録しておき…

問題 TopCoder Statistics - Problem Statement 解法 最終的に使用するconstantの長さとその数について、実は一意に定まる。 以下を見て欲しい。 constantの長さ | 1 2 3 4 数 | 11 8 5 2 ↓ constants 4 を1回使うと残るのは ↓ constantの長さ | 1 2 3 4 数 …

問題 TopCoder Statistics - Problem Statement 考えたこと むずい！Div1 Easyってこんなにむずかったっけ！？ １時間考えてもできない・・ せや！他の人のソースコードを見て何やってるか考えたろ！ 解法 ヒーローは頂点を色で塗っていく流れだが、それを逆…

問題 TopCoder Statistics - Problem Statement 考えたこと 公約数といえばやっぱり2^a * 3^b * 5^c + ... と素因数分解して考えればよさそう。素数(2, 3, 5, 7, 11...)ごとに、関数Pにその素数が最小何個含まれるかを計算できればよい。そのときに|s|より大…

問題 TopCoder Statistics - Problem Statement 考えたこと Div1 Easyの難しい版。Nがとんでもなく大きくなっている。 ・・・が、確定リンゴの数は50以下と大したことない。 大半は確定リンゴではない買うも買わないも自由な日となる。確定リンゴがない場合…

問題 TopCoder Statistics - Problem Statement 考えたこと 結論から言うと、1 * 2のタイルをN * Mに敷き詰める時のパターン数え上げと同じ考えのbitDPでいけちゃう。毎日人の配置が変わっているためbitDPが適用できないと思いきや、そうでもなかった。下の…

問題 TopCoder Statistics - Problem Statement 考えたこと 貪欲でいけそう。n回目の買い物の時に、リンゴを買っても大丈夫ならば、買っちゃうのが最善。しゃくとり法っぽくi回目からi - K回目の範囲のリンゴの総和の計算し、総和がK / 2未満であるのことがK…

難易度 Coding Time Status Point Easy 1:15 Opened 0.00 Medium ---- ---- ---- Hard ---- ---- ---- Easy：貪欲までは分かった。実装であせりまくり時間切れ Med：見てない Hard: 見てない練習であせってどうするのよ

問題 TopCoder Statistics - Problem Statement 考えたこと 最大流問題だけど、いかんせん流量がでかすぎる・・(最大3^2000)それぞれの辺の流量は、3^0, 3^1, 3^2...3^n-1, 3^nという具合に割り当てられており、ある流量(3^x)はそれ以外の全ての流量の総和(3…

問題 TopCoder Statistics - Problem Statement 考えたこと ぬこグループが取るべき行動は２通りある。１つは一匹ずつ散らばること。(パターン１) 複数ポイントが0になるため理想的な動き方。ネックはこの動き方をするための条件が厳しいこと。ぬこの数だけ…

問題 TopCoder Statistics - Problem Statement 考えたこと まず、サンプルを良く見る。 ！！ Sample5で制約MAXでやってるやーん！ 最大でも93回でいけるのか！(サンプルから重要な情報を拾うとは今日は冴えてるぜ俺)・・・うーん、DPかな？ dp[i][c9][c3][c…

問題 TopCoder Statistics - Problem Statement 考えたこと グラフは木ということで、Simple Pathの長さ(距離)には、以下のような性質があるっぽい。まず、隣のノードは違う色になるように赤青２色で塗り分ける。 すると、赤と赤もしくは青と青のノード同士…

難易度 Coding Time Status Point Easy 0:23 Challenge Succeeded 0.00 Medium 0:52 Opened 0.00 Hard ---- ---- ---- 順位 ?/?(otinn.comがお亡くなりになっていたので分かりません) Rate 1357 -> 1302Easy：「撃 沈」。コーナーケース見逃してました。 Med…

問題 TopCoder Statistics - Problem Statement 考えたこと 頂点が２つ以上あれば、適当な頂点を２つ選ぶことで必ずkを2にすることができる。kを3以上にするには、最短パスで共通的に使う頂点cがなければならない。頂点u, v, wからcへの最短パスの距離が同じ…

問題 TopCoder Statistics - Problem Statement 考えたこと １つの形を頂点として、共通の味を持つ形同士を辺で結ぶグラフを考える。１つの形には２つの味があり、１つの味には２つの形がある、というルールより、グラフは複数のサイクルで構成される。サイ…

問題 TopCoder Statistics - Problem Statement 考えたこと 穴の辺上に合わせるようにボードを乗っけることはできないと・・つまりどういう事だってばよこう、縦横をテクニカルに埋めていって最小にする、みたいな事はできなそうだな！（フィーリング）縦な…

難易度 Coding Time Status Point Easy 0:19 Challenge Succeeded 0.00 Medium 0:56 Opened 0.00 Hard ---- ---- ---- 順位 375/627 Rate 1402 -> 1357Easy：撃 墜 Med：解法の手がかりは思いつけた Hard: 見てない黄色が遠のいた・・

問題 TopCoder Statistics - Problem Statement 考えたこと 頂点iを使用するには頂点f[i]は必ず使用しなければならないので、頂点iを含んだサブセットの数え上げは頂点f[i]とは独立して計算することができる。そこで、f[i] -> iというパスがあるグラフを作成…

問題 TopCoder Statistics - Problem Statement 訳 ヤヌシュは若い物理学者だ。彼は現在電気回路で実験をしている。最も単純な回路は単一の導体によって構成されている。そのような回路は"X"という文字列で表される。ヤヌシュは２つの方法を用いて、回路を２…

問題 TopCoder Statistics - Problem Statement 訳 ハリナは若い数学者だ。現在、彼女は正の整数を操る関数hについて興味を持ち勉強している。d(n)をnの正の約数の数とする。関数hはh(n) = n^d(n)と定義される。言い換えれば、h(n)はnをd(n)乗したものである…