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

hamayanhamayan's blog

競技プログラミング

Can Can Mart [第六回 アルゴリズム実技検定 H]

https://atcoder.jp/contests/past202104-open/tasks/past202104_h 解説 https://atcoder.jp/contests/past202104-open/submissions/22654243 缶切りが必要なものと必要でないものを分けて考えよう。 すると、それぞれから最適に缶を選択してくることを考え…

One Step at a Time [第六回 アルゴリズム実技検定 G]

https://atcoder.jp/contests/past202104-open/tasks/past202104_g 解説 https://atcoder.jp/contests/past202104-open/submissions/22652811 何から始めようかという感じであるが、愚直なやり方から考えてみる。 愚直に探索できないか 操作を行っていく上で…

Safety System [第六回 アルゴリズム実技検定 F]

https://atcoder.jp/contests/past202104-open/tasks/past202104_f 解説 https://atcoder.jp/contests/past202104-open/submissions/22645973 問題文で要求されている仕様も難しいが、ちゃんと読み解ければ実装はそれほど難しくない。 foreverとなる場合 自…

Third from Front [第六回 アルゴリズム実技検定 E]

https://atcoder.jp/contests/past202104-open/tasks/past202104_e 解説 https://atcoder.jp/contests/past202104-open/submissions/22645719 高度実装問題である。 配列では任意箇所の要素を削除することは時間がかかる。 先頭123個目、末尾123個目が操作さ…

K Integers Summations [第六回 アルゴリズム実技検定 D]

https://atcoder.jp/contests/past202104-open/tasks/past202104_d 前提知識 累積和 解説 https://atcoder.jp/contests/past202104-open/submissions/22645520 ここから点数があがり、単なる実装問題ではなくなってくる。 計算量を意識していこう。 愚直解法…

Buying a Cellphone [第六回 アルゴリズム実技検定 C]

https://atcoder.jp/contests/past202104-open/tasks/past202104_c 解説 https://atcoder.jp/contests/past202104-open/submissions/22645364 たくさんの入力が与えられて、要求仕様を満たす実装ができるかを問う問題。 どんな実装をしても計算量が超えてし…

PASTal Code [第六回 アルゴリズム実技検定 B]

https://atcoder.jp/contests/past202104-open/tasks/past202104_b 解説 https://atcoder.jp/contests/past202104-open/submissions/22645258 文字列をマッチングしてくる実装問題となっている。 連結される文字列はどちらであっても4文字なので、文字長をN…

POSTal Code [第六回 アルゴリズム実技検定 A]

https://atcoder.jp/contests/past202104-open/tasks/past202104_a 解説 https://atcoder.jp/contests/past202104-open/submissions/22645201 実装問題。 ループ(必須ではないか)と文字列が扱えれば解ける問題。 数字の判定に戸惑うかもしれない。 C++では…

Xor Distances [マイナビプログラミングコンテスト2021(AtCoder Beginner Contest 201) E]

https://atcoder.jp/contests/abc201/tasks/abc201_e 前提知識 (XOR関連知識) 解説 https://atcoder.jp/contests/abc201/submissions/22639728 まず、方針を色々考えていく上でビット毎に処理していくという発想を出すところがまず難しい。 ビット毎に処理?…

Game in Momotetsu World [マイナビプログラミングコンテスト2021(AtCoder Beginner Contest 201) D]

https://atcoder.jp/contests/abc201/tasks/abc201_d 前提知識 ミニマックス法 解説 https://atcoder.jp/contests/abc201/submissions/22636331 今回のゲーム問題はミニマックス法を知らないとだいぶ解くのが厳しい。 DPといえばDPではあるが、このやり方をD…

Secret Number [マイナビプログラミングコンテスト2021(AtCoder Beginner Contest 201) C]

https://atcoder.jp/contests/abc201/tasks/abc201_c 解説 https://atcoder.jp/contests/abc201/submissions/22640379 根性計算、根性場合分けをする問題。 最近あんまり見ていなかったが、今回のように丁寧に場合分けをして解いていくような問題もある。 o…

Do you know the second highest mountain? [マイナビプログラミングコンテスト2021(AtCoder Beginner Contest 201) B]

https://atcoder.jp/contests/abc201/tasks/abc201_b 解説 https://atcoder.jp/contests/abc201/submissions/22640502 C++だとpairでソートするのがいい。 pairでソートした場合は、第一要素でまずはソートして、同値であれば、第二要素でソートするようなソ…

Tiny Arithmetic Sequence [マイナビプログラミングコンテスト2021(AtCoder Beginner Contest 201) A]

https://atcoder.jp/contests/abc201/tasks/abc201_a 解説 https://atcoder.jp/contests/abc201/submissions/22640618 並び替えを全探索して、等差数列であるかを判定してもいい。 そっちの方が実装簡単だったかも。 条件を改めてみてみると、 A[3] - A[2] =…

自分のテンプレについて

解説を見るうえで、テンプレが無いと理解できない部分を補うページ。 テンプレは必須ではないし、かの旅人はテンプレを持っていないので、ここら辺は好き好きという感じ。 #include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:</b;i++)></bits/stdc++.h>…

Patisserie ABC 2 [京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200) E]

https://atcoder.jp/contests/abc200/tasks/abc200_e 解説 https://atcoder.jp/contests/abc200/submissions/22441425 今回の問題は辞書順でK番目のものを答えよという問題と同様の解き方で解いていく。 辞書順でK番目のものを答えよという問題の場合は [A..…

