https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_b 解説 https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4206062通るパターンを全探索しよう。 4つの街で訪れる可能性のあるパターンは4!通りなので、これ…

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つ毎にカンマを入れる処理となる。 これを実装しよう。 実装を簡単にするために、「与えられる数は文字列として考えて処理」 「反転…

https://atcoder.jp/contests/abc117/tasks/abc117_d 前提知識 桁DP 解説 https://atcoder.jp/contests/abc117/submissions/4166833桁DPをする。 2進数で60桁を想定して解く（10^12なので、もうちょっと小さいが、横着した）。 dp[dgt][isless] := 上位dgtビ…

https://atcoder.jp/contests/abc117/tasks/abc117_c 解説 https://atcoder.jp/contests/abc117/submissions/4162169隣接する点に移動するというのと、ソートできるときは大体したほうがいいので、Xをソートする。 まずは最適行動について考えてみよう。 す…

https://atcoder.jp/contests/abc117/tasks/abc117_b 解説 https://atcoder.jp/contests/abc117/submissions/4160902便利な定理が提示されているので、それをそのまま実装しよう。 Lをソートして、一番長い辺以外の総和と一番長い辺を比べて答えを出そう。 i…

https://atcoder.jp/contests/abc117/tasks/abc117_a 解説 https://atcoder.jp/contests/abc117/submissions/4160726世界A→世界Bで×Xなので、 逆なら/Xとなる。 つまり答えはT/X。 小数なのでdouble型とかで計算しよう。 色々注意点はあるが、 T,Xは小数型に…

https://community.topcoder.com/stat?c=problem_statement&pm=15296体力HPの敵がいる。 自分の初期攻撃力がattackで、攻撃するたびに(初期attack)*level/100だけ増える。 （つまり、増える量は常に固定） 1度だけスペル詠唱が可能で、スペル詠唱後はduratio…

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_d 前提知識 トポロジカルソート 解説 https://atcoder.jp/contests/nikkei2019-qual/submissions/4101570まず、N頂点の木があり、ある頂点uからその子孫vに辺がはられている。 これは全…

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c 前提知識 特殊なソートで最適解を得るテク 解説 https://atcoder.jp/contests/nikkei2019-qual/submissions/4140532正直ソートの理由は分からないんやけど、典型があるので紹介してお…

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_b 解説 https://atcoder.jp/contests/nikkei2019-qual/submissions/4097460各文字毎に操作は独立しているので、別々に考えることができる。 各桁で最小で必要な回数は、全て同じ・1つだ…

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_a 解説 https://atcoder.jp/contests/nikkei2019-qual/submissions/4096706両方を購読している人の最大は、なるべく重ねると実現できるので、min(A,B)となる。 最小は、なるべく離せばい…