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

hamayanhamayan's blog

2021-10-01から1ヶ月間の記事一覧

Happy Wedding! [第八回 アルゴリズム実技検定 K]

https://atcoder.jp/contests/past202109-open/tasks/past202109_k 前提知識 最小費用流 (もしくは重み付き二部グラフ上での最大マッチング) 解説 https://atcoder.jp/contests/past202109-open/submissions/26707534 慣れていると、この問題がかなりフロー…

Reverse Array [第八回 アルゴリズム実技検定 J]

https://atcoder.jp/contests/past202109-open/tasks/past202109_j 前提知識 遅延評価セグメントツリー 解説 https://atcoder.jp/contests/past202109-open/submissions/26703507 遅延評価セグメントツリー以外にも沢山実装方法があるように見える。 今回、…

/2 and *3 [第八回 アルゴリズム実技検定 I]

https://atcoder.jp/contests/past202109-open/tasks/past202109_i 解説 https://atcoder.jp/contests/past202109-open/submissions/26690153 難しい問題。色々方針が思い浮かぶかもしれないが、思いつかないと中々厄介だろうと思う。 本質を見抜く 実は、今…

Shortest Path [第八回 アルゴリズム実技検定 H]

https://atcoder.jp/contests/past202109-open/tasks/past202109_h 前提知識 LCA 解説 https://atcoder.jp/contests/past202109-open/submissions/26687334 今回の問題は制約が割と緩いので、基本的な典型アルゴリズムを理解していると解ける。 愚直に考えて…

K-th element [第八回 アルゴリズム実技検定 G]

https://atcoder.jp/contests/past202109-open/tasks/past202109_g 前提知識 二分探索 解説 https://atcoder.jp/contests/past202109-open/submissions/26603092 この問題は正直典型問題として知っていないと解くのは難しいように思う。 二分探索を利用する…

Incomplete Permutation [第八回 アルゴリズム実技検定 F]

https://atcoder.jp/contests/past202109-open/tasks/past202109_f 構築 解説 https://atcoder.jp/contests/past202109-open/submissions/26602840 構築問題。 構築問題の基本は、シンプルな構築ルールである。 なるべく簡単に簡単に条件を満たせるルールを…

Colorful T-Shirts [第八回 アルゴリズム実技検定 E]

https://atcoder.jp/contests/past202109-open/tasks/past202109_e 解説 https://atcoder.jp/contests/past202109-open/submissions/26602632 貪欲法で解いていく。 かかる値段を最小化したいと考えた場合、簡単な方針として、安いものから選択するという方…

Divisor [第八回 アルゴリズム実技検定 D]

https://atcoder.jp/contests/past202109-open/tasks/past202109_d 前提知識 約数列挙 解説 https://atcoder.jp/contests/past202109-open/submissions/26602449 とある数の約数の個数が計算できれば、あとは判定するだけとなるので、 実質問題視されている…

Number of Apperance [第八回 アルゴリズム実技検定 C]

https://atcoder.jp/contests/past202109-open/tasks/past202109_c 解説 https://atcoder.jp/contests/past202109-open/submissions/26585529 問題で要求されていることを実装する問題。 入力の個数がやや多いので少し気を付ける必要があるかもしれない。 何…

intersection [第八回 アルゴリズム実技検定 B]

https://atcoder.jp/contests/past202109-open/tasks/past202109_b 解説 https://atcoder.jp/contests/past202109-open/submissions/26585385 やや工夫が必要になる問題。 配列A,Bに含まれる数は制約からすべて別々であるということから、 重複とかは考えず…

Bubbler [第八回 アルゴリズム実技検定 A]

https://atcoder.jp/contests/past202109-open/tasks/past202109_a 解説 https://atcoder.jp/contests/past202109-open/submissions/26585144 指定されていることを実装する問題。 取れる選択肢は、 「A + B - C」円(それぞれ頼んで割引する) 「D」円(セ…

箱と鍵 (Boxes and Keys) [JOI 2021/2022 一次予選 (第1回) 過去問 D]

https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_d 解説 https://atcoder.jp/contests/joi2022yo1a/submissions/26486427 宝箱を中心に考えてみよう。 とある宝箱を開錠するためには書かれている番号と同じ番号が書かれた鍵が存在する必要があ…

複雑な文字列 (Complex String) [JOI 2021/2022 一次予選 (第1回) 過去問 C]

https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_c 解説 https://atcoder.jp/contests/joi2022yo1a/submissions/26485238 文字種を数える問題なので、C++であればsetを使うのがオススメ。 setは同じ要素が入った場合でも1つにまとめてくれるの…

移動 (Moving) [JOI 2021/2022 一次予選 (第1回) 過去問 B]

https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_b 解説 https://atcoder.jp/contests/joi2022yo1a/submissions/26485022 A地点からB地点を経由してC地点に移動するにはX+Y時間だけかかる。 判定したいのはZ時間30分以内に移動できるかというこ…

余り (Remainder) [JOI 2021/2022 一次予選 (第1回) 過去問 A]

https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_a 解説 https://atcoder.jp/contests/joi2022yo1a/submissions/26484859 C++では何かで割った余りを計算する場合に%という演算子を使う。 21で割った余りを求めたいなら% 21だし、10で割った余…

Strange Lunchbox [サイシードプログラミングコンテスト2021(AtCoder Beginner Contest 219) D]

https://atcoder.jp/contests/abc219/tasks/abc219_d 前提知識 DP 解説 https://atcoder.jp/contests/abc219/submissions/26483767 あまりピンとこないかもしれないがDPで解ける。 初手でDPが思いついて試すとできたので、DPに至る過程は説明できない… DP dp…

Neo-lexicographic Ordering [サイシードプログラミングコンテスト2021(AtCoder Beginner Contest 219) C]

https://atcoder.jp/contests/abc219/tasks/abc219_c 解説 https://atcoder.jp/contests/abc219/submissions/26483284 実装問題。 C++であれば、特殊なソートは、比較関数を独自に作ることで実装が可能である。 比較関数 2つの文字列が与えられたときに大小…

Red and Blue Tree [エクサウィザーズプログラミングコンテスト2021(AtCoder Beginner Contest 222) E]

https://atcoder.jp/contests/abc222/tasks/abc222_e 解説 https://atcoder.jp/contests/abc222/submissions/26482282 恐らく初見だとかなり難しい問題に見えると思う。 問題を簡単化する 辺の塗り方を求める問題であるが、操作によってとある辺について何回…

Between Two Arrays [エクサウィザーズプログラミングコンテスト2021(AtCoder Beginner Contest 222) D]

https://atcoder.jp/contests/abc222/tasks/abc222_d 前提知識 DP 解説 https://atcoder.jp/contests/abc222/submissions/26480980 問題を眺めるとかなりDPな感じがする。 具体的には mod 998244353 先頭から数を決めていくと広義単調増加は1つ前しか見なく…

Swiss-System Tournament [エクサウィザーズプログラミングコンテスト2021(AtCoder Beginner Contest 222) C]

https://atcoder.jp/contests/abc222/tasks/abc222_c 解説 https://atcoder.jp/contests/abc222/submissions/26480601 シミュレーション問題、実装問題となる。 どういったことを問うているのかについては頑張って読み解いてほしい。 場合によってはサンプル…