解いた問題

9/23/2013

9/08/2013

SRM590 Div1 Easy

250

Rが右に移動している
Lが左に移動している
RとLが交差していない

の3つを確認する

7/27/2013

SRM585 Div1 Easy

250
http://community.topcoder.com/stat?c=problem_statement&pm=11361

ある頂点とその直接の子2つを移動する様な選び方が最適なはず。つまり、頂点3個毎を1塊。
木の頂点を高さごとに分けて考えたとして、根とその直接の親の部分のコストを付け足す様な DP になる。

6/23/2013

SRM578 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=12534&rd=15498

memo[前の前に配置した地点][前に配置した地点]
ある2点間が、ある1つの区間に含まれるかどうかを前もって作っておく。
あとは、今現在着目している地点をこれまで配置した2点と同様の区間にならない様に選んでいく。

6/22/2013

SRM575 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=12498&rd=15495

ある位置が部分列に選ばれる確率を計算する。
ある位置の数字が"最終的に"その場所にある確率を計算する。

こういう列の要素のスワップの問題って、"その位置"と"他の位置"に分けて考えるのが定番なの?

6/19/2013

SRM583 Div1 Medium

500

グラフ中の最長パスを求める。もし両端を切り替える必要があるなら、そのパスで切り替える。
パスの両端の片方あるいは両方を木から取り除いて同様の操作を繰り返す。

もっと簡単にDFSやループだけで解けるらしい。

SRM583 Div1 Easy

250

WFとか。
range[i]が頂点の数より大きくなる場合がある。
(i - range[i] + V) % Vだと負になったりする。

6/16/2013

SRM543 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=11912&rd=14735

DP[どの島][どの港]
普通にループを回すと当然のがら間に合わない。

何分探索かして今注目している位置より左から適切な場所を探すのかと思ったけど、そんなことはなかった。
最小値あたりのインデックスを持っておいて、距離の近い方へと見ていく。

6/09/2013

SRM536 Div1 Medium

500

http://community.topcoder.com/stat?c=problem_statement&pm=11797&rd=14728

(総和の半分) or (総和 - 最大値)

(総和の半分)はすぐに思いつく。
(総和 - 最大値)は分からなかったので小さいケースをいくつか手で試した。

6/04/2013

SRM528 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=11634&rd=14553

memo[一方をどこまで作った][もう一方をどこまで作った]

s[x[k]] = s[y[k]] の条件を満たしうる長さN/2の文字列を全て生成して数え上げる。
候補の文字列をtとして、memo[i][j]に注目している時、t[i]かt[j]のどちらかに文字を割り当てる。
割り当てられる文字はs[i + j]。

(2^20)*(20^2)は無理だろうと思ってひたすら別解法を考えたけど、結局はこれだった。
あまり手を抜くとTLEする。

6/01/2013

SRM522 Div1 Medium

450
http://community.topcoder.com/stat?c=problem_statement&pm=11604&rd=14547

いつも通りどれかを決め打ちして計算する。AとBを決めて、近い値を探す。

よく見たら解くの2度目だった。

SRM520 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=11496&rd=14545

DP1[どれを解いた][ポイント] = あるポイント以下を取るパターン数
DP2[何人目まで見た][ポイント] = パターン数

まず、幾らかの問題を解いてあるポイントを取るパターン数を数え上げる。
問題 i のポイントのとり方は、(1, points[i]) の区間。
注目しているポイントを p とすると、テーブルの更新にはそれまでの (p - 1, p - points[i]) の区間の総和が必要。
BITで挑戦するも、意外と遅くて方針転換。

ある区間の総和は、累積和で計算する。
DP1[bit | (1 << i)][p] = (DP1[bit][p - 1] - DP1[bit][p - 1 - points[i]]) + DP1[bit | (1 << i)][p - 1]
加算の左辺値が区間の和で、右辺値が累積
※この累積和の区間はinclusive

次に、全体のパターン数を数える。
n番目の参加者は(n - 1)番目の参加者よりも大きいポイントを取っているはず。
n番目の参加者がポイントを p だけ取得しているとすると、(n - 1)番目の参加者が p 未満のポイントを取った場合のパターン数の総和が必要。
また総和が必要なので累積和をまた使う。 
DP2[c][p] = DP2[c][p - 1] + DP2[c - 1][p - 1] * (ポイント p の作り方)
加算の左辺値が累積で、右辺値がポイント p を取るパターン数
ポイント p の作り方は最初の累積和から、 (DP1[bit][p] - DP1[bit][p - 1])で計算できる。



難しかった。

5/23/2013

SRM518 Div1 Medium

500

とりあえず条件の通りに実装して終わり。

"どうせこんな感じだろう"で通してしまった。
正答率を見て問題を選んでいることを後悔した。


他の解法もあるそうなので考えてみよう。

