おここ

競プロなど

AtCoder 黄になりました！！

 

 

嬉しいね！！！

 

AtCoder で青になったのが 2023 年の 4 月 1 日に行われた ABC296 で、実はそこから1年以内に黄色になることを目標にしていたので、それが達成できなかったことだけ残念だったけど、それでも普通にめちゃくちゃ嬉しい。

 

一応 AtCoder Problems の色変時の状況を貼っておくか。とはいえ下埋めを全然してない以外は割と入黄達成者として普通くらいの感じだと思う。（正直他の人がどんなもんなのか全然把握してないんだよな。）

 

（画像貼るの飽きたしここまでで良いか。ここら辺まで見れば大体どういう感じか分かるでしょ。）


てかお前誰？

すいません。自己紹介が遅れました。おここと申します。(AtCoder: ococonomy1 Twitter: ococonomy4) 大学生です。えー、後はなんかあったかな。あ、さっき見てもらった通り、黄コーダーになりました。

 

あとは AtCoder 青になったときにこういう色変記事を書きました。この頃ははてなのアカウントを持ってなかった（これは嘘で、作ってはいたが動かす気が一切起きないくらい動かしていなかった。）状況なので note に書いてますね。今後は競プロのことはこのはてなに書いていくのでこの note は無理に追わなくて大丈夫です。

 

今回の色変記事の内容について

 

 

実は青コーダーの頃に考えていた色変記事の内容として「（元）寒色コーダーの目線でいろんな海外コンについて感想を述べます！」的なことをやろうと思ってたんですよね。私は比較的多くの海外コンに出てる方で、かつそれらの海外コンについて「このサイトはこういう特徴がある」みたいなのを寒色コーダーの目線で書いたものがないなと思っていたので、ちょっとは需要があるかもしれないし書こうかなと思っていたのですが、ちょっと書き始めてみて思いの外面倒だということに気付いちゃったので、諦めちゃいました。

 

でもこんなことを言っておいて一切触れないのも誠実でない（？）気がするので（日本の競プロコンテストをやっているサイトを含めて）雑にそれぞれのメリットを挙げておきます。

 

AtCoder - 問題文や解説が日本語だから読みやすい。ある程度競プロアカウントをフォローしておくとコンテスト後に流れてくる情報量が多い。

yukicoder - 問題文や解説が日本語だから読みやすい。問題傾向が広い。

AtCoder Problems(バチャ) - 問題文や解説が（略）。時間を測らずにやる下埋めや upsolve に比べて速解き力がつきやすい。

Codeforces - 「考え方の典型」みたいなものが身につく。 ARC に苦手意識がある人はとりあえず Div.2 を 30 回やりましょう。

CodeChef - 雑パターンマッチングでは解けないことが多いので考える癖がつく。思考停止でそれっぽいコードを書く癖が抜けやすい。

DMOJ - 時間の融通が利きやすい。頻度が少ないのでよく問題傾向が分かってない。

TLX(toki) - 順位システムが AtCoder に近くて分かりやすい。頻度が少ないので問題傾向がよく分かってない。

 

こんな感じですね。本当はもっとそれぞれのサイトごとにどういうコンテストがあってこういうメリットデメリットがあって……、みたいなことを書いたりそれぞれのサイトのリンクやスクショを貼ろうと思っていたのですが、面倒だったのでここら辺にしておきます。詳しく知りたい人はおここに聞いてください。（気軽に人に尋ねられない人のためにちゃんと説明した記事を書こうと思っていた気がするのだが……。）

 

ここからは、色変記事らしく精進の話とか感想とかの話をしていきたいと思います。

 

コンテストに沢山出る意義

 

先ほども言いましたが、私の青コーダー時代の精進の特徴として、コンテストにいっぱい出たというのがあります。今調べたところ、AtCoder の rated 出場が 165 回、Codeforces の rated 出場が 46 回、CodeChef の rated 出場が 13 回らしいです。（思ったより多くなかったな……。）あとは AtCoder Problems のバチャに 199 回出ていますね。（これはさすがに多い方だろ！）

 

