問題ページ Problem - C - Codeforces 考えたこと 色々数字をいじっていたらそれっぽい解法が思いついて投げたら通った。 gcdを求めたあと素因数分解をしたくなったが、a、bが大きな素数のときに計算時間が怖かったのでこの方針は捨てた。 立法数判定だけな…

問題ページ Problem - B - Codeforces 解法 各文字について最初に現れるタイミングと最後に現れるタイミングを調べてimosする。

問題ページ 解法 操作には周期4の周期性があるので周期性を使って判定する。

問題ページ F - Namori Grundy 解法 0以上a[i]未満の整数xが頂点iから辺が伸びている頂点jの値a[j]として全て使われているようなa[i]の決め方をする。 すなわち、a[i]から辺が伸びている頂点jの値として使われていない最も小さい値がa[i]の値となる。サイク…

問題ページ E - Decrease (Judge ver.) 解法 a[i]がn以上であればn未満になるように引き、数列の他の要素に適切な値を加えることを繰り返した。 最初からn未満になるように操作すると途中で遷移がバグってるところがあったので一回 7*n 未満になるように操作…

問題ページ D - Decrease (Contestant ver.) 解法 n=50で考える。 k=0のとき 49 49 49 … 49 とする。 k=1のときは1回操作してこの数列になればよいので 99 48 48 … 48 k=2でも同様に 98 98 47 47 … 47 これを繰り返していくと、 k = 50 で 50 50 50 … 50 k =…

問題ページ C - Cat Snuke and a Voyage dijkstraで殴った

F-見える数 読解が難しかったけど質問を見たらわかった。a[i]以前の最大の数がa[i]より小さければそのa[i]は見える。なので最大の数を保持して全てのa[i]を見ればできる。 G-あまり 10のa[i]の長さ乗を掛けたあとa[i]を足すを繰り返す。MODの取り忘れに注意…

dwacon2017-prelims.contest.atcoder.jpnnのときについて考える。 i番目までの寿司を食べるとすると、i番目をネタだけ食べ、1からi-1番目の中でネタだけ食べた時の幸福度の上昇が大きいものm-1個を選ぶのが最適な食べ方となる。そこで、i番目までの寿司でネ…

Hamako Online Judge区間と言われたので累積和を取りたくなる。累積和をSで書くことにするとl番目の要素を区間の左端とするとき P+S[l-1] 以上のもっとも右にある要素の位置が分かればl番目が区間の左端のときの最適な区間が求まる。右端がO(1)かO(logn)くら…