やむなく日記

競プロやCTF、ゲームなどの日記を書きます

模擬国内予選 2020 参加記

前日13:00~14:00 PGバトル

時間はかかったが満点を取れたのでチームの信頼を維持

前日14:00~16:00 BGA

SOLOとパパヨーと東海道をした記憶がある

前日 16:00~21:00 睡眠

前日 21:00~23:00 ARC106

フローを流すことにこだわったら冷えた

前日23:00~当日3:00 among us

初プレイ、インポスターがむずすぎる

当日 3:00~10:00 起きている

何してたっけ？最近こういう時間が多くて何もできない

当日 10:00~13:30 睡眠

起きて起床確認をしたら heno 君が寝ている

当日 14:00 コンテスト開始

ゆっくり準備してたら数分遅刻した、いくぜ！

遅刻してたので A は moririn 君に任せた

B

爆破できる爆弾があれば爆発範囲をみて、まだ爆破できないと思っていた爆弾があれば爆破できることにする

UnionFind を考えたが書かなくても解けるっぽいので切り捨てる（後から考えると、爆弾のペアを全部チェックしても間に合うので、こっちのほうが楽そう）

なんか初期地点の爆弾しかチェックしないバグを埋め込んだけど直して AC

B をやってる間に A が通ってるので C を moririn 君に任せる

D

こういうのは両端に括弧をつけるのが一番いいってのを信じる

列を左から見ていって必要になったら左に(を付け加える、これを逆からもやればなんか通るやろと思って書く

WA

バグがあったので直してまた提出

WA

出力をよく見たら1回目と2回目で内容が変わっていなかったらしい、diffをちゃんと取りたい

Dを書いてる最中に heno 君が起きてきたので E をやってもらう

問題文を見直すと、()括弧列) が実は invalid で、()())) みたいなので落ちてるっぽいことが発覚

括弧列を挟んだとき、その左右にある)の列はまとめずに別にして処理すればよさそう

書き直して 1 つめのケースが AC

2 つめのケースも AC したが、よく見るとソースコードがちょっと違うと言われている

ソースコードだけ昔のやつを提出していたらしく、新しいものを出しなおす必要がある

2 つめのケースは間違ったソースコードで通してしまったので、もう使えない

もうケースが 2 個しか残ってないので、昔のファイルを全消しして 5 回くらいチェックして提出する、AC

E はにぶたん→実行が終わらない→しゃくとりを経て AC したらしい

まだ C が通ってなくて大変そうだけど、実装が原因だろうし終了までには通るやろと思い任せる

実行を待ってる間に heno 君は F を考えていた

F の実装方針を決める手伝いをする、ダイスライブラリがある heno 君に書いていただく

H

G と H しか残ってなくて、数チームが解いてる H を読む

こうするのが最適って数回言うとシンプルな線形計画になる

フローっぽいけど昨日の ARC があるので流すことにこだわらなかった

見方を変えると DP っぽいのが浮かび上がってきたので書く

書いてる間に F が通ってすごかったので、heno 君に C のサポートをやってもらう

H が書き終わるがサンプルが合わない

辺の向きを逆にしたら合ったので提出してみると AC

C も AC したらしい、ナイス～

残りは G

幾何の実装はしたことがないので、heno 君に書いていただく

その間サンプルをひたすら作った

頂点間以外の移動が大変らしくて間に合わず…

 

f:id:yamunaku:20201026092845j:plain

ペナルティ42185 秒の重量感を漂わせながら、7 完で 5 位

 

反省

ちゃんと寝る

前日にチームメイトにリマインダを送る

問題文をちゃんと読む

古い解答は消す、必要なら別のとこに保存する

再提出では解答の diff を取ってみる

C を見ずに H を解きに行ったのはリスクが大きすぎた

コマンドプロンプトが使いにくいので WSL を入れた

幾何の訓練をいつかやりたい

JOI2019/2020 本選 問題4 オリンピックバス (Olympic Bus) をΟ((M+N)logM+N^3)で解く

公式解説が出るまでの気休め

問題概要

N 頂点 M 辺からなる有向グラフが与えられる。頂点には 1 から N までの番号がついている。 i 番目の辺は頂点  u_i から v_i への辺で、長さは c_i 、重みは d_i である。次の操作を高々 1 回だけ行える。

  • 整数 i を 1 つ選んで、 i 番目の辺の向きを逆にする。コストを d_i 払う。

