AtCoder Beginner Contest 139 - gratan’s diary

予定あって出れなかったやつやりました。

結果は70分5完で500位くらいでした。嘘解法だったのもあってちょっとつらみ

やるだけ。初心者的に文字列操作結構しんどいイメージあります。

問題文がわけわからんやつでした。

サンプルエスパーすると(b-1+a-1-1)/(a-1)で解けます

問題：高さが以下だったら右に移動できる。好きなマスからはじめて最長の移動回数を求めよ

考察：

右側から見ます。単調非減少な部分列を求めればよいです。

問題：ある順列について、順列のindex%整数の合計を最大化せよ

考察：

1つずらすことが最適です。

なぜかというと、整数ｉに対して%=ｉ－１になるとうれしいです。

もともとの和が一定から動かないことから、商が増える分目的関数値が減るため、ギリギリが良いです。

したがって2 3 4…n 1という順列が最適です。

ここでｰ2n+1より負の効用を減らすことはできません。

なぜならn番目をなににしてもx-1より大きくならず、xがあった箇所ではx-1以下になるためです。

問題：ｎ人の選手に対戦相手の順序が決まっている。1人の選手は1日に1試合しかできない場合、最短で全ての試合を完了する日数を求めよ

考察：

前から貪欲にやって、ケースが大きいときは最大の値を出したら通りました。ガバガバ。

トポロジカルソートをすればよさそうです。

ただし、1日にどこまでの試合がこなせるかを探しながら順序付けするのは難しそうです。

したがってボトムアップに決めていけばよいです。

dfsなどで実現可能です。

問題：ベクトルがｎ個ある。好きなものを選んだとき大きさを最大化せよ

考察：

最適に選んだ時、なす角はpai以下になるらしいです。

内積を考えるとわかりやすいです。

したがってあるベクトルから+paiまでを足すことをすべてでやればよいです。

角度でソートすればO(N^2)で解くことができます。