SRM580 Div1 Easy

250

区間の両端だけを気にすればいい。

SRM518 Div1 Medium

500

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

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


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

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メモ化)でよくある"どこまで見た"が登場しなかったので相当悩んだ。
思い込みはいけない。

SRM579 Div1 Medium

450

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

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

SRM579 Div1 Easy

250

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

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行目が確定している。下から上へ見て行って良い気がする。
とりあえず逆から見ていったらサンプルが合う。通る。

SRM503 Div1 Medium

500

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

SRM502 Div1 Medium

500

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

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

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

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

SRM499 Div1 Medium

550

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

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

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

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

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

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 は成り立たない。

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

SRM486 Div1 Medium

450

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

SRM481 Div1 Medium

500

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

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

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

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

SRM578 Div1 Easy

250

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