茶処・まっちゃら亭の一休みばしょ

UnionFind教信者が、何か言ってるブログです。

典型?もしくは怪訝?ラテのこれまで作った問題まとめ (2024.1月版)

Prologue

どうも、まっちゃラテです。今年二回目の登場です。
今回は、どっかからの綺麗な白鳥さんなのかスコティッシュフォールドなのかよくわからん人からのリクエスト企画です。

早速ですが、急に寝る直前にX(旧Twitter)でこう言ってきたんですよ。

:

:

:

:

「あのさぁ、君の問題沢山解きたいから、記事にまとめてくんね?」

:

:

:

:

まず、言わせていただきましょうか。お気持ち表明。

:

:

:

:

:

:

:

:

ありがとうございます。何より、すげぇ横暴※な言い方ですが、すげぇありがたいことです。
こんな現茶元緑コーダーが作った問題を解いてくれることが、本当に何より暖かいです。もしかしたら、おふとんより暖かいかもしれません。

:

(おふとんに銃を突きつけられる)
いや、やっぱおふとんには勝てませんね。やはり。正義。神。結婚対象。

:

※本来の言い方より259%誇張しています。本来の言い方はもっと丁寧であり、丁寧です。

本題へ戻りたい

本題へ戻ります。この記事は先述した通り、私が今までに作問し、公開してきた問題をまとめるといった、なんともシンプルな記事です。
言っておきますが、もちろん悪問であったりすることもあります。これは人によって難易度の捉え方、問題の解釈の仕方で違ってくるので、一概に「こいつが作った問題すげぇ最高な問題だらけです」とは言えません。

前置きがすげぇ長くなりました。では、どうぞ。

※これらの問題でこの先不具合が見つかっても、修正しないかもしれません。重大であれば修正します。ご了承ください。

始まりの作問er (Thanks to yukiCoder 様)

調子に乗ったラテ (Thanks to MojaCoder 様)

(これは裏話の記事に一言が書いてあるので省略)

GTXC(第一回目の単独コン)

MRSC(第二回目)

MSABC(第三回目)

※裏話書いてないけど、本当に書くことないです。。。すみません。(単に忘れてるだけ)

GTXC-GS(第四回目)

やばいね

改めてまとめましたが、こんなに問題作ったんだ....
全然実感がないです。こりゃあ、緑になってないと努力と能力に矛盾が生じますね...本当に。
申し訳ございませんでした(?)。これからも精進を沢山やっていこうと思います。

継続は、力なり。

Epilogue

ありがとあの白鳥さん!!!!!!!!
おかげで自分の無力さを実感したよ!!!初心って大切だね!!!✨✨✨✨✨✨✨

End.

今年の冬も、緑茶と一緒に。~4回目の単独コンテスト~

Prologue

こんにちは。久しぶりですね。
今年も私、まっちゃラテは4回目の単独コンテストを開きました。

その名も
Green Tea's Xmas Contest ~Grand Snowing~ : GTXCGS

※サブタイトルに特に意味はありません。

今回は、このGTXCGSのうらばなしをしていこうと思います。
こんなテンションな私ですが、背景ではかなり厳しいことが山積みであったりして...

なぜコンテストを開こうと思った?

ええ...これには別に深い理由はないのですが、もうほぼ、毎年恒例行事となったというか...本当に

「作問スタックもたまってきたし、いっちょコンテスト、開くか☆」

という浅い一心でした。そう、この決心は確か...9月?あたりですかね、そこらへんに決定したのです。

突然ですが、皆さんはレポートというものをご存じでしょうか。なんかの科目の授業に対して、どういう原理で、どういうことを学び、どのように活かすのか、をまとめ、人に発表するといったようなもので。文理問わず、一回くらいは書いたことがあるでしょう。
私の大学では、9月は後期が始まったばかりでした。これは何を示しているのかというと、このころは、まだレポート課題がマジで少なかった時代でした.....

なので、コンテストを開く余裕を持っていました。
あの地獄を、突きつけられる日が来るまでは。

9月: コンテスト問題調整

9月。課題がとりあえず余裕な日々が続きました。
問題をスタックから取り出そうと思い、散策しました。というか、探索してました。...え~.....

案の上、コンテストに向いていない問題たちでした。取り出したのは、たった1問。
そう、つまりほぼすべての問題を1から考え始めたのです。

はっきり言いましょう。マジで、きつかったです。この理由は、後程わかります。

10月: Tester公開に向けて、最終調整

10月。ここから課題がたまってきました。いうてもまだ余裕くらいですが。
さぁ、ここから地獄のテストケース作成、解説作成、問題文調整です。これが地獄の作業かどうかは、作問者の天才の度合いによって変わるので一定に地獄とは言えないですが、マジで地獄でした。

というのも、この時期はもう勉強に力を入れないと授業に追いつけない(そんくらいの難易度)だったので、せっかくのABCも参加できず、まともに精進の時間も取れないといった日々が続きました。

つまり

私の知識と能力は、茶色にとどまったまま、でした。

ええ。これからわかる通り、作問適正難易度が茶色であったにも関わらず、過去の自分が開いたコンテストの問題を見直してみると、

緑、
水色、
青色...

どれも足を踏み入れたことのない領域です。

嘘です。一度はあります。

でも、でも!!!当時の私にはどれも解くのにまだ脳が足りない時期...
この頃から、精進の時間が足りないと自覚しはじめ、課題は先におわらせ、精進の時間を取ろうと思ったのです。

しかし、大学生はそうはいきません。

:

:

バイトという奴が、一筋の光に通ずる道に向かう私の行く手を阻んでいたのです。

:

:

私が受けるバイトは、週3。1日5時間弱。ええ、こんなに時間が無駄...いや、お金をもらっている身なので決して無駄にはならないのですが、精進の時間をとるためには、本当に邪魔だと思っていました。正直。

こうしてバイトに嫌悪感を感じ、また問題調整の時間が夜中しか取れず、午前はおふとんタイム(こういう時間も無駄に感じるかもしれないが、一種の癒しなので💕)であり、時間の大切さを、知り始めました。

というより、時間が本当に早く過ぎていくんだ...と思い始めたのはこの辺ですかね...><

:

:

:

あ、で、問題調整の話に戻るんですが、課題とバイトのおかげで精進の時間が取れず、まともに解説がかけず、自分を責めるみたいなこともしていました。

なので皆さん、作問するときは絶対適正難易度で作ったほうが、無難です。
この経験から、精進の大切さを改めて知りました。

:

:

?

え、なんかテンション低くないかって?記事の文からして?
いや、気のせいです。風邪の病み上がりなので、読者の皆さんがバイアスをかけられているだけで、私は今すごく元気です!!!!!!!!!!Fooooooooooooooooooooooooooooooooo↑↑↑↑

(無理やり)

11月: Testerが天才しかいなかった件

11月。ええ、言わずもがな、レポートがどしどし入ってきました。そして苦手科目の課題もたくさん入ってきました。面白くなってきたねぇ!!!!!!

この月は、やっとTesterさんを集め、テストをしてもらいました。

:

:

:

:

ええ...

:

:

:

:

問題の不備が、多い?

:

:

終わりです。
そう、問題の不備が多すぎて、これはコンテスト開こうと思った自分は大バカ野郎なんだなとおもいました。

確かに、確かにね!!
ディスコのある競プログループで、こう言われたんですよ。

:

:

「1B(1年生後期)でコンテスト開くなんて、結構大変じゃない?」

:

:

あの頃の自分は、課題が本当に少なかったので余裕をこいていたんですが、
この時期になると、あの言葉が、しみます。体中に。緑茶を体中にかけて染みわたるような、あの感覚。(?)

いろいろありました。本当に。
なので、ちゃんと精進して能力をつけてからコンテストを開こうと思いました。

:

:

:

:

それもありますが!!!
まずTesterさんを集めてテストしたんですが、Testerさんが天才すぎて追いつけませんした。理解も能力も。

:

:

やばい、書くの面倒になってきた。書きますけど!!!!!!

:

:

そう、特にEx問題。これ、水~青を狙って考えたものなんですが、えー解説も実装もきつかったです正直。でもTesterさんが天才すぎて、トポロジカルソートしてDPという。え、何言ってんのこの人たちと思いましたもの!!!

たくさん質問しました。でも、知っているでしょう。

:

:

:

私が負けず嫌いなことを。

:

:

:

なので、あんまり人に頼りすぎない程度で自分で解決したかったので、あえて質問しないといった最悪の選択をしましたが、ええ...

トポ+DPは、そりゃ思いつかないよねぇ...
私は最初、ダイクストラ法の応用を解答例にしていましたが、嘘解法なことがわかってですねぇ...本当につよつよerに見てもらうって大事ですね。。。

そんなこんなで、いろいろメンタルを壊されていました。
大学とバイト、無くなればいいのに!!!って思い始めました。時間が、ほしい。。。

12月前半: メンタル壊れかけのラテ

12月前半。レポートは当たり前のように残り、勉強は当たり前のようにむずい。
これはやばいです。勉強がついにきつくなってきました。

せっかく誕生日(12/5)だってのに、レポートは無慈悲に出されていました。誕生日の夜に気合で終わらせました。

コンテスト調整もやっとラストスパート。...だと思ってた私がバカでした。

:

:

解説コードのバグ、
テストケースの不備、
解説の記述不備、
問題文の修正......

:

:

あんなに自分だけで調べて!!!!Testerさんは本当に鋭いところを突いてきました。同時に自分の今の能力に喧嘩売ろうとして(?)、メンタルは「壊れかけのラテ」になっていきました--

多分、私のX(Twitter)のFFさんならご存じだと思いますが、壊れてましたね...
ABC出れなくて嫉妬して。バイトの際の態度悪い客の悪口を言って。望みもしていないのにお気持ち表明して。唯一のストレス発散だったと思っています。

そんなこんなで、私のメンタルは崩壊寸前でしたが、気合で泥を泥で洗い返しました。ストレスに、打ち勝ったのです。

:

:

:

そして、12/28。無事、コンテストを開くことができました。
あそこであきらめなくて、本当に良かった....✨✨

問題分野別のうらばなし

ここからは問題別のうらばなしについてご紹介していきます。 ※ネタバレ注意!

A: Swap to Right

どこからともなく、swapという言葉が出てきて、文字列操作の問題を作ろうとしたら、こうなりました。
これは特にうらばなしはないです。

diff予想は、10~60くらい?

B: Footprint 2

前回のGTXC↓ mojacoder.app

この回では、Footprint(足跡、という意味)という、なんとも綺麗なタイトルの問題を出題しました。
このインスピレーションを受け、今回は2作目として作りました。そしたら、LRUDで移動の看板が立っており、雪玉を大きくするといった問題ができました。

正直、良問を作るのがきつかったです。
ただ、問題が綺麗だったので、これで行こうとなりました。

そして、今回も重実装を狙ってみました。やっぱBはこれくらいじゃないとねGTXCは特に!!!!!!^^

diff予想は、100~250くらい

C: Graph Palindome

ええ、言わずもがな、一番の良問だと思いますこの回においては。
これはスタックから取り出した問題です。でも当時はまともに解けなかったのでお蔵入りにしていましたが、なんか解けるようになっていたので採用することにしました。

今回のコンテスト、伝家の宝刀であるUnionFindちゃんを用いる問題がなかったので、せめてCにグラフ要素を入れようと思いました。
そしたら偶然にも、UFを使って実装できたので、got a kotonakiを得ました。

diff予想は、300~500くらい

D: Prevented to Carry Snowman

実は、去年の冬、雪が降ったのですが、その時に思いついて作ったものです。その改題です。
前回の問題は、幅優先探索の評価式の変更を問う感じでしたが、Overflowやら不等式だけど小数誤差があるやらで、なんとなく恐怖を感じたので、さらに簡易化したら、いつのまにか根付き木になっていました。
まぁ、現代に応用できるかと言われればできると思ったので、これを採用しました。

diff予想は、450~600くらい

E: Jingle,Jingle,Presents!!

これも、スタックから取り出したものです。yukicoder様のサイトで出題しようとしたやつですが、いつの間にか忘れ去られた神殿になっていました。
なんと問題はそのままを採用しました。ただ、ストーリーがめちゃくちゃになったのだけは、後悔しております。。。

F: Walnuts in Xmas Lease

