橙になりたいaquarium

にゃーんにゃーんにゃにゃーん

ICPC Asia Pacific Championship 2024 参加記

regionalの参加記はこちら

shinchankosen.hatenadiary.jp

チーム

kotamanegi_mijingiri

阪大の2軍の黄色3人チームです。

  • KowerKoint (@KowerKoint2010) 実装が一番できる。

  • Daylight (@Daylight_pro) 問題読解が一番できる。

  • shinchan (@Sophia_maki) 数学が一番できる、はず。

戦略

Regional までの戦略(コピペ)

KowerKoint君にAのFAを狙ってもらったあとセットアップ。Daylight君にはB。僕はそれ以降の問題に後ろからざっと目を通して、問題文が短いものから読んで解けそうなのを探す。

また、その都度得意不得意に合わせて問題の交換は行い、読解がわからない問題があったり新しく読みたい問題はDaylight君に任せたり、重実装やライブラリ写経はKowerKoint君に任せたりという方針をとりました。

そして、私はできる限り実装をしない。すぐかけそうなのは書いてもよい。と決めていました。

あと特にこういうのは決めてるわけではないですが、僕の性格的にいろんなことに口出ししたいタイプなので、2人に指示を出したり、2人の解法のコーナーケースを探したりすることが多かったです。

変更点

Regionalと同じキーボードを購入し、自分でも実装力が上がってきてることが自覚できるくらいになりました。よって、ある程度積極的に僕が実装してもよいことにしました。

あと、Aに簡単が置かれていないのでは?と思ったので最初のA, Bを見てもらう工程ではわからなかったらすぐ他の問題に行くように促しました。

出発まで

卒研発表会があったりで2月中旬までなにも精進できませんでした。2/16から実家に籠り、そこから一週間くらいは1日12時間くらい使って黄diff埋めをやりました。なんとか出発までにRated黄diff以下が埋まりました。自分の足りないところは単に知識であることが多いので、網羅的にやろうと思いました。

出発の数日前にはチーム練を行いました。ベトナムのRegionalを走ろうとしたのですがジャッジが壊れててダメでした。そもそも入試の関係で大学に入ったらダメだったらしく、僕の家に移動してJAGのを走りました。

さて、この数週間研究室のミーティングをこれらのためにサボっており、卒研発表会終わったときに担当教員には「3月まで逃亡します」と事前に言ってはいるものの、事情をわかってくれている研究室の先生方は寛大でございます。渡航費も出してくださりました。大阪大学最高!!!

海外なので、いろいろと準備が必要です。なんせ1月中旬に通過の連絡が来たため、急ぐ必要がありました。会計上のことは全部こたまねぎさんや顧問の猿渡先生、各研究室の先生方がやってくれました。個人ではパスポートを取っただけで、保険やWi-Fiはmijingiriで一緒にやりました。

Day0

出発の日。関西国際空港に集合し、荷物の重量とかを確かめたあと、最後の日本食を噛みしめました。うどんとかつ丼のセットでした。飛行機では隣のベトナム人の方がとてもフレンドリーでした。「ベトナムで気を付けることはありますか?」と聞くと「交通量」だと。本当にとてもよくわかります。

入国審査とかは英語を使うこともなくパスポート見せたりするだけで簡単に終わりました。両替は一番大きくて人がそれなりに並んでるところの方が安心感あるかなと思ってそうしました。

空港での夕食はおいしかったです。

ホテルについてから歩いてサークルKに行きました。歩いていくのはとても危険でベトナムの洗礼を受けました。ポカリとカップ麺を購入しました。

社会主義国家なのでところどころに共産党のアレがありました。でも文化や製品は日本韓国中国アメリカのものが入り込んでいて、なんとも不思議でした。

Tシャツなど。

Day1

UET!!

昼食は匂いが合わなくてほとんど残してしまいました。

Huaweiのブースにあった、一休さんの音楽が流れるパチモンのミッキーをもぐら叩きするゲーム。

リハーサルでは双方向リストをイキって実装しようとして破滅した記憶があります。やっぱ実装したくないになりました。

夕食はシーフードのバイキングでした。飲み物がコーラしかなかったのですが私は炭酸が飲めないので…。肉類はやはり匂いが合わなくて生ものを主にとりました。これが悲劇を招くことになります。生ものばかり食べるのは危険だと思ったので(遅い)、途中からプリンばかり食べてました。実質スイパラです。

Day2

朝から台湾のチームと仲良くなって中国語で自己紹介してみたりした。通じてよかった。「ノゲノラ全巻持ってる!」「おれも!」みたいな会話をしました。

本番

順位表

icpcasia.firebaseapp.com

コンテスト開始と同時にKowerKoint君がA、Daylight君がB、shinchanがCを読みました。Cはすぐ細部を詰めるのが難しいのでKowerKoint君に変わってもらいました。

他の問題を読んでいると、Hが解かれていることわかったので、Daylight君に読んでもらいました。すぐ解けたみたいなので実装してもらいます。実装がちょっと詰まってたので、問題と考察を聞くと、より簡単な方針があったので伝えた。しかし不正解だった。KowerKoint君のCも不正解で、「ジャッジ壊れてんじゃね?」とか言ってた。

KowerKoint君の実装を見ると詰め切れてなくてサボってるところがあったので適切に詰めたりすることでAC。

C(1:12) KowerKoint (考察: KowerKoint, shinchan)

HをKowerKoint君にも言うとコーナーケースにすぐ気づいてくれたのでそれを詰めたことでAC。

H(1:34) Daylight (考察: shinchan, Daylight, KowerKoint)

このあたりで昼食が来る。バインミーと豆乳はおいしかった。みかんは種が10個以上あって鬱だったのでチームメイトにコンテスト中は食べないように指示した。

Jも問題読解をDaylight君がしてくれてたので、聞くと解法が生えたので伝えた、嘘解法だったが。僕が実装するもサンプルが合わない、Daylight君がコーナーケースを見つけてくれた、を3回くらい繰り返して、最終的には過去3頂点を保管することでなんとかACした。

GもDaylight君が読んでくれてたので聞くと、「これで間に合うやろ!wえい!」をすると通った。計算量解析的なところはDaylight君がやってくれた。

そうこうしているうちに2人がEの考察を終えていた、通った。

G(3:16) shinchan (考察: shinchan, Daylight)

J(3:23) shinchan (考察: shinchan, Daylight)

