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

hamayanhamayan's blog

2020-02-01から1ヶ月間の記事一覧

Pairs [AtCoder Beginner Contest 155 D]

https://atcoder.jp/contests/abc155/tasks/abc155_d 前提知識 二分探索 尺取り法 解説 https://atcoder.jp/contests/abc155/submissions/10163251 競技プログラミングに慣れている人は、全通りのK番目を答えよと言われたら真っ先に二分探索かなと思う。 get…

Poll [AtCoder Beginner Contest 155 C]

https://atcoder.jp/contests/abc155/tasks/abc155_c 解説 https://atcoder.jp/contests/abc155/submissions/10161782 文字列をそれぞれ数えて、一番頻度の高いやつをまとめて答えるという問題。 指示されていることを実装するのだが、c++であればmapを使う…

Papers, Please [AtCoder Beginner Contest 155 B]

https://atcoder.jp/contests/abc155/tasks/abc155_b 解説 https://atcoder.jp/contests/abc155/submissions/10161046 全部の整数のうち、条件を満たさないものがあるかを判定する。 条件を満たさないものは、偶数であるが、3でも5でも割り切れないことにな…

Poor [AtCoder Beginner Contest 155 A]

https://atcoder.jp/contests/abc155/tasks/abc155_a 解説 https://atcoder.jp/contests/abc155/submissions/10160560 「かわいそう」である条件は、数が2種類しかないという条件にしても問題ないことが分かる。 数の種類数を手軽にカウントするにはsetに入…

最長増加部分列の数え上げ [yukicoder 992]

https://yukicoder.me/problems/no/992 前提知識 座標圧縮 LIS セグメントツリー 解説 https://yukicoder.me/submissions/430662 Aに負の数が入っているのは、ちょっと面倒な気がする。 かつ、配列Aは実際の値は特に重要ではなく、数の大小だけが問題なので…

N×Mマス計算(Kの倍数) [yukicoder 990]

https://yukicoder.me/problems/no/990 前提知識 最大公約数、約数列挙 解説 https://yukicoder.me/submissions/430660 opが和と積で場合分けして考える。 opが和の場合。 A[i]について全探索しよう。 mo = A[i] % Kとすると、B[j]%K=(K-mo)%Kを満たすB[j]の…

N×Mマス計算(K以上) [yukicoder 989]

https://yukicoder.me/problems/no/989 前提知識 二分探索 解説 https://yukicoder.me/submissions/430655 どこから手を付けようかという感じだが、何かを全探索して解きたいところ。 A[i]について全探索したときに、条件を満たすB[i]の個数が高速に計算でき…

N×Mマス計算(総和) [yukicoder 988]

https://yukicoder.me/problems/no/988 解説 https://yukicoder.me/submissions/430654 すべての要素について計算することはできない。 場合分けをして、それぞれで効率な解き方をやろう。 opが和の場合。 主客転倒テクを使う。 すべての組み合わせを列挙す…

N×Mマス計算(基本) [yukicoder 987]

https://yukicoder.me/problems/no/987 解説 https://yukicoder.me/submissions/430653 すべての要素を愚直に計算しても、104通りなので行っても問題ない。 注意点としては、積の場合はlong longでやらないと、オーバーフローする。 int N, M; char op; ll B…

Add [yukicoder 982]

https://yukicoder.me/problems/no/982 解説 https://yukicoder.me/submissions/428751 A=1、または、B=1の場合は全部作れるので、0となる。 2≦gcd(A,B)の場合は、作る数は全てその倍数になるので、無限に作れない数があり、-1。 それ以外のパターンを考える…

Many Many Paths [AtCoder Beginner Contest 154 F]

https://atcoder.jp/contests/abc154/tasks/abc154_f 前提知識 2次元累積和の考え方 mod素数上での二項係数 解説 https://atcoder.jp/contests/abc154/submissions/10005470 問われているのは、ある矩形区間での総和であるが、変数が4つもあるのは扱いにくい…

Almost Everywhere Zero [AtCoder Beginner Contest 154 E]

https://atcoder.jp/contests/abc154/tasks/abc154_e 前提知識 [桁DP](https://www.hamayanhamayan.com/entry/2017/04/23/212728 解説 https://atcoder.jp/contests/abc154/submissions/10002125 数がとても大きい上に、個数計算とのことなので桁DPをしよう…

Dice in Line [AtCoder Beginner Contest 154 D]

https://atcoder.jp/contests/abc154/tasks/abc154_d 前提知識 期待値の線形性 解説 https://atcoder.jp/contests/abc154/submissions/10001499 期待値の線形性というのがある。 それぞれのサイコロは独立に期待値を考えることができるので、合計の期待値は…

Distinct or Not [AtCoder Beginner Contest 154 C]

https://atcoder.jp/contests/abc154/tasks/abc154_c 解説 https://atcoder.jp/contests/abc154/submissions/10000046 ある数列が全て異なる数であることを判別するには色々方法がある。 データ構造を使うやり方であれば、setを使うのがいいだろう。 setに全…

I miss you... [AtCoder Beginner Contest 154 B]

https://atcoder.jp/contests/abc154/tasks/abc154_b 解説 https://atcoder.jp/contests/abc154/submissions/9999489 Sの全ての文字をxに置き換えて出力するが、 言い換えると、Sの文字数分xを出力すればいい。 個数を数えて、その数だけxを出力しよう。 str…

