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

hamayanhamayan's blog

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

Graph Smoothing [AtCoder Beginner Contest 199(Sponsored by Panasonic) F]

https://atcoder.jp/contests/abc199/tasks/abc199_f 前提知識 行列累乗 解説 https://atcoder.jp/contests/abc199/submissions/22041784 この問題は数学パートと行列累乗高速化パートに分かれる。 行列累乗を使ったDP高速化を知らない場合は解けないのでま…

Permutation [AtCoder Beginner Contest 199(Sponsored by Panasonic) E]

https://atcoder.jp/contests/abc199/tasks/abc199_e 前提知識 bitDP 解説 https://atcoder.jp/contests/abc199/submissions/22040868 今回の問題はbitDPで解ける。 dp[msk] := 1~Nの数についてmskのものを使用していて、条件が満たされる数列の組み合わせ …

RGB Coloring 2 [AtCoder Beginner Contest 199(Sponsored by Panasonic) D]

https://atcoder.jp/contests/abc199/tasks/abc199_d 2020/4/25修正。後半部分が嘘解法でした。 前提知識 UnionFind dfs 解説 https://atcoder.jp/contests/abc199/submissions/22051608 制約を見ると全部の状態を全列挙しても大丈夫そうな感じがある。 本当…

IPFL [AtCoder Beginner Contest 199(Sponsored by Panasonic) C]

https://atcoder.jp/contests/abc199/tasks/abc199_c 解説 https://atcoder.jp/contests/abc199/submissions/22039696 この問題のミソはT=2の処理である。 T=1の場合はswapがO(1)で行えるので問題ない。 T=2の場合は、普通にやるとO(N)かかるのでこれを何と…

Intersection [AtCoder Beginner Contest 199(Sponsored by Panasonic) B]

https://atcoder.jp/contests/abc199/tasks/abc199_b 解説 https://atcoder.jp/contests/abc199/submissions/22039415 この問題は色々な解法が考えられるが、計算量が最も良いものを選択した。 求めたい整数xはとある範囲に限定される。 その範囲は、N個の[A…

Square Inequality [AtCoder Beginner Contest 199(Sponsored by Panasonic) A]

https://atcoder.jp/contests/abc199/tasks/abc199_a 解説 https://atcoder.jp/contests/abc199/submissions/22038994 問題文を実装しよう。 言語によるが累乗をサポートしていない場合は、普通に掛け算に直して計算する。 特に気を付ける所はない。 自分が…

Max Matrix [第二回日本最強プログラマー学生選手権 F]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_f 前提知識 BIT 座標圧縮 解説 https://atcoder.jp/contests/jsc2021/submissions/21832371 クエリ問題に対する取り組み方というのはそれほど多くない。 今回の問題は差分計算をする問題である。 差分計…

Level K Palindrome [第二回日本最強プログラマー学生選手権 E]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_e 解説 https://atcoder.jp/contests/jsc2021/submissions/21831951 実装が爆発して、実装の手直しをあきらめてしまった。 理論を記しておくので参考程度で。 何から手を付けるか 情報量が多く、何から始…

Nowhere P [第二回日本最強プログラマー学生選手権 D]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_d 解説 https://atcoder.jp/contests/jsc2021/submissions/21831261 まず、109+7 modライブラリを持ってない場合はAtCoder Libraryを使おう。 今回の問題はNもPも上限が109(intの最大を狙って良く使われ…

Max GCD 2 [第二回日本最強プログラマー学生選手権 C]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_c 解説 https://atcoder.jp/contests/jsc2021/submissions/21830976 問題で要求されているx,yを全列挙する方針は1010通りを超えてしまうのでこれはできない。 何か別の視点で考えることはできないか。 答…

Xor of Sequences [第二回日本最強プログラマー学生選手権 B]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_b 解説 https://atcoder.jp/contests/jsc2021/submissions/21830500 判定方法は色々あるが、自分の実装では1つのmapに入れて個数を数えることにした。 1つのmapに入れて集計をすると、 0個 -> どちらにも…

Competition [第二回日本最強プログラマー学生選手権 A]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_a 解説 https://atcoder.jp/contests/jsc2021/submissions/21830396 1gあたりの価格が安くなるようにすればいいので、式としては ans / Z < Y / X が満たれればいい。 変形すると、 ans < ZY / X とな…

Unique Color [AtCoder Beginner Contest 198 E]

https://atcoder.jp/contests/abc198/tasks/abc198_e 前提知識 dfs 解説 https://atcoder.jp/contests/abc198/submissions/21691565 競技プログラミングの問題で木を題材とした問題が多く存在する。 どのようにプログラミングするとよいかは人それぞれかと思…

Send More Money [AtCoder Beginner Contest 198 D]

https://atcoder.jp/contests/abc198/tasks/abc198_d 解説 https://atcoder.jp/contests/abc198/submissions/21692252 覆面算のソルバーを普通に作る。 各文字にその数字を割り当てるかを全探索で決めていこう。 各文字にどの数字を割り当てるかということを…

Compass Walking [AtCoder Beginner Contest 198 C]

