https://atcoder.jp/contests/abc145/tasks/abc145_e 解説 https://atcoder.jp/contests/abc145/submissions/8486494 よくあるDPを考えると、 DP[i][t] := i番目までを注文して今までt分経過しているときの満足度の最大値 っぽいが、最後に時間を超えて食べ…

https://atcoder.jp/contests/abc145/tasks/abc145_b 解説 https://atcoder.jp/contests/abc145/submissions/8482706 Nが奇数であれば、同じものが2回繰り返された文字列であることはありえない。 Nが偶数なら、Sを前半と後半に分割して等しいかどうかを判定…

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_c 解説 https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8373471 TLで見つけたスーパーコーナーケース 4 2 1 4 3 1 2 3 4 なるほど、という言葉しか出てこない。 解説に…

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_d 前提知識 セグメントツリーによるDP高速化 解説 https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8371669 本家解答はダイクストラ。 以下、セグメントツリーとDPによ…

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_b 解説 https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8371235 300点問題ではあるが、累乗を使う所があるので、そのライブラリを持っていないと厳しい。 mod上での掛…

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_e 解説 https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8372437 yes/no判定だけでなく、構築結果も出せという問題なので、 単純なルールで構築が出せるのだろうとまず…

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_a 解説 https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8370714 組み合わせを全探索してもいいが、計算だけでも解ける。 N=1+(N-1)=2+(N-2)=...=(N-1)+1 と考えると(N-…

前は傾向と対策とか書いていたけど、かなり無責任な記事だった（しかもちょっと情報も古かった）ので、ただの解説まとめにした。 JOI2020/2021 一次予選(第1回) # 題名 配点 要求（白塗りしてあるので選択で見て） 解説 A 100 余り (Remainder) 実装問題 解…

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_d 解説 https://atcoder.jp/contests/joi2016yo/submissions/8344299 それぞれの制約が大きく、制約から考えていくのは難しそう。 問題の弱点について考えていこう。 立ち止まる条件を考えると→←とな…

https://yukicoder.me/problems/no/921 解説 https://yukicoder.me/submissions/396568 同じ大きさの場合は消えないので全部ずんだ餅にできる。 基本的には、「ず餅ず餅」みたいな感じにすればよさそう。 影響するのは2つ前くらいなので、ちょっと前くらいを…

https://yukicoder.me/problems/no/920 解説 https://yukicoder.me/submissions/396330 XYZの制約が小さいので、個数で全探索できそう。 白色のボールが何個赤色になるかを全探索しよう。 赤にならない白ボールは青にすればいい。 あとは、紫色のボールはmin…

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_b 解説 https://atcoder.jp/contests/joi2016yo/submissions/8343032 操作は複雑だがN,Mのサイズは小さい。 全ての操作回数を考えるとNM回くらいなので、シミュレーションしても間に合う。 シミュレ…

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_e 前提知識 複数始点BFS ダイクストラ 解説 https://atcoder.jp/contests/joi2016yo/submissions/8344819 まずは危険な街を特定しよう。 これはゾンビの街からKステップで到達可能な所であるが、到達…

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_c 解説 https://atcoder.jp/contests/joi2016yo/submissions/8343183 どこから考えようかという話だが、全探索できそうな所が無いか探そう。 ゴールの形はそんなに状態が無い。 上からwhite行が白で…

https://community.topcoder.com/stat?c=problem_statement&pm=15702 N種類のシャツがあり、それぞれshirtValue[i]を持つ。 M種類のジーンズがあり、それぞれjeansValue[i]を持つ。 D種類のペアがあり、(i番目のシャツ, j番目のジーンズ)のようにそれぞれ1種…

https://community.topcoder.com/stat?c=problem_statement&pm=15738 パラメタより生成される3つの数列A,B,Cがある（正式は問題文参照）。 以下の操作のいずれかを何度も行うことができる。 配列A,Bから要素を1つずつ消す。コストは(x + 消した要素の総和) …