E(3:31) KowerKoint (考察: KowerKoint, Daylight)

FとKの考察を進めていたが、時間が少なくなってからはF一本に絞って考察を進めた。

O((約数の個数) N) の方針をKowerKoint君に伝えたが、結局それでも通らないらしい。

本番後・夕食

寺院でひたすらコンテストやこれからの話をして、移動して表彰式を迎えた。

夕食は台湾のチームと同じテーブルになった。

Day3以降

体調を崩しました

Day10現在、わりとよくなりました。

あとがき

mijingiriとしては相応の結果だと思います、ボーダー通過だったし。阪大としては悔いの残り結果だったと思います。来年のチームがどうなるかがわからないですが、World Finalsに行けるようにがんばります。

初海外の洗礼をとても受けてしまって、これもいい経験になったと思います。

私たちのサポートをしてくださった、主に先生方、本当にありがとうございました。

XOR基底の感覚的な理解

前提

  • 線形独立、線形従属を理解していること

線形空間、基底、行列のrankについて知ってるとなお良いです。

本記事ではxor基底についてコスパよく理解させることが目標です。

もっと厳密に学びたい方はこちらなど。

qiita.com

問題

この問題に沿ってxor基底を学びます。

atcoder.jp

数列Aの要素を組み合わせてXORを計算し、できあがるものを集合にします。集合で小さい順にL番目からR番目まで列挙するという問題です。

解法の方針とXOR基底

L, Rについてはこういう問題にありがちな上のビットから順番に考える二分探索を使いますが、本記事では述べないことにします。

実は、できあがる集合のサイズは2のべき乗となります。これは少し非自明かもしれません。

少し例を見てみます。

a, b, c, dという要素がAの中にあったとします。いったん重複や順番を考慮しないまま列挙すると、0, a, b, c, d, a xor b, b xor c, c xor d, d xor a, a xor b xor c, a xor b xor d, a xor c xor d, b xor c xor d, a xor b xor c xor dの16種類です。

d=b xor cのときを考えてみましょう。例えば、a xor dはa xor b xor cで表せますし、a xor b xor dは、d=b xor c→c=b xor dから、a xor cと表せます。このように、d (b, c, dのうちどれか1つ)は数列中にないのと同じと考えることができます。

線形代数とXOR基底

線形独立・線形従属を思い出してみましょう。d=b xor c、a=b xor c xor d、b=cなどのように、数列中の値が他の値のxorだけで表現できてしまうとき、線形従属であると言えます(たぶん)

同様に、ある空間の基底は、それぞれが空間の別の基底で表せないものです。3次元空間だと、(0, 0, 1), (0, 1, 0)の実数倍の和で(1, 0, 0)で表せないですよね。

a, b, cが基底であるとします。このとき、a xor b, b, cを基底にするとかしても問題ないです。xorの組み合わせでできあがる集合は変わりません。集合の各要素の表し方は複数存在せず、基底が決まればただ1つ存在します。私は、ベクトルA, B, Cが線形独立であって、A+B, B, CだとかA, B, C-B-Aを基底にしてよいことは、行列式だとかrankを求めるときの行基本変形と同じだと思っています。ただし、A+B, -A-B, Cとかは基底にできません、1個ずつ実数倍の加減算(本問題だとxor)の計算をしてできあがるものならば良いと考えられます。

集合の各要素の表し方は複数存在せず、という部分について、複数存在する、つまり重複があると、その分集合のサイズは減ります。しかし、重複がないことで、とりあえず重複を考慮せず列挙してみた2の(基底の個数)乗個の要素は小さい順に並び替えるだけでそのまま集合として成立します。

XOR基底の実装方針

実装するとき、基底はrankを求める操作のような形(上三角行列?)で表します 基底として、11010, 01101, 00011のようにすると、上のビットから考えて、xorするかどうかを考えることができます。基底ごとに、xorするかどうかとなり、2の3乗であることがわかります。

ARCで困ったときに見る用

※ほぼ自分用

ゲーム

atcoder.jp

atcoder.jp

atcoder.jp

このようなよくわからないゲームにも最善手というものは存在します。 基本的にゲームは真似っ子戦略や、Nim, Grundy数を考えるとよいです。 また、再帰やDPで、現在の状態からスタートすると勝ち・負けを判断できるようにすることもありますね。

上に貼ったような問題は、適切な場合分けをすることで、「この状態は先手必勝」などを判断することができます。単なる傾向としては先手が有利なものが多く、これを考察に使うのもいいかもです。

よくわからないときに大切なのは、実験です。手元で小さいケースで実験し、わからなければ機械にも頼るかめんどければ飛ばして次の問題に行きます。

  • ARC137-C Distinct Numbers

この問題はまじで実験ゲー感があります。実験してみて、そして余力があれば実際に証明しましょう。この手の問題は証明に帰納法使ったりします。「この状態だと勝つと仮定すると、これも勝てます」みたいな。

この問題は手元でやってみて「数字小さい方が有利だな」という些細なことに気づけるかが肝です。実際にX, Yの大小で場合分けして証明しましょう。解説にあるX+Yで割った余りを考えるってのは、真似っ子戦略ですね。

  • ARC148-D mod M Game

これも手元でやってみるなり実験が大切です。これは僕個人の感覚なのですが、modといえば周期です。周期といえば約数です。Mの約数を感じ取りながら、差の変化を見てみましょう。

atcoder.jp

これはちょっと違う。計算量いい感じに落とせるやつ。制約から√ってわかる。

包除原理

  • コピペ用

atcoder.jp

  • 符号・偶奇で遷移を簡単にできる

atcoder.jp

矛盾省いたら終わる典型

atcoder.jp

atcoder.jp

尺取り

  • N通りの数列に対して順番に行うやつに有効?

atcoder.jp

順列

ARC典型、「順列はグラフで考えろ

辞書順

  • 矛盾省くだけ

atcoder.jp

  • めんどい

atcoder.jp

  • うまくやる

atcoder.jp

連結成分・閉路

  • 辞書順

atcoder.jp

挿入DP

piとiの距離が関係してくるやつは箱根

  • bitDPなのは制約からわかる。

atcoder.jp

これの>=バージョンがあった気がする。覚えてる人いたら教えてください。

  • よくわからん多項式時間の問題は(数え上げなら)DPって決まってる。(最大値とかならフロー)

atcoder.jp

