https://atcoder.jp/contests/abc135/tasks/abc135_f 前提知識 Suffix Array トポロジカルソート 解説 https://atcoder.jp/contests/abc135/submissions/6588977 まずは尖ったケースを考えてみる。 -1が尖っているので、この辺から考えてみる。 まずは、-1と…

https://atcoder.jp/contests/abc135/tasks/abc135_d 前提知識 桁DP 解説 https://atcoder.jp/contests/abc135/submissions/6588492 桁DPしていこう。 dp[dgt][mo] := dgt桁目まで確定していて、そこまでで13で割ったあまりがmoである組み合わせ ?でないとき…

https://atcoder.jp/contests/abc135/tasks/abc135_c 解説 https://atcoder.jp/contests/abc135/submissions/6588408 どこから考えようかという問題。 DPを考えてみると、dp[i][rest] := i人目までの勇者が倒し終わっていて、最後の街にrest体のモンスターが…

https://atcoder.jp/contests/abc135/tasks/abc135_b 解説 https://atcoder.jp/contests/abc135/submissions/6588394 入れ替え操作は全部でO(N2)なので、全通り試すことはできそう。 昇順になっているかの判定もO(N)でできるので、全部でO(N3)で間に合う。 C…

https://atcoder.jp/contests/abc135/tasks/abc135_a 解説 https://atcoder.jp/contests/abc135/submissions/6588371 abs(A-K)=abs(B-K)というのは、言い換えると、KはAとBのちょうど真ん中にある数ということになる。 これはA,Bの平均であると言えるため、…

https://atcoder.jp/contests/abc134/tasks/abc134_f 前提知識 動的計画法（箱根DP） 解説 https://atcoder.jp/contests/abc134/submissions/6480100 箱根DPという典型DPテクがあるので、そこをベースに考えてみる。 今回の問題を1つの順列の入れ替えと考え…

https://atcoder.jp/contests/abc134/tasks/abc134_e 前提知識 2Dセグメントツリー、セグメントツリーにセグメントツリーを載せるテク ← 公式解法ではいらない 解説 https://atcoder.jp/contests/abc134/submissions/6479037 先頭から貪欲に増加列を作ってい…

https://atcoder.jp/contests/abc134/tasks/abc134_d 解説 https://atcoder.jp/contests/abc134/submissions/6478841 B[i] := i番目の箱にボールが何個入っているかと定義しておこう。 まず、自明なところから考えていこう。 A[N]=B[N] これがまず分かるとこ…

https://atcoder.jp/contests/abc134/tasks/abc134_c 前提知識 累積和 解説 https://atcoder.jp/contests/abc134/submissions/6478504 ある1要素以外の最大値を取りたいという要望には典型テクがある。 累積和を利用するのだが、先頭からと後尾からの2つを構…

https://atcoder.jp/contests/abc134/tasks/abc134_b 解説 https://atcoder.jp/contests/abc134/submissions/6478072 監視員がカバーできる範囲は[i-D,i+D]なので、2D+1の範囲をカバーできる。 よって、len=2D+1とすると、N/Dの切り上げが必要な監視員の最少…

https://atcoder.jp/contests/abc134/tasks/abc134_a 解説 https://atcoder.jp/contests/abc134/submissions/6477844 問題に書いてある計算式をそのまま実装しよう。 int R; //---------------------------------------------------------------------------…

概要 JSONを渡すAPIに対して、XMLを渡すことができる場合がある その場合にXXEが行えてしまう JSONを渡すAPIに対してXMLが渡せる現象 Playing with Content-Type – XXE on JSON Endpointsのほぼ日本語訳。 例えば、 POST /netspi HTTP/1.1 Host: someserver.…

https://ctftime.org/task/8791 前提知識 XXE 問題 There is not much to see in this enterprise-ready™ web application. https://bnv.web.ctfcompetition.com/ Writeups https://www.youtube.com/watch?v=OqDxy-wm9to https://medium.com/hmif-itb/google…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0656?year=2019 前提知識 動的計画法 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/2/0656/judge/3760168/C++14 「区間についての制約があって、合計の…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0655?year=2019 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0655/judge/3760197/C++14 海面の高さが上昇すると、島が分割または消滅していって、ま…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0654?year=2019 前提知識 動的計画法 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0654/judge/3757763/C++14 貪欲法でも行けそうな感じであるが、DP…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0653?year=2019 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0653/judge/3757737/C++14 シミュレーションで解こう。 駒は追い越すことは無いので、…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0652?year=2019 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0652/judge/3757726/C++14 少なくともC日の間には条件を達成できるので、C日を上限とし…

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/E 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3745712 説明のため、D[u][v] := 頂点uから頂点vへの最短経路としておく。 この問題を見たときに…

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/D 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3746197 問題を見ると、経験から特殊な性質・規則性を用いる問題だと見える。 こういう時は、実験…

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/C 前提知識 構文解析（優先順位有り） 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3746462 まずは、与えられた論理式が理解できないと、始まら…

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/B 前提知識 エラトステネスの篩を使った区間約数列挙 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3745884 クエリ問題への取り組み方はいろいろ…

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/A 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3745829 A問題でむずかしめ感じに見えるが、とりあえず全探索を考えてみよう。 パッケージを買う…

結論 Expressでクッキーレスセッションはできない 代わりにJWT認証を使おう 以下、物語。 発端 今あるサービスのWebAPIを作っていて、アプリ開発サイドに向けて、一旦仕様を出した。 Androidだとクッキー使わないと思うので、パラメタでトークン指定する形式…

http://mnctf.info/mnctf2019/ 参考 CTFmanさん解説 yam7k5さん解説 悪意部品 分からんワード辞書 PLEAD: BlackTechという攻撃者集団が使ったマルウェア RAD機能：Remote Administration Tool, Remote Access Tool 攻撃対象のコンピュータにアクセスできるよ…

https://atcoder.jp/contests/abc133/tasks/abc133_f 前提知識 LCA クエリ先読み 解説 https://atcoder.jp/contests/abc133/submissions/6312857重要なこととして、制約を簡単にした問題が解けないか考えてみる。 今回で言うと、辺の長さの変更が難しいので…

https://atcoder.jp/contests/abc133/tasks/abc133_e 解説 https://atcoder.jp/contests/abc133/submissions/6312375木でmod10^9+7なので、とりあえず木DPを疑う。 dp[cu] := cuを根とする部分木での塗り方の総数 これをベースにまずは考えてみよう。 正直こ…

https://atcoder.jp/contests/abc133/tasks/abc133_d 解説 https://atcoder.jp/contests/abc133/submissions/6312080各山にx1, x2, x3, ... 降ったとする。 すると、ダムには(x1+x2)/2=A1のように溜まっていく。 割り算は面倒なので、全部二倍しておこう。 1…

https://atcoder.jp/contests/abc133/tasks/abc133_c 解説 https://atcoder.jp/contests/abc133/submissions/6313028300点問題にしては難しい問題に見える。 (i×j) % 2019 = (i % 2019) * (j % 2019) となる。 理論的な最小値は0であり、これを目指すことを…

https://atcoder.jp/contests/abc133/tasks/abc133_b 解説 https://atcoder.jp/contests/abc133/submissions/6311855(i,j)の組は全探索できるので、全探索して、距離が整数となる組を数え上げよう。 ルートの解決が少し厄介であるので、距離^2が平方数である…