はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミング

DDCC Finals [DISCO Presents Discovery Channel Code Contest 2020 Qual A]

https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_a 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8586587 賞金額の合計を求めよう。 1位、2位、3位の賞金を入れておき、どっちも1位なら追加で40万与える。 int X, Y; //----…

Tahoiya ga Tokuiya [TSG LIVE! 4 プログラミングコンテスト E]

https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-tahoiya-ga-tokuiya/problem 前提知識 動的計画法 解説 https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-pr…

LCM Interval [TSG LIVE! 4 プログラミングコンテスト F]

https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-lcm-interval 前提知識 Disjoint Sparse Table 想定解はSliding Window Aggregationだが、本解法では使ってない 解法 https://www.hackerrank.com/contes…

Constructable [TSG LIVE! 4 プログラミングコンテスト C]

https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-constructable 嘘解法かも https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-constructable/submissi…

Three Sushi Game [TSG LIVE! 4 プログラミングコンテスト B]

https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-three-sushi-game 解説 www.hackerrank.com 寿さんは自由に手を決めることができるので、毎回最適な手を出せばいい。 サンプルには丁寧にも全てのパター…

Live Performers [TSG LIVE! 4 プログラミングコンテスト A]

https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-live-performer 解法 https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-live-performer/submissions/…

よくあるボールを移動するやつ [yukicoder 929]

https://yukicoder.me/problems/no/929 解説 https://yukicoder.me/submissions/400103 なんとなく貪欲でやれば良さそうな気がする。 先頭からなければ前から持ってくるか、後ろから持ってくるかすればいい。 これはボールに最初にある場所の添字を付けて、…

軽減税率? [yukicoder 928]

https://yukicoder.me/problems/no/928 解説 https://yukicoder.me/submissions/399903 不等式にして条件を満たすラーメンを考えてみる。 floor( (1+P/100)x ) < floor( (1+Q/100)x ) + A floorは切り捨ての関数である。 両辺のfloorについてなんとかするの…

Second Permutation [yukicoder 927]

https://yukicoder.me/problems/no/927 解説 https://yukicoder.me/submissions/399615 2番目に大きいものとあるが、最も大きいものを考えてみる。 与えられた文字を降順で並べると、最大の数が得られる。 サンプル1にもあるように、最大の321の下2桁をスワ…

休日の平均 [yukicoder 926]

https://yukicoder.me/problems/no/926 解説 https://yukicoder.me/submissions/399496 最後の「一週間の内の休日の位置が変わった場合でも平均の休日数は変わらないことが証明できます。」が あるおかげで簡単に解けそうだ。 一週間の先頭C日間が休日として…

Average Length [AtCoder Beginner Contest 145 C]

https://atcoder.jp/contests/abc145/tasks/abc145_c 解説 https://atcoder.jp/contests/abc145/submissions/8483703 まず、Nが非常に小さい。 経路は全部でN!通りあるが、最大でも40320通りなので、これは全探索ができる。 C++だとnext_permutationを使うと…

Circle [AtCoder Beginner Contest 145 A]

https://atcoder.jp/contests/abc145/tasks/abc145_a 解説 https://atcoder.jp/contests/abc145/submissions/8482353 円の面積の公式はπr2なので、半径がr倍されれば、面積はr2倍となる。 よって、r2が答え。 int R; //------------------------------------…

Knight [AtCoder Beginner Contest 145 D]

https://atcoder.jp/contests/abc145/tasks/abc145_d 前提知識 二項係数 mod 素数を高速に計算する方法 解説 https://atcoder.jp/contests/abc145/submissions/8484697 400点にしては問題が難しい感じがする。 何か全探索対象を探そう。 まず、(+1,+2)か(+2,…

Laminate [AtCoder Beginner Contest 145 F]

https://atcoder.jp/contests/abc145/tasks/abc145_f 必要知識 座標圧縮 動的計画法 解説 https://atcoder.jp/contests/abc145/submissions/8491333 必要な知見として高さを操作するが、最初に与えられているHiの高さにするか0にするかしかない。 中途半端な…

All-you-can-eat [AtCoder Beginner Contest 145 E]

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

Echo [AtCoder Beginner Contest 145 B]

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

Swaps [NIKKEI Programming Contest 2019-2 C]

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 なるほど、という言葉しか出てこない。 解説に…

Sum of Two Integers [NIKKEI Programming Contest 2019-2 A]

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-…

Non-triangular Triplets [NIKKEI Programming Contest 2019-2 E]

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

Counting of Trees [NIKKEI Programming Contest 2019-2 B]

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

Shortest Path on a Line [NIKKEI Programming Contest 2019-2 D]

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

日本情報オリンピック 予選の傾向と対策

自分は日本情報オリンピック出たこと無いし、運営という訳でもないので、参考程度にご覧ください。 はじめに 概要と特徴 JOI: 日本情報オリンピック 一人で実施する 6問あり、全部100点満点であるが、部分点がある問題が多い 部分点の付け方もJOI2017/2018を…

JOI国のお散歩事情 (Walking in JOI Kingdom) [第15回日本情報オリンピック 予選(オンライン) D]

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

あかあお [yukicoder 920]

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

ずんだアロー [yukicoder 921]

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

ロシアの旗 (Russian Flag) [第15回日本情報オリンピック 予選(オンライン) C]

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

ゾンビ島 (Zombie Island) [第15回日本情報オリンピック 予選(オンライン) E]

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

ゼッケンの交換 (Swapping Bibs) [第15回日本情報オリンピック 予選(オンライン) B]

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

ShoppingSpree [SRM 770 Div1 Med]

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

DeleteArrays [SRM 770 Div1 Easy / Div2 Hard]

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