操作の後、次で定義されるコストを払う。

  • 頂点 1 から頂点 N までの最短距離と、頂点 N から頂点 1 までの最短距離の和
  • ただし、経路がない時のコストは  \infty である。

払うコストの最小値を求めよ。

制約

  • 2 \le N \le 200
  • 1 \le M \le 50000
  • 0 \le c_i \le 10^6
  • 0 \le d_i \le 10^9

 

解法

どの辺も逆にしないときのコストは普通に求まる。

辺 i を逆にしたときのコストを、すべての i について求めればよい。

辺 i を逆にしたときの 1 → N の距離と N → 1 の距離を、別々に求めることにする。 1 → N が求まるなら、同じようなことを N → 1 に対して行えばよいから、前者の場合だけを考える。

どの辺も逆にしないときの 1 → N の距離 D を求めておく。辺 i を逆にしたときの 1 → N の距離  D_i は、 D より小さくなるか、 D より大きくなるか、 D と等しい、のいずれかを満たす。

距離  D_i が D より小さくなる場合の検出

辺 i を逆にして新たに発生する経路の中で最短なものは、 1 → v_i の最短経路、 v_i → u_i の辺 i 、 u_i → N の最短経路を順につなげたものである。この経路の距離 D_{new} を求めたい。

辺 i を消したときの 1 → v_i の距離 D_{1v_i} と u_i → N の距離 D_{u_iN} が求まっていれば、 D_{new} = D_{1v_i}+c_i+D_{u_iN} と求めることができる。この D_{new} が D より小さいときのみ、最短距離が小さくなって、 D_i = D_{new} となる。

辺 i を消したときの D_{1v_i} と D_{u_iN} を求めなければならないが、これはもとのグラフで頂点 1 および頂点 N からダイクストラをすることで、すべての i について D_{1v_i}^* および D_{u_iN}^* をまとめて求めることができる。

こうやって求めた D_{1v_i}^*, D_{u_iN}^*, D_{new}^* には、辺 i (向きを逆にしていないもの)を経路に使ってしまっている場合があるが、この場合は D_{new}^* \geq D となり、影響がない。なぜなら、例えば D_{1v_i}^* の計算で辺 i を使ってしまった場合、 D_{1v_i}^*=D_{1u_i}+c_iであり、 D_{1u_i}+D_{u_iN} \geq D であるから、

D_{new}^* = D_{1v_i}^*+D_{u_iN}+c_i = D_{1u_i}+D_{u_iN}+2*c_i \geq D

となる。したがって、 D_i の計算には影響を与えないことがわかる。

辺 i を使わない条件のもとでの 1 → v_i の距離を D_{1v_i} とすると、 D_{1v_i} \geq D_{1v_i}^* であり、辺 i (向きを逆にしていないもの)を使わない本来求めるべき D_{new} について、 D_{new} \geq D_{new}^* である。つまり、辺 i (向きを逆にしていないもの)を使ってしまったときは、 D_{new} が D より小さくならないために、距離が小さくなる検出をする必要がなく、また異常な値によって D_i を更新することもない。

距離  D_i が D より大きくなる場合の検出

どの辺も逆にしないときの 1 → N の最短経路 Path を1つ選ぶ。

Path に含まれていない辺の向きを逆にしても、距離 D の経路 Path が残っているのだから、 1 → N の距離は D より大きくならない。したがって、 Path に含まれる辺についてのみ、新しい最短距離を計算すればよい。

Path に含まれる辺 i を逆にした場合について考える。辺 i を逆にすると、 Path は 2 つに分断されて、パス Q = (1 \rightarrow \ldots \rightarrow u_i) とパス R = (v_i \rightarrow \ldots \rightarrow N) に分かれる。パス Q に含まれる頂点集合を U 、パス R に含まれる頂点集合を V とおく。パス Q は 1 → ( U  内の頂点) の最短経路を含んでいて、パス R は ( V  内の頂点) → N の最短経路を含んでいることがわかる。(そうでないと、 Path が最短経路でなくなる)