5/22/2013

SRM513 Div1 Medium

500

memo[両方の位置が特定されていない組みの数][片方の位置が特定されていない組みの数] = 期待値

全ての位置を記憶できるという事は、あるターンで最初にめくるカードはまだ一度もめくっていない位置を選ぶのが最適。
絵が合わなかった場合、もう片方が出るまではずっと放置することになる。

"初めてめくるカード" -> "初めてめくるカード" (運良く同じ絵)
"初めてめくるカード" -> "初めてめくるカード" (違う絵)
"初めてめくるカード" -> "もう片方の位置が分かるカード"
"もう片方の位置が分かるカード" -> "もう片方のカード"

の4パターンを考える。

SRM511 Div1 Medium

500

memo[いくつ選んだ][ビット] = 必勝 or 必敗

{1, 10, 11, 500}がわかりやすいが、ORを取っても変化しない場合が存在する。
DP(orメモ化)はDAG上での計算なので、これは非常に困る。
しかも、数字は50個ある。2^50は無理。

現状のビットを作るために使える数字の個数の最大は、ORを取って変化がない数字の個数になる。
"これまで選択した数字の個数"と"使える個数の最大"を比較することで、変化しない場合を繰り返せるか分かる。
{1, 11} ⊂ {1, 10, 11}という包含関係の集合の大きさの差を思い浮かべると良いのかもしれない。

DP(orメモ化)でよくある"どこまで見た"が登場しなかったので相当悩んだ。
思い込みはいけない。

5/19/2013

SRM579 Div1 Medium

450

DP[どこを巡った][今どこ] = 最短時間
O(2^N * N)

前もって全点間最短距離を計算しておく。

SRM579 Div1 Easy

250

最初の行は全てタイプするしかない。
それ以外は、
1.直前のバッファにそのまま付け足す。
2.履歴からプレフィックスに一致する文をもってくる。
3.バッファを消して全てタイプする。

5/18/2013

SRM507 Div1 Medium

500

2辺の長さを決める。よくあるアレ。

入力が大きいので、とりあえず2辺を決める方向で考える。
大きい方に合わせて残りの1辺の長さを決めて、小さい方で帳尻を合わせてみる。
問題は、小さい方をキューブのどの面の方向に並べるか。

i <= j <= k のとき、
A. (i + 1) * j * k
B. i * (j + 1) * k
C. i * j * (k + 1)

格方向へ1だけ大きくした場合、 i * j だけ増加する C が小さそう。

大きくする量が 1 より大きくても同じ事が言えそうな気がする。
小さい方の残りは、ある1つの面だけを必要なだけ伸ばして対処してみる。
サンプル合う。投げる。通る。

SRM504 Div1 Medium

500

入力の大きさを見てDPを捨てる。

H-1行目を埋める段階では、H-2行目が確定している。下から上へ見て行って良い気がする。
とりあえず逆から見ていったらサンプルが合う。通る。

5/14/2013

SRM503 Div1 Medium

500

村ごとに計算する。1番近い村が選ばれる確率、2番目に近い村が選ばれる確率、... を計算する。
これを間違わずに実装できる気がしないけれど、本番での正答率はそれなり。
ツラい。

5/11/2013

SRM502 Div1 Medium

500

貪欲 & DP
DPか貪欲だろうとは雰囲気で察することができた。
が、具体的な解法が思いつかない。試しに問題からでなく上限から解法を考えてみる。

入力の上限から、( 時間 * 問題数 ) くらいの計算はできそうなので、それを足がかりに DP を考える。
DP[どの問題まで][経過時間] ならできそう。

こうなると、解く順番が問題。
解く問題が決まるということは、ポイントの総和が決まるということ。
なら、解く順番は減少が少なくなるように決めるはず。

( 減少 / 消費時間 ) でソートして試す。サンプル合う。通る。


5/10/2013

SRM499 Div1 Medium

550

DPを疑った後で諦めて貪欲へ。

小さいケースとサンプルを手で試す限りでは DELETE 無しでも答えが合う。
SPACE と相殺するから?

**
****
******
#####
###
#
作る順番に制約がないので、* 側を作る途中で RETURN して # 側を作っても構わないはず。

*******
*****
***
**
*****
*******
こう凹みがあったとしても、凹んだ部分で分割すれば山になる。

増加にだけ着目してしまえば良さそう。300 とか 450 くらいの問題にも思える。
どうやら、DP 解がちゃんとあるらしい。

5/08/2013

SRM498 Div1 Medium

450

マークのある地点までの距離をが等しい箇所を数えてしまって良い。
同じ地点が F 箇所ある場合、ただの並び替えなので F 階乗パターン。

SRM496 Div1 Medium

500

2部マッチングの個数にしかみえなくて絶望。

経過した秒数 D の数はたかが知れている。
D を決め打ちしたとすれば、2部グラフが作れる。