その他

  • ただの筋肉

atcoder.jp

  • 中央値、その値から見て大きいか小さいかを考える典型

atcoder.jp

グラフ

  • swapするタイミング、次数に注目。木DP

atcoder.jp

https://atcoder.jp/contests/abc337/tasks/abc337_gatcoder.jp

  • 立式して木DP

atcoder.jp

その他のグラフ

  • ハイパーグラフ?小さいものから確かめてちゃんと考えると二部グラフがでてくる。

atcoder.jp

  • グラフで考える、彩色

atcoder.jp

その他のDP

  • iが連続するのはi個まで。これはadhocなDPだと思う。

atcoder.jp

数学

  • 小さい桁から埋めていくの非自明

atcoder.jp

  • CHT

atcoder.jp

XOR

  • 木の構築

atcoder.jp

  • XOR基底

atcoder.jp

  • XOR基底

N個全部使うやつを除いた最大値探したいときは、除外するのを固定すればよい。

atcoder.jp

解の範囲を絞っていくやつ

  • O(N)

atcoder.jp

上界を考える感じのやつ

  • やや数学

atcoder.jp

  • 幾何、最悪ケースを考えると良さそう。

atcoder.jp

区間クエリ?

セグ木で端を1個ずつずらして進めていくやつ

atcoder.jp

codeforces.com

atcoder.jp

codeforces.com

乱択

過半数という文字とか過半数に帰着できるような問題設定のとき、乱択であるケースが多い

atcoder.jp

atcoder.jp

文字列

  • 辞書順・LCPなどに使える定理

noshi91.hatenablog.com

その他

  • 高橋君歩かせてぶつかったら反転できるやつ。距離最大化

atcoder.jp

  • 負の数考慮すんのめんどい

atcoder.jp

atcoder.jp

  • 逆からもやって状態数小さくできるやつ

atcoder.jp

  • 正の閉路と負の閉路それぞれ見つけたら終わり

atcoder.jp

次追記するときに記事分ける

OUPC2023 原案を出した問題の余談

shinchan(@Sophia_maki)です。

OUPC2023お疲れ様でした!楽しんでいただけましたか?

私が原案を出したのは17問中7問でした。各々好きに原案を出していって、vwxyzくんが魔改造、全体的な運営をKowerKointくんがやりました。

↓コンテストサイト

atcoder.jp

A - Mijingiri

そのまま出されました。実は去年から「この問題名の問題を作りたい!」とは言ってたのですが、いい感じのが思いつきませんでした。今年はいい感じに簡単なのが作れたので「これをAに置きたい!」と言ったら承認されました。

ちなみにICPCでのチームも kotamanegi mijingiri でした。

B - Gomamayo

ゴママヨ好きな人が回りに何人かいたので作ってみました。

サンプル2のssssはそのときSSSS.GRIDMANを見ていたから入れました

L - KowerKoint Doko

ふざけた問題を作ろうとしてたら思いつきました。

H - Wonderful Stage

vwxyzさんに問題の形にしてもらしました。

元はというと、ラブライブスクールアイドルフェスティバルという音楽ゲームで、「ちょうどX点にするための労力ってどのくらいになるだろう」と思ったのがきっかけです。

最初に原案を出したときの題名は「Never Ending Stage」でした。ラブライブで一番好きな曲がMusic S.T.A.R.T!!というのですが、歌詞にあるのがNever Ending Stageです。

ところで、Never Ending Stageで検索すると、あんさんぶるスターズが出てくるので、それを避ける感じで同じくWonderful Rushの歌詞にあるWonderful Stageにしてみました。

I - Min!? Max!? Max!? Min!?

高専のときの卒研で、似たようなグラフから定式化してコネコネしてみたのがきっかけです。今回の問題では式からグラフを思いつけるか、という問題にしてみました。

問題文で最大とか最小とかこんがらがるかなーっと思って、「おにまい」のオープニング曲の歌詞の「あり!?なし?!」の部分を思い出して題名をつけてみました。

原案提出時は部分点の制約でした。vwxyzさんが「M, N≤200,000」と言ってこうなりました。

J - Sum Sum

行列累乗の問題を作ろうとして思いつきました。最初は小課題1の制約でした。そのときの行列↓

vwxyzさんによる魔改造が入りました。

ちなみに、vwxyzさんがこの行列を眺めてたらボス問の O-Special Matrix を思いついたらしいです。

え、ボス問が生えたの僕のせい?

Q - Kurukuru

知り合いに崩壊スターレイルを嗜んでいる方が何人かいて、「くるくるー」と言いながら攻撃を行うキャラがいるようです。

最初はN<=1000で操作を順番に行って終了後の盤面を出力っていう原案でした。また、盤面を回転させる操作があって、それがkurukuru要素だったのですが、他の操作で再現できてしまうため、消されました。

writer陣で話してて

僕「行列をセグ木に乗せて操作の範囲のクエリにするとか面白そうとかも思ったんですけどね」

KowerKoint・vwxyz「それで長方形領域の総和とか面白そうですね」

感想

楽しんでいただけてうれしいです!! ありがとうございました!!!!

運営は KowerKoint に marunage

高専カンファレンス150 osakaでLTをしました

スライドをそのまま公開はしたくないなーとなったので抜粋しながら補足させていただきます。

編入関係の話をしました。が、実情は編入の中身の話はあんまりしてないです。はてなブログの方に体験記置いてるのでこっちに勉強方法とかいろいろ書いてます。他にどの大学がどうとか専攻科と迷ってるとかそういう質問はdmいただけるとうれしいです。

shinchankosen.hatenadiary.jp

自己紹介

shinchanです。大阪大学工学部の4年生です。高専は明石でした(kosen17s)。

X(twitter)は以下の2つです。上が主に高専とか大学用、下が競プロとか用です。

https://twitter.com/shinchankosen

https://twitter.com/Sophia_maki

バイトで量子コンピュータ関係のことをやってます。 研究では機械学習とか画像処理とかやってます。

趣味は競技プログラミングです。

AtCoderは黄色です。上位1%くらいです。今年はICPCとかトヨタコン×2で3回東京のオンサイトに行かせていただきました。

https://atcoder.jp/users/shinchan

もし興味あれば私たちが主催しているOUPCに来てください!

主なリンクは↓ここにだいたい置いてます。

https://shinchankosen.github.io/shinchan.github.io/

編入あれこれ

