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

hamayanhamayan's blog

2021-06-01から1ヶ月間の記事一覧

Tree Patrolling [AtCoder Beginner Contest 207 F]

https://atcoder.jp/contests/abc207/tasks/abc207_f 前提知識 二乗の木DP 解説 https://atcoder.jp/contests/abc207/submissions/23806639 二乗の木DPという手法を用いる。 知らないと解けない気もするが、計算量的なセンスがあれば自ら生み出せるかもしれ…

Mod i [AtCoder Beginner Contest 207 E]

https://atcoder.jp/contests/abc207/tasks/abc207_e 前提知識 https://blog.hamayanhamayan.com/entry/2017/02/27/021246 解説 https://atcoder.jp/contests/abc207/submissions/23805901 高度なDP。慣れていないと簡単ではないと思うのだが、500人も解くん…

Congruence Points [AtCoder Beginner Contest 207 D]

https://atcoder.jp/contests/abc207/tasks/abc207_d 前提知識 幾何知識 解説 https://atcoder.jp/contests/abc207/submissions/23804855 微妙に幾何知識が必要。 自分の解法は想定解法ではなく、かつ、コンパイル時最適化でTLEをごり消した解法です。 慣れ…

Many Segments [AtCoder Beginner Contest 207 C]

https://atcoder.jp/contests/abc207/tasks/abc207_c 解説 https://atcoder.jp/contests/abc207/submissions/23803776 区間をすべて[l,r)の半開区間に変換して比較をしよう。 [l,r] -> [l,r + 0.5) [l,r) -> [l,r) (l,r] -> [l + 0.5, r + 0.5) (l,r) -> [l …

Hydrate [AtCoder Beginner Contest 207 B]

https://atcoder.jp/contests/abc207/tasks/abc207_b 解説 https://atcoder.jp/contests/abc207/submissions/23803329 愚直にシミュレーションをしていって、目標が達成されれば即座に回数を答えれば答えになる。 ただ、目標が達成可能でない場合は無限に操…

Repression [AtCoder Beginner Contest 207 A]

https://atcoder.jp/contests/abc207/tasks/abc207_a 解説 https://atcoder.jp/contests/abc207/submissions/23802672 選んで手に取る組合せは3通りなのでそれをすべて列挙して最大値を求めてもいい。 自分の実装では、求めたい最大値は3つの数から大きい2つ…

Interval Game 2 [AtCoder Beginner Contest 206(Sponsored by Panasonic) F]

https://atcoder.jp/contests/abc206/tasks/abc206_f 前提知識 grundy数 解説 https://atcoder.jp/contests/abc206/submissions/23623437 今回の問題はgrundy数を知らないとまず解けない。 解説範囲がとても広くなってしまうので、grundy数についてはどこか…

Divide Both [AtCoder Beginner Contest 206(Sponsored by Panasonic) E]

https://atcoder.jp/contests/abc206/tasks/abc206_e 前提知識 約数系包除原理 解説 https://atcoder.jp/contests/abc206/submissions/23623547 しょっぱなから発想の転換が必要な問題。 類題を多く解いているので、すぐ思いついたが、そうでないと難しい。 …

KAIBUNsyo [AtCoder Beginner Contest 206(Sponsored by Panasonic) D]

https://atcoder.jp/contests/abc206/tasks/abc206_d 前提知識 UnionFind 解説 https://atcoder.jp/contests/abc206/submissions/23624301 以下の解説は、この問題はUnionFindを知らないと理解は難しいので、どこかで学習してきてほしい。 UnionFindを知らな…

Swappable [AtCoder Beginner Contest 206(Sponsored by Panasonic) C]

https://atcoder.jp/contests/abc206/tasks/abc206_c 解説 https://atcoder.jp/contests/abc206/submissions/23625007 まず、i,jの組を全探索する方針があるが、これは9*1010通りとなるので間に合わない。 全探索系は107くらいが上限。 だが、片方だけ全探索…

Savings [AtCoder Beginner Contest 206(Sponsored by Panasonic) B]

https://atcoder.jp/contests/abc206/tasks/abc206_b 解説 https://atcoder.jp/contests/abc206/submissions/23625300 この問題は実は1日目から順番にシミュレートすれば間に合う。 200点問題ではあるが、ちょっと計算量について考え始めると心配になったり…

Maxi-Buying [AtCoder Beginner Contest 206(Sponsored by Panasonic) A]

https://atcoder.jp/contests/abc206/tasks/abc206_a 解説 https://atcoder.jp/contests/abc206/submissions/23625515 今回の問題で精度が要求されるかは分からないが、テクとして、小数計算は精度が心配だから、できるなら整数で計算するというものがある。…

BCACTF 2.0 解説 (Writeup)

解けたものだけ。 Countdown Timer [Web] 100日間は待てないので何とかしなくては。 カウントダウンが終了するとgetFlagが呼ばれる。 直接コンソールでgetFlagを呼ぼうとしたら呼べなかった。うーん。 適当にブレークとして、待ち時間を0に書き換えてやれば…

Toulouse Hacking Convention 2021 解説 (Writeup)

