2019-02-09から1日間の記事一覧
https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_a 解説 https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/42037511~Nで差が1にならないように選ぶには飛び飛びで選んでいくのがいい。 つまり、N/2の切り上…
https://yukicoder.me/problems/no/789 前提知識 動的構築セグメントツリー 解説 https://yukicoder.me/submissions/315636このクエリは動的構築セグメントツリーで解決できるので持ってる人は貼るのが最速。 持っていない場合は、今回はクエリ先読みできる…
https://yukicoder.me/problems/no/788 前提知識 ダイクストラ 考察過程 1. かなり難しい問題に見えるので、小さいことから紐解いていく 2. M≦2000が気になる(普通なら10^6くらいじゃない?) 3. この制約なら、全ての頂点間の距離を求められる 4. とりあえ…
https://yukicoder.me/problems/no/787 解説 https://yukicoder.me/submissions/315634条件付き確率で解く。 P,Qは÷100して確率にしておく。 答えはP(裏切り|裏切りっぽい)となるので、 P(裏切り|裏切りっぽい) = P(裏切り∩裏切りっぽい) / P(裏切りっぽい) …
https://yukicoder.me/problems/no/786 前提知識 動的計画法(組み合わせ系) 解説 https://yukicoder.me/submissions/315631dpで解く。 dp[i] := i段目に到達するまでの登り方の組み合わせ数 すると、遷移は dp[i + 1] += dp[i] // 1歩で1段 dp[i + 2] += d…
https://yukicoder.me/problems/no/785 解説 https://yukicoder.me/submissions/315630ある色について、使えない文字がn種類あった場合は、使える文字は16-n種類となる。 ある色は2桁で表現されるので、この場合は(16-n)^2通りの表現ができることになる。 答…
https://yukicoder.me/problems/no/784 解説 https://yukicoder.me/submissions/315624数字を文字列として見ると、後ろから3つ毎にカンマを入れる処理となる。 これを実装しよう。 実装を簡単にするために、「与えられる数は文字列として考えて処理」 「反転…