新しい 1 → N の最短経路は、 Q の一部を通った後、 Path に含まれない辺をいくつか経由して、 R の一部を通るような経路であることを示せる。 1 → N のどの経路  X についても、最後に訪れた U 内の頂点 x と、 x よりも後に訪れた頂点の中で、最初に訪れた V 内の頂点 y がある。パス Q には 1 → x の最短経路が、パス R には y → N の最短経路が含まれているのだから、 Q の一部を通って頂点 x に移動し、 Path に含まれない辺を X の通りにいくつか経由して頂点 y に移動し、 R の一部を通って頂点 N に移動するような経路を考えると、この経路の距離はパス X の距離以下であるからだ。

Q の一部を通るときに最後に訪れる頂点 x \in U と、 R の一部を通るときに最初に訪れる頂点 y \in V を固定する。 1 → x の距離  D_{1x} と、 y → N の距離  D_{yN} は、事前に計算しておける。 Path に含まれない辺をいくつか経由して頂点 x から頂点 y に移動する部分の最短距離を  D_{xy} とすると、新しい最短距離は、 \min_{(x,y)} \{ D_{1x}+D_{xy}+D_{yN} \}である。 D_{xy} は、以下のようにして求めることができる。

元のグラフから Path に含まれる辺をすべて取り除く。このグラフにおいて、ワーシャルフロイドを用いれば、すべての (x,y) の組について、最短距離 D_{xy} をまとめて計算できる。また、この結果は Path 内のどの辺 i についても使いまわすことができる。つまり、ワーシャルフロイドを行う回数は 1 回だけでよい。

  Path 内の各辺 i について、ありうる (x,y) の組をすべて試していっても Ο(N^3) しかかからない。

距離  D_i が D と等しい場合の検出

上の 2 つを行って、距離が小さくも大きくもならない場合は D_i=D である。

 計算量

ダイクストラを 4 回、ワーシャルフロイドを 2 回行えば解けて、計算量は Ο((M+N) \log M+N^3) である。

 

考察めっちゃつらいし実装がしんどすぎる

 

提出

オープンのコードをそのまま提出した

リファクタリングはしたくない

atcoder.jp

 

AOJ 暗号化システム

問題URL

https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim/1195

 

感想

これめっちゃ難しく考えてしまった…

 

各文字は1回しか変わらないから異なる文字列は高々2^20個しか登場しない

 

与えられた文字列から逆の操作をして、もとの文字列へ復元したい

逆の操作で作れる文字列を全列挙していけばいいとなって泥沼にはまった…

 

[いらなかった考察]

与えられた文字列をtとして、もとの文字列をsとする

i番目の文字s[i]をt[i]からt[i]-1に変更できる条件は、s[j]==t[i]であるすべての j (i<j)についてs[j]は変更済み(すなわちt[j]==t[i]+1)であること

s[i]をt[i]のままにできる条件は、s[j]がt[i]-1である j (j<i)が存在して、s[j]は変更済み(すなわちt[j]==t[i])であること

逆の操作で作れた文字列とその各文字を変更したかどうかのフラグをペアにして、setとかに入れて管理すればなんとかできる

[考察ここまで]

この考察は記事にするときに一度整理されたもので、解いている間は1番から逆の操作をやってみたり、各位置の文字がそれぞれ1度しか変更されないことを意識できに復元中の文字列sの文字種だけに注目していたりと破滅していた

 

ググったら何も考えなくても解ける賢い方法が出てきて、2^20通りの文字列すべてを暗号化して、与えられたものと一致するか見ていけばいいらしい

やられた

(CodeChef December Challenge 2018) Colorblind Feast

問題概要

Contest Page | CodeChef

あなたは空の配列と定数Kを持っている。以下のクエリをQ個処理せよ。

  • 1 c d : [更新クエリ] 先頭に色c, よさdのモノを追加する
  • 2 c d : [更新クエリ] 末尾に色c, よさdのモノを追加する
  • 3 c : [質問クエリ] 現在の配列から色が[c-K,c+K]内にあるモノだけを残して、それ以外を取り除き、空いたところを詰める。残ったモノのよさdの区間和の最大値を求め、取り除いたモノを元に戻す。

制約

1 <= Q <= 2*10^5

1 <= c,K <= 10^9

|d| <= 10^3