Happy Birthday! 2 [京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200) D]

https://atcoder.jp/contests/abc200/tasks/abc200_d 解説 https://atcoder.jp/contests/abc200/submissions/22441528 DPして経路復元する。 (公式解説は鳩ノ巣原理です…なるほど…) DP DPについては組合せDPが分かっていれば中身はそれほど難しくない。 dp…

Ringo's Favorite Numbers 2 [京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200) C]

https://atcoder.jp/contests/abc200/tasks/abc200_c 解説 https://atcoder.jp/contests/abc200/submissions/22436968 これは類題を解いたことがないと最初の発想が難しいかもしれない。 i,jの全列挙はN2通りくらいになるので、1010でこれは間に合わない。 …

200th ABC-200 [京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200)B]

https://atcoder.jp/contests/abc200/tasks/abc200_b 解説 https://atcoder.jp/contests/abc200/submissions/22435193 問題では一部文字列として計算しているが、普通に数値計算できるので、数値計算としてやっていくのがオススメ。 ちなみに、文字列を経由…

Century [京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200)A]

https://atcoder.jp/contests/abc200/tasks/abc200_a 解説 https://atcoder.jp/contests/abc200/submissions/22433894 上手く計算できるように変換していく。 1-100: 1 101-200: 2 201-300: 3 +99してみる 100-199: 1 200-299: 2 300-399: 3 これで100で割っ…

Notification [第五回 アルゴリズム実技検定 O]

https://atcoder.jp/contests/past202012-open/tasks/past202012_o 前提知識 平方分割 解説 https://atcoder.jp/contests/past202012-open/submissions/22306825 平方分割ではないかもしれないが、雰囲気は似ているのでとりあえず入れておく。 かなりテクニ…

Travel Agency [第五回 アルゴリズム実技検定 N]

https://atcoder.jp/contests/past202012-open/tasks/past202012_n 解説 https://atcoder.jp/contests/past202012-open/submissions/22304844 クエリ先読みをして解く。 特定のクエリ問題では、クエリを一度にまとめて計算することで計算量の改善を図るもの…

Shipping Sticks [第五回 アルゴリズム実技検定 M]

https://atcoder.jp/contests/past202012-open/tasks/past202012_m 前提知識 セグメントツリーを利用したdp高速化 二分探索 累積和 解説 https://atcoder.jp/contests/past202012-open/submissions/22299599 複合的な問題。 しかも、二分探索+セグメントツリ…

Collecting T [第五回 アルゴリズム実技検定 L]

https://atcoder.jp/contests/past202012-open/tasks/past202012_l 前提知識 区間DP 解説 https://atcoder.jp/contests/past202012-open/submissions/22298486 区間DPで解くことができる。 なぜ区間DP感があるかというと、削除できる領域を考えてみると、ど…

Pitching [第五回 アルゴリズム実技検定 K]

https://atcoder.jp/contests/past202012-open/tasks/past202012_k 前提知識 bitDP 期待値DP 解説 https://atcoder.jp/contests/past202012-open/submissions/22325031 考え始めが難しい問題。 ここがまず重要であるが、全体の状態を考えると216通りしかない…

Long Long String [第五回 アルゴリズム実技検定 J]

https://atcoder.jp/contests/past202012-open/tasks/past202012_j 解説 https://atcoder.jp/contests/past202012-open/submissions/22292068 このような問題を初見で解くのはかなり難しい。 今回の問題で重要なのが「やや再帰的な構造を持っている」という…

Evacuation Plan [第五回 アルゴリズム実技検定 I]

https://atcoder.jp/contests/past202012-open/tasks/past202012_i 前提知識 bfs 解説 https://atcoder.jp/contests/past202012-open/submissions/22291597 標高が設定されているが、計算途中に変化したりはしないので、水路と標高を合わせて 有向グラフと考…

Conveyor [第五回 アルゴリズム実技検定 H]

https://atcoder.jp/contests/past202012-open/tasks/past202012_h 前提知識 bfs 解説 https://atcoder.jp/contests/past202012-open/submissions/22291073 今回の問題は到達性判定問題といえる。 この手の問題はbfsでの解法が有名であり、今回もbfsで解けな…

Snake [第五回 アルゴリズム実技検定 G]

https://atcoder.jp/contests/past202012-open/tasks/past202012_g 解説 https://atcoder.jp/contests/past202012-open/submissions/22290363 一筆書きを探す問題。 制約がかなり小さいので全探索で一筆書きを探すことができる。 制約の小ささから全探索は思…

Dangerous Chemicals [第五回 アルゴリズム実技検定 F]

https://atcoder.jp/contests/past202012-open/tasks/past202012_f 解説 https://atcoder.jp/contests/past202012-open/submissions/22284174 制約を見ると、薬品の混ぜ方が全探索できることが分かる。 これは薬品の混ぜ方は214通りであるためである。 ビッ…

Stamp [第五回 アルゴリズム実技検定 E]

https://atcoder.jp/contests/past202012-open/tasks/past202012_e 解説 https://atcoder.jp/contests/past202012-open/submissions/22282335 実装問題。 要求されていることがかなり複雑なので、適度にモジュール化しないと混乱するかもしれない。 特に目立…