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

hamayanhamayan's blog

競技プログラミング

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 + 消した要素の総和) …

尾根 (Ridge) [第16回日本情報オリンピック 予選(オンライン) E]

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_e 解説 https://atcoder.jp/contests/joi2017yo/submissions/8141535 まず、順当に考えると、座標を全探索して、シミュレーションをして、その座標が尾根であるかを判定する。 どのようにシミュレー…

ポイントカード (Point Card) [第16回日本情報オリンピック 予選(オンライン) B]

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_b 解説 https://atcoder.jp/contests/joi2017yo/submissions/8138857 N≦A[i]であれば、当たりとなり、当たりとなるようにM-1個選んでいく。 どれを当たりカードとすべきか考えたときになるべく、A[i]…

電子レンジ (Microwave) [第16回日本情報オリンピック 予選(オンライン) A]

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_a 解説 https://atcoder.jp/contests/joi2017yo/submissions/8138403 場合分けをする。 Aが凍っている場合は解凍するまでの時間を追加で計算する。 あとは、凍っていないときにかかる時間を追加で計…

Fork in the Road [AtCoder Beginner Contest 144 F]

https://atcoder.jp/contests/abc144/tasks/abc144_f 前提知識 期待値DP 解説 https://atcoder.jp/contests/abc144/submissions/8180528 グラフ全体はDAGになっているので、期待値DPをすることで答えが求まる。 まずは、通路を塞がないパターンを考えてみよ…

ぬいぐるみの整理 (Plush Toys) [第16回日本情報オリンピック 予選(オンライン) D]

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_d 解説 https://atcoder.jp/contests/joi2017yo/submissions/8140685 何から始めようかという感じになるかもしれないが、M≦20というところがまずはヒントになりそうだ。 種類について何かうまくやる…

尾根 (Ridge) [第16回日本情報オリンピック 予選(オンライン) E]

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_e 解説 https://atcoder.jp/contests/joi2017yo/submissions/8141535 まず、順当に考えると、座標を全探索して、シミュレーションをして、その座標が尾根であるかを判定する。 どのようにシミュレー…

ヘビの JOI 君 (Snake JOI) [第16回日本情報オリンピック 予選(オンライン) F]

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_f 解説 https://atcoder.jp/contests/joi2017yo/submissions/8142007 パット見てダイクストラ感はある。 状態を考えると、(どの部屋にいるか, 寒すぎる・暑すぎるのどっちが最後か, 寒すぎる・暑すぎ…

休憩スペース (Refreshment Area) [第16回日本情報オリンピック 予選(オンライン) C]

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_c 解説 https://atcoder.jp/contests/joi2017yo/submissions/8139896 重複なく数えるために、かぶらないような特徴を見つけることが大切である。 今回で言えば、休憩スペースの左上端とする座標につ…

ポイントカード (Point Card) [第16回日本情報オリンピック 予選(オンライン) B]

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_b 解説 https://atcoder.jp/contests/joi2017yo/submissions/8138857 N≦A[i]であれば、当たりとなり、当たりとなるようにM-1個選んでいく。 どれを当たりカードとすべきか考えたときになるべく、A[i]…

電子レンジ (Microwave) [第16回日本情報オリンピック 予選(オンライン) A]

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_a 解説 https://atcoder.jp/contests/joi2017yo/submissions/8138403 場合分けをする。 Aが凍っている場合は解凍するまでの時間を追加で計算する。 あとは、凍っていないときにかかる時間を追加で計…

科目選択 (Selecting Subjects) [第15回日本情報オリンピック 予選(オンライン) A]

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_a 解説 https://atcoder.jp/contests/joi2016yo/submissions/8142856 物理、科学、生物、地学から点数が高いものを3つ選んで総和を取るが、 これは、「(総和)-4つのmin」と実は等しい。 こっちのほう…

Walk on Multiplication Table [AtCoder Beginner Contest 144 C]

https://atcoder.jp/contests/abc144/tasks/abc144_c 解説 https://atcoder.jp/contests/abc144/submissions/8157943 まず、制約を見ると、掛け算表を作るのは現実的ではない。 Nが書かれているマスはどんなマスだろうと考えたときに、ij=Nを満たすマスであ…

Gluttony [AtCoder Beginner Contest 144 E]

https://atcoder.jp/contests/abc144/tasks/abc144_e 前提知識 二分探索 解説 https://atcoder.jp/contests/abc144/submissions/8164566 まず、最大値の最小化ということで二分探索かというところ。 最大値が決まっていれば、各メンバーについて何回修行が必…

Water Bottle [AtCoder Beginner Contest 144 D]

https://atcoder.jp/contests/abc144/tasks/abc144_d 解説 https://atcoder.jp/contests/abc144/submissions/8169237 数学的な問題のようだ。 0°の状態から傾けていくと、水の形は最初長方形だが、台形の柱となり、三角柱となりと遷移する。 三角柱になる前…

81 [AtCoder Beginner Contest 144 B]

https://atcoder.jp/contests/abc144/tasks/abc144_b 解説 https://atcoder.jp/contests/abc144/submissions/8155035 2つの整数の積として表現できるかということなので、その2つの整数を全探索する。 それぞれ9種類なので、全体で81通りなので、間に合う。 …

9x9 [AtCoder Beginner Contest 144 A]

https://atcoder.jp/contests/abc144/tasks/abc144_a 解説 https://atcoder.jp/contests/abc144/submissions/8153919 A,Bのどちらかが10以上なら計算できないので-1 そうでないならできるので、A*Bを答える。 int A, B; //---------------------------------…