Codeforces Round #38 - simezi

ICPCルール。
Out of competitionなんだけどレートは変動するらしい……よく意味がわからない。

76位 5AC 00:02 / 00:15 / 00:25 / 01:29(5WA) / 00:49 / - / - / -
1712 -> 1803

4時間8問セット！？
21時スタートで4時間は来週に疲れ残りそうだから途中で寝よう。

階級iからにi+1に昇級するにはd[i]年の時間が必要である。
階級aからbまで昇級するのにかかる時間を求めよ。

うお、Codeforcesなのに異様に簡単だ……

書いた。送信。AC.
最近Codeforces Formatばかりだったからその場で結果が出るICPCルールがなつかしい；ｗ；

8x8のチェス板にルークとナイトが互いに利かない位置にある。
ここに3つ目の駒としてナイトを、3駒のうちどの2つも互いに利かないかつ他の駒のない位置に置く。
そのような場所として可能なのはいくつか。

えーと、ナイトを3つ置く？（←誤読
書くだけだな。書いた。サンプル合わない。

んー？最初に置く駒はルークかよ！
ルークを2つ置いてナイト置くんだな（←誤読
書いた。合わない。なんでだよ！！！

おいルークとナイト置くんじゃないか！
ダメだこりゃ。
書いた。送信。AC.

n本の幅1長さa[i]の長方形がある。
この棒は縦に好きなだけ切ることができる。切って、長さl以上の同じ長さの棒を作る。
できた棒の本数をk,長さをdとするとk*dの最大値はいくつか。
棒は全く切らなくてもよく、棒同士をつなげることはできない。

問題文の読解でまたも手間取る。
ICPCルールだからだからか知らないけどどうも今回の問題文には難しい単語が多い……

読めば言ってることは簡単。
l≦100なので単にループをまわして棒を切り出して最大値を求めるだけだった。
書いた。提出。AC.

なんか幾何っぽいので飛ばす。

数直線状に点x1,x2,...,xnがある。
この点はそれぞれコストc1,c2,...,cnでピン止めすることができる。
ピン止めしなかった点は左へ転がり、他のピンで止めた点にぶつかるまで動く。

これに大して次の二つの値の合計を考える。

この最小値を求めよ。
n≦3000を満たす。

DP？ある一点をピンで止めると、ピンより左は、ピンより右の状態の影響は受けないからDPぽい。

何をテーブルにするんだろう。
dp[i][j]でi番目とj番目をピンで止めた時のコスト？
いや違う、dp[i]にi番目をピンで止めた時のコストを入れればいいんだ。
で、dp[i]=min{dp[j]+cost[i][j]}の漸化式でテーブルを更新する。

cost[i][j]は事前にO(n^2)計算できるので、全体の計算時間はO(n^2).
でけた。dpはlonglongにしないとダメだね。かきかき。
サンプル合った。送信。AC.

Dにもどる。

立方体を積み上げて塔を作る。

立方体は座標軸に辺が平行になるように置き、かつそれぞれのx座標,y座標は初めから与えられている。
立方体を与えられた順番に、崩さず何個まで積み上げられるかを求めよ。

これも問題が把握しにくい……
i番目が積める⇔1＜j≦iなる各jについて、j,j+1,..,iの重心がj-1番目の上面の内部に入っている
なので、愚直にやってO(n^3).立方体は100個までだから間に合う。

最初立方体を直方体だと思っていて、高さが与えられてないけど1でいいのか？
とかわけのわからないことをして1WA.
誤差死したのだと思ってEPSを付け加えて1WA.
もしかして直方体を1,2,3,4...と積むのではなく、n-1,n-2,...と積むのではないかと思い直してみて1WA.

与えられる座標ってx1,x2の大小関係与えられてないことに気づいて修正。しかし直方体のままでやってるので1WA.
立方体だということに気づいて修正。しかしn-1,n-2,...と積むに変更したままだったので更に1WA.
積む順番を元に戻してようやくAC.

この辺で疲れたので就寝。
現在順位55位くらいなので、終了時まで放置しても100位には入るだろうと思ったら予想通り。