まずは私の元クラスメートの進学実績です。補足しておくと、教員には「今年は旧帝が1桁しかいなかった…」と言われており、過去はえぐかったことがわかります。が、最近の明石高専は下がってきていて、今年は旧帝が2人とかしかいなかったはずです。なんでレベル下がってきてるのかって話を最後にしました。まぁ、もちろん強い人が入学してくる運要素もあるとは思います、うちのクラスにはIパス・基本情報・応用情報・セキュスペ・ネスペの史上最年少がいましたし。

以下、各大学のエピソード

↑日本語が悪そう、落ちたって言ったのは私です。

編入とか就職のためになにができるか

ベタなところ

編入では面接だとか調査書があります。調査書には高専時代にがんばったこととかを書かなければいけません。僕は高専時代、吹奏楽部やったりボドゲやる同好会の部長やったり数学研究会クラスメートと一緒に創ったりしてました。競プロは言うまでもなく。

情報系に限ると

jig.jpの福野さんとかが、開発のこととか話してましたね。githubに自分に開発したものを投下しましょう。インターンのESにはgithubのURLを書く欄があったりします。

また、私は高専に来たにも関わらずものづくりに興味がなかったのですが、そういう人におすすめなのが、競プロ・CTF・kaggleです。競プロが一番とっつきやすいかなと思います。競プロはレートという自分の強さを表す指標が可視化されます。競プロのサイトにAtCoderというものがあるのですが、これもインターンのESで書く欄がありました。

人と交流しましょう

僕は高専時代はとてもコミュ症だったので人と会話が続かないことが多かったです。単にコミュ力というだけで高専生には「うっ」となる内容ですね。それこそ高専生が彼女を作る方法についてLTをしている方がいらっしゃいましたね。ただ、別にリアルでちゃんと話せる必要はこの段階ではないかなーと思ってます。twitterでちゃんとしゃべれてるなら人脈という意味では大丈夫だと思ってます。

知り合った高専生とは、twitterは交換しておくとよいです。数年たってから、編入なら、家に泊まらせてもらえたり、過去問もらえたり、その学部の友人を紹介してくれたり。編入に限らず、後々就活とかでも生きてきます。

別に会ったことなくても、twitterでいいね押しまくってたらある程度覚えてもらえると思います。DM凸して「過去問ください」してもいいと思います。僕も歓迎してます。

さて、元の話に戻ります。なぜ数年前の明石が強かったかという話です。

5年ほど前のtwitterは明石と木更津が強かったです。twitterをやってる高専生はカンファなどのリアルの交流もなんやかんや多いです。4年くらい前、関西でのカンファには毎回私のクラスメートが5人くらい参加してたと思います。明石高専での開催も2回くらいありました。

そうやって外でいろいろ吸収する人が多くなってきて、その中で競プロが流行ったりしました。特に競プロは数学力と直結します。競プロから外れてそれぞれの道に行った人も多いですが、そうやって強い人が量産されていきました。

その他

時間の都合上言えなかったことがいくつかあります。編入のことなんて全部しゃべろうと思ったら90分とかでも足りませんからね。

なんで編入したとか。専攻科との違いとか。各大学の特徴とか。勉強法とか。

はてなブログに書いてる部分もありますが、気軽に質問してください。

競プロ始めて6年、知らないうちに黄色になってました

この記事は競プロ Advent Calendar 2023 の 9 日目の記事として書かれました。

この6年間の話を、まとめる機会がほしいと思って、書かせていただきました。

↓ これよりも自分語りをすることが目標です。

leaf1415.hatenablog.com

目次

自己紹介

大阪大学工学部B4の shinchan (@Sophia_maki) です。

さて、本題に入ります。

競プロを始める前

高専・情報系に進んだきっかけ

高専・情報系に進んだきっかけは簡単に言えば、数学好きで国語嫌でセンター受けたくなくて、阪大に行く最適ルートは高専からの編入だと考えたからです。

私がいた明石高専には、機械工学科・電気情報工学科・建築学科・都市システム工学科の4学科があります。機械か電気だなぁと思ったあと、高専の先生に数学がしたいなら電気だと言われ、友人にも「数学なら情報系」と言われたのがきっかけでした。

↓ 具体的にはこんな感じです。

なお私は、中学の時点でpcについてはwordが使えたり高専のこと調べるのに使ってたくらいで、プログラミングとかは高専入ってからでいいやーって思ってました。スマホは中学卒業時に買ってもらったため、SNSも使ったことがなく、「アカウント」とか「ログイン」という概念も知りません。

中学までの学力面は、数学力はわりとあったので、田舎の公立中(学年66人)で2位以内に入ることに困ったことはないくらいです。中3のときに「下剋上受験」というドラマを見て中学受験の存在を知ったくらいには過疎ってて、都会のことや科オリとか競プロのことは知らなかったです。数オリはサマーウォーズで知ってたけどオリンピックと言うんだから大人がでるものだと思ってました。

中学の暇だったときにこういうことをもっと知れたらなぁとは今でも思います。

0年目(高専入学後)

私は意識だけは高かったので、上記のような世界があると知ると、いろいろ始めようとしました。

しかし、例えば英語を勉強しようとしても、今まで勉強をほとんどしたことがなくてやり方がわかりません。暗記科目は特に苦手でした。数学はもともと自信があったのでなんとかはなりましたが、例えば f(x) という表記に数ヶ月つまづいてました。

クラスメートには例年よりもすごい人が揃っていて、IPA資格史上最年少5つ持ちなんかがいました。

彼らを中心にして AtCoder がクラスで流行り始めました。多いときで毎週10人くらいが参加してました。登録するだけなら30人くらいしてるかもです。

この頃私は、「ものづくりに興味がない」ということに気づいてしまいました。高専生なのに?

いわゆるWebページの開発とかそういうものを、やってみたいとは思いつつ、多分それは自分がしたいことではなかったと思います。

そんな中、弊学ではCTFや競プロが流行っていて、自分もプログラミングを趣味でやりたいと思って、クラスメートにエディタのインストールやらいろいろやってもらったのですが、結局なにがなんだかさっぱりでした。何かしらのツールを自分でインストールすることすらできなかったです。

授業でもプログラミングが始まり、毎週クラスメートに教えてもらってなんとかついていってました。githubを使う課題があって「ログインってなんだろう」って思ったのを覚えています。

