やむなく日記

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

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がゲットできた

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

こどふぉ#480Div2 E問題の反省と真解法のメモ(後日更新予定)

この問題

codeforces.com

ダメな解法

番号が一番でかいノードを根とする。

すべての葉をヒープに突っ込む。

ヒープからひとつ取り出してその親をヒープに突っ込む。

k個取り出すまで繰り返す。

Submission #38044094 - Codeforces

(ここにtestcase7を踏まえた、なんでダメなのかという考察が入る)

 

よさそうな解法

AGC022Cでみた

C: Remainder Game - AtCoder Grand Contest 022 | AtCoder

ノードiを取り除くなら、i未満のノードを全部取り除いたほうがまし

→i未満のノードを全部取り除くことでノードiを取り除かないですむなら、取り除かないでおきたい

→i未満のノードを取り除くことでノードiを取り除かなくてもいけるか???

 

番号が一番でかいノードを根とする。

すべての葉の番号をsetに突っ込む。

取り除くものがなくなるまで以下を繰り返す。

  自分より親の番号が大きいような葉の親の番号をsetに突っ込む。

  自分より親の番号が大きいような葉を木から取り除く。

setの中身がすべて0になるまで以下を繰り返す。

  setの中で、番号が最も大きいものAを探す。

  setに含まれるノードで番号がA未満のものの個数を調べる。

  k以上なら

    setからAを取り除く。

  k未満なら

    AとAの子孫だったものをダメにして、それらをsetから取り除く。

    その個数だけsetに0を突っ込む。

    木からAを取り除く。

    取り除くものがなくなるまで以下を繰り返す。

      自分より親の番号が大きいような葉の親の番号をsetに突っ込む。

      自分より親の番号が大きいような葉を木から取り除く。

ダメにしたものを番号順に出力する。

 

(ここにやってみた結果が入る)

AtCoder Regular Contest 097 反省

爆死

実装力が全然足りなかった

arc097.contest.atcoder.jp

 

問題C

a,aa,aaa,aaaa,aaaaa,aaaab,aaaac,…,aaabaみたいに辞書順に並んだ文字列を頑張って生成することしか考えてなくて、実装力がないため終わった

 

問題D

Union-Findを使う

オリジナル即日実装したらバグを量産した

結局ネットに落ちてるやつをコピペして使ったので、バグの原因を明らかにしないといけない

setとかqueueとかを使うたびにSTLの解説ページを読まなきゃいけないので、早いとこメソッドの名前などを覚えてしまいたい

38:23でAC

Submission #2499950 - AtCoder Regular Contest 097 | AtCoder

 

問題E

2回も解法を間違えた

1回目

どっちか一方に白を全部まとめてからやればいいと思った

サンプルケース1ですら読んでなかったのが原因の1つ

Submission #2502454 - AtCoder Regular Contest 097 | AtCoder

 

2回目

次に並べるべき白球,黒球2つのうち近いほうを持ってくればいいと思った

真解法には近づいたが詰めが甘い

Submission #2503991 - AtCoder Regular Contest 097 | AtCoder

 

結果

パフォ:1160

レート:1313->1281

競プロ全振りしなきゃ…