引退

いろいろあった結果、競プロ引退です

ブログ見に来るような人には一応報告しておこうかなと

拡散はしないでいてくれると嬉しいかな？

現状

AtCoder→消した

Codeforces→消し方がわからない

TopCoder→Tシャツが届き次第消す

AOJ 2178 - Problem D: Futon

問題リンク

解説

2色で同じ色に塗る場所と異なる色で塗る場所が指定されるので、それを満たすように塗ることができるかという問題です。

noshi91.hatenablog.com

そうすると、これとほぼ同じやり方で解くことができました。

実装も楽だね

提出コード

onlinejudge.u-aizu.ac.jp

Codeforces Round #514 (Div. 2) - D. Nature Reserve

問題リンク

解説

半径r$r$に明らかに単調性があるので二分探索します。

以下、半径をr$r$とします。この時、円の方程式は中心を(c,r)$(c,r)$とすると、

(x−c)2+(y−r)2=r2$(x-c{)}^2+(y-r{)}^2=r^2$

になります。

ある点(xi,yi)$(x_i,y_i)$が円の内部にある条件は、

(xi−c)2+(yi−r)2≤r2$(x_i-c{)}^2+(y_i-r{)}^2\le r^2$

xi−r2−(yi−r)2−−−−−−−−−−−√≤c≤xi+r2−(yi−r)2−−−−−−−−−−−√$x_i-\sqrt{r^2-(y_i-r{)}^2}\le c\le x_i+\sqrt{r^2-(y_i-r{)}^2}$

となります。

よって、全てのn$n$の区間を含むようなc$c$が存在するかを調べると二部探索ができるので、計算量はO(nlogn)$O(n\log n)$でできました

提出コード

codeforces.com

コンテスト中に激冷え！？が確定したときに、レートを上昇させる秘儀

7Hackする

AtCoder黄色になった

そういや書くの忘れてた

なれたらしい

3691ACです。

SoundHound Programming Contest 2018 Masters Tournament 本戦 - B - Neutralize

問題リンク

かなり典型だと思うのですが、詰まってる人が多かったので

解説

dp[i] := i$i$番目まで見た時の最大値としましょう。

i$i$番目を取るときは、

dp[i]←max(dp[i],dp[i−1]+b[i])$dp[i]\leftarrow max(dp[i],dp[i-1]+b[i])$

です。取らないときはi$i$番目からK$K$個以上を消すことができるので、

dp[i]←max(dp[i],dp[j])  (0≤j≤i−K)$dp[i]\leftarrow max(dp[i],dp[j])(0\le j\le i-K)$

です。よってi$i$番目までのdpの最大値を管理しながらやれば、遷移はO(1)$O(1)$で求まるのでO(n)$O(n)$で求めることができました。

提出コード

atcoder.jp

Codeforces Round #664 (Div. 1) - B. Boboniu Walks on Graph

問題リンク

解説

c$c$の組み合わせとして全て考えられるものを全探索します。

今回のグラフは出次数が全部1でかつ、全ての頂点でループを作らないといけないことから、入次数も全て1でないといけません。

もう少し突っ込むと入次数が2以上のが1つでも存在するとダメです。

よって、任意のci,cj$c_i,c_j$の全てのペア(O(k4)$O(k^4)$)を調べて、2以上の入次数が1つ以上あるかを予め前計算しておきます。

あとは全てのc$c$の組み合わせでそのようなペアがあるかどうかをチェックします。

提出コード

codeforces.com