さて、数学ならいけるだろうと、1月の数オリにノー勉で特攻したところ2問しか解けませんでした。ようやく、AtCoderを始める決断をしました。高1の1月下旬にクラスメートにアカウントを作ってもらってスタートです!

1年目

茶色になるまで

初めてでたコンテストは確かunratedで、0完でした。ratedにでると、C言語でなんとか1問解けました。B問題すらわからない頃は、寮でもクラスメートの部屋で過去問の解法を教えてもらっていました。初めは人に教えてもらわないとわからないですよね。なぜ初心者プログラマは自分で調べようとしないのかを考えてみました。

  • 英語の記事が多くてわからない(翻訳に通してもわからない)

  • 専門用語多くてわからない

  • インターネットで調べるだけなのは悪だと教えられてきたのを「インターネットは悪」だと解釈し、学問(プログラミング含む)とインターネットは完全に切り離さないといけないと認識している(私の場合)

レートが600を超えるまでは言語はPythonとCとC++をいったりきたりしていました。授業で習うのはC、クラスメートがよく競プロで使っているのはC++、よく教えてくれるクラスメートが使っていたのがPythonだったからです。

さて、この頃の灰色というのはratedに出ればレートがあがります。Cの文法を学んでコンテストの復習をしていたくらいで、数ヶ月で茶色になりました。

茶になる直前の画像を発掘しました。アイキャッチ画像用。

緑になるまで

高2になりました。灰色の頃使っていた環境は、コンパイラコマンドプロンプトminGWを使っていて(これもクラスメートに入れてもらった)、エディタはatomだった(これもクラスメートに入れてもらった)と思います。

茶になってからは先輩にWSLを教えてもらって、エディタもsublimeになりました。WSLは先輩のサポートでなんとか入れて、sublimeは自分でなんとか入れることができました(成長)

さて、レート600の頃、停滞したのでちょっとした精進として、3日間でA問題やB問題を100問ほど埋めたりするとレートはまた上がり始めました。また、言語もC++に固定しました。

なにかプログラミングに関連したものに参加したいと思って、高専プロコンの課題部門に出たりしました。ひたすら足手まといと雑用をしました。JOI予選はおちました(クラスメート4人通過しててすごい)。

あとは基本情報を受けました。一緒に受けた3人は全員受かって僕だけ落ちました…。午前は勉強してさえ取れるのですが、午後は国語力がなくて全然取れませんでした(午前65な時点で勉強不足ではありますが、午後35…)

数オリは高2のときが一番惜しく、あと1点でした。多少は勉強した。

緑になった。

この頃の心境

競プロをやっていたのは、なにかに役立つとは思うものの、競プロだけではやっていけないとはかなり感じていました。まだクラスで競プロは流行ってはいたものの、競プロは役に立たないという意見は身の回りにもけっこうありました。

そんな中でも競プロを続けられたのは、「競プロを辞めたところで自分が他になにか始めるわけではない」ということを自覚していたからです。競プロのいいところは他の情報系の分野に比べて始めやすいことだと思います。興味自体もそうですが、難易度的に自分のレベルで競プロ以外のものを続けられる気がしなかったです。基本情報も高専プロコンも自分がなにかできるわけではなかった。せめて、自分の数学力が生かせる競プロなら、と思ってこれ続けられなかったら電気のコースに進むしかないと思いながら続けていました。

知り合った強い人

当時競プロerは校内しか知り合いがいなかったのですが、どんどん校外に知り合いが増えていきました。クラスメートに水コーダーはいた(4つ上に橙がいたらしいですが…)。

春には青コーダーのたつやんさん、夏には黄色コーダー(現橙)のこたまねぎさん、秋には橙コーダーのけんちょんさん。

正直青以上は宇宙人だと思っていました。夏に会った高1で青の女性もなかなか衝撃でした。

2年目

水になるまで

2年の終わり頃、クラスメートに本を借りたりしながら、プログラミング言語をいろいろ触ってみた記憶。java, ruby, kotlin, C#くらいですかね。正直、「kotlin実行時間遅いなー。C#javaはコード長くていやだ。rubyは、なんか、嫌だ」という感想でした。

初めて技術書を買ってみました。kotlinでandroidアプリ開発する本です。1/3くらい読んで挫折してしまいました。

高3の最初の数学のテストで、クラス1位になることができました。競プロのおかげで数学力も上がってきていることが実感できました(テイラー展開とかの範囲なので関係ないかもだけど)。また、緑になると、「自分は競プロerである」とはっきり考えられるようになりました。高3にもなると思春期的なものも終わりかけて、自分に自信が一番あった時期かもです。codeforcesも始めました。


精進に関しては、水になるまでは茶のレート600付近での精進や日々のrated以外は精進の記憶があまりないです。そうこうしてたら水になりました。

もしかしたら事実と異なる記述があるかもしれませんが、以下の記事の方が多分合ってます。

shinchankosen.hatenadiary.jp

水になってから

この頃になると競プロを続けているクラスメートは5人くらいになってたと思います。私はというと、水になったはいいものの、青パフォ以上を出したことがないので緑のときに比べて自信がなかったです。そうこうしてたらabc140で運よく黄パフォを出すことができました。

atcoder.jp

この直後にはPCKがありました。校内からは2チーム出ており、残り10分までは勝ってたのにそこから抜かれてしまい、校内制限で通過できませんでした。またしてもオンサイトに行けず…。

この時期はかなり忙しかったです。私は入学当初から、以下の3つの団体に所属していました。

  • 吹奏楽部 : 週6なので一番重い

  • 棋道同好会 : 将棋とかのボードゲームやる。3年のときは部長だった。

  • 数学研究会 : クラスメートと入学してすぐ立ち上げた。副部長と会計やってた。

あと忙しかった原因といえば、明石高専生なら「おしろ」と言えば伝わるだろう。某レポートやら、他にもレポートに追われていて高専生っぽい忙しさだったと思う。

そんな感じで精進はあまりできず、ただ、数オリの勉強はしていた。今年こそは本選に行きたかった。行きたかった…。

落ちた。帰りに連れと一緒にカラオケに行って叫びまくって、「もう自分には競プロしか残ってないんだ」と感じた。その日から極度精進を始めた。

3年目

青になるまで

そんな中、某コロナがきた。春休みは1ヶ月伸びて2ヶ月になり、結果的に7月にオフライン授業が再開するまで部活も停止。