cの値は直前の質問クエリの答えがわからないと求められない

 

解法

問題で与えられた通りの配列をそのまま持つと質問クエリで時間がかかってしまう。

 

まず、色を無視して、配列の区間和の最大値を高速に求めることを考えてみる。

先頭にモノを追加したとき、区間和の最大値はどう変化するか？

変化するとすれば、その値は、先頭に追加したモノを含む区間の和の最大値になるはず。

そこで、追加前の区間和最大値ansと、追加前の先頭から連続した区間の和の最大値frontmaxの情報を持っていれば、

ans = max(ans, d+frontmax)

frontmax = max(d+frontmax, d)

というように更新できる。

末尾に追加する場合は、追加前の末尾から連続した区間の和の最大値backmaxを持っていればよい。

これによって、配列の中身をそのまま持つことなく、時間Ο(1),空間Ο(1)で区間和最大値を求めることができる。

 

区間和最大値をこのように更新していくためには、それぞれの質問クエリに関係ないモノをそれぞれ無視しなければならない。

つまり、質問クエリの引数それぞれについて上のような情報を持ち、上のような更新を行っていかなければならない。

これを愚直にやっても、更新クエリの数はQ個であるから、Ο(c_max*Q)かかって間に合わない。

色xのモノが影響を与える質問クエリは、引数が[x-K,x+K]内にあるようなクエリのみだから、上のような情報を引数の大小で並べて保持していると、区間に対して更新していくことができる。

セグメント木が使えそう。

 

更新クエリが来たときは区間を更新し、質問クエリが来たときは点が含まれる区間を順に見てansを出力する。

遅延評価のように、区間に対しての更新を考えると、モノはどこかのノードで積もることになる。質問クエリそれぞれについて積もったこれらを1つ1つ順番に追加しているようでは、セグ木を使ってないときと変わらず遅くなってしまうから、モノの列とモノの列を高速にマージしなければならないことがわかる。

これは、ansとfrontmaxとbackmaxのほかに、列全体の和totalを保持しておけば以下のようにマージできる。

列Fの末尾に列Bをマージするとき、

ans = max(ans, F.backmax+B.frontmax)

F.frontmax = max(F.frontmax, F.total+B.frontmax)

F.backmax = max(B.backmax, F.backmax+B.total)

F.total = F.total+B.total

とすればよい。

これによって時間Ο(Qlog(c_max))ですべてのクエリを処理することができる。

両側についてこのように更新を行うセグ木を実装すればよいが、面倒なので、それぞれの側に関してセグ木をもち、質問クエリ処理の最後に双方をマージすることにした。

 

以上より時間は改善できた。が、セグ木の空間Ο(c_max)はやばい。

すべての質問クエリの引数cがあらかじめわかっていれば、座標圧縮すればいいのだが、この問題は前の質問クエリの答えがわかっていないとcがわからない。

10^9個程度の配列はさすがに取れないから悩んでいたが、セグメント木の必要な部分だけのメモリを保持し、それ以外はメモリ取得をサボるというアイデアを知った。

以下の13~14ページ目に記載されている。

プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～

これを自力でいい感じに実装すれば、空間もΟ(Qlog(c_max))となる。

ほんとうは平衡2分木を書かなくちゃならないのかと思っていたが、これのおかげで命拾いした。

 

ソースコード

Solution: 21868813 | CodeChef

 

 

競プロコンテストサイトを7つぐらいまとめる

こんにちは、精進していますか？

KMC1回生のyamunakuといいます。

この記事は KMC Advent Calendar 2018 - Adventar の12日目の記事です。

adventar.org

 

競技プログラミングについて

競技プログラミング（競プロ）とは、「プログラムを書いて、与えられた課題を決められた以上の効率で解決する競技」のことです。

問題を考察し、効率よく解くための手法（アルゴリズム）を考えて、それを素早く正確にプログラムとして記述する能力を競います。

 

この記事について

この記事では、競プロのコンテストサイトを7つぐらいまとめます。

この記事の対象は、競プロに慣れてきたから、今やってるのとは違うコンテストサイトの存在も知りたい、という方です。

競プロを始めたばかりの方や、これから始めたいという方には AtCoder というコンテストサイトを強くおすすめしています。まずはここで練習してみましょう。