3回目に開いた夏のコンテスト、Matcha's Summer Amazing Part-time Contest -MSABC- 🏝🍉 | MojaCoder に出題しようとしましたが、いろいろ不備あってお蔵入りになったやつです。
でも、優先度付きキューを用いれば簡単になることを知ったので、どうにかしてもっと難しくしたいと思った結果、こうなりました。

Testerの方たちは、二分探索などでさらに高速になるといっていましたが、メンタルのおかげで脳が言うこと聞いてくれなかったのでこんな制約にしました。

diff予想は、700~1000くらい

G?: From matcharate12

驚いたでしょう^^
題名に私の名前を入れて、手紙の題名ぽくしてみました。

まぁ、そういう意味もあるんですが、本当は、「タスクをほどよく切って、楽に生きよう」というメッセージを込めた問題にしたのもあります。

:

:

:

:

え、なんか問題文を言ってる内容が違う?
そうです...その問題は、bitDPを用いる問題になってしまって、私の能力不足で絶対解説書けんと思い、なんか互換の操作の問題になっていました。

実はこの問題もスタックから取り出したものです。本当は辞書順最小からK番目に相当するように、互換の操作をしろみたいな問題を作っていたんですが、この「辞書順からK番目に相当するような順列」を計算するのが調べればすぐに出てくることを知って、冷めたのです。

なのでこうなりました。

diff予想は、800~1100くらい

Ex: Prevented to Carry Snowman REVENGE

D問題をさらにむずくしたやつですね。Ex問題、本当は全く別問題を考えようと思っていたんですが、メンタルといい心の健康状態といい自分の能力の度合いといい、無理でした(直球)。
ストーリーもなぜか最後は意味深な感じになっていますが、別に私は「本当は雪が大嫌いなんですよwww早く夏になればいいのにwww肉まん食いてぇ」という意思も別になくて、雪が大好きなのは本当です。じゃあ真実の顔の口に私の腕を当てはめてみましょう。

:

:

腕が、取れなくなれましたね。

:

:

じゃなくて!!!

とりあえずここの問題は!!!考えるのが!!!!むずかった!!!!
だからこそ精進は大切であることを知りました。色々な観点から問題を見ることは、大切です。皆さんも気を付けて人生を過ごしましょう。

diff予想は、1100~1500くらい

終わりに

皆さん、本当に今年もありがとうございました。今年は、3回もコンテストを開いたようです。
来年は、コンテストを開くかどうかは、決めていません。なぜなら、精進しないと強くなれないし、というより緑に戻らねばならないという使命感が強いためです。

なので、コンテストを一回も開かないかもしれないし、逆に599回くらい開くかもしれません。
1回も開かないなら、私はやりたいことに夢中になっていると、解釈してください。時間が、ほしいのです!!!!

Epilogue

来年は、さらに充実するような年にしたいな。まずは、目指せ水色!!!
そして、コミュ力も同時に身に着けて...

To be Continue...🏔✨🌅

ぴょこっ

皆さんは風邪にお気を付けください。はっきり言って、この記事を書く気力がありません。
なので文がめっちゃアレになってましたね、、、今度からは万全の状態でテンションMAXで書きます。

では、またどこかで。

ラテ、AHCに初参戦してみたらしいです。

お久しぶりです、まっちゃラテです。
なんと私、プログラミング歴3,4年で、初のAHC(AtCoder Heuristic Contest)に参加してみました。
その備忘録として、なんか何をしたかどうかを、ここに記しておきます。 初心者なので参考にできることもあれば参考にもならんほど当たり前なことを言ってるかもしれません。なのでそんな真剣に見ないで、ジェットコースターに乗ってる最中に見ておく程度でお願いします。

では、早速書きます。
お楽しみください。

※ストレスやばすぎるのでなんかよくわからん部分もあると思われますが、溶岩のような温かい目で届けてください

1日目(参加初日)

何もわからん。

とりあえずBFSで最短距離を計算。でも水路の境界線のやり方で詰み。得点は取れず。

バイト、大変でした。英語でオーダー初めてなんだもの!!!!

2日目

やっと境界線探索のバグを発見、(といってもif文条件式をがちゃがちゃしただけ)修正した。やっと動いた...
そして初めて SampleCode の存在を知る。見てみた。なんだこのコード!!!わからん!!!

とりあえず見様見真似で、自分が実装したGrid探索以外のコードを書いてみた。書いてみると、そんな難しくないのね...
で、SampleCodeを出してみた。143000pt。これが...みんな最初にやるやつなのね。じゃあ自分社会性なかったわごめんなさい。

※以下 n は、k がindex同不順で k_1,k_2,...,k_nn 個のみを植える作物として採用させる個数とします。

n\le\min(K,10)10 をいじくってみると、n\le K のままだと TLE、n\le\min(K,40) でぎり 200msに収まるくらい。へぇ~...。面白いじゃん。
自分の実装したコード+templateコードの局所的参考で \min(K,40) に変えて提出。結果572000 pt。今回 100万は行きたいな...頑張ろう。

計算時間がかなり長いことを知った。線形時間×線形時間...なるほど K じゃ間に合わないわけだ。知らんけど。
そこで思いついた最初の探索高速化の方針、

それは迷路を \text{UnionFind} で管理するということ。

巷ではアッカーマンの逆関数がかなり定数としてみなせることができるといわれている。

これで管理すれば、かなり高速化できるので、n\le\min(K,200) くらいは行けそう O(nHWT)=8.0\times10^7まで、十分間に合いそうではある。
他にも考えた方針はあって、余った土地は活用したいのでDFSの帰りがけ順で S_k が大きい順に埋めていくといったことである。これも...むずそう。

ただ is_valid_move 関数を使えば楽に判定できそう。
3日目も頑張る。

3日目

AHCのことしか頭になかった(正直)。ということで実装開始。
昨日はtemplateの存在を初めて知ったので、そこから派生させようと考えた。

1日目で気づいた方針を活用することに決めた。
それは、BFSで計算した各マスと (i_0,0) からの最短距離から、D_k が遅い順に、かつ最短距離がより長いマスを採用することを考えた。

そうして実装し、templateも参考にしながら変更を加え、提出。得点は 743050pt。前回より 20 万も上がってるので、まぁよし!

templateでは、n\le\min(K,10) 個の作物を植えているが、n\le\min(K,30) でも時間に間に合ったことが分かった。なのでこの性質を使ってみる。

templateは愚直DFS、かつ毎度 O(HW) まで回しているので、かなり遅いことが分かった。
そこでさっきも言ったBFSの計算テーブルを利用して、最短距離の MAXmx から mx-1,mx-2,...,0 としてどんどん計算してみた。このときはtemplateと同じ感じで、空いているマスがあったらそこを採用する。この方法で提出してみると、得点は 2564050pt。初期に比べてみたらかなり上がってきた。超うれしい。

ビジュアライザを見てみると、作物 k=1,2,...Kとして1つずつ丁寧にマスを探索していたので、余分なマスがかなり多かった。

なので k=1,2,...,K ではなく、k ごと回しながら空いているマスを採用する、といった方法で実装してみた。提出すると、得点は 6991225pt。さっきの1ずつ回すのに比べて 400万pt上昇。かなりよくなったし、X (a.k.a Twitter) で見る天才な方々の過去のビジュアライザを見てみると、なんだか似ているような気がして、もっと嬉しくなった。

やっと "H" の楽しさを噛み始めた。
ただまだまだ改良の余地しかないことは自分でもわかっているので、もっと頑張ろうと思う。

4日目

やっぱり朝からAHCだよね!!になってしまった完全に脳内が(完全なる倒置法)。
3日目に気になっていたスコア上昇法、X_k=D_k-S_k+1 が大きいほど加算されるスコアも増えることに気づいていたので、D_k-S_k の大きい順にソートできないかと思っていた。
でもバグが何なのかわからなくてあきらめかけた。なので、まずはコード全体のリファクタリングを行った。

すると、変数 d が重複していることに気づいた。for文のカウンタ変数と同じ名前だったのだ。

というのも、3日目に \text{TIME_LIMIT} まで許す限り解を見つけ出すといった方法を用いていた。そのとき計測時間も d だったのだ。
d がかなり変な動きをするので、不安だった。しかしなぜか n\le\min(K,475) が間に合ったので、そのまま変数だけ変えてあとは放っておいた。

dtime にして、もう一度実行。
ん、ちょっと待って。スコア減ってない?

不安の気持ちいっぱいで提出してみた。得点は... 6981800pt。ええ、減りました。しかも 9000ptだけ。この誤差、命取りです。

そしてもう一度、あの D_k-K_k ソートを考えてみた。
templateを見直したり、デバッグしたり。すると、思っていた通りのバグを発見した。
(3日目ももちろん思ったけど、何もわからなかった)

indexが間違っていました。大変申し訳ございませんでした。
そしてそのバグを直し、いざソート。うまくいきました。
そしてビジュアライザを片手に実行。\text{seed}=0 ケースで [text:20] 万を超えました。
これは...いける?

提出してみた。得点は、なんと 13955525pt!!

生まれて初めての H で 1000 万の大台を達成!!!!!
思わずガッツポーズをかましました。ああ、神様ぁ...
AHC、ガチ楽しい。

(ちなみになんかソートの単調性があり S_k がほどよく大きい、といった性質から、ソート済の配列で10番からの要素を探索してみましたが 40000pt減少しましたありがとうございましたおはようございます)

5日目

もう何もわからない!!撤退したい!!!!でもしない!!!楽しいから!!!

ソートの評価関数を D_k-S_k が等しいときは S_k が速い方にする、にしてみて提出。得点は 13944450pt。減りました。ありがとうございました。

とりあえず、plant・harvestの採用リストを無駄に再計算していたので、それを1回で判別できるようにした。でもそんな変わらなかった。。。
なのでやけくそで \text{TIME_LIMIT} の上限を上げて提出。結果は 14304175pt。これが俗にいう、微増か.....

6日目

バイト行く前に方針を考えてみた。
もしかして、各月の盤面は t=S,D にのみに依存する...?全部T=0,1,2,...調べなくていい?

ということで実装してみた。

:

バグりまくった。

:

バグりまくった。

:

バグりました。

:

:

:

:

:

:

さようならみなさん。私は雨の一部になります。

悔し紛れにplanだけで表してみて、提出。少しスコア伸びた。得点は 14945700 pt。500000 伸びただけでもだいぶましでしょ!!!

7日目

うーんと、まぁ...バイトの時間もあるし?某精進鯖からBANされるのを回避するための緑問解く時間もあるし?なんなら明日のゴルフの準備もあるし??

...いや無理!!!時間がない!!!! 皆さん、対戦ありがとうございました。私は雲の上で寝ます。

後悔と反省

初めてAHCに参加してみましたが、めっちゃおもろい!!!!
こうやって現実とリンクできるような問題を解くと、本当にいいな~と思いました。
というかこういう社会に生かせるようなコンテスト(ABCもそうですがAHCもかなり生かせる)に参加して、自分で解を編み出すの、めちゃくちゃ楽しい...

でもそのためにはやっぱりABCをやりまくる必要があるんだなと思いました。そりゃそうだよね~...
他の天才たちの解法を見てみると、私の親友(?)のUnionFindくんでなんかやってる~感動友達になってくれてありがとうと思いました(めちゃ上から目線ですすみませn)
ただ、やっぱり S_kD_k のみに依存する、って方針実装し切れたらよかったな~と思いました。
まあ時間がなかったので...仕方なかったです。方針が完全にあってるのかどうかも確信がなかったので、結局実装しなくてよかったのかな~とも思いました。

ちなみに...

BFS計算を \text{UnionFind} で管理する!とかほざいてみましたが、皆さん、よく考えてみましょう。
計算済のマスを UnionFind で管理すると、1つのマス毎に O(\alpha(HW)) かかるんですよね。

んでBFSをグラフで考えてみると、計算量は O(N+M) っていうのは有名ですね?
グリッドにすると、N=HW 個の頂点 M=4HW ※辺のグラフとして考えると、大方計算量は O(HW) かかるわけなんですよね。

そして結論、UFちゃんで管理すると O(HW\alpha(HW)) かかるんですよね。

まぁつまりは?計算量が、悪化しま~す★
アッカーマンの逆関数だけにね★

:

:

:

:

:

:

:

M=4HW といっていますが、これはグリッド上の移動が四近傍のためです。八近傍なら M=8HW となります。

Epilogue

家のエアコン、AI付きだって言ってるのに私の好きな温度がわかってくれないの!!?!?
じゃあ強くなったらプログラム改善させてあげるね!!!!!!!!