開いた時間で毎日問題を解き続けた。休みの日は平均して10時間、実家からのオンライン授業だったので授業中もひたすら競プロして、平日も6時間くらいやった。

青になったとき、思わず叫んでしまった。

shinchankosen.hatenadiary.jp

青になってから

まずはICPC。学内1チームで黄色がいるのでそれはそうなのだが、通った。

shinchankosen.hatenadiary.jp

しかし、またしてもコロナによって、オンサイトに行くことができなかった。

shinchankosen.hatenadiary.jp

この頃たぶん「そろそろ自分にもできるんじゃないか??」と考え、機械学習に手をだした。「ニューラルネットワーク自作入門」とかをやったり、kaggleのtitanicをちょっとだけやった。でもそこからが難しくて結局ここでもなにもできなかった。

精進はというと、青になってからしばらく休んだ。5か月間の極度精進に終わりを告げ、編入試験応用情報の勉強を始めた。

応用情報は落ちた…。午前72、午後50とかだった…。クラスメートにも、「これは国語でしんちゃんに向いてないから競プロだけやってればいい」と言ってもらった。でもさすがに、某クラスメートが小6で最年少合格してる試験に大学1年の青コーダーが落ちるのは、かなり悲しい気持ちがあった。

AtCoder青より応用情報の方が難しいよ。まじで。

すっかり精進から離れたものの、競プロキャンプに行ったことで変わった。ちょっとフライングするけど入黄記事の中で、私が青になってからも精進を続けた理由が書いてあったので紹介します。コンテスト・精進のところに諸々が書いてます。

shinchankosen.hatenadiary.jp

tozangezanさんがyoutubeの概要欄に書いていた、「競技プログラミングよりも役に立たないものの例として、競技プログラミングが役にたつかどうかというくだらないTwitter上の議論に何時間も参加することが挙げられます。あなたが競技プログラミングが役に立たないと言っている人に対して役に立った例を探してきてリプライしている時間に、本当に強い競技プログラマーは問題を解いているのです。」

のいみさんに競プロキャンプで言われた、「目の前にRatedがあるのになんででないんですか?」

これらがなければ青で満足しきって競プロをやめてた可能性が高い。

4年目

この時期はさすがにクラスも編入一色。精進はしたいけどできない状況。我慢できなくてGWあたりにTechFulに手をだして3日間ひたすらやり続けて総合ランキング3位とかまで上がった。

編入は現在通っているところに合格。入学時の成績からすると、阪大に合格できたのは競プロのおかげだなぁと今でも思います。高専数学とか電気系の専門科目とか、直接関わる分野はないけれど、数学力という点においては共通していて、ここが鍛えられたことは競プロのおかげです。

編入試験が終わるとまた競プロは再開。Highest1998まで行ったのに黄色になれなかった…。

そういえばICPCはひっそりと落ちました。

後期になって、兄の紹介でとあるweb系のアルバイトをした。技術系のアルバイトをなにかしたかったところ、運よく拾ってくれるところがあったからである。

Ruby on Railsが生理的に受け付けなくて仕事1つしかしないままフェードアウト…。。

5年目

卒論の時期はさすがに競プロはしてなかった。

大学編スタート。

某量子バイトもスタート!!

黄色になりたくて、精進は続けていた。でも編入なので2年の授業ととらないといけなかったりでうまく時間が取れない面もあった。

明石から一緒に編入した3人でICPCにでてもちろん落ちた(青・青・水)。



夏にはDDCCに出た。24卒枠でなんか通ったが、初オンサイトでウキウキ。

shinchankosen.hatenadiary.jp





それと、インターンに行きました!!!!

AtCoder Jobsにもある田町にある高速化で有名なF社です。競プロが実務に生かせるということが実感できてますます競プロに熱が入るきっかけになりました。ただ、どこにいってもgitは必要だなぁと感じ、ライブラリをgitで管理し始めたのはこの頃からだったかも。

さて、、、












黄色に、、、なりました!!!!!!!!

shinchankosen.hatenadiary.jp

6年目

黄色になってから

トヨタコンの決勝に参加しました。大した結果はでてないのですが、懇親会や大宴会で話しかけてくれる人が多くて気持ちよくなったりしてました。

shinchankosen.hatenadiary.jp

今でもいろんな人が「え、黄色????就活つよつよじゃん!!!!」と言ってくれて正直けっこう気持ちいいです。


ICPCは3年ぶりのRegional!!!!

shinchankosen.hatenadiary.jp

shinchankosen.hatenadiary.jp



黄色になってからは解説を書いたり、作問もちょっと増えてきました。作問は全然少ない方ではあるのですが、OUPCなどでどんどん放流していきたいと思ってます。

shinchankosen.hatenadiary.jp


直近の話

さて、話は変わります。研究室選びです。基礎工学部ではなくて工学部なのであまり競プロっぽい研究室はほぼありません。また、この頃は就活のことを考えたりしていて、Jobsを徘徊したり、career design dayに参加したりしていたのですが、Web系と機械学習系に対極しているのでは?と感じるようになります。「Webはもう嫌だし、機械学習だとちゃんとやれば自分に向いてるかも」と思ったり、いもすさんとか秋葉さんみたいな「競プロと機械学習両方強い人」にあこがれを感じ、機械学習にちゃんと手を出してみようかな?Kaggleもちゃんとやろう。と思いながら、第二希望ですが現在の研究室で機械学習をやっています。競プロ単体で一生食べていくのは危険だと思ったのもあります。

また、「kaggleやるんならAHCもできなきゃだめだろ」と思ってAHCに出始めました。なにもわからないので緑パフォを連発していたのですが、運よくトヨタAHCに通ってしまいました。インターンでお世話になった方に挨拶ができてよかったです。

shinchankosen.hatenadiary.jp

サンダー本は一応読んだのですが、その後も運ゲー貪欲を重ねて青になりました。まじでありがたい。

機械学習自体に対しての動きなのですが、関西Kaggler会に参加したり、東大松尾研がやっている GCI をするなどしています。Kaggle自体はまだ始められてない…。でも始める準備は整ってきてる…!



そんな感じで、機械学習にせよ、gitにせよ、競プロ以外のものは競プロから徐々に広げていける方向だと身に付けられるそう、というかそうじゃないと挫折するだけだとわかった。