Remaining Balls [AtCoder Beginner Contest 154 A]

https://atcoder.jp/contests/abc154/tasks/abc154_a 解説 https://atcoder.jp/contests/abc154/submissions/9999194 文章が等しいものがあれば個数を減らす必要があるので、 S=UであればA--、T=UであればB--をしてA,Bを答えよう。 string S, T; int A, B; s…

picoCTF2019 Web問題 全編解説

picoCTF2019 中高生向けの教育的コンテスト そのうちWeb関連の問題を全て解いて(最後の最後だけギブ…)解説をまとめた。 picoCTFサイトにもHintはあるし、以下の要求知識もHintにしながらまずは解いてみるといいと思う。 自分も勉強しながら解いた。全体的…

cereal hacker 2 [picoCTF 2019 Web 500]

https://ctftime.org/task/9491 前提知識 ディレクトリトラバーサル、LFI(:Local File Inclusion) Blind SQL Injection 解説 (実は最後まで解けてない) guest:guestは削除されている。 ディレクトリトラバーサルの出番。 その一部のLFIというタイプ。 Loca…

Empire3 [picoCTF 2019 Web 500]

https://ctftime.org/task/9490 前提知識 SQLi Flaskのセッション偽装 解説 今までの脆弱性は塞がれている。 Cookieにあるセッション情報を復元してみると、user_idが変更できそう。 ここに再署名のやり方が書いてある。 {{ config.items() }}とTODOに入れて…

cereal hacker 1 [picoCTF 2019 Web 450]

https://ctftime.org/task/9493 前提知識 SQLi 解説 guest:guestで実はログインできる。 クッキーに謎の文字列があるので、2回URLデコードをしてbase64decodeすると、それっぽいものが出てくる。 adminでログインしたいので、usernameをadminにして、base64e…

Java Script Kiddie 2 [picoCTF 2019 Web 450]

https://ctftime.org/task/9501 前提知識 javascript読解 バイナリに対する導入知識 解説 javascriptが変わっているが原理は同じなので読み直す function assemble_png(u_in){ var LEN = 16; var key = "00000000000000000000000000000000"; // 32桁になって…

Empire2 [picoCTF 2019 Web 400]

https://ctftime.org/task/9498 前提知識 Flask (SSTIの代表格?) SSTI: Server-Side Template Injection base64, url-encoding 解説 先程の脆弱性は修正されているようだ。 問題文にXX is passing secrets around when you log inと挑戦的なことが書いてあ…

Java Script Kiddie [picoCTF 2019 Web 400]

https://ctftime.org/task/9502 前提知識 バイナリデータに関する導入知識 解説 ソースをチラッと見ると、与えられたキーを元にバイト列を生成している。 形式はimage/pngになっているので、先頭がPNGのヘッダーとなるように調整すれば良さそう。 バイナリデ…

JaWT Scratchpad [picoCTF 2019 Web 400]

https://ctftime.org/task/9874 前提知識 JWT John The Ripper 解説 adminではもちろん入れない。 どこから攻めるかという感じだが、JWTがなんだか強調されているので、Cookieを見てみると、JWTが入ってる。 中をここで見てみると、HS256でハッシュ化されて…

Irish-Name-Repo 3 [picoCTF 2019 Web 400]

https://ctftime.org/task/9547 前提知識 SQLi(SQLインジェクション) 解説 こちらはパスワードしかない。 そう言えばhidden属性でdebug=0というのをPOSTで送っていたので、これを1にしてみると実行クエリが表示される。 試すと以下の通り。 <pre>password: fd SQL</pre>…

Empire1 [picoCTF 2019 Web 400]

https://ctftime.org/task/9499 前提知識 SQLi(SQLインジェクション) 解説 利用者登録をしてTODOリストを表示する問題。 既視感はある。 解いた事のある方針で考えると、うまいことやって自分のTODOリストに他の人のTODOを表示させる。 問題を起こさせること…

Irish-Name-Repo 2 [picoCTF 2019 Web 350]

https://ctftime.org/task/9546 前提知識 SQLインジェクション 解説 前の問題のペイロードを試すと、SQLinjectionが検知されてしまう。 メッセージで出している所を見ると、判定関数を噛ませてあるのだろう。 何で引っ掛けているか分からないが、判定関数を…

Irish-Name-Repo 1 [picoCTF 2019 Web 300]

https://ctftime.org/task/9545 前提知識 SQLインジェクション 解説 問題文にTry to see if you can login!とあるので、ログインを頑張る。 ログイン時のExploitといえばSQL Injectionなので、まずはそれをやってみる。 Supportページを見ると、'が含まれる…

picobrowser [picoCTF 2019 Web 200]

https://ctftime.org/task/9667 前提知識 User Agent偽装 解説 ウェブサイトがブラウザを判別する方法はUser Agentなので、 ここにpicobrowserを入れるとフラグが出てくる。 Chromeであれば標準のDeveloper Toolで偽装が可能。 (しかも簡単!)

Open-to-admins [picoCTF 2019 Web 200]

https://ctftime.org/task/9568 前提知識 Cookieの編集方法 解説 adminが要求されているが、何もできない雰囲気がある。 問題が以下になっている。 This secure website allows users to access the flag only if they are admin and if the time is exactly…