hamayanhamayanがインターネットを巡回して得た情報まとめ。 "Japan"と言うには主語が大きすぎる。 Hottest 競技プログラミング AtCoder Beginner Contest 161 - AtCoder Lunlun Number [AtCoder Beginner Contest 161 D] Yutori [AtCoder Beginner Contest …
https://ctftime.org/task/10853 本当はVolgaCTF全解説する予定だったけれど、気力切れたから、これだけ。 何も情報がない（しかも、静的サイトじゃん） 初手は皆、URIを全探索するスキャニングツールを使っている gobusterを試しに使うと、docsというサブデ…
![はてなブックマーク - NetCorp [VolgaCTF 2020 Web]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/04/04/232900)
https://atcoder.jp/contests/abc161/tasks/abc161_d 解説 https://atcoder.jp/contests/abc161/submissions/11550250 サンプルを見ると105の場合が紹介されている。 あまり桁数が増えていないので、普通にインクリメント作業をしても間に合いそうだ。 x++の…
![はてなブックマーク - Lunlun Number [AtCoder Beginner Contest 161 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/04/04/231247)
https://atcoder.jp/contests/abc161/tasks/abc161_e 前提知識 DPの復元 解説 https://atcoder.jp/contests/abc161/submissions/11549308 ※ 本解説は、DPの復元が理解できてないとちょっと厳しいかもしれない 色々な方針が見える。 ある日で必ず働くというこ…
![はてなブックマーク - Yutori [AtCoder Beginner Contest 161 E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/04/04/230324)
https://atcoder.jp/contests/abc161/tasks/abc161_f 前提知識 O(sqrt(N))による約数列挙 解説 https://atcoder.jp/contests/abc161/submissions/11544845 余談であるが、1012という制約はとても特徴的であり、平方根をとると106となって、まだやれる計算量…
![はてなブックマーク - Division or Substraction [AtCoder Beginner Contest 161 F]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/04/04/224111)
https://yukicoder.me/problems/no/1017 解説 https://yukicoder.me/submissions/458766 今までの経験からして、これ系で行けそうというものはあるが、制約がちょっと厳しいのと、構築する必要がある。 なにも思いつかんけど、難易度がREDじゃないというとき…
![はてなブックマーク - Reiwa Sequence [yukicoder 1017]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/04/04/172130)
https://yukicoder.me/problems/no/1016 解説 https://yukicoder.me/submissions/458599 貪欲法で解けそう。 まずは自明な所から考えてみる。 既にoooがあるなら勝っているし、どこか1マスにoを入れれば勝てるなら勝ち。 複数手で勝てる手を考える。 3手詰め…
![はてなブックマーク - 三目並べ [yukicoder 1016]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/04/04/172030)
https://yukicoder.me/problems/no/1015 解説 https://yukicoder.me/submissions/458591 問題の見た目と★2なので、貪欲方針系だろうというのは分かる。 本番では別の貪欲をしてしまって通せなかった。 （ちゃんと落としてくるのが、さすが、maspyさん+beetさ…
![はてなブックマーク - おつりは要らないです [yukicoder 1015]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/04/04/171929)
https://atcoder.jp/contests/abc160/tasks/abc160_c 解説 https://atcoder.jp/contests/abc160/submissions/11325671 ある家iから出発してすべての家を回る最短経路はi -> i+1 -> i+2 -> ... -> N -> 1 -> 2 -> ... -> i-1という感じになる。 つまり、1パタ…
![はてなブックマーク - Traveling Salesman around Lake [AtCoder Beginner Contest 160 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/29/034804)
解法 簡単に書いておく。 貪欲法で解ける。 先頭から埋めていくことを考えると使える要素がどんどん少なくなっていく。 だが、末尾から埋めていくことを考えると使える要素がどんどん多くなっていく。 多くなる方がうまくいく場合が多いので、そっちでまず考…
![はてなブックマーク - RankingStudents [SRM 782 Div1 Med]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/29/033536)
前提知識 O(3N)のbitDP 解説 簡単にまとめておく。 サイコロで出せる合計の目の上限は2Dなので、Tが2Dを超えていたら、その部分は絶対余る。 なので、Tは2Dまでを考えればいい。 すると、bitDPができることに気が付く。 dp[msk] := 残っているペナルティトー…
![はてなブックマーク - EmptyTheBox [SRM 782 Div1 Easy]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/29/033002)
https://atcoder.jp/contests/abc160/tasks/abc160_f 前提知識 全方位木DP 解説 https://atcoder.jp/contests/abc160/submissions/11325358 全方位木DPが分かっていないと解けない。 この問題で全方位木DPを学ぶには少し問題がややこしい。 入門問題としては…
![はてなブックマーク - Distributing Integers [AtCoder Beginner Contest 160 F]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/29/032615)
https://atcoder.jp/contests/abc160/tasks/abc160_e 解説 https://atcoder.jp/contests/abc160/submissions/11320313 今回の問題では、2種類の取り組み方をブレンドして解く。 C個の無色のリンゴの中で使う個数を「全探索」し、そのパターンで「貪欲」にリ…
![はてなブックマーク - Red and Green Apples [AtCoder Beginner Contest 160 E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/29/000846)
https://atcoder.jp/contests/abc160/tasks/abc160_d 解説 https://atcoder.jp/contests/abc160/submissions/11318810 今回の問題で最も重要なのは、制約に気が付くところにある。 Nは最大2000なので、O(N2)が通る。 計算量は107くらいを上限にしてとりあえ…
![はてなブックマーク - Line++ [AtCoder Beginner Contest 160 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/29/000745)
hamayanhamayanがインターネットを巡回して得た情報まとめ。 "Japan"と言うには主語が大きすぎる。 Hottest Good Job!（グッジョブ） | Nintendo Switch | 任天堂 これの紹介動画に面白い工夫を見た 2人プレイで場所が離れたときに、最初は引きのカメラ1つだ…
CTFtime.org / ångstromCTF 2020 まだサーバが生きてたので、復習がてら、解法まとめ。 と思ったら教育的で昔の年もできるのね。 20点 The Magic Word The Magic Word [AngstromCTF 2020 Web] - はまやんはまやんはまやん htmlはChromeとかを使うと簡単に修…
https://atcoder.jp/contests/abc159/tasks/abc159_d 解説 https://atcoder.jp/contests/abc159/submissions/11139315 今回のようなクエリ問題に対する対処はあまりパターンがない。 各クエリについて高速に計算 全部前計算してしまう 差分を計算することで…
![はてなブックマーク - Banned K [AtCoder Beginner Contest 159 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/22/235319)
https://atcoder.jp/contests/abc159/tasks/abc159_f 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc159/submissions/11138847 DPを使ってまとめて数え上げることができる。 思いつく仮定としては、DPで解くんだろうと考え始めることと、N,S≦300…
![はてなブックマーク - Knapsack for All Segments [AtCoder Beginner Contest 159 F]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/22/234317)
https://atcoder.jp/contests/abc159/tasks/abc159_e 解説 https://atcoder.jp/contests/abc159/submissions/11137460 どう見てもHの制約の小ささが気になるので、2Hを中心に考えてみる。 チョコレートを横に切る操作は2H-1通りあるので、全探索できる。 横…
![はてなブックマーク - Dividing Chocolate [AtCoder Beginner Contest 159 E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/22/231629)
hamayanhamayanがインターネットを巡回して得た情報まとめ。 "Japan"と言うには主語が大きすぎる。 Hottest 競技プログラミング なんだかなぁ 小山高専プロコン fizzbuzz [OyamaC] rot and rot [OyamaC] storage [OyamaC] sumsumsum [OyamaC] tiktak [OyamaC…
https://atcoder.jp/contests/agc043/tasks/agc043_b 解説 https://atcoder.jp/contests/agc043/submissions/11065208 まず、答えは0,1,2の3択になる。 このどれが答えになるかを求めていこう。 これは実験すると分かるし、操作を見てみるとそうなりそうなこ…
![はてなブックマーク - 123 Triangle [AtCoder Grand Contest 043 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/22/020306)
https://atcoder.jp/contests/agc043/tasks/agc043_a 解説 https://atcoder.jp/contests/agc043/submissions/11063628 左上から右下へのとある経路を考える。 この経路で移動しようと考えたときの必要な最小操作回数は「白→黒」となった回数である。 （スタ…
![はてなブックマーク - Range Flip Find Route [AtCoder Grand Contest 043 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/22/003736)
https://codeforces.com/contest/1326/problem/D2 前提知識 Manacher 解説 https://codeforces.com/contest/1326/submission/73898734 高速にクエリをさばいていこう。 文字列のprefixとsuffixで回文となる最大長を計算しておく。 この最大長以下であれば、…
![はてなブックマーク - Prefix-Suffix Palindrome (Hard version) [Codeforces Global Round 7 D2]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/22/001248)
https://codeforces.com/contest/1326/problem/C 解説 https://codeforces.com/contest/1326/submission/73896496 最善の答えは、最も大きいK個の総和であり、これはうまく分割することで達成できる。 そのような分割にするには、最も大きいK個の間に分割の…
![はてなブックマーク - Permutation Partitions [Codeforces Global Round 7 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/22/001147)
https://codeforces.com/contest/1326/problem/B 解説 https://codeforces.com/contest/1326/submission/73896052 実は順番に構築していけばいい。 x[0]は0で固定。 b[i]=a[i]-x[i]なので、a[i]=b[i]+x[i]である。 なので、a[0]=b[0]+x[0]を使って、a[0]を計…
![はてなブックマーク - Maximums [Codeforces Global Round 7 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/22/001046)
https://codeforces.com/contest/1326/problem/A 解説 https://codeforces.com/contest/1326/submission/73895303 n=1のときは、その桁で必ず割り切れるので答えがない。 2以上のときは必ず答えが存在する。 自分は222222....222223を作って、全体が3で割り…
![はてなブックマーク - Bad Ugly Numbers [Codeforces Global Round 7 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/22/000945)
https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/M 解説 根性構築。 N=1,2のときはサンプルにあるやつを答えればいい。 3≦Nのときは、00, 010, 0110, 01110, ...と構築していけばN-1個を達成できる。 なぜN-1が上限（最適解）であ…
![はてなブックマーク - 文字列集合 [Kyoto University Programming Contest 2020 Spring M]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/21/205857)
https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/K 前提知識 ダブリングDP 解説 どこから手を付けるかと言うと、まずは1クエリでの計算である。 クエリ問題での方針は、「毎回高速に計算」「一気に前計算しておく」「差分だけ計算…
![はてなブックマーク - トーナメント [Kyoto University Programming Contest 2020 Spring K]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/21/205810)
https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/E 前提知識 grundy数 解説 ゲーム問題は実験せよと古事記に書いてあるのでやる。 正確には勝ち負けだけ分かればいいので、grundy数が0になる規則性を探してくる。 ひたすら実験し…
![はてなブックマーク - 数列ゲーム [Kyoto University Programming Contest 2020 Spring E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/21/205712)
https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/D 前提知識 累積和による動的計画法高速化 前提知識 DPの作り方で運命が変わる。 dp[i][xo][lst] := 数列のi個目まで確定していて、総XORがxoで、最後の要素がlstであるときの組み…
![はてなブックマーク - Xor Array [Kyoto University Programming Contest 2020 Spring D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2020/03/21/205557)