本当に初めての方は、[競プロ はじめて] などでググるとよいです。ありがたい導入ブログが数多く見つかります。

 

コンテストサイトの特徴

コンテストの多くは特定のサイトでだいたい定期的に開催されています。

サイトによってその頻度はまちまちですが、今から挙げるサイトは比較的高い頻度でコンテストを開催しています。

それぞれのサイトには様々な特徴があります。共通してみられる特徴についてはここで説明しておきます。

言語

日本以外のサイトで行われるコンテストでは、基本的に現地の公用語と英語だけがサポートされています。また海外コンテストは現地時間に合わせて開催されるので、開催時刻が深夜になることが多いです。

フィードバック
  • フル: 解答提出直後に完全なテストが行われ、すぐに正誤が確定します。
  • 不完全: 解答提出直後は一部のテストが行われるだけで、コンテスト終了後に完全なテストが行われます。
  • なし: コンテスト終了後に初めてテストが行われます。

フィードバックがフルでないときは、コンテスト中に自分のコードの正しさが保証されないので不安になります。コーナーケースをエスパーする力は身に付きます。

解答形式
  • 標準出力: 解答を標準出力します。
  • メソッドの戻り値: 解答をメソッドの戻り値として返します。

メソッドの戻り値として返すタイプでは、コンテストページにコーディング環境が備え付けられていることが多いですが、標準出力を表示する画面がないことがほとんどで、デバッグが非常にやりづらいです。手元の環境で書こうとしても、標準入力に対応しにくい入力形式であることが多く、あまり嬉しくないです。

 

 コンテストサイト紹介

1. AtCoder

beta.atcoder.jp

  • 頻度: 月2~4回
  • 言語: 日本語
  • フィードバック: フル
  • 解答形式: 標準出力

いわずと知れた日本のコンテストサイトです。最近はこのサイトから競プロを始めた方が多いのではないでしょうか。

問題の難易度と配点が紐づいているので、配点を見るとその問題が自分に適したものなのかがわかるのが特徴です。

主に次の3つのコンテストが開催されます。

AtCoder Beginner Contest (ABC)
  • 時間: 100分
  • 問題数: 4問
  • 配点: 傾斜

ほぼ毎週行われる、初めての方向けのコンテストです。

AtCoder Regular Contest (ARC)
  • 時間: 100分
  • 問題数: 4問
  • 配点: 傾斜

競プロに慣れた方向けのコンテストです。

開催されるときはABCと同時開催で、ABCの後半2問がARCの前半2問として、残りの2問はARCオリジナルとして出題されます。

AtCoder Grand Contest (AGC)
  • 時間: 120分
  • 問題数: 6問
  • 配点: 傾斜

初めての方からプロの方まで、幅広い難易度の問題があるコンテストです。

月に1回ほど開催されます。

 

2. Codeforces

codeforces.com

  • 頻度: 月10回程度
  • 言語: 英語
  • フィードバック: 不完全
  • 解答形式: 標準出力

ロシアのユーザ投稿型のコンテストサイトです。

コンテスト回数が非常に多く、コミュニティが活発なことが特徴です。

併設されているブログでアルゴリズムやデータ構造を学んだり、解法の議論を眺めたりすることができます。

レートによって異なるDivisionに振り分けられ、コンテストではそのDivisionにあった問題が出題されます。

主に次の2つのコンテストが開催されます。

Codeforces Round
  • 時間: 120分程度
  • 問題数: 5~7問
  • 配点: 傾斜

各問題の配点は時間が経つごとに減少していきます。

提出した自分の解答が弱めのテストを通過すると、自分の解答をLockできるようになります。

Lockすると解答の再提出ができなくなりますが、他の人が提出したコードを読むことができるようになり、他の人のコードをバグらせる（Hackする）ことで追加の得点を得られます。

Educational Codeforces Round
  • 時間: 120分程度
  • 問題数: 7問
  • 配点: 均等

解答までにかかった時間の合計がペナルティになります。

Hackはコンテスト中にはできず、終了後12時間の間に行えます。しかし、成功しても得点は得られません。

これら以外の企業コンテストなども頻繁に開催されています。

 

3. Topcoder