+D 秒後と -D 秒後の 2 つしかマッチさせる候補がないので
あるマッチングの連結成分の右側と左側の頂点の個数は
R == L
R + 1 == L
R == L + 1
の3パターンしかない。

R == L のマッチングの個数は 1 通り
R + 1 == L はどこの入次数を 2 にするかで L 通り
R == L + 1 は成り立たない。

後は、連結成分ごとのパターン数の積を計算する。

5/06/2013

SRM486 Div1 Medium

450

実際にソートしながら試す。

SRM481 Div1 Medium

500

ます、同じ人のタスクは連続して処理されるべき。
混ぜると、同じ時間の消費でも互いの終了時刻が後ろにずれてしまう。

どれから最初に処理すべきかというと、時間の総和が小さい順。
逆だと、同じ時間の消費でも終了時刻が後ろにずれてしまう。

同じ時間同士の場合は、1/2して期待値に足す。
どちらが先に行われるかは等確率なので、それより前の場合と後の場合になる。

同じ人のタスクの中での期待値も同様の理由から、1/2にして期待値に足す。

5/03/2013

SRM578 Div1 Easy

250

マンハッタン距離が dist 以下の点同士をまとめておく。
"選ぶ" or "選ばない"の2択で偶数になる場合を数え上げる。
DP[どこまで見た][総和の遇奇]=パターン

4/29/2013

SRM479 Div1 Medium

500

safety の値を2分探索しながらダイクストラする。
ところどころ signed int に収まらないことに注意。

問題文が長いし、どこか見落としそう。
UVaみたいな問題だから好きになれない。

SRM477 Div1 Medium

500

2部マッチングするだけ。
入力の仕様に殺意を覚えた。1時間も悩んだ。

4/28/2013

SRM466 Div1 Medium

500

5箇所を選ぶパターン数を数える。
DP[何列目まで決めた][残り何箇所][勝利状態かどうか] = パターン数

dp[N][0][true] / (dp[N][0][true] + dp[N][0][false])
で確率が出る。

SRM473 Div1 Medium

500

円の中心を通るような直線を含む三角形は直角三角形になる。

a = 0, b = 0 のときが問題で、愚直にやると O(N^2) かかる。
気のきいた方法を取るべし。

通した後で気付いたけど、set.lower_bount でいいのでは。

4/24/2013

SRM463 Div1 Medium

500

加算の方が大きくなるのは 2 以下だった気がするので、下限が 1.5 だとある数字の加算が 1 度しか行われないことになる。
また、乗算はそれぞれの数字の差が小さい方が結果が大きくなる。
小さい方から、ある範囲をそれと隣接する範囲へ逆順に加算し、総乗する。

4/22/2013

SRM462 Div1 Medium

450

ある組みのスワップが起こる確率は 2.0 * (c / (n * c)) * (c / (n * c - 1.0))
ある交換で変化する期待値の差分は score[i] - score[j]
各箱に入っているキャンディーの数は言うまでもなく C

あとは、数値を S ターンだけ更新する。

こういう、"スワップした後"と"期待値"が出てくる問題の類はひどく苦手。

4/21/2013

SRM451 Div1 Medium

500

dp[どれを最後に拾った][最後に足したK] = 最大
i 番目の次に j 番目を拾おうとする場合、最小でも、
k + (k + 1) + (k + 2) + ... (k + (j - k)) = (j - k) * k + ((k + 1) * k / 2)
だけは足す必要がある。それ以上であれば、移動可能ということになる。
あとはいつもどおり DP する。

4/15/2013

SRM450 Div1 Medium

500

10^12 とか 10^6 程度でどうこうできるだろうと見切り発車して後悔。意外と難敵。

ある工場か従業員を雇うなら可能な限り多く一度に増やすべき。
増やせない場合は、増やせるターンまで飛ばす。
それとは別に、これ以上増やさずにいったとして何ターンかかるかも計算しておく。

オーバーフローとか怖い。
もっと綺麗に実装できそう。

4/07/2013

SRM575 Div1 Easy

250
2の累乗の場合は指数の遇奇。
それがいは単なる遇奇。

実験ゲーらしい。
本番中に解けなかった。ツラい。

4/05/2013

SRM557 Div1 Medium

550
DAGの最小パス被覆。Dilworthの定理。
サイクルに含まれるような頂点は無視する。

SRM557 Div1 Easy

250
貪欲に近い方へ移動する。
その後、その移動が正しいか確かめる。

3/29/2013

SRM551 Div1 Medium

450

変更の回数をコストにしてダイクストラする。

SRM551 Div1 Easy

250

並べる文字と並べる位置を全部試す。

SRM574 Div1 Medium

450

memo[ どの頂点を使った ][ 最後にどこを使った ]