で、コンテストやバチャに沢山出る意義として、速解き力・安定性がつくというのがあると思っています。下埋めとか upsolve とかやるとき、恐らく多くの人がそこまで時間を気にせずにやってると思うんですが、コンテストやバチャに出ると前半の自分にとってそこまで苦労せずに解ける問題も、速く、確実に、解けるように意識するんですよね。その積み重ねが他のコンテストに活きてきて、今まで 90% の確実性で解けた問題が 95% や 99% の確実性になったり、今まで 20 分で解けた問題が 15 分や 10 分になったりすると思います。（少なくとも私は、なりました。）

 

ここら辺の話は自分のレートより一色分くらい下の difficulty の問題のことを想定しているんですが、それらの問題を速く、確実に解けるようになると、当然下振れは上がりますし、実は上振れも上がるんですよね。

 

というのも、崖回だったら速解きでパフォーマンスは大きく伸びますし、さらに崖じゃなくても、今までなら厳しかった適性ちょい上くらいの問題にかけられる時間も増えるので、コンテスト中に多く解く力にも繋がるというのもあります。コンテスト終了 5 分後にやっと通せたということがあったとき、次はコンテスト中に通せるように無駄な考察を減らそうとか、スムーズに実装しようとか思うのが自然な人間の考え方ですし、実際私もコンテスト後はそっちに意識が向くんですが、手前の問題を素早く解いて 5 分を捻出する、というソリューションもあるというのは言っておきたいですね。

 

まあそんな訳で、コンテストとバチャにいっぱい出て、速解き力と安定性をつけるという精進が、お勧めです！

 

コンテスト振り返り

 

せっかくだし AtCoder で青になってから黄色になるまでの印象的なコンテストを振り返っていきたいですね。私は自分語りが好きなのでこういう話を無限にしたい。

2023年 4-6月

青になった直後。2023年4月1日に青になったので「青になってから X か月」みたいなのが計算しやすいことで知られている。実はこの青になった ABC296 が初めての ABC での黄パフォだったのだがこれ以降ちょくちょく ABC で黄パフォが出せていてすごい。あとやっぱり目を見張るのは ARC160 の灰パフォでしょうか。緑-水コーダーだった頃は ARC で水-青パフォをちょくちょく出していて ARC に得意意識があったがここで灰パフォを出して結構心が折れた。この頃から ARC にはしばらく苦手意識があった気がする。

 

あとちょくちょく unrated になっていますね。 DDoS 攻撃とかジャッジ詰まりとかあった頃ですね～。個人的にはここら辺の unrated 回でちょっとだけ助かっていたんだよな。これが全部 rated だったらこの頃のレートが -10 くらいになっていたはず。（ちゃんと計算したわけじゃないけど、そのくらいな気がする。）

 

2023年 7-9月

青と水を行ったり来たりしている。この頃 AtCoder の色の伸ばし方がマジで行方不明だった。あと ICPC の国内予選があったり JAG 夏合宿があったりで競プロモチベ自体は低くなかったのが救いか。 JAG 夏合宿(9月中旬)で同じ部屋になった黄コーダーの話を聞いたり、Day1 で青コーダー 3 人のチームでめちゃくちゃ好順位を取ったことで上振れ力に自信がついたりしたことで、安定性を上げたいしレートより低めの difficulty の問題をバチャで積極的にやろうみたいに考えるようになった気がする。

 

2023年 10-12月