www.topcoder.com

  • 頻度: 月2回程度
  • 言語: 英語
  • フィードバック: なし
  • 解答形式: メソッドの戻り値

古くからあるコンテストサイトです。

コンテストページまでたどり着くのがむずすぎる

登録した後、[Topcoder Arena] で検索すると、簡単にコンテストページにたどり着けます。

このサイトにも2つのDivisionがあります。

 Single Round Match
  • 時間: 75分
  • 問題数: 3問
  • 配点: 傾斜

75分のCoding Phaseで解答を書きます。

各問題の配点は、その問題のページを開いてから時間が経つと減少していきます。

その後、15分のHacking Phaseで相手の解答をHackし、成功すれば追加の得点を得ることができます。

 

4. CodeChef

www.codechef.com

  • 頻度: 月3回以上
  • 言語: 英語
  • フィードバック: フル
  • 解答形式: 標準出力

インドのコンテストサイトです。

このサイトにも2つのDivisionがあります。

主に次の3つのコンテストが開催されます。

Challenge
  • 時間: 14400分(10日)
  • 問題数: 8問
  • 配点: 均等

マラソン1問とマラソン以外7問が一緒になって出題されます。

コンテスト時間が長い分、歯ごたえのある問題が多いです。

僕も現在このコンテストに挑戦しています。

Lunchtime
  • 時間: 180分
  • 問題数: 5問
  • 配点: 均等

部分点があります。

Cook-Off
  • 時間: 150分
  • 問題数: 5問
  • 配点: 均等

部分点はありません。

これらのコンテストで上位をとったり、皆勤したりするとポイントがたまり、Tシャツやリュックや豪華景品などと交換することができます。

 

5. LeetCode

leetcode.com

  • 頻度: 月4回
  • 言語: 英語
  • フィードバック: フル
  • 解答形式: メソッドの戻り値
  • 時間: 120分
  • 問題数: 4問

毎週日曜日のAM11:30から開催されます。

問題は簡潔で難しくないことが多いですが、デバッグが非常にやりにくいです。

上位をとったり、問題を提供したりするとポイントがたまり、Tシャツと交換することができます。

 

6. YukiCoder

yukicoder

  • 頻度: 月2,3回
  • 言語: 日本語
  • フィードバック: フル
  • 解答形式: 標準出力
  • 配点: 傾斜

日本のユーザ投稿型のコンテストサイトです。

研究的な問題が多いような気がします。

僕はコンテストには参加したことがないので、何も言えません。

 

7. HackerRank

www.hackerrank.com

  • 頻度: 2か月に1回以上
  • 言語: 英語
  • フィードバック: 不明
  • 解答形式: ファイル出力

自分が用意した問題で非公式のコンテストを好きに開くことができることが特徴です。

HourRank
  • 時間: 120分
  • 問題数: 4問

上位に入るとTシャツがもらえます。

僕はコンテストには参加したことがありませんが、練習問題が豊富です。

 

おわり

存在するすべてのコンテストに出ようとすると、生活習慣が乱れます。

 

明日13日のアドベントカレンダーは、pastakさんの「npmモジュールのアップデートを良い感じに楽するためのアイデア」です。

adventar.org

2018 ICPC Asia Jakarta Regional Contest K問題 "Boomerangs"

問題概要

Contest problems

N頂点M辺の無向単純グラフが与えられる。2本の辺からなる集合であり、その2辺が1つの頂点を共有しているものをブーメランと呼ぶ。ブーメランの集合であり、互いに素である、すなわちそれに含まれるどの2つのブーメランも辺を共有しないようなもののうち、要素数が最大であるものを1つ求めよ。

1<=N,M<=10^5

 

解法

各連結成分について以下を行います。

まず初めにすべての辺に適当に向きをつけ、各頂点の出次数を数えてみます。

連結な2頂点で出次数がどちらも奇数のとき、間の辺の向きを逆にすることでどちらも出次数を偶数にできます。

連結な2頂点で出次数が一方だけ奇数のとき、同様に向きを逆にして偶奇を入れ替えることができます。

そこで、グラフ上でDFSをして、行きがけと帰りがけの両方で頂点を見ていき、今訪れている頂点が奇数ならばその次に訪れる頂点との辺の向きを逆にすることを繰り返せば、出次数が奇数である頂点が高々1個(あるとしたらDFSの始点/終点)であるようにできます。