また、この界隈にいたり大学で勉強するだけで、それに伴って競プロ以外の知識もついてくることはあるので、いろんな分野の基盤が固まってきたのかなとも思いました。

webとか機械学習とかって競プロとの大きな違いは、ファイルが複数あってごっちゃごっちゃしててよくわからんことですね。競プロって1ファイルで完結してしまうのめっちゃいいですよね。

それはそうと、アルバイト・長期インターン・春インターンなど、機械学習の方面でjobsから申し込めるとこにしたいと思いつつどうしようかなーというのが直近の迷いです。


てか最近のAIやばくないですか??競プロ一生続けるとかは言ってられなくなってきました。さすがにICPCにあと2回出れるので学生のうちは続けるとは思うけど…。競プロという一つの宗教から目が覚めたという意味ではいいかもしれません。将来がますますわからなくなりそうですね。

↓ こういうことをいつも考えてはいるものの…。まぁ働き方という面では変わらないのかな。どういう職につくかはかなり影響がでそうです。

まとめ

かなりダラダラ書いてしまったので言いたいことだけまとめます。母数N=1なので共感・否定の意見待ってます。

  • 情報系に行きたいor来てしまったけどものづくりに興味がないなら競プロを始めろ

  • プログラミングをやりたいけどなにがなんだかわからなくて進まないならとりあえず競プロを始めろ

  • 基本情報や応用情報を解いて無理だと思ったら競プロを始めろ

  • 緑になったらある程度自信も出て楽しいと感じるようになるからそこまではがんばれ、大丈夫、情報系ならどの分野でも緑はあった方がいい。

  • 「自分にはこれしかない…」と感じたものを大事にしよう。継続しよう。

  • いきなり違う分野に行ってもわからない。得意なことや今までやってきたこととの共通点を探して広げる方向で精進しよう。

  • それでも無理なもんは無理だと思う。今は無理で諦めてもいいと思う。その分野が得意な人が身近にいたり、結局大学で最低限度やらなきゃいけなかったりで、なんやかんや知識は少しずつ身についていって、数年後には、できるようになってることがある。

  • gitはやっといた方がいい。ライブラリの整理とかから始めよう。

あとがき

このブログの名前は「橙になりたいaquarium」です。まだ茶か緑の頃、ラブライブサンシャインの「恋になりたいaquarium」をもじって「橙になりたい」ってしてみました。もっとも、そのころは「行けて青」だと思ってましたが。でも、codeforcesは橙で、AtCoderもいつのまにか黄色…。かなり現実的になってきました。学生のうちには間に合うかわからないけど、将来的に橙はいけそうだなーという感触です。赤はわからないですが、赤にもなるとそれこそ、こっちの道に骨をうずめるしかないですね。

追記

まとめの後半で無理なもんは無理だとか言ってたんですが、補足をさせていただきます。

自分も競プロを始めて最初の1年間はあまり楽しいと感じませんでした。楽しいから続けられるはそれはそうなのですが、気持ちはどうであれ継続してみることも大事だと思います。数年やってたらある程度のレベルにはなるはずです。業務とか学業で義務化されるのがこれにあてはまりそうです。

ところで自分語りが足りなかったと思うので学業の方面について補足させていただきます。

「自分には競プロしかない」をわりと強調してしまってるかもなんですが、自分は(高1のときを除いて)学業が崩壊していたことはないです。

競プロのやりすぎで学業に支障の出ないようにはした方が良いです、あたりまえですが、、。とはいいつつ、競プロ関係の記事を読んで理解するだけでも、特に専門科目や理系科目で新しいことを理解しやすくなります。競プロは学業の役に立ちます。(じゃないと僕が阪大なんか受からないだろ、という気持ちでいます)

学業が崩壊しない程度に精進がんばりましょう…


最後にはなりますが、ものづくりは今でも興味あまりないです。数学とかアルゴリズムによる高速化とかがまったく絡まない分野の開発について、手を出してみるものの長く続かないがちです。数学やアルゴリズムをやるための手段としての開発は全然やっていきたいです。じゃないと競プロも実装という工程がある以上続かないし。




お知らせ

OUPC来てね!!!!!!!!!!!!!!!

connpass.com

ICPC2023 Asia Yokohama Regional 参加記 (kotamanegi_mijingiri, shinchan 視点)

7完20位。阪大内2位。

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

shinchankosen.hatenadiary.jp

チーム

kotamanegi_mijingiri

黄色下位3人チーム(最近KowerKointは2段になりました)で、阪大では2軍でした、国内では3軍のチームに負けましたが…。

  • KowerKoint (@KowerKoint2010)

一番レート高い。実装とか早解きの鬼。

  • Daylight (@Daylight_pro)

DPとかデータ構造が得意らしいです。3人の中では一番英語ができるので問題読解を頼むことが多かった。

数学とかFPSとか構築が(2人に比べて)ちょっとだけできます

戦略

KowerKoint君にAのFAを狙ってもらったあとセットアップ。Daylight君にはB。僕はそれ以降の問題に後ろからざっと目を通して、問題文が短いものから読んで解けそうなのを探す。

また、その都度得意不得意に合わせて問題の交換は行い、読解がわからない問題があったり新しく読みたい問題はDaylight君に任せたり、重実装やライブラリ写経はKowerKoint君に任せたりという方針をとりました。

そして、私はできる限り実装をしない。すぐかけそうなのは書いてもよい。と決めていました。

あと特にこういうのは決めてるわけではないですが、僕の性格的にいろんなことに口出ししたいタイプなので、2人に指示を出したり、2人の解法のコーナーケースを探したりすることが多かったです。これは結果的に(最後の15分を除いて)いい方向に招くことができたと思います。

実力は遠く及びませんが、これのりんごさんみたいなポジションがしたいのかなと感じました。 japlj.hatenablog.com

リハーサル

順位表が見当たらないので解いた順番とかは忘れました。

A問題

KowerKoint君にFAを狙ってもらいましたが2位だったような気がする。おしい。

B問題

インタラクティブ。KowerKoint君が実装を終えてサンプルが合わなかったかペナったかだった気がします。僕も問題を聞いて考察は自明。KowerKoint君の解法だと実装バグらせやすそうと思って僕が実装しなおしてAC。

C問題

Daylight君が困っていました。解法を思いついたけどサンプルがなぜそうなるかわからない、という状況でした。KowerKoint君も手伝ったかは忘れました(ごめん)。僕も問題を聞いて、お気持ち解法と注意点をいろいろ説明してサンプルだとこの注意点にはまってしまってーというのを説明した。Daylight君が細かいところを詰めて実装してAC。

