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

hamayanhamayan's blog

2020-05-06から1日間の記事一覧

アルゴリズム実技検定解説まとめ

第三回 アルゴリズム実技検定 # 配点 題名 要求(白塗りしてあるので選択で見て) 解説 A 9 ケース・センシティブ 実装 解説 B 8 ダイナミック・スコアリング シミュレーション 解説 C 8 等比数列 数学(自分は実装で解いたけど) 解説 D 7 電光掲示板 実装…

Variable Spanning Trees [第二回 アルゴリズム実技検定 O]

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

Building Construction [第二回 アルゴリズム実技検定 N]

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

Cafeteria [第二回 アルゴリズム実技検定 M]

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

Lexicographically Minimum [第二回 アルゴリズム実技検定 L]

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

Parentheses [第二回 アルゴリズム実技検定 K]

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

Parse [第二回 アルゴリズム実技検定 J]

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

Elimination [第二回 アルゴリズム実技検定 I]

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

1-9 Grid [第二回 アルゴリズム実技検定 H]

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

String Query [第二回 アルゴリズム実技検定 G]

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

Tasking [第二回 アルゴリズム実技検定 F]

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

Permutation [第二回 アルゴリズム実技検定 E]

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

String Match [第二回 アルゴリズム実技検定 D]

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

Landslide [第二回 アルゴリズム実技検定 C]

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

Plurality Voting [第二回 アルゴリズム実技検定 B]

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

Elevator [第二回 アルゴリズム実技検定 A]

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