End.✨

ABC-110 C - String Transformation 別解説

またここに来ました。
今回は緑梅していた時に公式の解説や他の人のユーザー解説とは異なった(かな?)解答をしていたので、一応共有しておきます。

問題はこちら

※この解説は筆者が個人的に書いてるので、読者のみなさんが求める厳密な証明などは書かれていません。ご了承ください。

公式の説明(ざっくり)

正直私も正確に理解できてません(おい)が、とりあえず次が成り立てばいいということだと思われます。

  •  i \neq j であるとき、 S_i = S_j ならば  T_i = T_j である...① (異なる英小文字に置換するので合ってそう)

これは、例えば

abcb
afdf

などの入力の場合だと、

  • a は何も操作しないようにする(明らかに  S_1 = T_1 であるため)
  • b 2 , 4 文字目にあり、f も同じ位置  2 , 4 文字目にある
  • cd に置換するなどする

ことで、答えは Yes になります。しかし、

abcb
afdk

などの入力では、

  • cd に置換するなどするが、(  S = abcb T = afck となる)
  • bf に置換すると  S = afcf T = abck となる
  • その後 kb に置換すると、 S = afcf T = akcb となってしまう

したがって答えは No になります。こうして実験してみると、確かに①を満たすときに限り成り立つことがわかります。

この  i , j を全探索してしまうと  O ( |S|^2 ) となり間に合わなくなるので、置換表をうまく利用して  O ( |S|) に落とす、といった方法が書かれています。

自分なりに考えた解法

この""置換表""が私にはあまりよくわかっていないので、そんなことをせずに、各文字列  S , T について次の配列を作って判定することを考えました。

  •  S_{ i , j } := 文字列  i (  i=1 のとき  S を、 i=2 のとき  T を表す) における  j\ ( 1\le j\le 26 ) 番目のアルファベットがある index の配列

というか、単に  S , T に対して位置するアルファベットの index を配列として保管すればよいと思います。これは C++ 言語では map (連想配列) を用いて容易に実装可能です。

そして、今調べている文字列に対する map に対して異なる文字列について①の条件を満たすか調べればよいです。詳しくは以下の実装例をご覧ください。

以下は解答例です(C++)。こちらはSubmissionです。

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i < b; i++) //[a,b)
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(all(A))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<ll,vector<ll>,greater<ll>>;
const ll inf = 8e18;
const int iinf = (int)1e9;
const int mod9 = 998244353;
const int mod1 = 1000000007;
struct Edge { int to; ll cost; int from; };
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
using Graph = vector<vector<int>>;
using EGraph = vector<Edge>;
using SGraph = vector<set<ll>>;
template <typename T>
int siz(T& a){return (int)a.size();}

bool judge(const map<char,vector<int>> mp,string base){
    bool aok = 1;
    for(auto& [k,v] : mp){
        bool ok = 1;
        if(siz(v) != 1){
            rep(i,siz(v)) if(base[v[0]] != base[v[i]]) ok = 0;
        }
        aok &= ok;
    }
    return aok;
}

int main(void){
    string s,t; cin >> s >> t;
    map<char,vector<int>> mpt,mps;
    rep(i,siz(t)) mpt[t[i]].push_back(i);
    rep(i,siz(s)) mps[s[i]].push_back(i);

    cout << (judge(mps,t) && judge(mpt,s) ? "Yes" : "No");
}

※1 judge 関数内において rep(i,siz(v)).. とありますが、拡張for文で実装してもいいと思います。その判定元となる文字 base[v[0]] の処理が余計にコードを増やすかなと思ったため、こう書いています。

※2 judge はどちらの文字列に対しても判定する必要があります。そうしなければ、例えば

ajaa
bjbn

bjbn
ajaa

の少なくとも  1 つ以上のケースなどで落ちると思われます。

Epilogue

文字列も好きなんですよね~
なんか、こう、自由性がありますよね入力ケースなどに!!!!!!

AtCoder Beginner Contest 294 参加記

こんにちは、またやってきました、ABCのお時間です。
今回はかなり楽しかったですね...問題も解答も!!!

※あ、この記事は C++ only です

結果

今回は ABCD 20分以内早解き、E 50分以内でした。パフォは 1177 と、なかなか私にとって好成績でした。
レートは 852 (前回比+43) に上がりました。よしよし...

今回のABCの結果

:

:

:

:

実は、E 本番 AC は、この回が初めてです。あまりにも突然すぎたので、私はAC直後に素直に喜べませんでした...すみません

解説

※思考ふわふわ解説になっています。厳密に解説していないので正当性もふわふわなので、「ふ~ん抹茶ってこんな美味いんだ~」程度で見てください。

:

:

:

:

A

問題はこちら

まぁ普通に、for文+if文で頑張りましょうって話です。
偶数かどうかは A_i\bmod 2=0 かどうか判定することで実装できます。

Submissionは以下のようになります。

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i < b; i++) //[a,b)
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(all(A))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<ll,vector<ll>,greater<ll>>;
const ll inf = 8e18;
const int iinf = (int)1e9;
const int mod9 = 998244353;
const int mod1 = 1000000007;
struct Edge { int to; ll cost; int from; };
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
using Graph = vector<vector<P>>;
using EGraph = vector<Edge>;
using SGraph = vector<set<ll>>;
template <typename T>
ll siz(T& a){return (ll)a.size();}

int main(void){
    int n; cin >> n;
    rep(i,n){
        int a; cin >> a;
        if(a%2 == 0) cout << a << " ";
    }
}

B

問題はこちら

まぁこれも、普通にやるだけです。
HW 列のグリッドを入力して、そこからアスキーコードで頑張るという感じです。

アスキーコードとは、端的に言うと各文字に振られる番号のことです。逆にその番号が振られた文字をアスキー文字と言います。
例えば a には 97b には 98 の番号が振られています。これは小文字だけでなく大文字でも、なんなら数字、記号などにも同じように振られています。

つまりどういうことかというと、 A_{i,j}. でない場合は、答えは  (A_{i,j}-1)+65(=X) というアスキーコードをアスキー文字に直したものです。ここで 65 という数値はアスキー文字 A に対応しています。わからない場合は、実験してみるとわかるかと思われます。

アスキーコードからアスキー文字に変換しますが、これは int 型を char 型に変換する※ことでできます。

Submissionは以下のようになります (ll siz=...から上は同じなので省略しています)。

int main(void){
    int h,w; cin >> h >> w;
    rep(i,h){
        rep(j,w){
            int a; cin >> a;
            if(a == 0) cout << ".";
            else cout << char(a+'A'-1);
        }
        cout << "\n";
    }
}

※この変換を一般には型キャストと呼ばれるようです

C

問題はこちら

最初は「おっ...!?」となりましたが、問題を要約するとこういうことです。

  • 長さ  N+M の数列  C=(A_1,A_2,...,A_N,B_1,B_2,...,B_M) を昇順にソートを行う。各 A_1,A_2,...,A_N B_1,B_2,...,B_M についてそれぞれの要素が C の何番目にある?

この問題では、全探索をするとざっくり (N+M)^2 回くらいなので、間に合いません。つまりこの「何番目にあるか?」の判定を高速化する必要があります。
制約より、 C の要素は相異なるため答えはただ  1 通りに定まります。よってこれは連想配列などを用いて実装することができます。

連想配列  mp として、キーを要素、値をその index 、すなわち mp[C_i] = i  (1\le i\le N+M) として記録することで、「何番目にあるか」を  log(N+M) で判定できるので、全体で  (N+M)log(N+M) で実装が可能です。

(すみませんtex記法がバグるのでオーダー記法で書かれていませんが、そういうことです)

:

Submissionは以下のようになります。

int main(void){
    int n,m; cin >> n >> m;
    vector<int> A(n),B(m),C;
    map<ll,ll> mp;
    rep(i,n) cin >> A[i];
    rep(i,m) cin >> B[i];
 
    rep(i,n) C.push_back(A[i]);
    rep(i,m) C.push_back(B[i]);
 
    sort(all(C));
    rep(i,n+m) mp[C[i]] = i;
 
    rep(i,n) cout << mp[A[i]]+1 << " ";
    cout << endl;
    rep(i,m) cout << mp[B[i]]+1 << " ";
 
}

(読みにくかったらすいません)

D

問題はこちら

うっ、ってなった問題です。特に日本語がむずかったので、何度も読み直してなんとか通りました。
私は次のようなキュー(set)を作って解きました。

  • st\ := N 人の呼ばれていない人の番号管理
  •  Q\ := 受付に行ってないけど呼ばれた人の番号管理

問題を見た感じ、次のようなことが高速にできるやつを探してくればいいと思いました。

  • 数値 x をキューから消去する
  • ソート済の配列から最初の要素を取り出す

う~ん...と思ってると、天から set が舞い降りてきたのです。そう、set は順序付き集合であるため、数値を挿入するときに自動的にソートをしてくれるのです。 しかも、計算量は要素数 n として  logn です。さらに set には erase 関数で該当する数値を高速に消去することができます。

3種類目のイベントにおいて「最も小さい番号の人が呼ばれる」ということは、ソート済のキューのうち最初の要素を取り出す、すなわち set に対するイテレータ begin を取り出すことで実装可能です。

さらに「人 x が呼ばれる」というのは、キュー Q から数値 x を消去することに相応します。
さらにさらに「受付に呼ばれていない人のうち、最も小さい番号の人が受付に呼ばれる」というのは、キュー st から *st.begin() ※を消去することに相応します。

Submissionは以下になります。

int main(void){
    int n,q; cin >> n >> q;
    set<int> st,seen,Q;
    rep(i,n) st.insert(i+1);
 
    rep(i,q){
        int t; cin >> t;
        if(t == 1){
            Q.insert(*st.begin());
            st.erase(*st.begin());
        }
        else if(t == 2){
            int x; cin >> x;
            Q.erase(x);
            seen.insert(x);
        } else {
            cout << *Q.begin() << endl;
        }
    }
}

* は、イテレータが指し示す要素のことを表します
seen というキューがありますが、関係ありません。最初、受付に行った人のキューとして書きましたが、st が代わりにやってくれているのでいらなかったためです。

E

問題はこちら

一瞬、ふへ?になった問題です。
でも、考えてみましょう。実はこれ、皆さんのご想像通り、私が作った問題とほぼ同じだったのです。

あ、ってなりました。その問題(自作)の想定解、ついおととい(3/18?)に書いたもので、「え、運命の出会い...💕」ってなりました。

私の友だちもなんか高速で解いてたので、それを見てからもう一度見たら思いついたのです。
もしかしたら序盤で気づいていたら青perfも夢ではない...!?!?

:

:

...あ、じゃあ解説に入ります。

