解いた問題

7/21/2011

SRM462 Div1 Easy

250
見るからに二分探索。
コーナーケースに注意する。
何度かリサブミットしてやっと通った。Easyじゃないと思った。

SRM461 Div1 Medium

500
ある町からある町へ直接行くために必要な新設の町の数は割り算すれば分かる。
[町][追加した町の数]でダイクストラ。
頂点数が大きい。ちょっと手を抜いて実装してタイムリミット出してしまった。

7/20/2011

SRM461 Div1 Easy

300
交互に(同じ色同士は触れない様に)使うという条件があるので、赤からと青からの2通りを試す。

7/19/2011

SRM460 Div1 Medium

500
dp_table[いくつまで見た][いくつ選んだ][ファンの合計]

dp_table[a+1][b][c] += dp_table[a][b][c] * 選ばれない確率
dp_table[a+1][b+1][c+d] += dp_table[a][b][c] * 選ばれる確率 * d人選ぶ確率

7/18/2011

SRM460 Div1 Easy

250
各問題にYesがNoを割り当てて、どの答えがどの質問に対する答えなのかを全部調べてたら終わらないと思って、頑張って計算する問題だと思った。もちろん、そんなことはなかった。
挙句、解説を見て解いた。意外と単純な回答だった。悲しい。
質問を "Yes" か "No" か "2回目以降の出題" に割り当てながら数える。

7/17/2011

SRM459 Div1 Medium

500
まず、各マスに入る数字の重みを計算する。
次に、重みを足してtopを作るパターンを数える。
数え上げるdpで、for(各重み)for(和)と間違って、for(和)for(各重み)でやると、重複して数えてしまう。
間違えに気付くまで意外と時間をくった・・・。

7/15/2011

SRM458 Div1 Medium

450
かなり悩んだ。
例えば、硬貨が価値1のものと価値Aのものしかない場合、価値Aで払いきれない分(あまり)は価値1の硬貨で払うしかない。
同様に、価値Aの次に大きい硬貨が価値A*Bだった場合、価値A*Bで払いきれない分(あまり)は価値Aを使ってできる限り払うことになる。

7/14/2011

SRM458 Div1 Easy

250
全部試す。

SRM457 Div1 Medium

500
悩んだ。まだまだ実力が足らないみたい。
図に描いてみると分かるけど、1度に使う色の組は意外と少ない。
どの色にどの数を使うかの組み合わせを計算する。

SRM457 Div1 Easy

250
間違う場所が満載な気がする。

7/12/2011

SRM Div1 まとめ

SRM411   Easy

SRM430   Easy  Medium

SRM434   Easy  Medium


SRM450   Easy   Medium
SRM451   Easy   Medium
SRM452   Easy
SRM453   Easy
SRM453.5   Easy   Medium
SRM454   Easy   Medium
SRM455   Easy
SRM456   Easy   Medium
SRM457   Easy   Medium
SRM458   Easy   Medium
SRM459   Easy   Medium
SRM460   Easy   Medium
SRM461   Easy   Medium
SRM462   Easy   Medium
SRM463   Easy   Medium
SRM464   Easy   Medium
SRM465   Easy
SRM466   Easy   Medium
SRM467   Easy   Medium
SRM468   Easy   Medium
SRM469   Easy   Medium
SRM470   Easy   Medium
SRM471   Easy   Medium
SRM472   Easy
SRM473   Easy   Medium
SRM474   Easy
SRM475   Easy
SRM476   Easy
SRM477   Easy   Medium
SRM478   Easy
SRM479   Easy   Medium
SRM480   Easy   Medium
SRM481   Easy   Medium
SRM482   Easy
SRM483   Easy
SRM484   Easy
SRM485   Easy
SRM486   Easy   Medium
SRM487   Easy
SRM488   Easy
SRM489   Easy
SRM490   Easy
SRM491   Easy
SRM492   Easy


SRM495   Easy
SRM496   Easy   Medium
SRM497   Easy
SRM498   Easy   Medium
SRM499   Easy   Medium

SRM501   Easy
SRM502   Easy   Medium
SRM503   Easy   Medium
SRM504   Easy   Medium
SRM504.5   Easy
SRM505   Easy
SRM506   Easy
SRM507   Easy  Medium

SRM509   Easy
SRM510   Easy
SRM511   Easy  Medium
SRM512   Easy
SRM513   Easy  Medium
SRM514   Easy
SRM515   Easy
SRM516   Easy
SRM517   Easy
SRM518   Easy  Medium
SRM519   Easy
SRM520   Easy
SRM521   Easy   Medium
SRM522   Easy   Medium/Medium
SRM523   Easy   Medium
SRM524   Easy   Medium
SRM525   Easy   Medium
SRM526   Easy
SRM527   Easy/Easy   Medium
SRM528   Easy   Medium
SRM529   Easy
SRM530   Easy   Medium
SRM531   Easy   Medium
SRM532   Easy   Medium
SRM533   Easy   Medium
SRM534   Easy
SRM535   Easy
SRM536   Easy   Medium
SRM537   Easy   Medium
SRM538   Easy   Medium
SRM539   Easy
SRM540   Easy
SRM541   Easy
SRM542   Easy
SRM543   Easy   Medium
SRM544   Easy   Medium
SRM545   Easy   Medium
SRM546   Easy   Medium
SRM547   Easy   Medium
SRM548   Easy



SRM550   Easy  Medium
SRM551   Easy  Medium


SRM556   Easy
SRM557   Easy  Medium


SRM560   Easy
SRM561   Easy  Medium
SRM562   Easy
SRM563   Easy  Medium
SRM564   Easy  Medium
SRM565   Easy  Medium
SRM566   Easy  Medium
SRM567   Easy  Medium
SRM568   Easy
SRM569   Easy  Medium
SRM570   Easy
SRM571   Easy  Medium
SRM572   Easy  Medium

SRM574   Easy  Medium
SRM575   Easy  Medium
SRM578   Easy  Medium
SRM579   Easy  Medium
SRM580   Easy


SRM582   Easy
SRM583   Easynbsp; Medium




SRM590   Easy

SRM453.5 Div1 Medium

450

SRM453.5 Div1 Easy

250

SRM454 Div1 Medium

500
意外と苦労した。
dp_table[桁数][動かした本数][他の桁へ移った本数]

SRM454 Div1 Easy

250

SRM455 Div1 Easy

ある長方形の領域中の解は、周囲の4辺の1つを切り落としたモノの最大値 or 4辺全てを切り落としたモノ+1