今日の競プロ(2020/4/5) + Judge System Update Test Contest 202004

AtCoder 6問

JOI 4問

ABC161 D - Lunlun Number

問題

これコンテスト中にACできなかったん大反省すぎる。入出力例4から答えは最大でも10桁だとわかるので、10桁以下のルンルン数を全列挙すれば解けます…。

提出

ABC161 E - Yutori

問題

全体から1個取り除くやつは両端からの累積を考える！！！これとか、先週でてきた全方位木DPとか。

提出

JOI2011春合宿 Day 1 - 横断幕 (Banner)

問題

結構悩んでしまった…。長方形の北端、南端の緯度を決め打つ。

提出

またしてもこれ。

$\gcd(...(\gcd(\gcd (X,A_1),A_2),...,A_j)=\gcd(X,\gcd(A_1,A_2,...,A_j))$ なので、累積gcdを事前に計算しておけば $j$ 回目の操作の直後の $X$ の値は爆速で求まる。 $X$ は一度 $1$ になると一生 $1$ のままなので、 $X$ が初めて $1$ になる場所は二分探索で求まる。

提出

JOI2011春合宿 Day 4 - 国際情報オリンピック (IOI)

問題

金メダル確定→残り $N-M$ 問で自分がずっと0点、自分以外がずっと100点を取ったときに金メダルがもらえる人。

金メダルの可能性あり→残り $N-M$ 問で自分がずっと100点、自分以外がずっと0点を取ったときに金メダルがもらえる人。

提出

JOI2012本選 C - 夜店 (Night Market)

問題

時刻 $S$ をまたぐときの遷移に気をつけて、DP。

提出

JOI2013春合宿 Day 1 - JOI ポスター (JOI Poster)

問題

解説AC。

解法自体はとても簡単で、4点の選び方 $O(N^4)$ 通り全てについて条件を満たすか調べる。最初4点が異なるかの判定をsetでサボったらTLEしてしまったので書き直すと、WA。小課題2が誤差で落ちてるらしく、一向にACできないので解説を読むと、実はこの前パナソニックコンで出たやつでした…。整数 $a,b,c$ について、 $\sqrt{a}+\sqrt{b}\lt\sqrt{c}$ ですか？という問いには誤差0で答えることができる！！