ABC の 2400 パフォが 2 つも！！！！この頃から明確に ABC が楽しくなり始めた。ARC や AGC に関しては、 ABC の普通が ARC/AGC のちょい上振れくらいで、 ARC/AGC の下振れは ABC だと相当でないようなパフォーマンス、という感じだったから苦手意識はあった。あとこの時期はモチベが高くて海外コンを結構やっていた気がする。ただ海外コンの成果はこの時期はまだ表には出てないね～。あと 11月にあった ICPC の Asia Yokohama Regional の大会当日にそれまで結構繋いでいた AtCoder Problems の streak を切らしてしまい、それ以降 streak を繋ぐモチベが下がったが、競プロ全体のモチベに関してはそこまで下がらなかったな。そもそも streak を繋いでいた時期も灰 diff で繋いでいた日がちょくちょくあったし。

 

2024年 1-4月

 

色変直前のこの数か月が一番波乱万丈だった気がする。二週連続で出した 2400パフォ(ABC337,ABC338)、あと一回 2400 出せば入黄というところから4回連続で冷えて失った120ものレート、今まで苦手意識があった ARC/AGC での橙パフォ、そしてレートが1950 を超えておりいつ入黄してもおかしくない状態が3週続いての、初 ABC 全完で入黄。ABC での上振れが増えたのはバチャをいっぱいやったおかげだし、 ARC と AGC で橙パフォを出せたのはコドフォの Div.2 をいっぱいやったからだと思う。やっぱり自分がやってきたことが数字に反映されるのは嬉しいね。別に競プロの精進を苦しいと思ったことはないが、それでも何かが報われた気がする。

 

これから

 

 

今年の初めにこんなツイートをしたが、このジンクスというのは正確に言うと「具体的な目標を他の人に言ってしまうと達成できない」というもので、もう達成してしまった目標や、期限を過ぎた目標については無効だと思っている。で、誰にも見えないところに今年の目標を書いていたのだが、それがこんな感じである。

 

達成していない目標については黒塗りになっている

自分でもびっくりなのだが4月時点で 4分の3 達成できている。（AtCoder 黄に関しては期限が守れなかったけど代わりに CF 薄橙タッチが 3 月で AtC 黄が 6月に間に合ったのでギリセーフってことで。（そんな理屈が通用したら、ダメだろ。））なので今後は、達成していないから黒塗りにしたもう一個の目標を達成できるように頑張っていきます。あともう一個「今年中に達成したいと思っていること」があったのだがここに書いてなくてビックリした。まあそれも公開できるように頑張ります。

 

ここまで読んでくれてありがとう！

 

おここより

ICPC2023 Asia Yokohama Regional 参加記

参加記ってどんな温度感で書けばいいんだ

 

自己紹介

いるか？一応書いとくか

AtCoder青 北大B3 早生まれではない

 

チーム紹介

チーム名:elephant_spaghetti

・yasagureprogさん

考察力が強い印象。AtCoderのレートは青だがAGCで一回橙パフォ取ってて「すげえ……！」と思った。ICPCに出るのは今回が初めて。

・usatyoさん

数学力（特に幾何）が強い印象。今はAtCoder青だがAtCoder水になってからABCに一回もratedで出ておらず、ARCunrated勢の逆をやっている。ICPCに出るのは今回が初めて。

・ococonomy1 

チームの中では比較的典型力がある？うちのチームで唯一のC++使いなのでTLが厳しそうだと自動的にこいつが実装することになる。ICPCのRegionalに出るのは今回が初めて。（国内予選は2022年も出た。）

 

国内予選の参加記はこちら

 

 

 

 

「こちら」をクリックすれば飛ぶと思った？書いてないので飛ぶ先がないよ。ごめんね。

 

本編（本編？）（何があったかを具体的に書くパート）

Day0

飛行機で横浜に向かう。この日は金曜日で2限があり、それに出席できるような時間の飛行機をとったのだがやる気が出ずにサボった。19時頃に横浜のとあるビジネスホテルに着く。北大のOBの人と中華街の店でご飯を食べることになっていたのでそこに向かう。色んな話が聞けて楽しかった。ちなみにこの日乗った飛行機にyasagureさんも乗ってたらしい。（別々に飛行機をとって、後で同じ飛行機に乗ってたらしいことが判明した。）

 

Day1

