やむなく日記

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

競プロコンテストサイトを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

競プロ全振りしなきゃ…

Codeforces Round #480 (Div. 2)

Codeforces

 

Codeforcesのルール

ただ問題を解けばいいということではないらしい

自分の解答に満足したら足を引っ張りあえるルール

 

英語で書かれた問題を読む。

→ 問題を解決するコードを書いて提出する。

→ pretestによって判定され、ACなら暫定的な得点がつく。

(AC: ACcepted/正解の意。 対してWA: WrongAnswer/不正解の意。)

→ よさそうならlockする。こうするとコードの再提出ができなくなる。

→ lockするとhackできる。すなわち他人の提出コードを見てバグりそうな入力を送り付けることができる。

→ hackに成功すると得点を得て、失敗すると得点を失う。また、自分のコードがhackされるとそのコードの得点がなくなる。

 

コンテスト終了後に再度ジャッジをして、そこで通ったら得点が確定し、通らなかったら得点がなくなる。

 

2時間で6問出題される。

n問目の配点は最大500*n点で、時間とともに減少する。(終了時には500点減少してる?)

再提出でも減点される。(ACできなかった問題への提出でも)

 

 

参加記

今回はCodeforces Round #480 (Div. 2)に参加しました

Div1,2,3があって、番号が小さいほど難しい

codeforces.com

開始前(0時5分スタート)

頭が痛かったのでちょっと寝て15分前に起きた

 

問題A

パールとリンクを繋いで輪状のネックレスを作る。

パールとリンクの個数が与えられるので、パールを等間隔に配置することができるか判定する問題。

パールがあるならリンクの個数をパールの個数で割った余りが0であればよい。

パールがないなら無条件でよい。(これを見落として1WA)

8:34でAC

Submission #38027551 - Codeforces

 

問題B

4行n列のマス目が与えられる。(nは奇数)

このマス目の辺でも隅でもないところに、k個の通れないマスを配置して、次の[条件]を達成することを考える。

[条件] (1,1)から(4,n)へ隣り合ったマス目を通って最短で移動する経路の個数と、(4,1)から(1,n)へ同様に最短で移動する経路の個数が一致する。

この条件を満たす配置が存在するか判定し、存在するなら構成する問題。

2番目のテストケースを見て謎になった。

 

問題C

画像データを扱いやすくするために、似ている色の部分を1色で塗りつぶすというテーマの問題。

具体的には、色データがとりうる範囲[0,255]を、幅がk以下になるようにいくつかの連続した区間に分割し、ある区間に属するデータをその区間の最小値に置き換える。

(ここでいう幅とは、区間に属する整数の個数のこと。例えば区間[2,5]の幅は4)

データ列が1列になって入力されるので、置き換えた結果で辞書順最小になるようなものを出力する問題。

辞書順最小なので先に入力されたデータを優先的に小さくしていけばよく、後から入力されたデータはそれに合わせてできる限り小さくすればよい。

46:24でAC

Submission #38036259 - Codeforces

 

問題D

数列の項をいくつかのグループに分け、グループに属する任意の2要素の積が必ず平方数になるようにする。

入力される数列の連続した部分列のうち、以上のようにグループを分けた時のグループの個数の最小値がkであるような部分列の個数を、各kについて出力する問題。

めっちゃめんどそうなのでやらなかった。

 

問題E

ある国で地区対抗のゲームが開催されるが、参加させない地区をいくつか選ぶことになった。

ある地区から別のある地区へは、直接移動するか他の地区をたどって移動することができ、その移動経路は1通りしかないことが保証されている。

すなわち、地区を頂点として直接行き来できる地区同士を辺でつないだグラフは木構造をなしている。

地区には番号が振られていて、i番目の地区を参加させないことにするとコストが2^iかかり、またそのi番目の地区は通ることができなくなる。

地区の構造が入力されるので、参加する地区同士は行き来できるようにしながら、k個の地区を参加させないようにする。このときのコストが最小になるような地区の選び方を出力する問題。

pretest7でWA(なんでや)

Submission #38044094 - Codeforces

pretest7の内容を見ると自分のが嘘解法であることが分かった。

考察しなおして真解法がわかった(と思う)ので、これについてはまた別の記事で書こうと思う。

 

問題F

Eが通らないのがつらくて読めなかった。

 

結果

A,Cの2完で1658点、6793人中982位。(参加人数がすごい)

レートは1555で緑色、Specialistになった。(称号は持ち上げすぎな気がする)

 

ブログやってみます

 はじめまして

やむなく( @yamunaku )といいます。

プログラミングコンテストやCTF、ゲームなどの日記を書くつもりです。

 

自己紹介 [18/05/08現在]

やむなく ( @yamunaku )

京都大学工学部1年生

Atcoder 水色(1313)

Topcoder 未参加

Codeforces 未参加

CTF 超初心者

好きなもの: ゲーム

 

近況

現在ニーアオートマタ(steam版)をプレイ中です

switchとゼルダとスプラとぷよテトをamazonのカートに突っ込んで、いつ買うか悩んでいます

最近チュウニズム金レートになりました

f:id:yamunaku:20180508222304j:plain

長い銀レ人生だった