第八回 アルゴリズム実技検定 # 配点 題名 要求（白塗りしてあるので選択で見て） 解説 A 9 Bubbler 実装問題 解説 B 8 intersection 実装問題 解説 C 8 Number of Apperance 実装問題 解説 D 7 Divisor 約数列挙 解説 E 7 Colorful T-Shirts 貪欲法 解説 F …

https://atcoder.jp/contests/past202004-open/tasks/past202004_o 前提知識 最小全域木 解説 https://atcoder.jp/contests/past202004-open/submissions/12901968 どこから手を付けようか。 最小全域木を作る問題なので、既存の最小全域木アルゴリズムから…

https://atcoder.jp/contests/past202004-open/tasks/past202004_n 前提知識 二次元imos 座標圧縮 2Dセグメントツリーか平面走査 解説 https://atcoder.jp/contests/past202004-open/submissions/12901572 二次元imosを拡張させて解く。 二次元imosが分から…

https://atcoder.jp/contests/past202004-open/tasks/past202004_m 解説 https://atcoder.jp/contests/past202004-open/submissions/12901167 問題をパッとみて、実装を頑張るような印象を受ける。 実際、実装を頑張るような問題は一定数あり、問題は「実装…

https://atcoder.jp/contests/past202004-open/tasks/past202004_l 解説 https://atcoder.jp/contests/past202004-open/submissions/12899490 こういった構築には典型が存在する。 「辞書順最小の構築問題は先頭から貪欲に選択していく」 さて、先頭から貪欲…

https://atcoder.jp/contests/past202004-open/tasks/past202004_k 前提知識 動的計画法 解説 https://atcoder.jp/contests/past202004-open/submissions/12899146 どことなく問題が編集距離のDPに似ている。 類題を解いたことがあるので、以下のDPが思いつ…

https://atcoder.jp/contests/past202004-open/tasks/past202004_j 前提知識 構文解析 解説 https://atcoder.jp/contests/past202004-open/submissions/12898808 この問題は適切に構文解析を行えるかを問う問題。 構文解析の一番単純な手法として再帰で行う…

https://atcoder.jp/contests/past202004-open/tasks/past202004_i 解説 https://atcoder.jp/contests/past202004-open/submissions/12898293 トーナメントでの戦いがあるので、これをシミュレートする問題。 先頭から2つずつ戦わせていくというのをN回繰り…

https://atcoder.jp/contests/past202004-open/tasks/past202004_h 前提知識 BFS 解説 https://atcoder.jp/contests/past202004-open/submissions/12898078 この問題は類題を解いていないといきなり解くのは難しいだろう。 SからGへの最短距離なので、盤面上…

https://atcoder.jp/contests/past202004-open/tasks/past202004_g 解説 https://atcoder.jp/contests/past202004-open/submissions/12897574 この問題は実装が重い問題である。 愚直に文字列を追加する解法では、文字列の長さが1010とかになってしまうので…

https://atcoder.jp/contests/past202004-open/tasks/past202004_f 解説 https://atcoder.jp/contests/past202004-open/submissions/12896163 例えば、1日目に選ぶタスクはどのタスクがいいだろうか。 複数タスクがある場合は最もポイントが大きいタスクを選…

https://atcoder.jp/contests/past202004-open/tasks/past202004_e 解説 https://atcoder.jp/contests/past202004-open/submissions/12895699 各整数iについて、操作をシミュレーションして、条件を満たす整数jを答える。 そのまま、配列Aを受け取ると、「A[…

https://atcoder.jp/contests/past202004-open/tasks/past202004_d 解説 https://atcoder.jp/contests/past202004-open/submissions/12895517 競技プログラミングの基本は全探索である。 文字列Tは全部で273+272+27通りある。 これはだいたい20000通りくらい…

https://atcoder.jp/contests/past202004-open/tasks/past202004_c 解説 https://atcoder.jp/contests/past202004-open/submissions/12894322 文字列を扱う問題は慣れないと難しいかと思う。 問題で与えられている操作をシミュレーションしよう。 完全に自分…

https://atcoder.jp/contests/past202004-open/tasks/past202004_b 解説 https://atcoder.jp/contests/past202004-open/submissions/12894206 まずは候補者ごとに票を集計する。 cnt[i] := 候補者abcのi番目に入った票の数 次に、最も多い票数maを探す。 最…

https://atcoder.jp/contests/past202004-open/tasks/past202004_a 解説 https://atcoder.jp/contests/past202004-open/submissions/12893803 やり方はいろいろありそうだが、自分はフロアを下から順に0,1,2,3,...,17と番号を付けて、 それに変換して、フロ…