次に使う頂点との両側にすでに訪れた頂点があれば交差する。はず。
0 と N-1 の隣接を忘れるという悲しい出来事があって本番中に通せなかった。

SRM574 Div1 Easy

250

とりあえずメモ化する。意外と間に合う。

3/25/2013

SRM550 Div1 Medium

500

配置の仕方が、nCk = n-1Ck-1 + n-1Ck を何となく連想させる。
描画してみる。向きと幅がアレだけど、nCk mod 2 のフラクタルに見える。しかし、値の範囲が大きすぎる。

どうやら、nCkが奇数であることと(~n&k)==0は同値らしい。

3/24/2013

SRM550 Div1 Easy

300

座標の最大と最小から盤面のサイズを予測する。
予測した盤面上で動きが再現できりるか試す。

問題を把握するまでに時間を要した上に、実装でもつまらない間違いを連発。
悲しい。

3/21/2013

SRM572 Div1 Medium

500

前半分と後半分に分けて、半全列挙。
半全列挙なんて最後に使ったのいつだったろう。すっかり存在を忘れていた。

探索でも解けるらしい。rand を使っている人もいた。

SRM572 Div1 Easy

250

前からの範囲と後ろからの範囲がオーバーラップすることに注意。
同じ文字にする必要のあるインデックスの中で、どれに合わせるべきかを調べていく。

3/17/2013

SRM 567 Div1 Medium

500
文字数の多い文字から考える。難しさが easy と大差ない気がする。

SRM567 Div1 Easy

250

積が平方数になるような2つの数を考えればいい。

SRM571 Div1 Medium

500
クリークなんて、どうせバックトラック。3 m >= 2 n の条件から、16個くらいの頂点を消すことを考える。

SRM571 Div1 Easy

250
バックトラックして頭から作っていく。

2/18/2013

SRM569 Div1 Medium

500

O(n) の貪欲で解ける。
操作は、"Kの倍数を作る"、"全部上の階へ渡す"、"(倍数にならなくても)とにかく上の階から持ってくる"、の3パターンがある。
倍数を作れるなら極力そうした方が良いのは直感的に明らか。
m 階に注目しているとして、m 階に m - 1 階から幾人か上がってきている場合、彼らはその階で消費する必要がある。
その際、上の階からKの倍数にならないとしても全員を持ってきた方が、それより上の階で消費されるべき人数を減らせる。

苦戦した。貪欲は難しいと再認識した。

2/14/2013

SRM570 Div1 Easy

250

プログラムを何週か実行してこれまでと同じ向きで停止できれば、以降はそれの繰り返しになる。
実行回数 T を割り切れない様な周期での繰り返しになる場合は、残りを普通に実行してしまえばいい。

1/30/2013

SRM568 Div1 Easy

250

赤緑青のボールを入れる箱をそれぞれ少なくとも1つは選ばなくてはいけない。
その1つを選び、残りは最も手数の少なくて済む色にしてしまう。

1/16/2013

SRM566 Div1 Medium

500

行列の累乗で計算する。
1 日目と n + 1 日目は同じ移動パターンは同じになるので、(1〜n日目の繰り返し) * (1〜m日まで)を計算すればいい。
繰り返し部分は累乗で計算し、残りを掛け算すれば答えになる。
ただ、愚直に行列の計算をやるとTLEは必至だが、行列が巡回行列なので、最初の1行だけあれば計算できる。

巡回行列なんて初めて聞いた単語だったけど、
c[ i ][ j ] += a[ i ][ k ] * b[ k ][ j ] の i を 0 にして置き換えたら式が分かった。

しかし、以下の実装だとそれなりに遅い。
累乗の計算を再帰せずにやったとしても、行列の掛け算を(0〜n-1)、(0〜m-1)の2つに分けると間に合わない。

(0〜m-1)の時点で別の変数を使って残りを計算する、としている人がいたので真似てみた。
そしたら間に合った。

1/13/2013

SRM566 Div1 Easy

250

ある1頂点だけから複数本の辺が出ている
辺が1つしかない
辺が1つもない
ある3頂点が3辺で結ばれている。

の4パターンを数える。

1/03/2013

SRM565 Div1 Medium

500

約数でニムをやる。

しかし、ニムに関してより約数を求めるところでつまずく。
区間篩なるモノがあるそうなので、それを模倣してある区間の約数を計算した。ありがとうスパソ。

1/02/2013

SRM565 Div1 Easy

250

DP[どこまで見た][いくら使った] = 合計

SRM564 Div1 Medium

500

DP[何個目][どの色が残っている][次に消すべき色] = パターン数
k が 1-based ということを見落として数時間を浪費して悲しい。

SRM564 Div1 Easy

250

小さい場合はBFS。大きい場合は全て到達可能。
縦か横の長さが4以上だと全て到達可能になるらしい。