1つしか解けなかった・・・ Unsafe Math [Web] app.post('/', function(req, res){ const regex = /[a-zA-Z]/g; var width = req.body.width; var height = req.body.height; if(width === '' || height === ''){ return res.render('index', {'error':'one …

Grid and Tokens [AtCoder Beginner Contest 205 F]

https://atcoder.jp/contests/abc205/tasks/abc205_f 前提知識 最大流 解説 https://atcoder.jp/contests/abc205/submissions/23457322 今回の問題は最大流問題に帰着できる。 パッと見て類題を思い出して、選択肢を考えていくと最大流で解法が思いつける。 …

White and Black Balls [AtCoder Beginner Contest 205 E]

https://atcoder.jp/contests/abc205/tasks/abc205_e 前提知識 カタラン数 解説 https://atcoder.jp/contests/abc205/submissions/23454802 この問題は類題を知っていれば解法は一瞬で思いつくが、知らないと一生解けない(少なくとも自分は…) この問題はカ…

Kth Excluded [AtCoder Beginner Contest 205 D]

https://atcoder.jp/contests/abc205/tasks/abc205_d 解説 https://atcoder.jp/contests/abc205/submissions/23456683 自分はクエリ先読みと尺取り法っぽく解いた。 考え方が思いついても実装も大変な問題。 クエリ先読みについてはモチベは簡単なので、軽く…

POW [AtCoder Beginner Contest 205 C]

https://atcoder.jp/contests/abc205/tasks/abc205_c 解説 https://atcoder.jp/contests/abc205/submissions/23456949 発想力が必要となる問題。 真面目に計算するのは精度的に無理なので、logか…?とも思ったがこちらも精度が心配で、300点っぽくない。 大…

Permutation Check [AtCoder Beginner Contest 205 B]

https://atcoder.jp/contests/abc205/tasks/abc205_b 解説 https://atcoder.jp/contests/abc205/submissions/23457038 問題を少し変えて考えてみる。 今回の判定問題は、与えられたAを並び替えて、1,2,3,...,Nになるかというのを考えても問題ない。 と考える…

kcal [AtCoder Beginner Contest 205 A]

https://atcoder.jp/contests/abc205/tasks/abc205_a 解説 https://atcoder.jp/contests/abc205/submissions/23457255 単位数である1mLを経由することで計算をしていく。 100 mL -> A kcal 1 mL -> A / 100 kcal B mL -> A / 100 * B kcal ということでA/100…

Hanjo 2 [AtCoder Beginner Contest 204 F]

https://atcoder.jp/contests/abc204/tasks/abc204_f 前提知識 bitDP 行列累乗を使ったDP高速化 解説 https://atcoder.jp/contests/abc204/submissions/23263864 今回の問題はとても難しいのだが、典型度は高い。 まず、制約がかなりとがっているので、何を…

Rush Hour 2 [AtCoder Beginner Contest 204 E]

https://atcoder.jp/contests/abc204/tasks/abc204_e 前提知識 ダイクストラ 解説 https://atcoder.jp/contests/abc204/submissions/23263588 問題設定が有向グラフの最短経路問題なので、ダイクストラ法が最初に思いつく。 ダイクストラ法をもじって解くこ…

Cooking [AtCoder Beginner Contest 204 D]

https://atcoder.jp/contests/abc204/tasks/abc204_d 解説 https://atcoder.jp/contests/abc204/submissions/23262989 この問題はDPで解ける。 いかにDPで解くという所に帰着させるかを説明していこう。 まず、制約がとても小さい。 パッと見て貪欲で行けそ…

Tour [AtCoder Beginner Contest 204 C]

https://atcoder.jp/contests/abc204/tasks/abc204_c 前提知識 BFS 解説 https://atcoder.jp/contests/abc204/submissions/23261589 この問題では実装方針から正しく計算量を見積もれるかがポイントとなる。 計算量見積もりをして、オーダーで上限を当てはめ…

Nuts [AtCoder Beginner Contest 204 B]

https://atcoder.jp/contests/abc204/tasks/abc204_b 解説 https://atcoder.jp/contests/abc204/submissions/23260128 シミュレーションする問題。要求されていることを実装しよう。 それぞれの木の実について、 10以下であれば何もしない 10より大きいならA…

Rock-paper-scissors [AtCoder Beginner Contest 204 A]

https://atcoder.jp/contests/abc204/tasks/abc204_a 解説 https://atcoder.jp/contests/abc204/submissions/23259935 あいこになるのは全部同じか全部違う場合なので、その2つの状況で場合分けして答えることにしよう。 x=yであれば全部同じの場合なので、x…

Attacktive Directory 解説 (Writeup) [TryHackMe]

一部を■で隠しています。 Task1: Deploy The Machine デプロイプロセスを細かく指示してくれる。優しい。 Taks2: Setup 色々ツールを入れようという章になっている。 Impacketは今まで使ったことがあるexploitコードがまとまっている Bloodhound, Neo4jを入…

VulnNet: Roasted 解説 (Writeup) [TryHackMe]

一部を■で隠しています。 …えー、正直全く分からなかったのでWriteupを激読みしてます。 Writeups vulnnet_roasted/README.md at main · siddicky/vulnnet_roasted · GitHub TryHackMe | VulnNet:Roasted. A room on TryHackMe created by… | by FarisArch |…