こどふぉで青になりました

前書き

　こんにちは。2019/12/13(日本時間)に Codeforces というコンテストサイトでのレートが1600を超えていわゆる青コーダーになりました。こどふぉで青になるまでにやったこと、みたいなよくある内容をいくらか記しておきます。日本人向けとか言われがちな 

AtCoder と比べてどうのこうのって内容も気付いた範囲で書きます。

こどふぉでやったことなど

　1.青になれる実力を用意した後にDiv3に出る

　以上です。

　　日本人でこどふぉに出る人は英語で問題を読むことが多いと思います。ただでさえこどふぉの問題文は読みにくいと言われる時がよくあるのに、英語に慣れていない人は題意を理解する、入出力形式を理解する段階で上手くいかないでしょう。私が青になった時のRoundでも誤読をしました。私はAOJ-ICPCの問題を（英語しかない問題もあるけど）英語で読んで慣れました。競プロの問題でよく使われる単語は決まってるので、ICPCの国内予選の問題とかを解くと良いと思います。自分はサークルの活動で週2で2時間のバーチャルコンテストをしていたので、そのくらいのペースで英語の問題を読んでいるとすぐに慣れるでしょう。

　英文さえ読めるようになると、こどふぉ特有の難しさというのはほとんどないと思います。hackについては積極的にする必要はあまり無いと思います。Div3など、educational roundならコンテスト中にhackをする必要が無いので青になるまでならhackを気にする必要は無いと思います。私はhackを成功させたことがないです。AtCoderと違ってコンテスト中にACでもコンテスト後にWAと判定されることもあります。いわゆる嘘解法でもAC判定が出る可能性があることだけ忘れなければ大丈夫そうです。

次の目標

 　AtCoderでも青になりたいですね。

 

f:id:wakuwinmail:20191213172407p:plain

 

ICPC国内予選2019

　ICPC国内予選2019お疲れ様でした。特に選手の人はお疲れ様でした。私は北海道大学からチーム「Megido」で参加して3完51位でした。順位表はここから（https://icpcsec.firebaseapp.com/standings/）

 

コンテストの少し前・・・

　ICPC国内予選の環境は参加者各々に任せられているのですが、自分の大学では全参加チームにノートPCが貸し出され、それを適当にカスタマイズする感じでした。なので、Ubuntuでも入れようかなと思っていたのですが・・・

 

 　という事故が起こっていました。去年は同じチーム、同じマシンでWindows環境だったのでまあいいか、ということで結局Windows環境（賛否両論）で出ることに。

？？？「あの汚いコマンドプロンプトで作業したくない」

 

　あとは開始直前に印刷がうまくいかなくて焦った（なんとかなった）

 

序盤（～C）

　Aは自分が読んだ。やるだけ、だったけど入力形式を誤読してて手間取った。ここで詰まらなくて本当に良かった。Bは見てません。チームメイトが一瞬で通してた。その間にCの解法を聞いて大丈夫そうなのを確認してた。確認してたように見せて自分は正当性が何も分かってなかったけど合ってそうな雰囲気だったので適当にうなづいてた。

　Cが書かれてる間にDとEを読む。Dはデータ構造のDか？と思ったけどそういうのじゃなさそう。Eは虚無実装の匂いがした。愚直全探索がオーダー的にいけそうな気配がしたものの実装がヤバそうなのでDを考える。途中でlower_boundで値が見つからなかった時の戻り値endで合ってる？と聞かれたので合ってますって言った。リファレンスはオフラインでも参照できるやつをダウンロードしてあったけど調べるのは流石に面倒すぎる（活用したチームあるんか？）。

　なんやかんやCは実装が終わったけど一部ケースが通らないっぽい。詰まってそうなので、自分がDのサンプルが通るだけの適当なDPを書き始める。合ってると思ったんだけど、見積もりが甘かった。すぐにどこミスってたか分かったようで直してAC。

 

中盤以降

　Dでサンプルが通っちゃったので嘘であることをあんまり疑わずに提出してWAをもらった。順位表的にDを通してるチームがまだ多くはなかった気がする。fourtが3ペナ付けてるの見つけて嫌な予感はした。結局、落とせそうなケースを手作り出来ずに終了30分前くらいになってた。ここまで学内2位だったので去年の順位と今年の選抜ルールを思い出してギリギリ行けそうかなーって言ってた。

 

ラスト