D問題

読んだら典型と既出の組み合わせみたいな問題だった。重実装では全然ないけど僕が書くには重いので、KowerKoint君に解法を説明して実装してもらってAC。

本番

順位表があるのでできる限り時系列順に。

icpcsec.firebaseapp.com

コンテスト開始、KowerKoint君がAを読んで実装。Daylight君が封筒を開けてBを見る。shinchanはボールペンをすべて開封して後ろからさらっと雰囲気だけ目を通した。問題の種類だけメモった。

A(0:05) KowerKoint

2位だった。おしい。

Daylight君がBで詰まってたので僕も問題を教えてもらったが僕は苦手そうなのでKowerKoint君が手伝う形に。

このあたりのどこかで、僕が2人に「Dが構文解析みたいなの書いてある。サンプルみた感じは簡単そう、読んでみてほしい」と伝えてKowerKoint君にやらせてみたら考察(そんなに難しくなく、ロリハ+区間DP+復元らしい)と実装100行を爆速で終えてAC。FAでした!

D(0:27) KowerKoint

KowerKoint君が実装している間、順位表ではspeed starにFが解かれていた。読んでみると得意だった。setで i 行目と i+1 行目が反転しているとき i+1 が入っているみたいなのを行と列それぞれ持った。実装も簡単そうだったのでそのまま僕が実装してAC。

F(0:36) shinchan

このあたりでDaylight君かKowerKoint君がBを実装してペナを生やしていた気がする。僕はCを考えていた。Cはポリアの定理はそれはそうとして、回転の重複を無視する場合が解けなければ話にならないが、話にならなかったし順位表を見て難問らしいので捨てる。

BをKowerKoint君に任せてDaylight君と他の問題を見る。Kが解かれていたが海外なのでいったん無視する。speed starが解いていた問題をDaylight君に読解を任せて2人で考察してた気がする。

しばらくしたらKのACが増えていたのでDaylight君に読解と説明してもらうと解法はすぐ生えたのでDaylight君に伝えた。KowerKoint君がBを実装している間は、2人でインタラクティブ特有の質問回数の制限とかが大丈夫かの確認をしていた。

そうこうしてたらKowerKoint君がセグ木二分探索でO(NlogN)でBをAC。コンテスト後にわかった話では入力の数値Cの制約を見落としていてこのようなことになってしまった…。

B(1:54) KowerKoint (考察: KowerKoint, Daylight)

このあたり記憶があやふやなんですが、KowerKoint君がEの実装をしていた気もする。さて、Daylight君がKを実装、バグがあったので僕もコードを読んで2人でバグを見つけたりした。

K(2:45) Daylight (考察: shinchan, Daylight)

EとGは解きたいなぁという気持ちになる。Eは僕が「高速ゼータ変換…、うーん、ないか」と言ったのに思いつけなかった。KowerKoint君がいろいろ工夫して永続配列を書いたりしていた。

EはKowerKoint君に任せて、GをDaylight君と一緒に考えていた。2人でDPの添え字が合うことを確認したあと、高速化手法を考える。「FPSとか…、でも畳み込みじゃないしなー」って言ってた気がする。僕が「メモ化再帰でけっこう重複しそうで実際O(N2)もかかんないんじゃない?」と言ってワンチャンを狙ってDaylight君に実装してもらった。

動かしてみると時間制限の2倍くらいかかってた。KowerKoint君がその実装を見て「非再帰で書きたい」と言ってきた。そう、KowerKoint君はなんでも非再帰で書く。僕が「それは時間かかるからmapをunorderedにしてkeyをpairからlong longに変えてやりましょう」と指示。間に合いそうだったので提出。

なんと出力のコメントアウトを除き忘れていた!1ペナしてAC。

G(4:08) Daylight (考察: shinchan, Daylight)

さて、KowerKoint君がEでメモリのとりすぎとかでREが外れないそう。 メモリをその都度解放するようなコードに変えてなんとかAC。空間計算量 O(N*C(N, N/2) + 2N)とかで解いてたような記憶がある。

E(4:32) KowerKoint (考察: KowerKoint)

Jやってるdaylight君が「HL分解と貪欲でワンチャン…」と言い出し、他2人も「ワンチャンすぎるな…」となってKowerKoint君がとりあえずHL分解を書く。

僕が「貪欲はさすがに無理やろ~~」って言ってしまったのが戦犯。HL分解書き終わった時点で残り15分あったが、書き終われる保証はなかったけど。

このあたりは僕がちょっと貪欲解法を理解していなかったような気がする。コミュニケーションがうまくできていなかったかも。

最後に残りの問題に2,3回ずつa.cppを提出して終了。

英会話

3人いるときの英会話はほとんどチームメイトに任せていた。チーム紹介もKowerKoint君がやってくれたし。僕は単語しか言ってない気がする。

「hello」

「thank you」

「yes」

「ok」

「sorry」

「restroom」

「male」

「kotamanegi_mijingiri」

「Osaka University」

本番中にトイレに行きたいときも「restroom」と単語だけ言ってなんとかしていた。

MaleとFemaleを聞かれてどっちが男性なのか忘れたが2分の1が当たってよかった。

コンテスト前にボールペン開けていいのかなって思って「pen, open, ok?」って言ってダメって言われたけど隣のチームが開けてたの指さしたら申し訳なさそうにsorryって言われるなど。ライブラリを画面に置くアレといい、ライブラリの紙をなんとか立たせるチームもいたり、well-definedを求められる運営も大変だなぁと思った。

あとがき

阪大の1軍チーム、kotamanegi_marunageが4位で本当にすごい。こたまねぎさんとkuhakuさんはラストイヤーだったので来年は僕が1軍になる可能性がありますが、ここに追いつけるようにがんばります。vwxyzさんがよく「SPJには勝ちたい」と言っていて、SPJが5位でちゃんと勝っててすごい。

speed starもさすがです。今年がラストイヤーの強い人がけっこう多いですが、今の高3も赤がいたりしますし気を抜けませんね(阪大来てほしいな~~~)。

懇親会はいつも通り企業の人としゃべることや食べることを忘れてましたが、話したい人と話したり、話しかけられたりしてうれしかったです。

来年と再来年もよろしくお願いします!