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と番号を付けて、 それに変換して、フロ…

hamayanhamayanがインターネットを巡回して得た情報まとめ。 "Japan"と言うには主語が大きすぎる。 Hottest 競技プログラミング AtCoder Beginner Contest 166 - AtCoder Peaks [AtCoder Beginner Contest 166 C] I hate Factorization [AtCoder Beginner Co…

Datasets関連を調べたので、残しておく。 KaggleのDatasetsとは ユーザーがデータセットを置いて、公開できる場所 テストデータをOSSのように公開するためのプラットフォーム Datasetsには何がアップロードされているか その名の通り、学習に使えるデータセ…

https://atcoder.jp/contests/abc166/tasks/abc166_f 解説 https://atcoder.jp/contests/abc166/submissions/12765112 珍しい系統の問題。 以下のように考察を進める 場面を色々考えてみると、大体うまくいきそうな感じがする うまくいかない場合を考えてみ…

https://atcoder.jp/contests/abc166/tasks/abc166_e 解説 https://atcoder.jp/contests/abc166/submissions/12768207 まずは以下の典型解法をベースに考えよう。 「数列の2要素a,b(a

https://atcoder.jp/contests/abc166/tasks/abc166_d 解説 https://atcoder.jp/contests/abc166/submissions/12773980 この問題を解くにあたって最も注目すべき部分はどこだろうか。 他の問題と著しく異なっている部分はやはり「5乗」の部分である。 この部…

https://atcoder.jp/contests/abc166/tasks/abc166_c 解説 https://atcoder.jp/contests/abc166/submissions/12777268 今回の問題が解けなかった場合は、この問題よりも競プロにおけるdfsの書き方を学ぶことをお勧めする。 そちらの方が資料が多いためだ。 …

hamayanhamayanがインターネットを巡回して得た情報まとめ。 "Japan"と言うには主語が大きすぎる。 Hottest 障害対応時にまずはissueを作ると良い - そーだいなるらくがき帳 良い記事。issueのテンプレートを行動指針にするという流れは素晴らしいと思う 障…

https://atcoder.jp/contests/abc165/tasks/abc165_f 前提知識 座標圧縮 セグメントツリーを使ったLIS解法 永続セグメントツリー（部分永続でOK） 解説 https://atcoder.jp/contests/abc165/submissions/12637772 データ構造ズルをして解いた。 自分は手元に…

https://atcoder.jp/contests/abc165/tasks/abc165_e 解説 https://atcoder.jp/contests/abc165/submissions/12644257 頑張ってスマートな方針を考える。 最も厳しいパターンで方針を考えるのが良いだろう。 今回であれば、対戦相手が少ないほど、再戦の可能…

https://atcoder.jp/contests/abc165/tasks/abc165_d 解説 https://atcoder.jp/contests/abc165/submissions/12646306 D問題にしては難しい問題に見えるし、計算過程に実数も入ってくるので、とりあえず実験コードを書いてみる。 xを[0,N]に動かして何か発見…

https://atcoder.jp/contests/abc165/tasks/abc165_c 解説 https://atcoder.jp/contests/abc165/submissions/12649721 メタ読みをする。 制約を見ると、数列Aの全探索ができそうな感じ。 dfsを使って数列を全探索していこう。 dfsを使った数列の全探索方法が…

https://atcoder.jp/contests/abc165/tasks/abc165_b 解説 https://atcoder.jp/contests/abc165/submissions/12650100 制約が1018となっている、C++ではintではオーバーフローするので、long longで受け取ること。 入力例で1000000000000000000は3760とある…

https://atcoder.jp/contests/abc165/tasks/abc165_a 解説 https://atcoder.jp/contests/abc165/submissions/12650463 ジャンボ高橋君の出せる飛距離のパターンは103通りくらいなので、全部試してKの倍数があるか探そう。 体感としては全列挙したときに107通…

https://yukicoder.me/problems/no/1045 前提知識 bitDP 解説 https://yukicoder.me/submissions/475059 制約からbitDPを感じるので、その方針で考えるとできる。 遷移込みで状態を考えると、以下のようにすればいいと分かる。 dp[msk][lst][hei] := 使用済…

https://yukicoder.me/problems/no/1044 解説 https://yukicoder.me/submissions/475051 説明のため、N人の正直者を正直者1, 正直者2, ..., 正直者Nと呼ぶことにする。 円の数え上げの典型テクを使う 「1つを先頭として固定することで、列の数え上げにする」…

https://yukicoder.me/problems/no/1043 前提知識 動的計画法 累積和 解説 https://yukicoder.me/submissions/475040 初手がなかなか難しいし、色々なテクを必要とするので、少し難しい問題。 逆に言うと理解すれば色々な技を得られるだろう。 制約を見ると…