その後、各頂点について、そこから出ていく辺のうち2つを選んでブーメランを作っていくと、[連結成分内の辺数]/2個(切り捨て)のブーメランを作ることができ、これが最適になります。

 

SECCON Beginnersに参加した

2017.seccon.jp

結果

4問解けた

f:id:yamunaku:20180527124224p:plain

Reversingはバイナリ解析ソフトをインストールする気力がなかったし、Pwnは未知の領域なのでできない

以下、各問題の解き方

 

 

[Warmup] Greeting

f:id:yamunaku:20180527124501p:plain

こんな感じのページがでてくる

サーバは下のPHPコードに沿って動いてるようなのでこのコードの脆弱性を突きたい

htmlタグに入った時点で$usernameの値が"admin"じゃないとflagを表示してくれないので、それより上で$usernameの値を設定したい

ページ上のフォームによるPOST送信で値を"admin"に設定しようとすると"偽管理者"になってしまうのでダメ

他の設定方法を探す

よく見るとPOST送信をしないときは、$usernameをcookieから取得しているみたい

この場合は"admin"に設定しても"偽管理者"になることはない

 cookieをつくろう

適当なcookie管理アドオンなどを導入したあと、サーバが作ってくれたcookieを書き換える

値をname=adminに設定し、有効期限をいい感じに延ばせばよい

あとはPOST送信をしないでページを閲覧すればいいので、F5を押してページを更新するとフラグが出てくる

 

 

[Warmup] Veni, vidi, vici

タイトルの元ネタはカエサル(シーザー)

シーザー暗号を使いそう

(それぞれの文字を決まった数だけずらすやつ、3つずらすならA→D,B→E,C→F,D→Gといったように)

3つのファイルが渡される

1つめと2つめはアルファベットの部分をシーザー暗号で戻す

3つめは180度回転したような文字が書かれているので頑張って読む

3つのファイルのフラグの情報をつなげればフラグが復元できる

 

 

[Warmup] Welcome

ルールに載っている公式IRCチャンネルに入るとフラグを教えてくれる

 

 

Gimme your comment

とある架空webサービスのURLが与えられる

記事を打ち込むと向こうの社員がブラウザで閲覧してコメントをつけてくれるので、社員が使っているブラウザの種類を特定しようという問題

f:id:yamunaku:20180527130819p:plainf:id:yamunaku:20180527130827p:plainf:id:yamunaku:20180527130833p:plain

本文に <script>alert();</script> と打ち込むとアラートがでた

これは、入力された文字列をそのままページに入れ込むと、ブラウザがその文字列をHTMLコードの一部と勘違いして、<script>タグ内部のjavascriptを実行してしまうことで起きる現象(やばい)

社員が使っているブラウザでも同じことが起きてるみたいなので、これを利用して種類を特定する

javascriptの仕様をググってみると、window.navigator.userAgent がブラウザの名前を保持しているらしい

相手のこの値を僕に伝えてくれればいいので、どうやって僕に送るか考える

送り方

①僕が保有しているサーバに何らかのメッセージを送る

僕のサーバがwebサーバのときで、相手のブラウザを僕のwebページに遷移させることをXSS(クロスサイトスクリプティング)という らしい

②このサービスを直接利用して僕のブラウザにメッセージを送る

 

①と②を比べると、②のほうが圧倒的に楽なので②を使いたい

もしこのサービスが他者のwindow.navigator.userAgentのような値を表示することを禁止していると、①を使うしかないけど、ひとまずやってみよう

 

このようなコードを送った

f:id:yamunaku:20180527133617p:plain

getElementsByClassNameでほしいHTML要素のクラスを指定していい感じに操作をさせる

window.onloadは、値として入れられた関数を、ページをすべて読み終わった後に実行する変数らしく、これを追加しないと、このスクリプトが読み込まれた以前のHTML要素しか扱えない。今回扱いたいinputとbuttonは、HTMLコード上ではスクリプトの後に配置されるので、window.onloadの部分は必要になる

結果はこう

f:id:yamunaku:20180527133755p:plain

僕も巻き添えを食らったけどflagがゲットできた

ページを閉じない限り止まらないので、スクショを撮って手で打ち込んだ