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

hamayanhamayan's blog

2018-11-01から1ヶ月間の記事一覧

expression [Kaspersky Industrial CTF Web 50]

https://ctftime.org/task/7103これはコマンドインジェクションと呼んでいいの? 強いCTFerに教えてほしい。 解説 参考にした解説 1 2 3「1+2」とやると、Tokenが出てくる。 Token: TzoxMDoiRXhwcmVzc2lvbiI6Mzp7czoxNDoiAEV4cHJlc3Npb24Ab3AiO3M6Mzoic3VtIj…

Coins on the tree [CODE THANKS FESTIVAL 2018 F]

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_f 前提知識 構築問題テク『「条件を満たす辞書順最小」頭から貪欲に整合性が保たれるように決めていく』 (部分永続のやり方 ←これは実装をうまくやれば…

Union [CODE THANKS FESTIVAL 2018 E]

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_e 前提知識 動的計画法 解説 https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3664663DPをする。 dp[i][j] := 整数iまで…

Concatenation [CODE THANKS FESTIVAL 2018 D]

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_d 解説 https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3664721提出証明みたいな所があるが、貪欲で解く。 説明のため「…

Pair Distance [CODE THANKS FESTIVAL 2018 C]

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_c 解説 https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3664421競プロでよくあるテクとして、「絶対値は扱いにくいので…

Colored Balls [CODE THANKS FESTIVAL 2018 B]

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_b 解説 https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3664345 結構難しい問題に見える 200点問題 制約もでかい という…

Two Problems [CODE THANKS FESTIVAL 2018 A]

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_a 解説 https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3664295選択肢が「1問目のみ」「2問目のみ」「どちらも」「解か…

Square Rotation [Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 D]

https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_d 解説 https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3665682公式解説 公式解説放送公式放送、公式解説通りに実装した解法を紹介する。 ただ、時間が結構…

k-DMC [Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 C]

https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_c 前提知識 しゃくとり法 考察過程 1. 制約を見るとO(QN)な感じがする 2. O(N)でアルゴリズムを考えたときに運良くしゃくとり法がしゅっとでた 3. その方針で考えるとAC 解説 h…

Sum AND Subarrays [Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 B]

https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_b 解説 https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3660039まず、空でない連続する部分列は全列挙可能なのでやる。 本当に愚直にやるとO(N^3)掛かるが、…

Thumbnail [Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 A]

https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_a 解説 https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3659999問題で指定されていることをやる。 だが、実際に平均を出すと、誤差が怖いので、比較するとき…

チップ・ストーリー ~白銀編~ [DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 C]

https://beta.atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_c 解説 https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3650243条件を整理しよう 数列の値は全て自然数 各チップ(i,j)にP[i]*Q[j] 各チップの値は1以上N以下 2,3番目の条…

チップ・ストーリー ~漆黒編~ [DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 B]

https://beta.atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_b 解説 https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3650234ok[y][x] := 座標(x,y)が真っ黒か というのを用意して、真っ黒でない領域を消していくことを考えよう。 左…

チップ・ストーリー ~無色編~ [DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 A]

https://beta.atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_a 解説 https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3650208答えは4^Nとなる(4のN乗の意味)。 実装しよう。 int N; //-------------------------------------------…

Lost Root [Codeforces Round #523 (Div. 2) F]

http://codeforces.com/contest/1061/problem/FN頂点の完全K分木がある。 この木について 「? a b c」頂点a,c間に頂点bがあるか 「! s」頂点sが木の根であると答える というクエリが60*N回までできる。 正しく根を答えよ。 前提知識 乱択アルゴリズム 解説 h…

TV Shows [Codeforces Round #523 (Div. 2) D]

http://codeforces.com/contest/1061/problem/DN個のテレビ番組がある。 i番目はL[i]~R[i]分放送している。 最初はテレビを持っていないが、テレビ1つを初期投資X円、1分につきY円の料金で借りられる。 全てのTV番組を見るためにテレビを適切に借りた時の値…

Multiplicity [Codeforces Round #523 (Div. 2) C]

http://codeforces.com/contest/1061/problem/CN個の配列Aがあり、ここから(連続してなくてもいい)部分列を取ったものを配列Bとする。 配列Bは全てのiについて、B[i]がiで割り切れるときに良い配列とされる。 全ての部分列について良い配列であるのは何通…

Views Matter [Codeforces Round #523 (Div. 2) B]

http://codeforces.com/contest/1061/problem/B横Nマス、縦Mマスの盤面がある。 各列A[i]個のマスが下詰めで塗られている。 これを上から見た眺めと横から見た眺めがどちらも変わらないように塗られているマスを消す。 最大何マス消せるか。 解説 http://cod…

Coins [Codeforces Round #523 (Div. 2) A]

http://codeforces.com/contest/1061/problem/A1円、2円、…N円のコインがそれぞれ無限個ある。 総和がS円となるようにコインを選んだ時の最小枚数は? 解説 http://codeforces.com/contest/1061/submission/46065343なるべく高いコインを使うほうがいい。 な…

RITSEC CTF 2018 Web問題 Write-up

もたもた復習してたら、サイトが閉じてしまった [100] Space Force fun.ritsec.club:8005から抜き出す。解説1 解説2SQLインジェクションをする。 「'=''or'」と「'/**/union/**/select/**/*/**/from/**/spaceships#」がペイロードとして紹介されている。 「'…

Tough Journey [CODE FESTIVAL 2018 Final E]

https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_e 解説 https://beta.atcoder.jp/contests/code-festival-2018-final-open/submissions/3623338見方を変えて解く。 ある街で飲むペットボトルをどこで買う…

Three Letters [CODE FESTIVAL 2018 Final D]

https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_d 解説 https://beta.atcoder.jp/contests/code-festival-2018-final-open/submissions/3622829O(90000*52*52)を目指す。 まず、encode関数を用意して、全…

Telephone Charge [CODE FESTIVAL 2018 Final C]

https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_c 解説 https://beta.atcoder.jp/contests/code-festival-2018-final-open/submissions/3610538条件で「全てのプランiに対して、通話時間がA[i]分の場合に…

Theme Color [CODE FESTIVAL 2018 Final B]

https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_b 解説 https://beta.atcoder.jp/contests/code-festival-2018-final-open/submissions/3622296まず、確率pの式を立てよう。 分母はM通りがN個分あるので、…

2540 [ CODE FESTIVAL 2018 Final A]

https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_a 解説 https://beta.atcoder.jp/contests/code-festival-2018-final-open/submissions/3622174条件が a<c a != b b != c を満たす(a,b,c)となっているが…

Number of Amidakuji [AtCoder Beginner Contest 113 D]

https://beta.atcoder.jp/contests/abc113/tasks/abc113_d 前提知識 https://www.hamayanhamayan.com/entry/2017/02/27/021246:titie=動的計画法 解説 https://beta.atcoder.jp/contests/abc113/submissions/3558659dpで解く。 1,2,3,...,W本目ではなく、0,1…

ID [AtCoder Beginner Contest 113 C]

https://beta.atcoder.jp/contests/abc113/tasks/abc113_c 解説 https://beta.atcoder.jp/contests/abc113/submissions/3558586流れは以下の通り。 1. 県ごとに市を分ける 2. 県ごとに市の誕生年でソートし、順番に認識番号を作る 3. 最後に順番に答えていく…

Palace [AtCoder Beginner Contest 113 B]

https://beta.atcoder.jp/contests/abc113/tasks/abc113_b 解説 https://beta.atcoder.jp/contests/abc113/submissions/3558578温度がT-H[i]*0.006であり、小数になる可能性があるので、doubleで計算していこう。 全ての高さについて全探索しよう。 温度差は…

Discount Fare [AtCoder Beginner Contest 113 A]

https://beta.atcoder.jp/contests/abc113/tasks/abc113_a 解説 https://beta.atcoder.jp/contests/abc113/submissions/3558553答えはX+Y/2になる。 計算して求めよう。 今回の問題では大丈夫だが、整数の割り算をするときは小数点以下切り捨てになることを…