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

hamayanhamayan's blog

競技プログラミング

Max Matrix [第二回日本最強プログラマー学生選手権 F]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_f 前提知識 BIT 座標圧縮 解説 https://atcoder.jp/contests/jsc2021/submissions/21832371 クエリ問題に対する取り組み方というのはそれほど多くない。 今回の問題は差分計算をする問題である。 差分計…

Level K Palindrome [第二回日本最強プログラマー学生選手権 E]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_e 解説 https://atcoder.jp/contests/jsc2021/submissions/21831951 実装が爆発して、実装の手直しをあきらめてしまった。 理論を記しておくので参考程度で。 何から手を付けるか 情報量が多く、何から始…

Nowhere P [第二回日本最強プログラマー学生選手権 D]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_d 解説 https://atcoder.jp/contests/jsc2021/submissions/21831261 まず、109+7 modライブラリを持ってない場合はAtCoder Libraryを使おう。 今回の問題はNもPも上限が109(intの最大を狙って良く使われ…

Max GCD 2 [第二回日本最強プログラマー学生選手権 C]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_c 解説 https://atcoder.jp/contests/jsc2021/submissions/21830976 問題で要求されているx,yを全列挙する方針は1010通りを超えてしまうのでこれはできない。 何か別の視点で考えることはできないか。 答…

Xor of Sequences [第二回日本最強プログラマー学生選手権 B]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_b 解説 https://atcoder.jp/contests/jsc2021/submissions/21830500 判定方法は色々あるが、自分の実装では1つのmapに入れて個数を数えることにした。 1つのmapに入れて集計をすると、 0個 -> どちらにも…

Competition [第二回日本最強プログラマー学生選手権 A]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_a 解説 https://atcoder.jp/contests/jsc2021/submissions/21830396 1gあたりの価格が安くなるようにすればいいので、式としては ans / Z < Y / X が満たれればいい。 変形すると、 ans < ZY / X とな…

Unique Color [AtCoder Beginner Contest 198 E]

https://atcoder.jp/contests/abc198/tasks/abc198_e 前提知識 dfs 解説 https://atcoder.jp/contests/abc198/submissions/21691565 競技プログラミングの問題で木を題材とした問題が多く存在する。 どのようにプログラミングするとよいかは人それぞれかと思…

Send More Money [AtCoder Beginner Contest 198 D]

https://atcoder.jp/contests/abc198/tasks/abc198_d 解説 https://atcoder.jp/contests/abc198/submissions/21692252 覆面算のソルバーを普通に作る。 各文字にその数字を割り当てるかを全探索で決めていこう。 各文字にどの数字を割り当てるかということを…

Compass Walking [AtCoder Beginner Contest 198 C]

https://atcoder.jp/contests/abc198/tasks/abc198_c 解説 https://atcoder.jp/contests/abc198/submissions/21692994 小数でよくある誤差に気を付けた実装をしていたらバグり散らかしてしまったが、 そこら辺を全く考えないコードでリライトしたら通った。 …

Palindrome with leading zeros [AtCoder Beginner Contest 198 B]

https://atcoder.jp/contests/abc198/tasks/abc198_b 解説 https://atcoder.jp/contests/abc198/submissions/21693209 回文であることをいかに判定するか 計算量が厳しくなければ数字を文字列にして、コピーしたものをひっくり返して一致するか試すのが簡単…

Div [AtCoder Beginner Contest 198 A]

https://atcoder.jp/contests/abc198/tasks/abc198_a 解説 https://atcoder.jp/contests/abc198/submissions/21693353 本番はサンプルケースと難易度を見てエスパーして解いたが、理屈を再考しておく。 まず、A君とB君のお菓子の個数の和はNになるので、片方…

宝箱 [第四回 アルゴリズム実技検定 O]

https://atcoder.jp/contests/past202010-open/tasks/past202010_o 前提知識 動的計画法 SegTree 解説 https://atcoder.jp/contests/past202010-open/submissions/21475159 色々思案する必要がある問題であるが、必要な知識はセグメントツリーのみである。 …

マス目の穴埋め [第四回 アルゴリズム実技検定 N]

https://atcoder.jp/contests/past202010-open/tasks/past202010_n 前提知識 bitDP 解説 https://atcoder.jp/contests/past202010-open/submissions/21474259 横幅が制限されているのでbitDPで解ける。 bitDP 以下のようなbitDPを作ろう。 dp[y][msk1][msk2]…

筆塗り [第四回 アルゴリズム実技検定 M]

https://atcoder.jp/contests/past202010-open/tasks/past202010_m 前提知識 HL分解 遅延評価セグメントツリー 解説 https://atcoder.jp/contests/past202010-open/submissions/21473312 今回の問題はデータ構造で何とかなるので何とかした。 全然参考になら…

マンションの改築 [第四回 アルゴリズム実技検定 L]

https://atcoder.jp/contests/past202010-open/tasks/past202010_l 解説 https://atcoder.jp/contests/past202010-open/submissions/21473177 難しい問題だが、特殊なアルゴリズムは要求しない。 アルゴリズムをただ適用するのではなく、テクニックを駆使し…

転倒数 [第四回 アルゴリズム実技検定 K]