リハーサルのある日。朝ごはんを食べ終わった直後くらいにチームメンバーに「一緒にご飯食べませんか？」と言われた。残念ながら胃が1個しかないので断ることに。横浜産貿ホールに早めに着いて周辺をちょっと散歩してた。チームのメンバーとは現地集合で自分だけ早く着いてしまったため暇そうにしてた。

その後説明やリハーサル等があり、リハーサルが始まる前に「せっかくなのでFirst AC狙います？」と言ったら初めてだし慎重にいった方が……みたいな雰囲気になったので狙わないことになった。私はリハーサルでBを書いたが全然実装ができなくて無限にACできないかと思った。（最終的には有限にすることができた。）

リハーサルが終わった後は何があったっけ？チーム紹介か。スライド作ってる時温度感分かんね～って感じだったので結構ラフな感じなんだな～と思った。ちなみに我々の座ってる席はF-3だったのだが柱で全然壇上に立ってる人の顔が見れず、「あっここTwitterでFFの人がいるチームだ！」と思って顔を見ようとするもまるで見えない、を何回かやった。横浜産貿ホールさん、思いきって来年までに柱を撤去してみませんか？解散になった後はelephant_spaghettiのメンバーで中華街を食べ歩いた。途中ICPCのシャツ来た人やICPCの名札を付けてる人を見かけたりした。話しかけようかなとも一瞬思ったが、勇気も話題もないし向こうも複数人で集まってる感じだったので特に話しかけず。

 

Day2

本番のある日。朝にコンビニでライブラリを印刷した。500円かかった。前日にusatyoさんにpdf渡して「この番号コンビニのプリンターで入力すれば印刷できます」みたいな状態にしてもらったおかげで比較的スムーズにできたがそこに渡してなかったやつで印刷しておきたいのがあり、それを印刷しようとしたらスマホのバージョンが古いと言われたため、慌てて別のコンビニに。（ちなみに私のスマホは5年半くらい前に買ったやつを未だに使っており、slackやグルミクなどのアプリがバージョンのせいで入らないことで知られている。）二軒目に入ったコンビニで印刷できたので良かった。

本番

開始と同時にusatyoさんがログインを始め私とyasagureさんで問題を読む。Aは基本私で文字列操作が要求された場合(Pythonで書いた方が楽な可能性があるため)yasagureさんが担当することになっておりサンプル読んだ感じ文字列っぽいのでyasagureさんに投げてBを進める。yasagureさんに読んでもらったところ「こういう問題概要だけどちょっとすぐに実装方針が浮かばない」みたいに言われ、概要を聞いて私が書けそうだったので私が書くことに。その間にusatyoさんとyasagureさんにB問題をやってもらう。ほどなくして、Aを無事にAC(11分)

この辺りで順位表を見るとAが結構解かれてる他にSpeed StarがFを通している。Bは2人の感じ聞いてると結構大変そうで「今回難易度順なのAだけかも？」みたいなことを言ってFに取り掛かる。チームメンバー(どっちか忘れた)に「こんな強いとこが通してるの見てもあてにならないんじゃ」みたいなことを言われたが、順番が難易度順じゃないコンテストに出た経験値は自分が一番多い自信があり、そういうコンテストで強いところが早めに通した問題が時間経ってもなかなか解かれないことは稀だという認識があっため「少なくとも重実装なことはないですしいったん考えてみるだけでも価値はあります」みたいなことを言ってFに。普通にむずくね……？と思ったがusatyoさんが解いてくれた。(35分)