https://atcoder.jp/contests/abc198/tasks/abc198_c 解説 https://atcoder.jp/contests/abc198/submissions/21692994 小数でよくある誤差に気を付けた実装をしていたらバグり散らかしてしまったが、 そこら辺を全く考えないコードでリライトしたら通った。 …

Palindrome with leading zeros [AtCoder Beginner Contest 198 B]

https://atcoder.jp/contests/abc198/tasks/abc198_b 解説 https://atcoder.jp/contests/abc198/submissions/21693209 回文であることをいかに判定するか 計算量が厳しくなければ数字を文字列にして、コピーしたものをひっくり返して一致するか試すのが簡単…

Div [AtCoder Beginner Contest 198 A]

https://atcoder.jp/contests/abc198/tasks/abc198_a 解説 https://atcoder.jp/contests/abc198/submissions/21693353 本番はサンプルケースと難易度を見てエスパーして解いたが、理屈を再考しておく。 まず、A君とB君のお菓子の個数の和はNになるので、片方…

Wave a flag [picoCTF 2021]

調査 実行して色々やるっぽかったが、以下ツールでサクッと解析してしまった。 「青い空を見上げればいつもそこに白い猫」のススメ - Speaker Deck 「文字コード別文字列抽出」を使うとフラグが得られる

Tab, Tab, Attack [picoCTF 2021]

調査 zipが与えられるので、解凍していく。 するとフォルダが何層にもなっているので、潜っていくとfang-of-haynekhtnametというファイルがある。 これを以下ツールの「文字コード別文字列抽出」で解析するとフラグが得られる。 [「青い空を見上げればいつも…

Super Serial [picoCTF 2021]

調査 普通のログイン画面。 特に何もないな… こういう時はrobots.txtだな。 User-agent: * Disallow: /admin.phps /admin.phpsへアクセスしてみると404。 そもそも何なんだろう。 PHPを利用するためのApacheの設定 | XAMPPの使い方 なんかOfficialなドキュメ…

Static ain't always noise [picoCTF 2021]

調査 バイナリ解析して色々やるっぽかったが、以下ツールでサクッと解析してしまった。 「青い空を見上げればいつもそこに白い猫」のススメ - Speaker Deck 「文字コード別文字列抽出」を使うとフラグが得られる

Some Assembly Required 1 [picoCTF 2021]

調査 フラグっぽいのを入力すると判定してくれるサイト。 ソースを見ると難読化jsだった。 ふーむ 難読化がふくざつーと思ったが、wasmが置いてあった。 中を見るとリテラルが丸見えになっていて、フラグが書いてある

Scavenger Hunt [picoCTF 2021]

調査 画面遷移が発生しない。jsか。 Chrome Developer Toolsを開いて色々見てみる。 フラグがちりばめられていた。 / -> myjs.js -> /* How can I keep Google from indexing my website? */ mycss.css -> /* CSS makes the page look nice, and yes, it al…

Obedient Cat [picoCTF 2021]

表層調査 「青い空を見上げればいつもそこに白い猫」のススメ - Speaker Deck このような素晴らしいツールを発見したので、これに与えられたファイルを食わせて解析する。 「文字コード別文字列抽出」を使うとフラグが得られる。

Nice netcat... [picoCTF 2021]

調査 netcatしなさいと書かれているので、とりあえずやる。 > nc mercury.picoctf.net 22342 112 105 99 111 67 84 70 123 103 48 48 100 95 107 49 116 116 121 33 95 110 49 99 51 95 107 49 116 116 121 33 95 53 102 98 53 101 53 49 100 125 10 これをC…

Most Cookies

| 150 points Tags: AUTHOR: MADSTACKS Description Alright, enough of using my own encryption. Flask session cookies should be plenty secure! server.py http://mercury.picoctf.net:35697/ 調査 適当にCookieの名前を入れてみる。 pythonコードを見…

Magikarp Ground Mission [picoCTF 2021]

SSH接続する 以下コマンドを使いながらフラグを集めていくと、最終的なフラグが手に入る。 - ls: ディレクトリに含まれるファイル・フォルダの列挙 - cat: 指定ファイルの中身を出力 - cd: 指定ディレクトリへ移動 ctf-player@pico-chall$ ls 1of3.flag.txt …

It is my Birthday [picoCTF 2021]

調査 ファイルをアップロードできるので、画像をuploadしてみる。 small.pngを上げるとNot a PDF!と来た。 ネットから小さいPDFを2つ持ってきて渡すとMD5 hashes do not match!と来る。 全く同じファイルを渡すとFiles are not different!となる。 どっかで…

GET aHEAD [picoCTF 2021]

調査 とても目に悪い赤青のサイトが出てくる。 ボタンを押すと背景色が変わるがどうやっているんだろうか。 現地調査もほどほどにしてProxyの履歴を見てみる。 どうやって色を変えている? GET,POSTで色を変えているように見える。 他のMethodではどうだろう…

Cookies [picoCTF 2021]

| 40 points Tags: AUTHOR: MADSTACKS Description Who doesn't love cookies? Try to figure out the best one. http://mercury.picoctf.net:21485/ 調査 適当に打ってみるが、ないと言われる。 試しにdefaultで表示されている「snickerdoodle」をやってみ…