https://atcoder.jp/contests/past202010-open/tasks/past202010_k 解説 https://atcoder.jp/contests/past202010-open/submissions/21472875 差分計算を頑張ろう。 差分だけを計算することで計算量を抑えてACするという問題が一定数ある。 今回の問題も各ク…

ワープ [第四回 アルゴリズム実技検定 J]

https://atcoder.jp/contests/past202010-open/tasks/past202010_j 前提知識 ダイクストラ 解説 https://atcoder.jp/contests/past202010-open/submissions/21472629 ダイクストラをするが、特殊なグラフ形成をする必要がある。 ダイクストラをよく知らずに…

ピザ [第四回 アルゴリズム実技検定 I]

https://atcoder.jp/contests/past202010-open/tasks/past202010_i 前提知識 累積和 三分探索 解説 https://atcoder.jp/contests/past202010-open/submissions/21472485 様々な実装方法がある。 多分尺取り法でも解けるが、自分は三分探索を利用した。 何を…

マス目のカット [第四回 アルゴリズム実技検定 H]

https://atcoder.jp/contests/past202010-open/tasks/past202010_h 前提知識 二次元累積和 解説 https://atcoder.jp/contests/past202010-open/submissions/21472353 根性実装する問題。 制約が小さいので、前提知識として挙げている二次元累積和を使わなく…

村整備 [第四回 アルゴリズム実技検定 G]

https://atcoder.jp/contests/past202010-open/tasks/past202010_g 前提知識 UnionFind 解説 https://atcoder.jp/contests/past202010-open/submissions/21472171 実装問題であるが、一部アルゴリズムを知っていることで実装が楽になる部分がある。 今回の問…

構文解析 [第四回 アルゴリズム実技検定 F]

https://atcoder.jp/contests/past202010-open/tasks/past202010_f 解説 https://atcoder.jp/contests/past202010-open/submissions/21472068 実装問題。問題で要求されていることを頑張って実装しよう。 以下に示すのは実装例であり、各々が好き好きに実装…

アナグラム [第四回 アルゴリズム実技検定 E]

https://atcoder.jp/contests/past202010-open/tasks/past202010_e 解説 https://atcoder.jp/contests/past202010-open/submissions/21471881 この問題で一際目立つ特徴といえばNの最大値が5である。 極端に制約が小さいので全探索をまずは疑おう。 何を全探…

分身 [第四回 アルゴリズム実技検定 D]

https://atcoder.jp/contests/past202010-open/tasks/past202010_d 前提知識 (あったらいいレベルだが)imos法 解説 https://atcoder.jp/contests/past202010-open/submissions/21467860 慣れていないと問題を見たときに面食らうと思うが、1つずつ問題を解…

隣接カウント [第四回 アルゴリズム実技検定 C]

https://atcoder.jp/contests/past202010-open/tasks/past202010_c 解説 https://atcoder.jp/contests/past202010-open/submissions/21465859 シミュレーション問題というか実装問題。 問題文に書かれていることを実装しよう。 今回要求されているような周囲…

電卓 [第四回 アルゴリズム実技検定 B]

https://atcoder.jp/contests/past202010-open/tasks/past202010_b 解説 https://atcoder.jp/contests/past202010-open/submissions/21465680 まず、Y=0の時はゼロ除算となるので、指定のERRORを出して答えよう。 競プロの問題ではこのようなコーナーケース…

中央値 [第四回 アルゴリズム実技検定 A]

https://atcoder.jp/contests/past202010-open/tasks/past202010_a 解説 https://atcoder.jp/contests/past202010-open/submissions/21465476 ABCの数の比較をして中央値となるのが"A","B","C"のどれであるかを答える問題。 数を答えるならソートして中央値…

Traveler [AtCoder Beginner Contest 197(Sponsored by Panasonic) E]

https://atcoder.jp/contests/abc197/tasks/abc197_e 解説 https://atcoder.jp/contests/abc197/submissions/21324848 貪欲法で解く。 回収順 ボールは色が広義単調増加となるように回収する必要があるので、 同じ色のボールについては回収順番はどうなるか…

Opposite [AtCoder Beginner Contest 197(Sponsored by Panasonic) D]

https://atcoder.jp/contests/abc197/tasks/abc197_d 前提知識 幾何 解説 https://atcoder.jp/contests/abc197/submissions/21324773 幾何問題ではあるが、幾何ライブラリが無くてもギリギリ解けるラインをABCで狙ってきた感じがしますね… 幾何的な考察 これ…

ORXOR [AtCoder Beginner Contest 197(Sponsored by Panasonic) C]

https://atcoder.jp/contests/abc197/tasks/abc197_c 解説 https://atcoder.jp/contests/abc197/submissions/21324728 全探索できそうか? まず、分割方法の全てを全探索して、その最小値が取れないかを考えてみる。 分割の方法は、分割する箇所が数列Aの要…

Visibility [AtCoder Beginner Contest 197(Sponsored by Panasonic) B]

https://atcoder.jp/contests/abc197/tasks/abc197_b 解説 https://atcoder.jp/contests/abc197/submissions/21324614 宗教上の理由により、縦は長さHで変数yを、横は長さWで変数xを使うと決めているので、 それに従って問題の解釈を変えている。 つまり、X…