　もうDが無理ということでEを書き始めたけど実装が鬼で絶対に間に合わない。DのWAの原因が提出ファイルの選択ミスだといいなー、って言いながらチーム全員で確認しながら提出してWAをもらう。残り時間はFを書いててもらったけど自分は酸欠で何もできなかった。廊下で空気を食べる人になっていました。夜なので建物の電気が消えててトイレの辺りがめちゃめちゃ暗くて怖かった。ラスト30秒くらいは大学内で3位以下のチームが4問目を解かないことを祈ってた。どうすることもできない。

 

終了

　結局学内2位のまま終了した。なんかいけそうって言いながらチームメイトが通過チームを数えてた。

 

以下ネタバレあり

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

　国内予選通過してそうです（暫定）。正式発表はまだですけど、選抜ルールを見る限りでは大丈夫そう。

 

まとめ

　AtCoderみたいに最終提出時刻の勝負だと学内2位になってなかった。あぶね

RUPC2019参加記

　RUPC2019(https://atnd.org/events/103718)に参加しました。（参加してすぐに書き始めたんですが3/18まで放置してたのでかなり忘れてます。）

　自分は1・2日目はcontestantとして、3日目はjudgeとして参加しました。

０日目

　自分は立命館大学さんの宿泊施設であるエポック立命21(http://www.ritsumei.ac.jp/lifecareer/activity/facility/stay/#page-title2)に宿泊させてもらうことができたので前日入りでしたが・・・

　

 

　はい（はいじゃないです）

 

　これをしたので到着が遅れてしまい開始前からドタバタして他人に迷惑を掛けてしましました。（後で出てきますが荷物は大丈夫でした）

　宿泊施設には無事到着して0日目は終了でした。

 

１日目

　チーム「rupc_ftw」で出ました。メンバーはフェリン (@ferin_tech15) | Twitterさんと

tubuann (@tubuann1) | Twitterさんとランダムで組みました。

　AとBは自分が読んで開始6分くらいでどっちも通りました（チーム内最弱としての最低限の仕事）。つぶあんさんがEを解いてる間にDを考えたら二分探索っぽく書けそうな気がして図を書いたらいけそうだと気付く。Dがなんか構築できそうだとつぶあんさんに伝えると一瞬で実装をしてくれました。頼りになる。

そうこうしているうちにフェリンさんがCで絶対に置けないところがあると気付いたので「サンプル通ったら出しちゃおう」でAC。

残りの時間は睡眠をしました（ごめんなさい）

　夜ご飯は立命館大学の生協で食べたんですが、beetさんとかolpheくんとかが問題をたくさん解くと強くなる（地力が上がる）って話をしてたのが印象に残ってます。地力が付くとレートが誰かのように上下しにくくなるらしいです。

　夜はなんかカタンをしたりトランプをしてました。宿泊施設がキレイでシャワーも使えるし部屋もそんな狭くないしで快適。

2日目

　チーム「rupc_hmow」で出ました。メンバーはもやし先輩 (@oreha_senpai) | Twitterさんとはりぼて (@__hrbt) | Twitterさんとok (@okyako) | Twitterさんとランダムで組みました。

　問題文を読むのを分担したのですが問題概要を伝えるのが上手くいかなくて永遠に悩んでました。ごめんね。Nimっぽい問題はGrundy数を知らなかったのに考えてて時間を使ってしまった上にWAしか生みませんでした。Dの実装をさせてもらったのに最後に通らなくて本当に申し訳ない・・・という気持ちになっていました。DPが出てもいつも解けないので練習する必要性を感じました。

　最初の担当はC問題でしたが、直感的に苦手ジャンルだと感じたので他の人に投げたんですが制約が緩いことに誰も気付かず厳しくなっていました。もやし先輩以外は（当時のAtCoderレートが）自分より低かったのですが「いや2人とも強すぎるなぁ」と無限に言ってました。Eはokさんが実装をしていて、ミスが誤読くらいしかなくて実装力が高いなぁと思って見ていました。（こたつがめが爆弾を踏めるのは普通に罠ですよね）

　もやし先輩も、Hを見て「これ燃やす埋めるじゃん」「知らないから今から資料を読みます」みたいな発言をした上で結局通していたので天才みを感じました。（自分も燃やす埋める問題の基礎を知れたのでこれは良かったです）

　強くなりてぇ（得意分野を作ってチーム戦で貢献できるようになりたいと強く感じました）

　コスプレ集団がいたのは流石に怖かったんですけど本人たちが楽しそうだったので良いかなと思いました。見てる分には楽しかったです。

 

　夜は懇親会でした。りあんさんが色々と話していたのが面白くて、特に東工大のICPC事情（リッキーシータさんがあと1回しか出られないのでWFに行けるようにしたいとか、新入生が強いけど新入生同士でチームを組むんじゃないかとか（ちなみにもやし先輩も東工大に入学が決定しています））しかし本人はというと

 だそうです。

　うしさんは割と飲んでいて歩くのが大変そうでしたが、全体として見ると去年の会津合宿の時ほどひどいことになってなくて良かったみたいです。2次会は有志でゲーセンに行きました。ナンくんとmaimaiをして楽しかった（あとチュウニズムもした）。競プロer意外と音ゲーに強くて意味がわからないです。卓球をやっていた人もいたみたいで楽しそうだった（こなみ）

　立命館大学内の宿泊施設の門限が24:00らしくて割とギリギリに帰りました（23:30くらいだったかな）。雨が降ってて傘が無かったので傘を買いました（紛失した荷物の方に折り畳み傘が入ってたので悔しかったです）。

　帰ったらすぐにシャワー使って、あとは前日と同じようにカタンをしていました。正直、3日目はjudgeなので少しくらい寝不足でもいいかなと甘えていました。

 

3日目

　judgeです。集合が早くて荷物もまとめるので朝はバタバタしてました。会場に着いてから問題文の印刷を始めたんですが立命と会津の人はなぜあんなに問題文を印刷できたのか不思議なくらい印刷速度が遅かったです。風船は2日目までに使ったのがたくさん余っていたのでコンテスト中に膨らませたのは5個とかそんなくらいだった気がします。

　自分はAの問題文とBの入力を作っていたのですが、「問題文の意味がわかりません」とか「テストケース壊れてませんか？」とか言われなかったので良かったです。（というか全体を通して不備がほぼ無かったので安心でした）。問題が起きなければコンテストの状況を眺めているのは楽しいです。推しチームは「RUPC_Burningkotatsu」でした。ペナも少なくてタイムも良かったんですけど惜しかったなぁ

　コンテスト後、A問題の解説を担当しました。全チーム解いてたので解説は気楽にできました。ただ、オンサイトでFAのチームのチーム名の読み方がよくわからなかったです。キラキラネームってやつでしょうか・・・

 

 

 

　終わった後はご飯を食べて解散。京都駅経由でえびちゃんと一緒に東京に帰りました。初日に紛失した荷物は京都駅で受け取ることができたので良かったです（持ってきた意味がなかったなぁ）。

　ちなみに、自宅の最寄り駅で荷物を網棚から降ろす時にヒヤッとした感じがしたので今回の荷物紛失はかなりのトラウマです・・・

 

 

RUPCこれにて終了です（3/18）

AtCoderで水色になるまでにやったこと

　ブログを読んでくれてありがとうございます。

　少し前にAtCoderのレートが1200を超えて、いわゆる「水色」レートに到達しました。（レート推移やパフォーマンスはこちらhttps://beta.atcoder.jp/users/wakuwinmail/history）

 　今回は、私がレート1200に到達するまでやったことを色々と書いていきます。

 

初参加まで

　私が初めてAtCoderで参加したコンテストは2016年9月24日の「CODE FESTIVAL 2016 qual A - AtCoder」でした。まず、私の競技プログラミング以前のプログラミング歴について書いていきます。「苦しんで覚えるＣ言語 - 苦しんで覚えるC言語」というサイトを参考に、特に誰かに教えてもらうわけでもなくC言語の勉強をしていました。その後、DXライブラリ（http://dxlib.o.oo7.jp/）というものを使ってゲームを作るためC++について勉強していました。コードを書くことに抵抗はなく、バグやエラーが出た時に自力で検索して解決する程度のことはしていましたが、特別にアルゴリズムの勉強はしていませんでした。そんな中で、プログラムを書く練習として競技プログラミングをやろうと思ったわけです。

競技プログラミングを始めてみたが

　実際に、このくらいの経験でどのくらいの成績が出たのでしょうか？確認してみると、AtCoder初参加の成績はパフォーマンス1477でした。パフォーマンスというのは、簡単に言うと「そのコンテスト1回に限ったAtCoderレート」のようなものです。つまり、初参加のコンテストの時点で1200以上のレートに到達できる可能性は既にあったわけです。しかし、当時の自分はパフォーマンスの存在を知らず、またAtCoderの仕様である「参加回数が少ない内はレートが（パフォーマンスに比べてかなり）低くなる」ということも知りませんでした。2回目、3回目に参加したコンテストの成績もあまり良くなく、競技プログラミングを楽しいものとは考えていませんでした。2016年のJOI予選が終わると、私は競技プログラミングへの興味を失っていきました。

競技プログラミングへの興味

　競技プログラミングそのものは頭を使う数学パズルゲームのようなものです。なので、ちゃんと勉強していけば面白いだろうなとは思っていたものの、時間が取れずにいました。AtCoderの過去問を解くなどしてプログラミングをしっかり勉強するようになったのは2018年の3月ごろからでした。そして、過去問を解くようになると競技プログラミングの面白さを実感するようになりました。この時はC++ではなく当時興味を持っていたPythonやRubyを使用していました。

本格的な練習

　2018年4月頃からは大学内のサークル活動に参加するようになり、ACM-ICPC 国際大学対抗プログラミングコンテストに向けた練習のためC++でコンテストに参加するようにしました。サークル活動では1回2時間ほどの模擬コンテストを週に2回行っていました。この練習のおかげか、以前のブログにも書いたようにACM-ICPCではチームとして国内予選を通過することができました。20118年の8月以降はAtCoderのコンテストに毎週参加し、JAG夏合宿や会津合宿などの競技プログラミング関連のイベントにも参加しました。過去問を多く解いたわけではないですが、コンテストに多く参加することで慣れてきたのかもしれません。2018年8月18日のABC106「https://beta.atcoder.jp/contests/abc106」ではパフォーマンス1600となり、その後も徐々にレートを伸ばしていきました。ABCの300点問題を確実に、10分以内に解くことでパフォーマンスが1200を超えてきた気がします。

まとめ

　これは、競技プログラミングの上達に限った話ではないですが、問題を解いて慣れてくると何事も成績が良くなります。私の体感としては、コンテストに慣れてきたら10分以内に解ける問題は解いてもあまり実力が上がらない気がします。コンテストや競技プログラミングの問題に慣れていない内は簡単な問題を解くだけでコンテストでの成績は上がります。水色を目指すなら大半の300点問題は（実装も含めて）10分以内に解けるようになると良いと思います。

 

【11/7追記】

『水色を目指すなら大半の300点問題は（実装も含めて）10分以内に解けるようになると良いと思います。』の部分についてです。

大半の、と表記しましたが基本的にはABConly(ARCと同時開催されてないABC)の300問題を指しています。

また、この記事を書いている時の直近のABC-Cには難しい(もしくは実装が重い)問題もあります。そのような問題を10分で解く必要はありません。10分というのは、慣れてくるとこのくらいの時間で解けるようになる、という目安の数字と思ってください。

ICPC国内予選2018

　ブログを読んでくれてありがとうございます。

　まずは、参加者の皆さんお疲れ様でした。私はとても疲れました。ゆっくり休んでください。

　ここには、私のチームの3時間の流れを思い出しながら書いておきます。

 

チーム名：「Megido」

所属：北海道大学

 

　私のチームでは、問題の担当を予め決めておいて、苦手分野が当たったら交代という作戦でした。私はB問題担当でした。

　開始後、A問題担当の人は難なくA問題を通しました。私はB問題がやばそうだったので、先にC担当の人に実装を譲って2人でB問題を考えていました。しかし、これが中々難しかった。私はバグを埋め込む予感がしたのでコーディングはしませんでした。（予定では、各自の担当問題は各自が書くつもりでした）

　結局、B問題はなんとか0WAで通し、みんなでD問題を眺めていました。ここで、私はほとんど理解できずに座っているだけをしてしまったのが、今になると失敗だった気がします。ともかく、D問題はOJならTLE解でしたが、ICPC予選なのでACしました。D問題は、C問題担当の人が考察も実装も担当したのですが、めちゃめちゃ頭が良い人で方針でつまずくことは無かったです。B問題を考えている間にD問題の考察をしてもらっていて、時間を有効活用できていた感じです。

　D問題を通した後、校内2位ということで予選通過が少しだけ見えていることに気付き、5完を目指して頑張りました。幾何や、部分文字列を見るのは難しいだろうという判断の下で、Eを考えていました。結局、実装が終わらなかったので4完で終わることになりました。Eの方針は合っていたのでしょうか・・・

 

　全てが終わって順位表を確認すると、なんと45位という、練習会の成績からすると信じられない好成績でした。正直、予選通過することは考えていなかったので、チームメンバー全員が予選通過の条件を確認していませんでした。さっき数えたら、ギリギリ通ってそうです。喜びよりは戸惑いというか、まだ実感が湧きません。これからも頑張っていきます。

 

　最後までありがとうございました。

競プロを始めてから知ったC++のSTL

・vector

動的配列を使える便利なやつ

 

多重で作る時はvector<vector<int> >などのように書きます。後ろのカッコが離れてるのは正しいです。くっつけるとコンパイルエラーが出ます。テンプレートの関係のようですが、詳しいことはわかりません。

 

多重のvectorをソートしようとするとうまく行かないので、2つならpairを使うなどしましょう。詳細な条件付きのソートが必要な場合は構造体を作って演算子を定義するなどするとソートできます。

・list

状況によってはvectorより使えることもある

・pair

便利な比較演算子が勝手に定義されてるので楽、他のと組み合わせることもたくさん

・queue

先入れ先出しとか呼ばれるやつでBFSの問題をやったときに知った

・stack

後入れ先出しとか呼ばれるやつでカッコの対応の問題をやったときに知った

 

他にも色々やったような気がします。各メソッドのメンバ関数もちゃんと覚えると便利です。自分で実装が必要なケースはそんなに多くはないです。

 

また追記していくつもりです。

私がプログラミングを始めた時のこと

こんにちは

ブログを開いてくれてありがとうございます。

 

今回の記事では

・私がプログラミングを始めたきっかけ

・プログラミングの環境(の推移)

・プログラミングを使ってやったこと

を書いていきます。

 

私がプログラミングを始めたきっかけ

　これについては、ハッキリとした目的があったわけではないことは覚えています。記憶では、ゲームを自分で作ってみたい、というありきたりなものだった気がします。また、これはプログラミングを始めた時期と環境とも大きく関係があります。

　私がプログラミングを始めたのは中3の秋頃くらいでした。私は中高一貫校に通っていたので、ちょうど部活動の体験期間だったわけです。この時にパソコン部に入部して、プログラミングをやり始めました。知り合いもいたので特に問題なく馴染めました。ただ、私は兼部していたので活動には半分ほどしか出席していませんでした。

　私の学校のパソコン部は、よくあるように文化祭での作品発表が唯一の目標だったのですが、そこで発表される作品の多くがゲーム作品でした(ここ2年くらいで映像・音楽作品も増えてきました)。私も他の多くの部員と同じように、新歓期や文化祭での作品を見て、自分も作りたい、と思ったのです。

　なぜゲームエディタではなくC言語などを始めたのかはここでは割愛します。

 

プログラミングの環境(の推移)

　中高の部活動でプログラミングをしていたのですが、高1の夏頃までは家ではプログラミングはしませんでした。それなので環境は学校で使用可能なものを使っていました。

　学校のパソコンの環境は

・Win8.1

・ソフトのインストール不可

でした。これでプログラミングできるのか？と思う人もいるかもしれませんが、VS2013がインストールされていたので、困ることはありませんでした。インストール不要のソフトウェアなら、顧問の許可を取れば使うことはできました。

　私は、理由はわからないのですが、最初はC言語を勉強しました。その時は部内にC言語をやっている人はあまりいなく独学でした。そのためか、実行環境は【エディタ】がVS2013で、コンパイラをMinGWでコマンドプロンプトから実行をしていました。

　そんなこんなで、入門者向けのwebサイトを参考にして、少しずつ進めて一通り終わらせたところで私は気付きました。C言語でグラフィカルなゲームを作る方法が結局わからないということに。

　その後、グラフィカルなゲームを作りたいということでDxLibを使った開発を始めました。この時からVS2015を【IDEとして】使い始めました。C++を理解するのが難しく、STLもあまり使いこなせず、開発の時間は言語とライブラリの仕様との戦いでした。それでも1年半程度はDxLibを使ったゲーム作りをしていました。

　その途中で競技プログラミングを知りましたが、深くハマることはありませんでした。高3の年の部活動では、スクリプトが書ける人とペアを組んでゲームデザインに専念していました。GitHubを使い始めたのもこのゲームの開発を共同で始めてからでした。

　それ以降は、競技プログラミングやTwitterBot開発をしています。使ってる各言語の環境は以下の通りです。

・C++

CLion

Vim+gcc

・Ruby

VSCode

・Python

PyCharm

 

プログラミングを使ってやったこと

 　私のGitHubにある程度はまとめてあります。DxLibを使って作ったものは「ブロック崩し」と「ちくわブラスター」です。Rubyを使って作ったのは以前のブログでも紹介したTwitterBotです。制作物ではないですが、競技プログラミングをプログラミングの練習のためにやっています。

　こうして書き出すと、まだ何かやったぞと言えるほど大きなことはやっていないような気がします。今後も頑張っていきます。

 

終わりに

　最後まで読んでいただきありがとうございました。次の記事や過去の記事も読んでいただければ嬉しいです。

　ありがとうございました。