usatyoさんがFの実装に取り掛かってる間に全部の問題に少しずつ目を通し、Bは分からんが順位表見る感じ解けそう、Cは愚直書ければワンチャンエスパーいけるかも？Dは正規表現での説明書いてあって構文解析チックなので実装しんどそう、Eは自分の得意傾向っぽくて時間かければ解けそう、と判断。(Eを読んだ辺りでusatyoさんがFを通した)G以降はざっとしか読んでないが問題傾向的にKはusatyoさんが得意そう？という話をしながらyasagureさんとBを考えることに。2人で考えてたらyasagureさんが解けたっぽいのでそのままyasagureさんが実装し、その時間で私はEを考えることに。ここら辺で空腹を感じてきたためEを考えながらラムネを5粒/1口のペースでボリボリ噛んだりウィダーinゼリー(今はウィダーinゼリーではない)を5秒で飲んだりしていた。傍から見たら面白い食事をできていたと思うがおそらく誰も見ていない。その後、yasagureさんがBを提出。1回WAが出たがコードを見ながら私が「この変数ってどういう意味ですか」とか聞いていたらバグを見つけたらしくそこを直してAC(57分)

この後くらいから出来事の時系列が怪しいんだよな。

・usatyoさんが一旦諦めたKを再度考えてみたら良さそうな方針が思い浮かんだらしいので実装に取り掛かる

・yasagureさんがDの考察をできたが再帰とロリハがいりそうなので私がC++のロリハを書くことになるが、ライブラリを探してもロリハが見つからない（ICPC用のライブラリ整理でロリハは……、ハッシュの衝突とか恐れるような問題出ないだろ！と思ったことを後に思い出す）

・私がE問題の解法について、aとcの向きで不確定なのは高々11通りしかないため2^11=2048通りの全探索ができるのでは？という考察をする。（向きを全部確定できればトポロジカルソートと木DPで大まかな方法が浮かんでいた。）

・私がrestroomに行く。gentleman? lady? と聞かれて"gentleman"と答えながら「聞かれるならともかく自分について答える時にgentlemanは変じゃないか……？」と思う

などのことがあったが、あの時から24時間以上経ってる執筆中の私にはとても整理できない。

その後、usatyoさんがK問題の考察を終え実装をするもWAが出て、いくつか怪しいところを直しても通らなかったのでソースコードを印刷してもらいその間に私がロリハをライブラリなしで書く。（今振り返ると、ライブラリを持ってく時に「これいらんだろ！」で実際に必要になるライブラリを印刷しないでしまうというのが今回の一番のやらかしだったと思う。）バグらせつつもなんとか"abc"の[0,1]文字目と"cab"の[1,2]文字目のハッシュ値が同じになることを確認しロリハができ、yasagureさんの考察を聞きながら実装ラジコンになりDを書く。これをやりながら何回かusatyoさんがKのWAの原因っぽいところを見つけて直して提出してみる、というのをやっていたのだが、何回目かの提出でようやくAC(216分) 整数で出力すべきところが一部整数になってなかったらしい。

yasagureさんの考察を聞きながらDを実装し、しばらくかけて実装を終わらせる。最初TLEが出たが再帰をメモ化することでTLEが解消しWAになった。サンプルは合ってたしいくつか怪しいケースを見ても良さそうな出力になるのでどこでWAになってるか分からず、ハッシュの衝突では？という話になりMODを998244353から別の素数に変えてみるがWAが取れず。MOD2通り試すロリハを作るべきでは？みたいな話になり書いてみるも、どこかで実装ミスをやらかしていたらしくMOD10^9+7を追加して2通りのMODで見るバージョンで一致判定が動かなかった。しばらく(1時間くらい？)悩んでる時にusatyoさんが改めて問題見て「これ1桁までじゃないですか？」と気づく。なんとaaaaaaaaaaaaaaaaaaaaは20(a)ではなく4(5(a))とするべきらしい。同じ文字列を9個までしか見ないようにしたところAC(285分) 今思い返せば最初ロリハじゃなくstd::string::substrで一致判定してTLEになったらロリハ書く、みたいにやればよかったなあ。