ランレングス圧縮された情報をもとに頑張れ!って問題です。
これは A,B 毎に pos という現時点で見る index をもって動かします...ん~、端的に言うとしゃくとり法?貪欲法?ですかね...(本質は違うので多分そうは言えないかもですが)

 A,B 毎の現時点で見る index を pa,pb とします。で、入力は pair でやっているので、first,second を使います。

  • B[pb].second <= A[pa].second なら...
    • A[pa].first == B[pb].first (今見ている整数が同じか?) なら答えに B[pb].second を足す※
    • A[pa].second -= B[pb].second する (見た整数の個数を減少させる、これは pa が探索済であることを表す)
    • pb++ する (このブロックでは pa を基準にしているため、pb を進める)
  • それ以外なら...
    • A[pa].first == B[pb].first なら答えに A[pa].second を足す
    • B[pb].second -= B[pa].second する (これは pb が探索済であることを表す)
    • pa++ する (このブロックでは pb を基準にしているため、`pa を進める)

わかりづらくてすみません、でも実際にデバッグ大臣を呼んでみるとわかると思います...

Submissionは以下のようになります。

int main(void){
    ll l,n,n2; cin >> l >> n >> n2;
    vector<P> A(n),B(n2);
    rep(i,n) cin >> A[i].first >> A[i].second;
    rep(i,n2) cin >> B[i].first >> B[i].second;
 
    ll ans = 0;
    int pa = 0,pb = 0;
    while(pa < n && pb < n2){
        if(B[pb].second <= A[pa].second){
            if(A[pa].first == B[pb].first) ans += B[pb].second;
            A[pa].second -= B[pb].second;
            pb++;
        } else {
            if(A[pa].first == B[pb].first) ans += A[pa].second;
            B[pb].second -= A[pa].second;
            pa++;
        }
    }
 
    cout << ans;
}

B[pb].second <= A[pa].second の条件より、A[pa].second-B[pb].second0 以上になります。つまりこれは A[pa].second 以前に B[pb].second が被覆していることを示すため、そのまま答えに加算することが適切です。これも実験でわかります。多分。

Epilogue

入緑後初めてのABC、なんとかまた上げることができました。とりあえず、作問ができる資格が持てたのでよかったです。

よし、緑梅してきます。

私まっちゃラテは、"抹茶ラテ"に、なりました (入緑・後編)

Prologue

3つ前の私の記事に、こう書いて終わったと思います。

3つ前の記事にこう書いたと思います

注目してみてください。「え~...次書くのは入緑時かもね~楽しみにしててね~!!!www」と、描かれていますね?

:

そして、今書いてるのは、入緑記事です。

:

入緑、しました。

つまり、
私、まっちゃラテは、入緑を果たしました。

今回は、そんな入緑の小話的なものを書きます。

:

:

...え、前編と同じじゃつまらないって?
だって書くことが浮かばないんですもん!!!!!!!!!!その代わりもっと面白い記事にしましょうと思います!!!!!!!!!1

~Main: 入緑までの軌跡~ (後編)

  • 8: 現実逃避
  • 9: 「簡単なものばっかりじゃ、つまらないでしょ?」
  • 10: 手を差し伸べてくれた天使
  • 11: ただただ精進の日々
  • 12: 受験で薄くなり行く知識たち
  • 13: 桜咲くA,B埋め、灰梅の決心
  • 14: 「本」という名の無双
  • 15: 茶梅の出会いとその友情
  • 16: 絶対にあきらめない心

では、描きます。あ、実は記事day2です。

:

...え?キジ(鳥)ではないです。え?盛大に滑った?

:

:

:

:

:

:

:

:

:

:

...ではお楽しみください!!!!!(逃)

8: 現実逃避

さぁ、入茶を決めた私は心が舞い上がるくらいやばい精進のモチベを持っています!!!それでは、精進していきまSHOU!!!!☆

:

:

:

精進してみました。その後、入茶後初のコンテストの日がやってきました。じゃあ、解きますか。ま、茶色だし?余裕~っしょ!!

  • A: 計算は楽勝!
  • B: 該当部分だけ切り出して反転してもとに戻す!Foo!
  • C: うぇ...?なに?これ?
  • D: しゃくとり法...じゃない!?ナニコレ!?!?

はい。このザマです。茶色コーダーだからなんでも解けるぜヒャッハー!!とか、あまり「甘い」考えしない方がいいですよ?(圧
パフォは 423。レートは下がりましたが、まだまだ...こういうもん!うん!運もあった!仕方ない!!!

という気持ちでまた精進をしていました。

:

しかし入茶後、3回目のコンテスト。私の目を覚まされました。

  • A: 普通に計算
  • B: whileシミュ。なんか2ペなしました。
  • C: え。。。あ~。。。なにこれ

パフォは 210 。差分は -31 。
これは流石に堪えました。私の精進不足が柿間見えていたのです。

こっから、しっかり精進しようとしました。しかし...いや、この話はあとで。
とりあえず、4回目のコンテストを見てみましょう。

  • A: ほいほい
  • B: ぽいぽい
  • C: setで判定...?
  • D: なんじゃこれ!!とりあえず順列+bit全探索?->TLEらしい☆

パフォ、驚異の 914 !!そう、初の緑パフォをGETしました。
これは...もう、無双できるわ!!!!って、「油断」した瞬間でした。

:

:

:

あの悲劇が起きることも知らずに。

:

:

:

:

:

月日は経ち、6回目のコンテスト。どうせ、茶パフォはちょちょいのちょいでとれるっしょ!☆の、"愚かな"意気込みで挑みました。

  • A: お見事、n=1に殺されました。(1ペな)
  • B: な☆に☆こ☆れ
  • C: あ~...計算方法はわかったけど...(逆元を知らない人)

はい。パフォは、逆の意味で驚異の 200 ...レート差分も -35 です。

悔しい...というか...悔しい...悔しい...
その思いしかありませんでした。

しかし、この頃の自分はちょっとひねってきたB問題を解けないまま、言い換えれば知識を習得しないでほったらかし状態だったので、まあ妥当な「刑」ですね。

:

:

:

悔しさをバネに、私はみっちり精進をしました。
しかし、その精進はまるで「精進をまともにしていない」と等しい精進法を実践していたのです。その理由は、後々わかります。

9: 「簡単なものばっかりじゃ、つまらないでしょ?」

7回目のコンテスト。とりあえず、解きましょう。

  • A: 平方根か~...(誤差こわい)
  • B: ふへへ...// 負の数こわい... (3ぺな)
  • C: ナニコレ全探索?->TLE
  • D: ナニコレ全探索?(なんも思い浮かばない)

はい。やりました。マジで、やりました。
パフォは 137、差分は -43 です。完全に、やってます。

おかしい...しっかり精進してるはずなのに!早解き力も高めてるはず...!!実装力も高めたはず!!!!!泣泣泣

:

:

そして、9回目のコンテスト。

:

:

:

:

灰色に、落ちました。

:

:

はは...所詮、自分も灰色コーダーの力しか持ってないんだ...アルゴリズム大好きな灰色コーダーで一生生きていくわ...と、正直思っていました。

:

:

:

:

:

:

私は思ったのです。
もしかして、自分は「頭が固い」のか...?

:

:

:

:

え、これは真剣に、そう思いました。
そう、あの簡単なB問題が解けない時点で、柔軟な頭ではない、ただの堅物やん!!!!となっていたのです。

考えの転換も嫌いでした。多分、この頭で入緑きっかけの奇跡の問題も、解けなかったでしょう。どうせ一個に焦点を当て、他の解法には目もくれなかったことでしょう。

なので...これはもう、どうしようもないことです。
確かに基礎的知識はしっかり身に着けました。それの応用が、もしかしたら苦手だったのかもしれません。

そのアルゴリズムを、かくれんぼの鬼みたいに探し出すのが苦手だったのです。(私は小さい頃からかくれんぼは隠れるのがうまい方でしたが)
この問題でどーやってこのアルゴリズムを適用するんだよ~!!!!が、ずっと続いていたのがこの時でした。

:

:

:

頑張ろう。今度は絶対に考え方の転換を容易にできるような人になる!!!!そう心に決めました。

:

:

10: 手を差し伸べてくれた天使

心に火、いや、爆風が降り注いだ灰色レート帯に立っている自分がいました。
(しかし、私も言いました。灰色でも茶色でも、プログラムが扱えるだけめちゃくちゃすごい!!だから心配すんなよ!って。だから、心配は無用です。)

ここで、私は重要なことを書き忘れていますが、何かお分かりでしょうか...

:

:

:

「典型競プロ90問」です。This is 神様です。私もおせわになっております。

(言いながら★2,3しかやっていませんすみません今後は気を付けます)

それを踏まえた上で、精進をしたのもありました。

:

:

:

:

と、ありますが、実は過去にやった問題を総復習していた時期です。
自分は、確かに集中して精進をしていたのですが、それでも人です (何度も言いますが私は飲み物ではないので私も忘れることはあります!!!🍵🍵🍵)。
忘れるのです。忘却曲線をぐいーんとしたにドーンと伸ばした、指数関数のグラフみたいな感じ。

わかります。皆さんの心の声は、どうせ「何それ。(真顔」の一言です。
私も自分で言っててなんも理解できません。じゃあこの話、しなくていいですね。

:

:

:

:

:

:

:

いかんいかん!!このまま話を終わらせてしまう!!!
とりあえず、自分は、知識の総復習をすることにしたのです。

:

:

あ、あとこれもありますね!「アルゴ×数学本」(E869120様) これもやってました!
すいません、付属みたいな扱い方してますが、私ものっぷりはまりました。どっぷりじゃなく、「のっぷり」です。

こうして、数学的知識やアルゴリズムの知識、考え方の転換を再認識し始めたのです。

:

:

:

:

:

しかし、人生です。そんな簡単にうまくいくはずがありません。
わたしはその後の 10~17 回目のコンテストは、まるで y=2\sin x のグラフのように、レートを自由自在に操るように上げ下げを繰り返していたのです。

一時期、入茶後のレート最低値は 351 です。モチベがどんどん下がっていく...

11: ただただ精進の日々

また、心に火が付きました。もうこれは、真剣に集中して精進をしないと、強くなることなんかできるはずがない!!!!!
やっと目を覚ましたようです。"入茶したからってイキってた人"が、やっと"努力を重ねる頑張り屋"になった瞬間です。

もうこっからは、高3。受験も考えないといけない時期です。

:

「のんきに精進をしている場合じゃない。卒業までに、次の色へ...!!!!」

:

(もう何回目か数えるの疲れました!!)

そして 22' 6/25 、レートを維持しながら、なんとかまた茶色安全圏内に入ることができました。

私はAもBも解けなくなっていたので、もちろん復習していました。つまり、A,B全埋めを本格的に始めたのです。

:

:

ただ解きまくります。流石に沈黙もつらいので、音楽をたしなみながら。
解説AC、写経でもいい。身体になじませること。知識を蓄えること。ただそれだけ。

なんも考えないで解かない。とにかく考える。

:

:

:

:

話をいったん変えますが、私は高1の頃、こういう話を高校の先生方から聞いた覚えがあります。

「瞬間的に身に着けた知識を実らせるためには、最低でも3か月は必要。今ここで学びの努力が実らなくても、時を置けば必ず努力のつぼみは花開く。」

本当か~??とか思っていましたが、本当にその通りでした。
私も過去に分からない問題を今解いてみると、めちゃくちゃ簡単!!

「は?昔の自分、こんな簡単な問題も解けないのw?(C問題レベル)」の経験が、非常に多く感じましたね。正直。

なので、もしかしたら、いや、絶対に、「焦りは禁物」は、ガチだと思います。 (※個人差があります)

:

:

:

:

話を戻します。とりあえず、この思いを片手に持ちながら、その時が来るのを我慢していました。
つまり、分からない問題は「時」が解決してくれることがあるのです。この時、今でも大体、私は「時間、1998244353^{998244353} 時間くらいあればなー」とか言っていますが、この時は「1 日、10^{-998244353}] 時間にならないかなー」と思っていました。

:

:

:

しかし、気づいたら、もう 8 月。早ー!!!!!!!!!!! 受験も考えないとなので、いったん 8/6 の LINE 主催コンテスト?かな?そのコンテストで見事、私の大好きな再帰関数たんをばちこりかましながら 780 パフォで休止!!!勉強ZONEに入ります。

:

:

:

:

:

:

:

ふぅ...とりあえず受験形式も決まりました。受験する大学も定かです。
あと、将来の夢も変わりました。きっぱり何とはここでは言えないですけど。

その後はとびとびで参加。9/10 、気分転換に参加しました。見事レート差分は + !いい感じ!

そして...

:

:

大学受験は、無事に、終わりました。🌸 特定多数の人を怒らせる一言というわけでは決してないですが、次の文を書くときにこれを書いていないと、「合格してないのになんでABC参加してんの?勉強してんの??」人が出現してしまう恐れがあるためです。

12: 受験で薄くなり行く知識たち

はい。とりあえず、無事に終わり、ABCに再度参加することになります。

復活してから、2023年になったようです。あけおめことよろぱーりーぴーぽーナイトPonPonPon!!!!!って感じです🌄🎍。

しかし、そんなこと言ってたら、本当にNight Party Night PonPonPon★になったのです。それは、2023年になって2回目のコンテストです。
とりあえず解いてみましょう。

  • A: 2a+1=bか2a=bならYes、以外はNo
  • B: シミュ。ちょっとてこずったけど0ペなでok!
  • C: 26進数!10進数変換!!
  • D: 実験したらUnionFindでサイクル検出じゃぁぁぁぁll!!!!!!

なんと、驚異の 1121 パフォ!!!初 4 桁!!!
レートも +72 !!!!あ~~~~ゆにふぁいちゃん(UnionFindちゃんの意)!!!ありがとう!!!!!✨✨✨✨✨✨✨✨✨✨✨✨

で、多分こっから 「UnionFind 教」という新しい宗教を建てたと、思います。

:

なんか、勉強受験に焦点当てちゃってるし知識薄れていくかな~思うたんですが、そんなでした。

Q.じゃあこの章意味ないですよね?

:

:

:

:

:

  1. そうですけど何か!?!?!?!?!?!?!?!?!?!?!?!?!?!?!?!

13: 桜咲くA,B埋め、灰梅の決心

すいません、上に書いた文そのままなので、そちらを参照してください。

で、灰梅の決心はここからでした。すばらしいことをしたと、今でも思っています。

灰色は...まぁ~~~~~(ここで自分にとって悪夢みたいな問題(個人の意見です) ABC225-CABC223-CABC214-CABC212-C を思い出す)

全部解けます☆

という感じで頑張りました。後述しときますが、この精進法は最高でした。

14: 「本」という名の無双

ここの時期、確か「鉄則本」(E8様) がブームでした!!!私も最初、この名を聞いて、

「これは...買うしかないやろ!!!!!!」

になっていました。だって、""典型+鉄則=最強卍卍""だと思いましたからです。

買いました。早速取り掛かってみました。

「うおーimos法の解説わかりやす!!!え、二分探索ってこんな応用あったの!?DP、典型やっててよかった解説がすんなり入る!!!」

本当にこの喜びの連続でした。買って損は一度もしてません。買ってない人は、絶対買ってください。くらいのおすすめ度!!!!!!!

私はこの最強の組み合わせを片手に、また取り組みました。

:

:

:

:

:

何度も言いますが、私は抹茶です。
飽きました。なので、一回離れ、気分転換に何かしようと思いました。

:

:

:

:

待て!!!あの神サイトのことを書いてない!!!私としたことが!!!!
実は、茶色になって大体6か月が経過した後、とある神みたいなサイトを発見したのです。それは、

:

:

:

「アルゴ式」(けんちょん様) 、です。

:

:

:

はっきり言いましょう。これは、ガチで秘密兵器です。
ここでもURLを出したくない、なんなら名前出さずに自分だけの秘訣にしようと思ったくらいです。

私は、もうこの問題を...いくつやったんだろう、とある章ではもう私は 3 週くらいしてます。記憶がなくなってきたころに、もう一度やっているためです。
本当に、「このサイトなかったら二度と生きていけない!!!!」そう思いました。

:

:

:

...すいません。鉄則本とリアクションが違いすぎましたね。
個人的に、本で学習するのが十分に慣れてないっていうのもあって、サイトを...ほめる方になってしまいました。
もちろん、鉄則本も 3 週くらいはしようと思っています!!!これからは緑の問題を解きまくるので、絶対お世話になります!!!よろしくお願いいたします!!!!!!!!!!1!

:

:

:

と、とりあえずこの本たちを使って、私はしっかりとした""どこにでも活用できる知識""を、新たに身に着けたのです。

15: 茶梅の出会いとその友情

え~記事day3ふぅあぁぁ~(あくび)...ふぅです。朝11時に書いています。おはございます。

こっからは、茶色の基礎知識を集める感じになっていきます。つまり、しっかりした精進をまた新たに始めたのです。

:

:

:

そう、「茶梅」です。それに加え、C,D全梅を始めました。
正直に言いましょう。これでも、まだまだ埋められていませんし、習得途中の問題もあります。
上に書いた悪夢みたいな問題が、そうです。こういう問題、普通に苦手なんですよね...

で、この精進法を、決して舐めないでください。(まぁ舐めてる人は一人もいないとは思いますけどね!!!?!?!(圧 )
この精進は、私はどんだけ苦手な問題でもやりぬきました。C梅したら、まるで世界が変わったように、ABCのCが解けるようになったと思います。

...いや、もちろん苦手分野はあります。多分あの悪夢みたいな問題はもう一度出されたら解ける気が正直しません。
最近はグラフばかりなので(得意分野)、無双できるんだと思います。

ああいう問題が一番平和に感じられますね...
いやしかし!!本当にC梅は世界が変わる!!!!これは断言できましょう!(高校に属していたある先生みたいな口調で)

:

:

:

で?D梅はどうしたかって? D梅...マジで最近始めました。なのでまだまだですが、いや!!C梅とのCombinationがすばらしすぎて!!!
C全梅+D全梅!!!これはぜひやってみてほしいです!!!!嘘だと思うなら!!!!!!!!

Dは、マジでアルゴリズム応用みたいな感じの問題が多く感じられます。
近々、E梅もやるつもりです。水色を目指すなら...絶対やります。

てな感じ?
とりあえず何度も言いますが、
oo全梅は効きます。ぜひ、やってみてください。

:

:

:

:

:

:

あとは、この努力がどこまで実れるか...?
あのとき「時」が解決すると思ってましたが、本当に現れるのでしょうか...?

:

:

:

:

※ちなみ私の経験談ですが、これで、2/4のコンテストで初の水パフォをゲットしました。
レート差分は驚異の +84 です。はい、どう考えようと心は天国に行きました。ありがとうございました。

16: 絶対にあきらめない心

さぁ...レートが 740 付近。あと 60 だけ上がれば、なんと緑になれます。

2/11のコンテスト、参加しました。じゃあ解きましょう。

  • A: むん
  • B: ふにゃ!?レ点、概念は知ってたのに素直に連結成分に属する頂点をソートしてなんたらかんたら
  • C: bit全探索
  • D: 再帰関数(漸化式は全く思い浮かばなかった)->TLEしたのでメモ化->AC!!!!

パフォは 791 。まずまず!
ABCD4完がかなり続いてきました。マジで成長を感じる時でした。

:

:

:

2/19。参加しました。解きました。

  • A: A[B[i]]の総和
  • B: なんかやるだけ!
  • C: ふぇ...実験する->あこれ0,1,2,..の最大値か。ちょっとてこずる。
  • D: ふぇ...実験する->あこれ周期性あるな->何も思いつかない

パフォは 718 。多分、Cで20分経過が痛かったんだと思います。私はこのとき、3完は最低(すべて灰diffの場合)でも10分でACしようと心がけていたので、痛い...

:

:

:

しっかり精進をし、次の 2/26 のコンテストへ。トヨタさん!!!!あのときはがっぽりレートありがとうございます!!!の感謝の念とともに、解きました。
(余談ですが、この時で車買うときはほぼ100%トヨタさんで買いたいと思いました)

  • A: isupper()がtrueの場所!
  • B: う~ん実装煩雑になりそうだしsort+dequeでいっか!!!
  • C: set+pairで確認!
  • D: ほぇ...DPだ確定で->これっぽい->なんで答え合わんの!?!?怒
  • E: この構造...トポロジカル(ソート)くん!!!!!!->なんで答え合わんの!?!?!?!?!?!?!怒怒

パフォは 747。ABC早解きのおかげでレートは変動なしでした。しかし、解説を見た後、事件が起きたのです。

:

:

:

:

:

:

:

「これ、自分の書いたコードと何が違うの...?」

:

:

:

:

:

:

:

そう、マジで何が違うかわかりませんでした。いや、それは理解できない愚か者ってわけではなく、コードは全く同じ意味なのに、何が違うかわかりませんでした。
しかし、気づいたのです。

:

:

:

DPの遷移先を、逆にしてしまっていることを。

:

:

:

:

:

正直言いましょう。これは、本当に、パソコンにうずくまりながら、自分のこの静かな部屋で、隣の部屋に親が寝ている中で、

:

:

:

:

:

:

ひとりで、泣きました。

:

:

:

:

:

:

それも、初めて"競プロで泣きました"。これは、ただただ「悔しさの涙」でした。私はまた、このまたとないチャンスを逃した気持ちでいました。

で、Eの解説も見ました。

:

:

なんと、解法の方針はトポちゃんで、合っていたのです。え~...泣きました。
いや、でもちょっとてこずるところはわからなかったので悔しくはありませんでしたが、やはり D をこのケアレスミスでレート差分をなくしたことに怒りと悔しさで涙でもう前が見えなかった...くらい泣きました。

:

:

:

:

家族に見せたくなかったので、気合で泣くのを止(と)めましたが。
いや、目が赤くなっている...いや、なんでもないです。
とりあえず、自分は負けず嫌いなんだ、と改めて認識させられた瞬間でした。

:

:

:

:

:

そして、私、まっちゃラテは、とうとう高校を卒業しました。🌸🌸🌸
とうとう、卒業前に入緑する夢は、叶いませんでした。
しかし、PC部顧問には、必ず入緑してみせます!"的な"言葉を話して、高校を思い出とともに、去りました。

:

:

:

:

そしてその悔しさを経験の""糧""とし、次の 3/4 のコンテスト。解きました。

  • A: ふみょーん
  • B: ふにゃーん
  • C: 約数列挙と式変形、積の法則典型!!!
  • D: 連結成分に属する頂点数 = 隣接辺の本数-1の総和 であるかどうか!

パフォはなんと 1088。まるで息を吹き返したかのように、レートは上がっていきました。

:

:

私はこの時までの経験を得て、「絶対にあきらめない心」の称号を取得したような気がしました。
諦めなければ努力は報われる。まさに、あの悔しさからそれは True だ、と思います。

:

そして... 3/11 のコンテスト。私はついに...

:

:

:

:

:

:

:

:

:

:

:

:

:

入緑しました。

入緑、しました。(再掲)

:

:

:

:

:

この時は、マジで D 問題が神だった、というのはあります。今でも。
(これは絶対に載せます。 ABC293-D 、これが私をどん底から救ってくれたのです...Writerさん、本当にありがとうございます!!!そして UnionFind ちゃん!!!ありがとうございます!!!!!!)
そして、今までの自分、こんなに努力してくれて、ありがとう...。この念も同時にこみあげてきました。

:

:

:

:

入緑までにやったこと・総括

という感じでした。いかがでしたでしょうか?
自分は...はっきり言って、緑なんか解けるはずがないと思っていました。しかし、本番で緑diffをACできた事実は、変わりません。
言い換えれば、「緑diffも解けるようになってるんだ、自分。」 という成長を一番に感じました。

あ、あと忘れてて書いてなかったのですが...いっか!後で全部書きます!!

本当に!!精進は!!!やってるだけ!!!!知識は!!!!!!!!絶対に!!!!!!!!!!努力が!!!!!!!!実ります!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!(爆音)

入緑までに身につけたアルゴリズム

  • UnionFind (ほぼ必須。これは最終兵器です。)
  • トポロジカルソート (身に着けとくと楽すぎて泣けます)
  • 1次元、2次元imos法
  • 簡単な典型でないDP構築
  • 転倒数 ( O(N^2) 解)
  • セグメントツリー (これは...優先度低め?少なくとも最近は出てこない気が...)
  • 最小全域木 (身に着けると楽すぎて泣けます)
  • パスカルの三角形、Combinationの計算
  • 逆元計算
  • modint (もっとくと便利)
  • 包除定理 (ほぼ必須...かな?くらい)
  • 優先度付きキュー
  • ダブリング
  • 木上のオイラーツアー
  • 期待値計算
  • multiset
  • 座標圧縮 (必須!もっとくとめっちゃいい)
  • エラトステネスの篩

入緑までにやったこと、得た教訓

  • C,D全梅、灰梅、茶梅
  • アルゴ式でとにかく周回!!!!
  • 鉄則本、典型90、アルゴ数学本を読みまくる!!!
  • コンテスト中は、絶対にあきらめない!!!愚直解法と、高速解法を両方思いつけるような脳を養う!!!

あ、あとこれもストーリー中には書いてなかったのですが、

  • 実は、茶色で作問をしていました(GTXC⛄🎄 in Mojacoderさん)) この時は単に興味で作っていたので、問題の質はあまり重視してなかったですが、とにかく楽しめそうな問題を集めたって感じの、クリスマスコンです!問題文がわかりずらいですが、ぜひ解いてみてください!
  • そして、今年の 3/5 、2回目のコンテストを開かせていただきました(MRSC🌸🍡 in Mojacoderさん) この時は、問題の質+解いている時のうずうずしたあの感じ!!を重視しました。GTXCより1000倍以上面白くしました。ぜひ解いてみてください!! (Solverさんたちの反応によると、忠告より難しく感じたようです。私も、茶diffだと思って作った問題は、今は水diffになっています。やばすぎでしょ過去の自分)

で、実は、夏にも、開催予定なのです。続報を待て!!!!!(っていうやつありますよね。こういうの、こういう記事でこういう感じこういう唐突な宣伝をこういう感じでしたかったので、しました。)

あ、作問ってどうやってんのこのお茶は?って思った方は、こちら(私の記事、そして突然の宣伝)をどうぞ~

入茶+入緑まで、これまでの実績

ストーリーで書いた実績を、ずらーっとお見せします。

  • 現時点までに解いた問題数: 1099 問 (oo梅で、大体1週間で100問解いていた時期もありました。多分。)
  • ABCで解いた問題(問題別、G,Exは一回も解いていません)
    問題別ABCで解いた総数 (緑: AC、黄色: Non-AC、黒色: 手を付けてないやつ)
  • 色別で解いた問題数
    色別で解いた問題数 (色付き: AC、薄黄色: Non-AC、黒色: 手をつけてないやつ)
  • 日別AC問題数グラフ
    日別AC問題数グラフ(グラフの高さが...なんかAC問題数?かな)

Epilogue

というわけで、これからは入水に向けて精進をこれまで通り進めます。作問も、片手に。
作問はですね...自由です。なんでも作れるようになり、自分自身で解ける問題も多くなります。私も、自分で作った問題の想定解を作るのが、作ってから 3 ヵ月くらいかかったこともあります。まぁつまりは、その問題作った当時は「作ったはいいものの解法が何も思い浮かばなかった」、ということですね。

でも、改めてその問題を見てみると、解法がガンガン思いつくことがあるのです。これは、確かに過去問でも同じことが起こりますが、作問では「自分の作った問題が自分の力だけで解ける!」ことが、一番うれしいと思える瞬間だと、私は思います。
なので、作問の手を止めることはないだろうと思います。

しかし、さすがに作問だけやってても力はつきません。自分の力を、過信することが多くなってしまうためです。実際、私も、コンテストでレートが下がったときは、「いいも~ん!自分は難しい問題作ってるし~!で自分で解けるし~!!」みたいな愚かな思いで精進をさぼっていたこともありました。

みなさんはそうではないと、私は心の底から思います。なぜなら、この意味の分からん記事を読んでくださっている皆さんが、つよつよコーダーであるからです。

私も、自分の力を時々見直しながら、これからの競プロ精進を日々、重ねていこうと思います。

:

:

:

長くなってしまいました。ここまで見てくれた方々、本当にありがとうございました。そして、入緑を応援してくれた皆さん、本当に感謝しかないです。
では、またどっかで記事を書くことがあるかもしれないので、そこでお会いしましょう。

よし...
作問しよ(おい

私まっちゃラテ、"抹茶ラテ"に、なりました。(入茶・前編)

こんにちは!
抹茶大好き!まっちゃラテです!

入緑、しました。

ついに...やりました。本当の抹茶を、つかみ取りました🍵🍵🍵🍵🍵🍵

「これなんの記事?」

いや本題の内容を言う前に言わないでください!!!
今日は、私が入緑するまでの軌跡と、あの時全くTwitterを見ていなかったので分かち合えなかった、入茶までの軌跡を、ここにつづります。

というわけで、文がめちゃくちゃ長くなることを覚悟しといてください。

目次

~入茶までの足跡~ (前編)

  • 1: 高校一年、競プロとの出会い
  • 2: 初めてのAtCoder (過去のアカウント、晒します※)
  • 3: 初めてのしっかりアルゴリズム履修
  • 4: 初めての Atcoder Beginner Contest
  • 5: 挫折と苦悩
  • 6: 一刀両断と心機一転、悔しさのバネ
  • 7: 積み重ねた努力のつぼみ

~Main: 入緑までの軌跡~ (後編)

  • 8: 現実逃避
  • 9: 手を差し伸べてくれた天使
  • 10: 「簡単なものばっかりじゃ、つまらないでしょ?」
  • 11: ただただ精進の日々
  • 12: 受験で薄くなり行く知識たち
  • 13: 桜咲くA,B埋め、灰梅の決心
  • 14: 「本」という名の無双
  • 15: 茶梅の出会いとその友情
  • 16: 絶対にあきらめない心

ということで、書きます。ふぅー...よしっ!!!!🔥ぼっ

※これについて

横入りすみません。
私は AtCoder 様のサービス利用規約における、「複数アカウントの利用」に違反することを確認しておりませんでした。
今は既にこの過去のアカウントは消去(退会)はしましたので消えておりますが、それでも違反をした事実に変わりはありません。

以下の文は原文のまま残してあります。虚偽のことも、丸ごと文を変更することも、逃げに等しいと思ったためです。
そして利用規約を違反したことを知らないシーンも書かれています。ご了承ください。

以上を踏まえた上で、この記事をお読みいただけると幸いです。
今後、このようなことが起こらないように努めます。読もうとしている方々、しょっぱなからこのような雰囲気にしてしまって大変申し訳ございませんでした。

ちなみに、今のアカウント一筋で参加しようとしているので、過去のアカウントはここ 3 年間は私は既に使っていません。
もっというと、共有アカウントとして使っていたわけでは決してございません。アカウント間を行き来しながら精進をしたことも一度もしておりません(すいません、調べてみたら1回していました。これからしないから許してというレベルではないことは十分に承知しています。今後は気を付けます。)。
なので自分勝手ではありますが、処置は取らない...と、しています。万が一これに関する指摘があったならば、Twitter などでお知らせします。

:

:

:

長い話になってしまいました。では、お楽しみください。

~入茶の足跡~

1: 高校一年、競プロとの出会い

ついに始まりました。私の花咲く高校生活...!!!私もここで花が咲くのか...!?!?(青春、努力、勝利(?)...)

部活は、この時、実は野球部に入ろうとしていたのです。
...え、意外?実はこの頃はとあるスマホの野球ゲームにはまっていたのです。まぁつまりは、後先考えずに野球を楽しもー!!!!って思ってた奴でした。
本当にその一心で野球部の見学に行きましたが、その時の私は学校の構造がわかっておらず、どこで活動しているのかすらわからなかった人でした。
で野球部の人たちを見かけては、隠れて「かっこい~...!!✨✨✨✨」と言っている陰キャでした。

で、ふと新入生歓迎のポスターを見てみると、そこにPC部の勧誘ポスターを見つけたのです。そして、こう書かれていました。

「誰でも自由に活動できる!!なんでもできる!!!!!」(誇張は少しもない)

ほう。と最初は思いました。
とりあえず、見るだけ見てみようかな~と思って部室に入っていみると、あらびっくり!!!

マジで自由な空間じゃん!!!!!!

そう、何も打ち合わせせずにやったのかなー感が強い新入生歓迎をしていたのです。私は思わず、自由だな~ここ!!と思っちゃいました。

:
:

(待て待てこんなに書いてしまうととても40000字に収まらないのでは!?なので省略!!!!)

と、とりあえず、考えを変えた自分はなるべく自由性のある部活に入って活動したい!!!という思いで、無事、PC部に着弾した(=入部した)のです。

:
:

なんやかんやあり、時は高校一年の夏。PC部顧問から、こう言ってきたのです。

プログラミングを、やってみないか?」

ほう。となりました。同じリアクションしかしてませんが。
早速先生の言う通りに、学び始めました。最初は、paiza様のサイトから学習を始めました。

:
:

これが、私を「競プロ」の世界に誘った原点になったのです。

:
:

...え?Atcoder はどうしたって?
まぁまぁそんな焦らずに!まだまだpaiza学習は続きます。

paizaでは、主に JavaScript を学んでいました。理由?そんなの私個人の興味+かっこよさに決まってるじゃないですか!!!!!!!!!
で、paizaさんにある「スキルチェック」というサービスを使って、マジで特訓しました。

でも、私も人です。(お気づきではいると思いますが、""抹茶🍵"" ではないですよ?)
はっきり言いましょう。

:
:

飽きました。
(本当に、JavaScript を好きでいる+今も使っている人は、ごめんなさいとしか言いようがありません)

:

いや、今の私なら絶対楽しいはずです。
そもそもこの頃の私は、確かに興味はありましたが、「これ、学んでどこに生かせるの?」と、思っていたのです。
ここで私は、プログラミングの存在性を、探ってみることになったのです。

:
:

探ってみました。マジでわかりませんでした。この頃の私には主にWebサイトの制御?などで使用されることを、全く知らなかったのです。 そんなこんなで、JavaScript で作りたいものを少し作って、ほったらかしにしてしまい、プログラミングはもうやることはなかったのです...

...の、はずでした。
ある日、PC部顧問曰くとある大学からこんなメッセージが書かれていたのです(サイト内)。

会津大学主催、パソコン甲子園2020」

これに、参加してみない?ということを言い渡されました。私は、結構乗り気でした。
理由?だからそんなの興味+paizaで習ったことが生かせると思ったからに決まってるじゃないですか!!!!!!

ということで...ここで、競技プログラミング、略して競プロ」の存在を、初めて知ることになったのです。

:
:

...あ!AtCoderの話に、やっとなるわ~よかったとか思いました!?
残念ですが、まだまだ続くのです。

:
:

こうして、私たちPC部プログラミング班の、激闘の日々が始まりました。

#

確か...この時のパソコン甲子園(以下、PCK)は、C++, Java のみが使えたんですよね...確か。
で、顧問は、「C/C++より Java の方がいいんじゃないかなー」と言ってきました。なので、とりあえず、じゃあ Java ってみるかぁ~ということで、paiza様の学習環境をお借りして、学んだのです。

でもね~、(急にため語) やっぱり基本を押さえるだけじゃダメですよ、そりゃあ。

ん?どういうことだって?
実は、この時の過去問を見てみたんですよね...確か、私は2017年度の過去問(各自でご参照ください...)をよく取り掛かっていた覚えがあります。
(今この問題を見てみると、「エル」という人に反応しちゃうな...(ヒント: FFさん))

では早速解いていきましょう。第一問。じゃじゃん!(SE)

:

感想: あ~四則演算かな?はいはい、Javaなら...こうして、こうじゃあ!!!-> AC

:

まあ余裕ですね。第二問!じゃじゃん!

:

感想: if文かな~?これをこうして...あれ?じゃあこれをこうして...お、合ってそう!-> WA

:

ちょっと手こずりました。この時の私は、こういう単純な問題がマジで苦手でした。悲しい...(ちなみに他のプログラミング班の人は秒で解いてた)
第三問。じゃじゃん!

:

感想: 無理では?()

:

そう、ここで無理になりました。剰余がどういうところで扱われるか、まだはっきりしていない頃だったのです。

ということで、一回過去問から離れ、paizaさんのスキルチェックというサービスを借りて、熱心に取り組んでいました。
よし、大体Dは解き終えた!ばっちり!

じゃあ、もう一回解いてみましょう。あらびっくり!またてこずりました!そして無理でした!よし、次の問題へGO!!!!!!!!
第四問。じゃじゃん!

:

感想: みゃ?

:

はい。単純なアルゴリズム問題です。今の私なら、あ~あれね!になっております、今。
この頃の私は、HashSet の用途も知らず、ArrayList もまともに使えず、Entry もなんのこっちゃわけわからんもうJavaやめるわ状態でいたのです。

もう無理そうだけど、もう一問だけ見よう。第五問。じゃじゃん!

:

感想: MU☆RI☆DE☆SU☆

はぁ...意味わからん。自信を失いました。こんなん、自分解けるようになんの!?!?!?って、正直思っていました。

第六問も見ましたが、以下同文。

さぁ...どうすりゃいいんだ。と思いました。
とりあえず、paizaのスキルチェック: D,Cレベルの問題、問題集も同様に解きまくりました。

PCK当日まであと2か月くらい。
paizaをカチカチサーフィンしていると、"アルゴリズム講座" というのを見つけました。これは間違いなくいい賜物だ...じゅるり、と思い、軽い気持ちで臨みました。

結果は...MURIDESU☆
マジで意味わからん。この一言しかなかったです。(この時、マジで意味の分からない再帰関数や、巡回セールスマン問題を見ていました)

私はここで思いました。

:

ちょっと待て。
これ、このままじゃ一生無理なのでは?

:

ということで、本当にいろいろなアルゴリズムを調べてみました。そして、ひとことつぶやきました。

:
:

貪欲法...?」

:
:

これが初めてのアルゴリズム習得でした。じゃあ詳しく見てみましょう。

:

ふむふむ。

:

なるほど。

:
:

わからん。

:
:

いや、多分理解力がなさ過ぎて全く頭に入らないだけで、今見ると多分すんなり入ってくるとは思います。記事全体はマジでわかりやすかったです。
(記事...うろ覚えですが、確かこれだったはず...?)
(この記事の筆者様、本当にありがとうございます!!!!)

で、お気づきでしょうか。この記事に、Atcoderの問題が載っているのです。

ついに...?!?と思った方が多いでしょう。実はこの時、

:
:

Atcoder?なんか、外国で開催されてる...のかな?へーこんなのあるんだー (問題をよく見てからサイトを閉じる)」

:
:

くらいの程度でした。まだこの時は AtCoder 様の偉大さに気づいていない愚か者といっても過言ではないです(仕方ないのかもしれませんが)。

しかも拡大率 100% の時。(今は 125% (私の誕生日!?(偶然)) にして見ています)
むずそ~くらいしか考えてませんでした。

でも、その問題がどうやっているか、解説を見てみたのです。おお~分かる、分かるぞ...!!!になりました(こうなったのはPCKまであと20日前くらいなのは言わなくてもわかりますね?)。

なんやかんやあって、なんかアルゴリズムを適当に見ながら、初めての競技プログラミングの場、パソコン甲子園、当日。 私は身に着けた、貪欲法を片手に持ちながら挑みました。

START!!! 第一問。これはこの時の私でも意外に解けました。
第二問。if文パーティーです。手こずりました...(隣にいた友だちはすんなり通してました。くやしい!!!)
第三問。...ん?どゆこと?無理。次の問題を見ました。
第四問。実験してみました。すると、

「待て、これ、貪欲法か?」

その瞬間舞い上がりました。そして落ち着いて実装をし、まずは入出力例の答えが合っていることに、心がぴょんぴょんしました。
そして、恐る恐る提出し、祈りました。すると、

:
:

「正解」(ACの意)

:
:

の文字を、目にしました。これは、ガチで嬉しかったです。
ちなみにこの時点で第三問をACしてましたが、第四問は流石に解けず、「すげぇ~」って言われてめっちゃくちゃうれしかった記憶が、今でも残っています。

これがあるから、楽しい。競技プログラミングのモチベにもつながりました。
逆にこれがなかったら、今の自分はプログラミングを既にやめていたんじゃないかな...と思っています。

#

PCKから1週間が経過しました。競技プログラミングはもちろん続けていました。
すると私の熱意が伝わってきたのか、顧問からこう言ってきたのです。

「"AtCoder" っていうサイト、知ってる?」

私は、覚えていたのにも関わらず、知らないといいました。いや、AtCoderのサイトはあれっきり見てなかったので、存在を忘れていた、の方が適切でしょうか。
で、見てみたのです。

「サイト、かっこよ!!!!」

と思いました。そんなすごいサイトなのか...?と思いました。まだこの時の私は偉大さを知りません。

早速、顧問が言ってきたAtCoderのサイトから、APG4b (AtCoder Programming Guide for beginners) を見てみました。しかし、それは C++ の入門記事だったのです。
Javaじゃないのかぁ。と思いましたが、顧問から後押しをするように、

C++も、簡単だから使えると便利かもよ?」

なるほど。しかし、どこで使えるんだ...?と思った自分は即座に調べてみました。すると、

:
:

競技プログラミングでは、C/C++,Java,Python を使う人が多い」

:
:

という文を目にしました。あれ、これって C++ をやってもいいか...?と思いました。

つまり?言わずもがな、C++履修を始めました。

:
:

私は、ようやくAtCoder の偉大さに気づき始めるのです。

2: 初めてのAtCoder (過去のアカウント、晒します)

ついに始まった AtCoder 人生。まずは APG4b をやりまくることを考えました。
で、初めてコードテストを使い、初めてAtCoderで提出したのです。

「1.00 はじめに」の章での提出です。記念すべき 1 回目の提出の結果は...!!!!!!

AtCoderでの初提出!!!

WAです!!!!!🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉

...ん~~~~、かわいいコード!!!!!!!!
しかも、Copy&Pasteを知らない私は自力で最初からコードを書いているっ...!!!!💕💕💕

Hello, World! って出力しろ!っていうのに hello world 、かわいすぎる!!!!!!!💖💖💖💖💖💖💖💖💖💖💖💖

:
:

んんっ、すみません、取り乱しました。
あ、あと気づきましたか?私、このアカウント一本でやっていたわけではないのです。なぜ 2 つに分かれているかは、後々わかってきます。

じゃあつべこべ言わずに、ここにさらしておきましょう。

これです!!!! \Rightarrow NKmatcharate (※アカウントは退会済なのでページは残っていません)

灰色で止まっていますね。これも後々わかります。

という感じで、APG4b をどんどん進めていきました。

3: 初めてのしっかりアルゴリズム履修

幸いにも、二次元配列などは Java 学習でやっていたのですんなりわかりました。慣れるまではマジで長い年月をかけましたが...
あと、再帰関数!これもマジで最初は詰まりました...本当に、今やっと慣れたくらいですもの!!あれはむずすぎ!!!
(いろんな再帰関数のサイトを探しまわりました...最初からあの神様みたいな記事を見つけられればいいのに、むずいです...)

すいません、提出見てみたら何を血迷ったのか急にPythonを書き始めているのですが...(悪いことではないですけどねもちろん)
多分、paizaさんでPythonを履修して、やったんでしょうね...

って、思い出しました!!!この頃の自分はトリリンガルになろうと思ったくらい、言語を習得したんでした!!!
つまり?競技プログラミングそっちのけで基本を沢山習得していました!!!!

じゃあアルゴリズムはどこ行った?->その答えは、どっか行ったです。
貪欲法も、かすかに記憶に残っているだけで、マジで忘れていました。

: :

お!はじめて過去問に取り組んだ問題がありました!

これです!!!-> ABC181-A

なるほど、こういうのを沢山解いて楽しさを覚えた、っていうのはありました...思い出しました!

あ、B問題もありました!これです!-> ABC181-B

初B問題提出、全(Sample含む)WA+TLE...なかなかですね。あれか、コードテストでもサンプルが合ってるかわからなかったのかな...?

ん、待ってください。初C提出が...🧪緑diff!?

動的計画法(DP)~

この時の(今も)参考サイト: けんちょん様のサイト(EDPC)
参考にした問題: ABC040-C

そうでした。この頃の私は、動的計画法という、なんともかっちょいい名前のアルゴリズムを履修しようとしていたんでした(無謀にも)。
それで、簡単な問題からやろう♪と思い、最初からやりました。

そうか...「コードの完コピはあまりしちゃいかん!」ということを知らないので、まずはこのコードを完コピして、そこから自分の読解性を求めて変更しながら(俗にいう、リファクタリング的な?)、学習していました。まぁ何事にも自分に合ったように学ぶことは大事。

最終的に、自分好みの感じコードに味付けをして、自分のコードでACできたようです。

深さ優先探索(DFS)~

参考にした問題: ATC001-A

次は深さ優先探索を学んでいますね...
って待て待て!!!これ、平日だし授業中じゃない!?!?

(ここで思い出がよみがえる)

「そうか...この時自分は一番後ろの席だから、iPad(学校支給)を授業中にいじってもバレない...!(最悪)」

ん~...まぁ、いいのかな。勉強してるし。
ゲームとかSNSとかでもないからいっか!!(よくない)

グリッド上の探索ですね。この頃、探索問題はマジで好きでしたね...今もめちゃくちゃ好きですけど。

で、ここからグラフのことに好意を抱いていました。なんなら、リアルでも好きな人に好意を抱いていました。なんかすご!!!!!(?)

#

とまあ、まずはこんな感じか。

...待ってください。なんか重くなってるので、一回入茶の方の記事はこんな感じで締めます!!

:

後編へ続く。

:

:

に、しようと思いましたがめんどいのでこっから後編!!!!!

ここまでのStoryをまとめてみます。

あらすじ

高校生でパソコン甲子園に出場した。
そこではかなり厳しい知識量に対し、APG4b を解きまくった。
しかし、意味の分からないアルゴリズムに頭を奪われて...!?!?!?

では、どうぞ。9000字以上あるので、頑張ってください☆)

:

:

:

4: 初めての AtCoder Beginner Contest

ついにこの時が。
顧問から「毎週開催しているコンテストあるから、慣れたら出てみなよ!」と言われ、私はついに AtCoder Beginner Contest に出場する決心をしたのです。

コンテスト前の緊張感。周りのプログラミング班の人たちは個人個人のPCで家で解いてるので、何もわかりません。
で、肝心のTwitterですが、この頃の私はTwitterの存在を認識していなかったのでFFさんさえもいません。

つまり、今から初めて一人で挑むのです。PCKでは2人で解いていたのに、これは...!!となりました。

さぁ、始まりました。今回はこのコンテストに挑みました。->

ARC109

...ちょっと待ってください。A "R" C?ん?見間違いでしょうか...最近目を使いすぎているのでちょっと...(目をこする)

そうです。 初めてのAtCoder Contest、ARCで臨んだのです。( I'm True ばか. )

そりゃあね...むずすぎですよ。
待て待て全人類こんなむずすぎるやつ解いてるの!???!?と思いましたもん。

結果、いわずもがな 0 完太陽!🌞初コンテスト、パフォは54...妥当です。

「これはね...無理だ!!!!精進しよう!!!!」
とっさにそう思いました。

この結果を顧問に言ってみると、なんということでしょう!ARCじゃなくて、ABC に出た方がいい!!!なるほど!!!
ARCはむずい!!!なるほど!☆

(一応、提出してはいたんですよね...しっかり考えられてるの、すごいな...)

ということで、次の A"B"C までにとりあえず簡単な問題を解きまくり...ませんでした。過去問精進という言葉は、彼の頭には未だ存在しません。

:

つまり?ほぼノー勉で、今度こそ初めてのABC(ABC185)にとりかかりました。

結果は...まあ、残酷です。というか、問題の運が悪かったのはあります。

Aは全然解けたのですが、B...問題文がむずかったです...
しかも、t+0.5 って式も出てきて、小数!?って思って手こずりましたね...

パフォは 91 。うんうん、初めてにしてはいいのかな...?レートは 3 -> 11 に上がりました。

(なんならレートあることもこのときわかってません。つまりパフォもレートも存在を知りませんでした)

5: 挫折と苦悩

しかし、この結果は私に火🔥を注ぎました。
ここから過去問精進が始まったのです。

沢山解きました。とりあえず考えられる簡単な灰色の問題を中毒ののように解きまくりました。
茶色、緑色のdiffにも構わず、解説ACでもいい。とりあえず基本知識を蓄積しまくりました。

そして、2回目のコンテスト、ABC187。参加しました。
結果は...これも残酷でした。

  • A: 計算系。文字列でやった。
  • B: 傾き...?どうやって計算するんだそんなの...
  • C: 全探索かな~->時間計算量を知らず N2 で TLE ※Bに関して、この頃は高1なため、傾きの計算方法を知りませんでした

結果はA1完。パフォは 85 。前回より落ちましたが、レートは 20 になりました。

ここで私はCの解説を見て、set の存在意義を改めて認識したのです。

#

飽きるほど問題を解きまくる日々。実はこのときの精進は、マジで楽しかった記憶があります。
そして、今の私が大好きな探索アルゴリズムを、もう一つ知ることになるのです。

幅優先探索(BFS)~

これも、とりあえず見様見真似。はっきり言いましょう。マジで意味が分かりませんでした。
でも、こんな面白いアルゴリズムあるんだ...!!(おめめきらきら~)と思いました。

この頃から、グラフ理論に思いを寄せ始めていました。

#

飽きたので(おい)、Pythonで過去問を解いていました。
もちろん過去問精進に夢中だったため、コンテストには全く出ていませんでした。

そして月日がたち...3回目のコンテスト。これは学校から参加しました。
よし、スタート!

  • A: これ、ただの計算なはずなのに合わない...!!
  • B: bitでxorを計算...なのになんでRE!?!?!?
  • C: え...むずそうムリです

はい。なんと、友達が隣にいるのに、0完というなんとも恥さらしな結果になってしまいました。
パフォは17。最低値を更新し、レートは 19 に下がりました。

解説を見ました。
なんでこれができないんだろう...。もう一歩のところに、私は足を踏み出せなかったのです。

:

またまた精進です。
茶色が解けなすぎて、灰色をずっと解いていました。

そして、4回目のコンテスト。今回はZONe様主催のコンテストでした。
では、精進の知識片手に宇宙へGO!!!!!!!

  • A: i,i+1,i+2,i+3で判定
  • B: ...へ?
  • D: ちょっと実装してみるか...->RE+CE->へ?

"ふぅ...もう飽きた!!B問題解かせてください!!!" コンテスト後、この調子でした。
結果はA1完。パフォは 100 。初3桁!Aの早解きが効きました。レートは 27 になりました。

しかし解説を見ると、相似関係を使った数学的問題だったのです。
そしてここでやっと解説Youtubeの存在を確認します。見に行きました。なんのこっちゃわかりません!!!!!!!!!!!(この頃は特に数学が苦手だった)

#

ここまで(というか5回目のコンテストまで)に精進などで身に着けたアルゴリズム・テクニック、データ構造を列挙しておきます。

#

5回目のコンテスト。では、行ってきます。

実はこのコンテスト、私をグラフに夢中にさせたコンテストでもあります。

後ほど説明します。まずは結果を。

  • A: if文パーティー。10分使ったのは痛い!
  • B: 10超えてたら10引いた値の総和!3分で解けた!こっちの方がEasy!!
  • C: DFSが大好きな人でした。そして、m=0に注意しながら、解けました。

そう。ついに、初めての 3 完です。
これには思わず、ガッツポーズをしてしまいました。
しかも後々に難易度を見ると、茶diff!!!これも驚きました。茶色、自分解けるんだ...になりました。

パフォはなんと 675 !!!!レートも 66 になり(今考えたらしょっぱくない...?)、これは大歓喜でした。あの爽快さは、今でも忘れられません。

:

こっからはアルゴリズム精進に入りました。で、この頃はPC部の先輩からは「DP 兄貴」と呼ばれていました。つまり、DPを勉強しまくりました。

:

あ、余談ですが典型90が入ったのは、この時っぽい...?私はここからやり始めてますが、間違ってたらすみません。

月日がたち、6回目のコンテスト
これは...そんな悪くなかった(悪いですけど)ですね。

  • A: a*(b/100)
  • B: sortしてi=P_iじゃなかったらNo、それ以外はYes
  • C: 今見てみるとコードめちゃくちゃ複雑!!とりあえずif文パーティーですね...

パフォは 198 。レートも 79 になったし、まぁいっか...
しかし、Cが灰色とはこの時は思っていませんでした。なのでパフォは 500 くらい出ると思っていたので、悲しかったです。

で、推定水色の知識はある友だちが、いとも簡単に二分探索を覚えており、D問題をすんなり通していました。悔しかったです。

#

あ、ご飯呼ばれました!! またあとで~

#

よし、再開します。

ここからはもうマジで精進ですね。履修したアルゴリズムは以下です。

  • Algo: UnionFind
  • Algo: 約数列挙
  • Algo: 素数判定

はい。7回目のコンテストです。結果は...まあまあ最悪ですね☆

  • A: ふにゃん
  • B: n*(n+1)/2ですね...これTLEするんじゃね?で迷っていました
  • C: わおー...わからん [tex:O(N2)] しか思いつかん!!!

パフォは 71 。レートは 77 に下がりました。う~ん...

続けて8回目のコンテストへ。結果は(以下同文)

  • A: 計算ミスで1ペな...
  • B: 1が最初に奇数番目に来るならT、偶数番目に来るならA
  • C: ...ふえw?絶対TLEするんですけど...

パフォは 228 。まずまず。レートも 92 になりました。まぁまぁ...

:

マジ精進(以下同文)
履修したアルゴリズムは以下です。

  • Algo: しゃくとり法

:

9回目のコンテスト。結果は...おぉ~...でも...

  • A: 計算。
  • B: set。
  • C: え~むり☆

パフォは 478 。レートも 122 になりました。

...

この時、3完するコンテストが少なすぎて、自信を失っていたのです。つまりは、モチベをなくしてしまっていたのです。
あと、このときPC部内では今にも豪雨になりそうな雰囲気が続いていて、PC部存続の危機も迫っていたのです。

その関係もあったのでしょう...
あの時の私は、ほぼ「悪」でしたから...

:
:

動的計画法、とりあえず学んでいました。
しかし、これは負の効果でした。DPが自力で解けず、もっと自信を無くしたのです。もっと絶望しました。もっと挫折しました。モチベなんかなくなりました。

:
:

10回目のコンテスト。
これは言うまでもないです。またC問題にやられたのです。レートも落ちました。

そして月日がたち、競プロから一時期離れていました。

「これ、競プロ、続くかなぁ...」

そう思っていると、私は思いついたのです。

:

「いっそ、このアカウントを消して、新しいアカウントを作り直すか...?」

:

そう。こうして、私はこのアカウントを抹消しようとしたのです。
でも、退会は...なんか気が引けるし、せめて名前が変えられればいいけど...1回しか決めれないのか...

よし、
新しい自分を、作り出そう。

追記: ※何度も言いますが、これは違反行為です。私はこのとき、これが違反行為に気づいていなかった愚か者でした。皆さんもご注意を。私も気を付けます。

:
:
:
:

こうして、今の matcharate12 が生まれたのです。

6: 一刀両断と心機一転、悔しさのバネ

心機一転、私は一から精進することにしました。もちろん過去問の解いた形跡も、AtcoderProblemを見ても何も残っていません。
このまっさらな状態から、私は入茶を目指すことを決心しました。

このタイミングで、推定水コーダーの友だちは、入茶をしました。しかも、私の解けない問題をすんなり解きながら。

これは、嬉しさの半面、悔しさもありました。いや、正直悔しさの方が大きかったかも。

:

それに加え、部内の雰囲気を改善させる必要もあります。私がとった行動は...

:
:

「何もしない」ことです。

:
:

私はこの時、「時」が解決させてくれる、と確信していました。なので、当時好きな人ともしばらく離れることにしたのです。
はっきり言って、これはまさに「決断」でした。しばらく話さなくなると、あっち(好きな人)の印象も悪くしてしまうと思っていたからです。

...悔しいです。しかし、これは自分が蒔いた種、いや、地雷です。
この経験のおかげで、私は深淵の中から目を覚ますことができたのです。

#

心機一転、新しい自分で、精進を始めました。

新しいアカウントで、初めてのコンテスト

このアカウントで、初めてのコンテストがやってきました。解きました。

  • A: 素直に全探索
  • B: pair+sortで頑張る
  • C: おお...わからん。

初回はパフォ 348 で、レート 17 でした。ふむ、まあいい方?

:

さぁ、ここから私の本気の精進劇場が始まります。

そう、B全埋めです。
色を問いません。ABC only です。

B全梅しようとしたきっかけは、実装力をもっと上げようとしたことから始まります。

2回目のコンテスト

そして2回目のコンテストがやってきました。解きました。

  • A: ぴょーん
  • B: 全探索だけど範囲間違えて1ペな
  • C: なんこれー!!!!!!!!!

パフォは 272 。レートは 48 になりました。まだまだ伸びしろの時です。

さらにB梅しました。

3回目のコンテスト

3回目のコンテスト。解きました。なんと、友だちに救われました...!!!

  • A: かわいい問題!!!
  • B: N以下で2をずっとかけていく
  • C: 順列全列挙!!!!Foooooooo!!!!!

C、One More じゃない方を友達が解いていました。悔しい!!!
パフォは 663 !!レートも 114 と爆上がり!!!!(多分参加人数がめっちゃ増えてきた!?)

もっとB梅...ではなく、今度は簡単なA梅をやろうと思いました。Aをまずは解けないと、話にならん!!!と思ったためです。

4回目のコンテスト

4回目のコンテスト。解きました。なんと、友だちに救われました...!!!

  • A: if文パーティで大変でした
  • B: 同じかどうかは配列で確認
  • C: 逆に操作をしていく!!これ気づけたのはでかい!!!!

C、One More じゃない方を友達が解いていました。悔しい!!!
パフォは 663 !!レートも 114 と爆上がり!!!!(多分参加人数がめっちゃ増えてきた!?)

もっとB梅...ではなく、今度は簡単なA梅をやろうと思いました。Aをまずは解けないと、話にならん!!!と思ったためです。

ちょっと尋常じゃないくらいコンテストが多いので、ダイジェストで行きます!!!

7: 積み重ねた努力のつぼみ

5~6回目まで

さらC梅も同時に始動させました。きつかったですが、解けたときのあの快感は今でも同じです!!!!!
レートは 265 まで上がりました。

7~12回目まで

JOIも参加しました。私にとっては結構簡単目で、初めて全完も経験しました!!!
履修したアルゴリズムは以下です。

  • Algo: 二部グラフ判定

A梅と、初心に帰ってAPG4bの練習問題梅をしていました。

そして 12 回目のコンテストで、新たに3点の結んで作る三角形の面積公式を覚えました。このとき、ベクトルはぎり習っていなかったです。(このときは高二でしたが)

レートは 335 まで上がっていました。結構順調では!?!?!?

13~17回目まで

本格的に、まずはA梅を始めました。ほぼAしか解いていないはずです。そして、A梅を見事踏破しました。
次にB梅を始めました。 履修したアルゴリズムは以下です。

  • Algo: bit全探索

何回目かのコンテストか忘れましたが、深さ優先探索の重要さを改めて意識できた問題にたどり着けた覚えがあります。
レートは...374!!!あと+26で...!!!!

(余談ですが、記事day2です。花粉が明らかにやばいことだけが明らかにわかります)

そして、18回目のコンテストへ

そうして精進を得て知識を蓄積しまくった私は、ついに、突然、その瞬間が来たのです。運命の、18回目のコンテストです。

:

  • A: うにょーん
  • B: アスキー文字を変えるけど...うまくできず2ペな。痛い!!!
  • C: DFS+順列全列挙!!!!
  • D: うおーBFS!!!!!

:

:

:

:

:

...これが、何を意味するか分かるでしょうか?初めての、4完を達成したということもありますが、

そう、私、まっちゃラテは、

:

:

:

入茶、しました。

:

:

:

あまりに急すぎたのであまり喜びが難しかったのですが、確実に、茶色に、なっています。レートの数字も、名前も。

入茶直後にスクショした写真(携帯で撮ったので縦ですが)

そうして、Twitterもまともにやっていなかった自分は、PC部員のみんなと、喜びを噛みしめあいました。
あの時は、私もすごくうれしかった思い出を、今もずっと残っています。

:

入茶までに身に着けたこと・総括

...ということで、こっからは"ドラマチックラテ"から、普通のラテになりますね!

いや~...振り返ってみると、やっぱ「時」って早くない!?そしてなんか儚い!?!?
改めてみると、本当にいろんなことを学び、部員と仲良くふれあい、時には挫折し、時には幸福を感じ...まさに、「人生」そのものを表している感じです。

私も、プロフィール(LINE)では、「人生、山あり谷あり。うまくいかないことも、もちろんある。」って書いていたころもありましたが...マジでその通りになりましたね。

:

ということで、以下は私の入茶までにやったことリストです。ご参考にどうぞ。

身に着けたアルゴリズム

  • 深さ優先探索(DFS)、幅優先探索(BFS)、グラフ理論の基礎的知識
  • 二分探索 (特にめぐるちゃん式)
  • 累積和
  • しゃくとり法
  • bit全探索
  • 順列全列挙
  • 約数列挙、素因数分解素数判定 (約数の個数、約数の総和などの数学的知識含む)
  • 最大公約数 (ユークリッド互除法)、最小公倍数の計算
  • 基本的なデータ構造 (特に set, stack, queue, deque, priority_queue)
  • 基本的な典型DP (特にナップザック問題、1次元の問題)
  • 進数変換 (10進数 to K進数, その逆も)
  • ランレングス圧縮
  • 二部グラフ(※これは優先度低)

入茶までにやったこと(教訓)

  • A,B全埋め (A: 早解きの力をつけるため、B: 実装力を身に着けるため)
  • 灰梅、茶梅 (梅は全埋めの意)
  • とりあえず1日1個確実にACする(解説ACでもok、ただししっかり理解することが大切)
  • 思うようにいかなくても、とりあえず続けることが大切
  • 時には自分を振り返る!苦手を克服!!!

:

Epilogue

ということで、私の笑いあり涙ありの、灰溜まりからの脱出劇場でした。いかがだったでしょうか?
茶色になるための努力方法は人それぞれ自分のあったやり方でいいですが、oo全梅は、マジで効きます。嘘だと思ったら、ぜひやってみてください。

...でも、問題をやっただけで決して満足しないでくださいよ?満足するなら、問題解説を完全に理解したわ余裕(ドヤっ)くらいになってからにしてください。
(急に先生みたいな言い方がでうざって思う人もいるかもしれませんが、これだけはガチで言えます)

:

よし、やっとMainの入緑記事を書きます。
ぜひ、期待しないで待っていてください。