読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

Codeforces Round #162 (Div. 2) ○○××-

2回目の参加。1479->1606、青色になれました
ABは正解でCは不正解、Dは時間切れ。
+15/-2 hack できたので個人的には満足。

A問題

やるだけ。

B問題

最初の入力の値 + 入力列の差の絶対値の総和 + 2 * 入力の長さ - 1を返せば良い

C問題

ある範囲にリスがいて、入力文字列に従ってそれが左半分か右半分に移動する(どんどん範囲は狭くなる)。
このときリスがi番目の入力でいた位置に対して、座標の左から順番に番号iを出力する

リストなどを使うのが正解っぽい。
リストなどを適切に使えば、たぶんO(n)

座標を直接使って計算して最後にソートしている人が多かったので、左半分への移動だけの文字列を与えたら、値が2^{10^6}で割られてしまい、途中からすべて0になって落とせる人が多かった。
また最長の入力を投げるとTLEになる人がいた。

値が0になる対策として値を対数にしていて解けたと思ったのですが、何故か不正解orz
一番重いのがソートなのでO(n \log n)だから時間的には大丈夫なはずだったんですが、反例があるのか実装に問題があったのか……。

D問題

隣り合う数字が互いに素でないものだけを使った最長増加部分列の長さを求める。
O(n^2)の解を提出。
入力の長さが10^5だから、おそらくTLEなのがわかっていたので、すぐにロックして他人のコードをhackしていた。

-->