私がロリハの実装で苦しんでいるをしている時にyasagureさんとusatyoさんがGを考えて結構進んでいたらしく、書きますか？といったところまだ考察の細かいところが詰めれてなくて実装まで合わせて15分じゃ到底無理とのことらしく、手持ち無沙汰だったので実装が間に合わないと思いながらEの2048通り全探索を書く。このEは全然想定解法じゃなかったし結局これで通せるかは分からない（仮に通るとしてもめちゃくちゃ実装が重くなる）が、yasagureさんとusatyoさんが考えてたGは解説聞いたところかなり良いところまでいってたらしい。

コンテスト後

順位発表。elephant_spaghettiは5完(ABDFK),41位だった。その後懇親会？があり、JAG夏合宿で話したまーたさんやだれさんなどと話したり、TwitterではFFだったが対面での面識はなかったlogKさんやShirotumeさんなどと話した。HUPCの時の名札を持っていったのだがこの時Twitterのアイコンがあったおかげで向こうから気づいてもらうこともあり持って行って良かった～と思った。chokudaiさんやけんちょんのような有名人とも話すことができ、Youtubeとかで見る時と同じ見た目で同じ声だ！と思った。（それはそう。）JAG夏合宿で知り合った人で喋れなかった人もいるのでそういう人とも話したかったなとは思いはあるが、色んな人と話せてよかった。懇親会が終わるくらいのタイミングで飛行機の時間と今の時間を見比べて「ヤバい！！！」となり爆速で会場を出ることに。途中自分以外に人がいないエスカレーターでキャリーバッグを落としてしまい爆速で滑っていったが、人がいないエスカレーターで本当に良かった。本当に。あれで他の人を巻き込んでいたらと思うとぞっとするね。飛行機の時間がヤバい！！！と叫びながら（もちろん、実際に声を出してはいない）移動することで横浜駅で爆速での乗り換えに成功。乗り換え案内より一本早い電車に乗って羽田に着くことができた。そのまま一本早い飛行機に乗り一本早い電車に乗り一本早い人生を……、というわけにはいかず羽田空港で以外と暇を持て余したがまあ余裕があって良かったということで。都道府県境の長い飛行機から降りるとそこは雪国だった。横浜でもday2とかは結構寒くて「札幌か？」とか言ってたんだけど札幌では雪が積もっていた。この日はコドフォのdiv2が23:35からあり出ようかなと思っていたが帰宅が間に合わなかった。

day3

またいつも通りの日常が始まる。

 

感想

楽しかった！！！！2022年のICPCは国内予選に出て全然惜しくないラインで落ちたのだが、年末にYokohama Regionalに出てる人達のツイート見てて楽しそうだな～と思ったので今年出れて嬉しかった。来年も出たいね。来年の今頃はどれくらい強くなって誰とチームを組んでいるか今はまだ分からないけど、今より成長してると良いな。あと今年は「正直playoff進出はまあ厳しいだろうな～」と思っての参加だったけど、ワンチャンの上振れ狙いとかでもplayoff進出があり得そうだったらまたモチベーションも変わりそうなのでそういうラインに立ててると良いね。（ところでYokohama Regionalで何位くらい取れればplayoff進出が現実的なんですか？）

反省としてはチームとしての立ち回りをもうちょっと決めても良かったような気がする。elephant_spagetthiは使ってる言語がバラバラなのと、考察力が強い人が多い反面実装力が強い人がいないので各自で考察して思いついた人が書く、みたいなパターンでやっていて、国内予選はそれでうまくいったけど今回はそれが悪い方に作用した感があった気がする。あんまり立ち回り決めすぎても臨機応変に動けなさそうみたいなイメージがあるが、せっかく時間はいっぱいあったしそういうのを試しても良かったかもな～、という気になってきた。というか個人でコンテスト出る時も立ち回りで失敗したな……みたいになることあるしそこら辺の力もあるに越したことはないし考えていきたいよね。

感想を前向きな感想→反省の順でやっちゃったから暗い感じで終わる雰囲気になっちゃった！！！！！でも何より楽しかったです！！！さっきも言ったけど来年も是非！！！！！強くなるぞ！！！！！！