2023 ICPC Seoul Regionalの予選の参加後記と愚痴話

こんにちは。リユナと申します。

一昨年と昨年に続いて、今年も同じメンバーでICPCのソウルリージョナルを参加することに決定されて、１０月２６日土曜日の予選に参加しました。チーム名はなぜか今回からチーム名の長さと少しの規定が新しくできて、例の「MunSongSong Eggdrop」じゃなく「Gyerantak」(韓国語で「卵パカッ」という意味です。)で参加することになりました。ただ、運営上のミスが多くて、ちょっと愚痴話もしたくなります。

チーム結成の話とか、チーム員各々の特性とかは前のポストを参考してください！

では、始まります！

0. スコアボード

今年のスコアボードは二種類あります。その理由は後で説明いたします。

大会場でのスコアボード

最終結果のスコアボード

1.大会中のタイムライン

(0分)私が前の部分、songCが真ん中、mhyが後ろの部分を読みました。前にある問題が全部解決できなそうで、少し悩んでいました。それでも可能性がありそうなのはDだったので、Dの解き方を考え始めました。

(6分)songCがEが簡単だと言ってすぐに実装に入り、その後ACをもらいました。

(18分)続々SongCがHをACもらいました。

(33分)Fもやはりバックトラッキングでうまく実装すればそれほど難しくない問題だったので、すぐにACをもらいました。おそらくこの時点まではスコアボードで余裕に1位になっていたと思います。

…そして大惨事になりました。

(60分ごろから..?)mhyがCを取って解き始めました。ロリハやグラフ置換とダイクストラなど色々な方法を悩んでみて、問題理解を誤ったことに気づいて再び実装し、そのうちに例題がよく出てこなくて再び実装し、間違っているようでコードを出力した後に再び実装し、など数多くの試行錯誤の末にもACが出てくる気配は見えませんでした。私とSongCはmhyが止めたと判断し、他の問題からいっそ考えることを提案しました。

(91分)DのACをもらいました。最初は本当にbinary matrixを利用して変数2000個の連立1次方程式を解かなければならないのか、、と思いました。影響を及ぼす可能性のあるものが一つの変数に多くても二つだから式が思ったよりきれいに出るのではないかと思いましたが、これはヤバすぎだと思ってsongCと相談した結果、2-SATやもっと簡単にはUnion Findで管理しながらすぐに可能だという解釈を導き出して実装して当てました。

その後、mhyはC、私はK、songCはGに死活をかけて実装しましたが、皆実装が大きくできなくなり、とても進行が足踏みされました。私たちは本当にこの時点で、このままだと本大会の受賞と月波どころか、そもそも本大会進出も危ないと思い、大いに緊張して気をもんでいました。（結論的にこの時点で大会が終わっても本選進出は可能だったから杞憂だったんですけどねww）

やがてみんなが気が抜けた2時間半後の時点あたりから、私はなんとかKプールの構想を終え、SongCはGのデバッグがほとんど終わっていくようでした。それでも4ソロ大会を終えることはできなかったので、最後までベストを尽くしました。

(169分)奇跡的にsongCのGがACをもらいました。

(175分)なんと終了わずか5分を残して、私のKデバッグが終わって提出して、すぐACをもらいました。

その後、mhyはCをずっと見ていましたが、結局間違いは見つからず、大会は終わってしまいました。大会がほぼ終わる頃に、mhyが「いや、配列を20万までにしないといけないのに、10万だからといってREが出ないといけないんだけど？なんでWAが出るんだろう？最初から実装自体を間違えたのかな？」という発言が出て、これが後起こる事態の伏線となりました。

珍しくも今回の大会はフリーズがなかったので、結論的に当時スコアボード7位で、そのまま本選進出を決め、あっさりと大会を終えました。

2.大会のあとの話

まさに大事件が起きました。

翌日、突然チーム員たちとのチャットや他の韓国の競プロ界隈からCに対してACできたコードの反例が続出し、そもそもデータが間違っているようだという話などが聞き始まりました。どうせ私たちには間違った問題で気にせずいたんですが、あちこちでこの問題によるノイズがたびたびと聞こえました。

また、公式ページのお知らせ事項で「修正事項がありますので順位表を下げ、再採点を行います」って言って、問題にあったのはCに間違いないとみんな確信する雰囲気でした。

そのあと、Cの問題のデータは本当にエラーが確認されて、「既存CがACだったチームは正解認定、既存のCが間違ったチームによっては再採点でACが出たら正解を認定し、無条件で本選大会に進出、そしてそれにより既存よりもうちょっとチームの先発を行う。」というお知らせが公告されました。スコアボードも大会当時のスコアボードと(１番目のイメージ)再採点以後のスコアボード(２番目のイメージ)がすべて公開されました。

3.愚痴話

まあ、結論的に予選の順位は本当に関係ない話だし、本選大会の進出はどんなバージョンのスコアボードでも余裕にできるので私たちに直接できな障害はなかったんですが、やっぱりあまりにも残念でがっかりしているのが本気です。

私たちのCのコードはアルゴリズムは正しかったが、配列を宣言する長さが間違ったので、もしデータが正しかったらREが出なければならないコードでした。しかしWAが出ちゃって「これはそもそもアルゴリズム自体が間違ってるのか」と思わせてずっとデバッグしましたがバグを探せず結局間違ったままに残りました。もしかして間違ってたデータがなくて結果が「RE」で正しく出たなら、私たちのデバッグの方向性は配列の宣言の長さやindexなどに集中されて難なくデバッグができたかもしれません。

実際、私たちはCの正解の有無にはあまり影響を及ぼさないレベルのチームだったんですが、こんな理由でCを十分に解けるチームだったが解けなかったチームがないとは言えません。結果的に再採点以後ACをもらったチームたちは救済を受けましたが、こんな場合は結局証明もできず、証明してもそれはそれで問題だから処理が難しいことは看過できません。そもそもこんな事態になったことが非常に残念だと思います。

実はよく知られてないことなんですが、昨年のソウルRegionalの予選の問題にもデータにエラーがありました。Hの問題の入力ファイルの一つがおかしくなってて、C++で解けばあんま問題なく入力を受けることができますが、PythonでLineを入力されて処理すれば想定外に入力が多くてWAになる問題でした。大会であの問題が解けたチームが１チームしかないほどのかなり難しい問題だったのであんまり知られてなかったんですが、もし私が大会中にPythonで解いて提出して理由も知れずWAを受けたとしたら本当に腹が立ったでしょう。

どうか私は今年を最後にICPCに出場しませんが、競プロが好きな人として、その魅力に大きな傷となり得るようなこんな事態が本大会では絶対に、そしてこれからは二度と再発しないことを心から願っています。

なにとぞ、私も最後のICPC大会で悔いのないほど燃え尽きて、すべてをつぎ込んで見ます！できればPlayoffとWFまで！

4.問題たちの解き方

予選の問題はまだBOJを含めてどのOJサイトにもまだないんですが、多分近来にBOJに投稿されると思います。問題文はここで見られます。

A.

マジで実装だけの問題、大会中に解いたチームはちょっとだけありましたが私たちはこれを解く時間なんかなかったんです。

B.

与えられた順番ではなくその逆からBSTを構築しながら、いつも最後に追加された数がルートになることを利用すれば各々の実行で変化する辺は何個あるかは分かりやすいが、何となくちゃんとしたらO(NlogN)でできそうです、、、が実装できませんでした。大会中に解いたチームもいません。

C.

「あの」事態を起こした問題です。ロリハとDPをよく利用すればできると聞きました。

D.

Union-find、またはDFSで全部チェックすることができます。

E.

説明することもあんまりないです。ABCのBくらいのレベル。

F.

二つの点の間にある直線の数の奇遇性によって解けます。

G.

任意のMSTを一つ作って、あれに入れなかった線分たちにあれらを連結するMSTの経路の点数がちょうどあの線分の重さと一緒ならType2、じゃなければType3です。MSTの中の線分については似たようにしてType1とType2が比べます。

I.

今回に初めて出たInteractive問題。4分面について分けてよくしたらできるらしいですが、実はよく知りません。。。大会中に解いたチーム無し。

J.

二つの輪がどんな線分を基準として別れるのかをよく判別して、条件に注意しながら二分探索だと聞きました。

K.

めっちゃ変な機械装置と変な言語で整列を実装したらいいんです。頭が壊れそうだったんですが、私の方法は「空いたマスたちはいつも引接しているので、どこかで青い玉を拾って空いたマスの一番右に動かして、それでできた空いたマス1つには反対から見える球をすぐ拾ってあのマスへ入る」のような感じでしたらいいんです。問題の内容が分かったら多分理解できると思います。

整列されたかどうかを判別することは、空欄から初めて「青い玉なら進め」の命令と「白い玉なら進め」の命令の後に空欄の上にあるのかどうかで判別できます。

読んでいただき誠にありがとうございます！この記事は前に韓国語のブログに書いた2024 ICPC Korea regional 인터넷 예선 후기を適当に翻訳して投稿しました。もし韓国語ができたらあっちも見てくださったら嬉しいと思います。😉

OMC209の後記

こんにちは、リユナです。

今日のOMC209に出て、9位になる大活躍をしました！あとGのFAもしました！

ちょっとだけミスがあったんですが、でも久々のいい成績で嬉しいです！

では、今日の後記始めます！

G(4分、FA)

初めからなんか解けそうだったので挑戦。式を整理すれば結局(1からAまでの総和)、(1からBまでの総和)、(1からCまでの総和)の式で表せます。実は3の倍数のほうがはるかに多いので、3の倍数ではない場合を割り出すことが易いです。Aまでの和とCまでの和は3の倍数ではなく、Bまでの和が3の倍数になる場合の数を計算して、全体から引く。

初めてはA<B<Cを見てなかったので1ミス。

A(1分)

幾何ですがすぐ解きました。半分にして90度合わせたら正解。

B(54秒)

最初の条件から(x-23)^2+cの形で表せます。後は何とか。

C(2分)

1000a+100b+10c+dのことを勘違いして1と7、2と8、3と9が反対になりましたね。a, b, c, dは差が-6, 0, 6の中の一つなので3^4=81

D(4分)

まずあいこにならない数を数えます。これは「3種類のことの中で7個選んだ時それが全部2種類になる場合の数」なので、3C2*(2^7-1^7*2)でできます。あとはA君が勝つ場合と負けるのは対称だから半分すればいいです。

E(2分)

1とすべての素数に対して素数自身、または素数のk乗が入れば丁度要素数26の集合になりますね。2は6乗まで、3は4乗まで、5と7は2乗までできるので6*4*2*2=96

H(5分)

数列の$1000$以下の項の数を基準として探しながら規則を探して解きました。二つの場合が大事。

F(16分)

Hを全部解いて、Hの提出をここにして1ミス

一応日本語の翻訳が難しかったんです。DがAを中心としてBの対称点か？！と思って全然違う問題を解き始めました。後はこれを直して、スチュワートの定理を何回か使って体育で解こうとしたんですが計算ミス(多分)で1ミス。ECと平行する直線をAから描いて、これとBCの交点をFとしたら、BCDとCFAが相似となりますし、

EBCとABFも相似。これと角の二等分線の性質で何とか頑張って解きました。

総評

(今気づいたんですが、前の記事、総評の漢字が間違っていましたｗ)

Gのような、好きなタイプの問題がちょっとあって好きでした。全部そんなに難しくはないが面白くてよかったんです。4bとしては最高成績ですよね。早く全問完了して、あとGのFAも嬉しいですね！

ミスがちょっとあったのと、日本語の翻訳の問題でちょっと迷ったのが惜しいです。でも仕方ないですね。これは私がもっと日本語を勉強すればいいと思います。

とにかく、最近OMCがよくできなかったんですが、今回は結構いい成績が出てとても嬉しいです！

OMC206の後記

こんにちは、リユナです。

今日のOMC206に出て、4位になる大活躍をしました！

実は今日の整数論の授業がちょっと遅く終わって、少しペナルティがあったんですが、それに負けず素晴らしい成果を出て嬉しいです！

では、今日の後記始めます！

A(1分)

9の倍数になるためにはすべての桁の総和が9の倍数になればよい。あと、11の倍数は、偶数番目の桁と奇数番目の桁それぞれの総和の差が11の倍数になればよい。前者はnが9の倍数、後者はnが偶数の時成立するので答えは18です。

E(25分、1ペナ、FA)

前に競プロの作問をしながらほぼ同じことを勉強したことがあって助かりました！運がよかったんですね。

垂直についている2点をまとめて順番対で考えた方が楽です。 大体そんな風に漸化式を求めて、とにかくうまくやれば最終的に式が出てくるんですが、意外とそこで1237で割った余りを手に入れるのがなかなか難しかったです。

私は初めてのことを固定させていて、最後に6をかけることを忘れて1ペナでした。🥲

B(6分)

幾何に見えますがあんまり幾何的な要素が多くなかったので考えより早く解けました。A1A2Pが二等辺三角形になるのがポイントでしたね。角二つの値を未知数として式を整理すると範囲が出て、あれを満足するnは4以上10未満になりました。が。nが4になればPとQが辺の上に乗るのでだめです。5+6+7+8+9=35。

C(6分、1ペナ)

コインが合わせて14個あります。これらをまず配って、みんなに“配ったコインの数＋1”の枚数の1万円札を配れば1万円札はちょうど1個残ります。これを誰に配るかを考えたらいいです。

私は初めて「五郎君」を見なくて、“あ、四人あるんだな”と思って1ペナしました😂

D(10分、2ペナ)

FAできて嬉しいです！実は、昨日解いた競プロの問題と使われるアイデアが同じで助かりました。

7!=2^4*3^2*5*7で、ある約数dを、square-free(つまり、1以外の平方数で割り切ってない数)な数pと正の整数qに対して、pq^2として表せると、集合の中でpが同じ数字が二つ以上あればだめです。pで出来る数字は2, 3, 5, 7それぞれが一回かけられるかないかの場合を全部数えたら2^4=16になります。つまりn=16です。

後は総積ですね。基本的にpq^2の形にできると言って、pは1, 2, 3, 5, 7, 2*3, 2*5, 2*7, 3*5, 3*7, 5*7, 2*3*5, 2*3*7, 2*5*7, 3*5*7, 2*3*5*7の中の一つで、それは絶対変わりません。問題はqですね。7!の約数の中の平方数は1, 4, 9, 16, 36, 144の六つがありますが、特定何個の数字にはq^2として使わないこともあります。例えば、16=2^4ですが、7!にも素因数2は四つしかないので、もう2を含んでいる要素には16や144はかけられません。まあそんな風にしたら、総積の総和が計算できますね。2^16*3^16*5^24*7^16です。残りは約数の数を計算すればばいいです。

F(20分、1ペナ)

見た目より難しい過ぎて面白かった問題。まずは(a_n+a_n+2)/(a_n+1)の値が一定なのでa_3、a_4だけ整数になればそのあとは問題ないです。

a_3を考えたら、まずkを3で割った余りが1になることを確認できます。同じようにして、a_4を割り出す時にはkを64で割った余りが9になるのを確認できます。中国の剰余定理によって、k=192a+73の形になればいいんです。

ただし、ここに罠が一つあります。kが3913だったら、a_nが負数になることが起きます。すなわち3913を抜いて、73から3721までの総和を計算します。私は初めてはこれを気づけなかったので1ペナしました😢

総平

元々無印が一番得意だったし、しかも幾何がほぼないセットだったので私にとっては本当に有利なセットでした。しかも今回は私がある程度知っている内容が出るなど、運がすごくついてくれました。だが、ペナが少なくなかったので順位がちょっと下がったのは惜しいですね。ペナが2つだけ減ると1位になってたかもしれませんので、それがちょっと惜しかったです。

でも今までの中の歴代最高の成績だったので嬉しいです！問題は全部面白かったですが、特に最後のFの接近が面白かったんです！

おまけ

もうすぐで入黄です！多分次回やその次にできると思います！これからも頑張ります！

AtCoder 入青しました！(+ユリ漫画のおすすめ)

こんにちは、リユナです！

AtCoderでやっと入青しました！

実は初めからパフォ2400ですぐ入水したので、入(何か)は今回が初めてで嬉しいです！もちろんこどふぉでは入橙の経験までありますが、基本的にこどふぉよりAtCoderのほうがレーティングを上がりにくいですので、AtCoderの青ならこどふぉの紫以上だと思います。

それで、今まで頑張って最近のARCで入青に成功しました！今までの入青のための旅を繰り返してみます！

1. 初めまして！AtCoder！と休み

私の初のAtCoderは2022年の11月でした。

確かに初のAtCoderだったんですが、ABCDを解いて、なぜかGを解いてしまって2400というとんでもないパフォーマンスが出ちゃって、すぐ入水しましたｗこれで「なるほど、AtCoderって実は易いかも？」とおもいましたが、私は大きいミスをしました。それは

Codeforcesとは違って、AtCoderは参加登録して受けないとレーティングがめちゃくちゃ下がるのを知ってませんでした！！！

すぐに墜落してしまい、私はやる気を全部失って水に復旧だけさせておいてアトコーダーから手を離しました。

大体こんな風にですね。

2. 復帰。入青を目指せ！

昨年の11月くらいに初めて日本の競プロerさんたちと繋がれて、そのあとからまたAtCoderを再開しました！

あの時まで「私はこどふぉ橙だから、すぐ入黄まで問題なさそう！」と思いましたが、実はそうでもなかったし、実力は競プロを休んだ何年間めっちゃ下がって、それにAtCoderはこどふぉとはレーティングのシステムがちょっと違うのを知らなかったんです。簡単に言うと、こどふぉは1、2回うまくやればすぐに上がって、1、2回ちょっとミスったらすごく下がりますが、AtCoderはその程度がはるかに少ないです。

それですぐ1200から1600まで行くのは無理でしたね。12月まで定期的に参加しながら、前の実力を取り戻そう！という感じで頑張りました。

まあこんな時期でしたね。

3. 4連敗。やる気消失

順調に行ける！と思ってましたが、すぐスランプが訪れてしまいました。12月から1月までずっとどんなコンテストをやっても問題があんまり解けなくて、確かに解ける問題でもミスって、4連敗までしました。あの頃私は短期留学の準備と祖母の突然のお葬式などで忙しかったりして、さらにめちゃくちゃだったと思います。

「やっぱり私はまだまだダメかな」と思いながらも、ずっと練習をやり続けて、シンガポールに到着しても競プロはやり続けました。この時期から「AtCoderが終わった後、Twitterのスペースで日本語で解説を読みながら復習する！」ということを始めましたが、競プロと日本語の勉強の両方にめっちゃ役に立ちました。

4. 復活。5連勝で入青！

シンガポールの生活に慣れたからは安定しているせいか、その間の練習が功を奏したのか、すぐにまた調子が良くなって、レーティングがすぐに上がり始めました！上がるスピードが本当すごいですね！

すぐ1400、1500を超えて、前のARC171で363位をしてやっと入青に成功しました！

5. 入青のために勉強したこと

・実は競プロで使われてるアルゴリズムだとほぼ全部読んでみたことくらいはあるので、今の私に必要なことは新しいアルゴリズムの勉強よりは、知ってることをよく実装して、問題をすぐ把握して解くのだと思ったので、今まではBOJの問題をゆっくり解きながら勉強しましたが、過去のABCやARCのバーチャルで本物のコンテストのように練習しました。

・AtCoderはACLという強すぎる武器があります。私はセグ木が苦手でしたが、ACLの力であの恐怖を克服しました！ACLの使用になれるように練習しました！

・私個人的には、大会で使われてるアルゴリズムの八割以上は「アルゴリズム自体がむずかしい」ではなく、よく知られたこと(動的計画法、二分探索、BFSとDFSなど)をどうやって使ったらいいか？をテストすることに近いと思います。特に、入青までは先に言及したことたちと、Union Find、累積和、imos法、セグ木の基本だけで解ける問題だけ解いてもできると思います。入黄以上は私もまだまだですから、確実に言えませんね😢

・自分の強みである「数学力」を使って、数学的な分析ができる問題はできる限り頑張って数学的に考えました。これは皆の武器は各々違いますから、自分が一番自信のあることをよりよく使えるようにすればいいと思います。

・入青のためには基本的な競プロ数学は知っておいたほうがいいです。場合の数とかは競プロでも定番で出てくるタイプなので、簡単なものから練習することをおすすめします。例えば、私が入青したARC171番のB番も、「順列のサイクル」と「順列の可能な場合の数」を探す問題であり、この点を把握していれば、計算さえ少しで済む簡単な問題ですが、分からないとかなり近寄りがたいと思います。

・復習は徹底的に！ 特に「解はほとんど分かった気がするが、結局ACに失敗した！」という問題があればなおさらです！私は日本語でスペースを進行しながら日本語の勉強を兼ねて復習しました。

6. おすすめのユリ漫画

めっちゃ関係なさそうですが、これいつかはやってみたかったので、突然ですがユリ漫画のおすすめをします。

6.1. やがて君になる

(東方プロジェクトの2次創作ではない)ユリ漫画の入門作品です！今は8巻で完結されました！

王道的な展開の少女漫画、ところがもうその対象が全部女性である。 こんな感じです。 予想した方もいると思いますが、あそこにいる黒髪学生会長のお姉ちゃんが、右側にいる背の低い学生にすっかりはまってしまいます。 感情の変化の描写や高校生が恋をしながらしそうな悩みなどについての描写が本当に細かく表現されていて大好きです！二人の物語が一体どのように進むのか気になる方はこちらへ！

そして、2018年作のアニメも本当すごいです。よかったらどうぞ。(私は舞台探訪までしました。)

6.2. ささやくように恋を唄う

やはり素敵な展開の学園物です。右の子が左のバンドの先輩に「一目ぼれしました！」(フォン的な意味)って言ったんですが、左の先輩はあの瞬間めっちゃ右の子にはまってしまい、それから始まる面白くてドキドキする漫画です。

なお、今年4月からアニメ化予定だから、今こそがこの漫画を見るのにちょうどいい時期です！

6.3. 私の百合はお仕事です!

名前がこうして初めてはちょっと心配しましたが、本当にユリ漫画です！

(多分マリみてのような)コンセプトカフェで働く高校生たちの話です！ここでのユリは「仕事」に近いですが、実は本当に心を抱いている人たちも相当で、なんとかかんとか。 アニメも面白いのでぜひ見てください！

6.4. 熱帯魚は雪に焦がれる

これは「めちゃくちゃユリ！」っていう感じではないんですが、穏やかだが確実に流れていく学園背景の漫画です。二人の高校生がお互いに力を合わせてぶつかりながらも成長していくほのかな叙事と細かい描写が気に入った作品です！

因みに9巻で完結作です！

6.5. リ'ドラフト(おまけ)

こちらは連載真っ最中の韓国のウェブトゥーンで、別に日本語の翻訳版があるわけではないと知っているので、とりあえずおまけとして入れるのですが、最近私が一番ハマっている作品の一つなので、ぜひ入れたかったです。

女子プロ野球が興行している世界で、万年有望株だった引退捕手の羅璘(ナ・リン)は、解散してしまった自分のチームとつぶれてしまった自分の選手生活を取り戻すためにタイムループを重ねるが。。。？

こちらも厳密に言えば直接的な恋愛描写があったりはしませんが、数多くの女性キャラクターの固い絆と感情線が絡み合って対立する姿、スポーツものがお好き、ということで（そして韓国語ができるなら😢）ぜひご覧になることをおすすめします！ もう一度言いますが、私は普段、韓国の漫画やウェブトゥーンをあまり見る方ではありませんが、これ一つには最近本当にハマっています！

以上でポストを終わります。 百合「漫画」だけでなく、ライトノベル原作などの作品も次回はもっと紹介したいと思います。 次回はたぶん私が入黄する頃ですが、その前にでももしおすすめしてもらいたいことがあればいつでも聞いてください。 ありがとうございました！

OMC205の後記

こんにちは、リユナです。

実は競プロ以外にも私は最近競技数学を始めました！日本のみんなと交流する前には全然存在すら知らなかったんですが、楽しそうで何回参戦し、今は堂々と青solverです！

。。。実はRatedたった四回でこのレーティングで、すぐ入黄まではできそうですｗ

それでは、後記始めます！

D(5分、FA)

まずは何か一つでもFAしようとしてDとEとFから読みました。Dが面白そうですぐ解き始めました。

典型的な場合の数の問題でした。6999までの数がちょうど1665個だったので、7000以上の最小値を探せば正解！

E(5分)

次はEでしたね。今学校で整数論を頑張って勉強してるので私にはもっと有利な問題でした。結局d(n)で出来る数は4, 9しかなかったんですね。これで何とか。素数を数えるのが一番面倒でしたｗ

A(1分、1ペナ)

次はFを考えたんですが、私にはあまりにも難しい幾何問題だったので少し考えてあきらめてAから順に解くことにしました。

見た瞬間解ける易い問題ですが、初めてはPの値を計算するのだと思って1ペナ😢

C(5分、1ペナ)

Cもユークリッドの互除法を使えば接近できます。二つの最大公約数は|100-k|ですし、結局99!-1は1から100までのすべての数に対してお互い素ですから、k=100の場合以外は全部できます。ただし、私は計算ミスで1ペナ、200を外して1ペナ合わせて2ペナしました😢

B(10分)

10分もかかる問題は絶対なかったんですが、私の下手な日本語の実力が一役しました。

こんなミスをして、めっちゃムズイ問題を創造して解いて、12/95*4^1/3じゃん？へえ？と思って、何かが違ってるのを気づいて、泣きながら本来の問題(創造した問題よりめっちゃ易い)を解きました🥲🥲

創造した問題は大体こんな感じですｗ

F(35分)

めちゃくちゃ私の弱いタイプの問題。円と接線の性質を利用して、角をよく求め、似た三角形を何とか探して、似比を利用してBから接点までの距離、Cから接点までの距離をそれぞれ求めて解けばいいのです。

プール自体を間違えて一度、計算ミスで一度ペナルティを積みました。

総評

4eとしては私にはめっちゃ難しかったです。もちろん大部分はBの翻訳ミスとFのせいですが。。。問題をもっと注意深く読んで、特に幾何の問題では図形に気を使って描かなければならないという教訓を得ました。

序盤の問題の難易度も適当で、後半の問題が全般的にとても面白かったので楽しいセットでした。 準備してくださった皆様、心より感謝申し上げます！

競プロの数学問題にアプローチするポイントは？

こんにちは。リユナと申します。競プロでは考えより数学問題が結構出ますよ。今日はこれらをどう接近して解くのか、これらをためにどう勉強したらいいのかについて話そうとします！

0.初めに

数学科出身の競技プログラマーの道: ②私が競プロを勉強した方法

こんにちは。リユナと申します。今日は前の記事から続いて、競プロの勉強法についてちょっとだけ話そうとします！

0. 初めに

こんなことを書く前に、私の履歴を先に少し紹介してこそ説得力が生まれると思います。

ーICPC Seoul Regional 2019 13位、2022 7位、2023 4位

ーKOI 2017本選 銅賞

ーBOJほぼ2000問題

ーsolved.ac ダイヤモンド１。全体219位

ーCodeforces max 2224(薄橙)今は滑れちゃってまだ青

ーAtCoderはまだ水

「自慢できるほどすごい実力者！ 」こういうわけではありませんが、それでもそれなりに頑張ってきましたし、自分の考えを書いてみようと思います。Atcoderアルゴリズム黄以上の方々は笑いながら見逃しても構いませんよ。

1. 私は競プロを始めました！

ようこそ！競プロの世界へ！

実はですね。「競プロは初めて！」っていう方々の中でもかなり実力差があると思います。例えばプログラミング自体が初めての方ともうプログラミングには慣れてますが競プロが初めての人はスタートラインが同じだと考えるのは難しいですね。

始める時に意外と引っかかる部分が入出力だと思います。 もちろんプログラミングを学ぶときに一番最初に学ぶ部分ですが、意外と競プロで使われる入力はいろいろあります。 おそらくすでに慣れている方々は、この部分を大きく考えていないので、さらにアドバイスを受けにくい部分でもあると思います。もしこれでなんか問題ができたら、ぜひ！ここからじゃんとして始めましょう！

その次は時間複雑度/空間複雑度の概念についてある程度理解することだと思います。 言語によって、どの言語はどの動作をするのに何秒かかるのか、どのようにコードが制限を超えないのか、そのような感覚がちょっとでも取れていることが重要です。

例えばですね。Nの大きさによってアルゴリズムの時間複雑度はほぼここまでができます。(絶対的なことではないです！)

<10 : O(N!)(全探索などできます。)

<25 : O(2^N)

<100 : O(N^3)

<5,000 : O(N^2)

<500,000 : O(NlogN)、たまにO(NsqrtN)まで

<5,000,000 : O(N)

<10^12 : O(sqrtN)

<10^18 : O(logN)

大体こんな感じです。

あと、言語はC+＋がおすすめです！私はPythonを中心にしていますが、長所と同じくらい様々な短所(速度など)を持つ言語なので、Pythonを通じて競技プログラミングをするなら、様々な最適化技法や時間をできるだけ減らす方法などについての理解が必須です。

2. 何をすればいいんですか？

自分の意見ですが、競プロに必要な能力は大きく二つだと思います。

1. 実装

2. (アルゴリズムなどの)知識

その二つのバランスを取りながら進むことが大切な部分だと思います。ちなみに、私は実装が弱点です。知識さえも特定の分野に重点を置いていますが、皆さんは私のように偏食しないでください。その為には知識として学んだアルゴリズムや資料構造は、一回でもできる限り自分の力で実装してみる練習をすることが大事だと思います。

2.1. まずは興味があることから！

何をするにせよ、最も重要なことは情熱と興味を失わないことですよ！モチベーションが死んでしまったら競プロをやる理由もなくなるなと思います。(あくまで私自身の意見です。)それをためには、まずは好きなことから始めることをお勧めします！

「あれ？そうやってもいい？偏食じゃない？」って思うかもしれませんが、偏食してもずっとやり続けるのが何もやらないのよりはもっといいです。多くの人は「やってみましょうか」で考えが止まり「やる！」につながることがよくありません。 スタートでもするなら、もう既に上位20%だと思います！

好きなスタイルの問題をたくさん解いてみて、悩んでいるうちに他の要素が混ざっている問題も発見できるようになります！たとえば、私は数学が大好きですが、数学的要素がありますが、他の資料構造（セグ木など）を使って時間の複雑さを減らさなければならない問題に接し、セグ木なども勉強し始めました。 そして漸化式を立てて解く問題は本質的に動的計画法の一種だということを後で知り、その部分も勉強し始めました。

2.2. 良問を解いてみましょう！

AOJやBOJなどのOJサイトではあらゆる問題に触れることができます。もちろん、すべての問題を解くことができればいいのですが、単純に多量の問題を解くよりも、考えさせ、良いチップを与える問題に接することが重要だと思います！

私のおすすめはこんなことたちがあります！

ーAtCoderの過去問

この文をお読みの方なら、おそらく高い確率でAtCoderでのレーティングを狙われると思います。 個人的な考えですが、韓国国内や海外の様々なプログラミング大会などをさまよっていましたが、アトコーダーは中でも確かに問題の質が保障される良いプラットフォームだと思いました。

でも大会は週に一回じゃないですか？ では、1週間に1回だけ競プロの練習ができるでしょうか？ もちろん違います。 過去の問題を解いてみると本当に役に立つと思います。私はAtCoder Problemsのようなところを愛用しています。

ーUSACO/KOI/JOI/COCIのような色んな国家の情報オリンピックの過去問

このような大会の基本的な特徴としては、少ない数の問題を与え、一人一人が長い間悩みながら解かなければならない問題だということです。自然に出題される問題は単純に難しいだけでなく、色々な方法で考える能力を育てる方だと思います。
また、このような有名大会の問題はインターネットに解説が着実に掲載されていることが多いです。 解説を見ながらどんなテクニックがあるのか、確実に自分のものにすることが大切だと思います。

KOIは韓国の情報オリンピックです。「負うた子より抱いた子」っていうでしょう。私が韓国人なのでKOIを推薦せざるを得ませんでした(笑)もちろん私もJOIの問題もたくさん解きましたから、どうか許してください。

COCIはクロアチアの大会ですが、かなりいいです。こちらの問題も練習に使えばいいなと思います。

ーcodeforcesはどんな感じか試してみる！

世界的に最も多く利用されている競プロサイトはおそらくcodeforcesの方です。 開催時期も不規則で、(韓国/日本標準時基準)夜11時35分という曖昧な時間に大会が開かれ、問題や文章のクオリティもギザギザしていますが、それでも良い問題もたくさんあります。しかし、全部英問ですので、英語の実力がちょっと要ります。もしかしてロシア語が上手いならそっちで説いても構いませんが、多分みんなそれでも英語の方が易いと思います。普通第1外国語が英語ですからね。

(あれ？私は確かに第1外国語が英語で第2外国語が日本語だったのに、なんでAtCoderの問題を全部英語じゃなくて日本語にして解いてる？)

ちなみに、AtCoderとcodeforcesは問題が若干スタイルが違います。 うーん、言葉で説明するのは難しいですが、どちらも何回か参加してみれば、何を言っているのか理解できることだと思います。（無責任すぎる）

AtCoderとCodeforcesの難易度を比べたら大体

Div 3<ABC<Div2<ARC=<Div1<<AGC

のような感じです。

2.3. 分からない場合には解説を！

「ええ？それじゃ実力に役に立つの？」って思うかもしれません。ある程度はその通りです。 しかし、これは「知っている範囲で解ける問題」の時の話であり、「全く知らない資料構造やアルゴリズム、テクニックが必要な問題」なら悩むのは時間の無駄に過ごすことです。

もちろん、10秒で答え見る天才競プロer！とかになろうという意味ではありません。 あなたは多分、知らない場合にも「あ、これどうにかすれば解けると思うが、時間の複雑さの制限にかかる。 これを最適化するにはどうすればいいの？」のような状況であることが多いと思います。 こんな考えに達したのであれば、これの方法を少し考えてみるのもいいでしょう。 実際、多くの場合、そこから出発して時間を徐々に減らしていくことが実際に解釈が正しいからです。

ある程度悩みが終わりました。 あるいは「最初から知らない概念の問題のようだ」と感じたら解説を探してみましょう。そして、何よりもそれを自分の手で実装してみて、自分のものにじゃんと習得すれば最高のシナリオですね。

2.4. 錯覚すんな！あなたはまだ理解してない！

どんな概念がどのように作動するのか知り、それを通じて簡単な問題を少し解いてから「わぁ！ 私はもうこれを理解しました！ これが出てくる問題はすべて解けるだろう！」と勘違いすることがよくあります。

全然違います。あなたはまだ理解してない、または原理は理解したが実戦で使いにくい状態である確率が高いです。なぜなら意外と簡単な理由です。 皆さんが別々に勉強する時とは違って、実際の大会で問題を解く時は「どのようなアルゴリズムで解かなければならないのか」教えてくれないからです。セグ木を例にとってみましょう。

1. セグ木の概念をどこかで読む。うーん、分かった！

2. どこで使うのかを勉強する。うーん、なるほどね？

3. 実装してみて何個の易いセグ木の問題を解いてみる。うーん。行ける行ける！

4. よっしゃ！もう私はセグ木を理解した！楽しい！

5. 実際の大会にこんな問題が出てくる。あれ？

6. 何もできず沈没.。

7. あとで誰かに「あれセグ木をめちゃくちゃおにゃららしたら解ける！」って聞く。

8. おかしいな。私は確かにセグ木の勉強をしてたのになぜ？

お気づきかと思いますが、実は私の実話を脚色したものです。(笑)多分私じゃなくてもみんな一回はこんな経験があると思います。それは先ほども言ったように当然まずは「それがセグ木を利用する問題だ！」と大会では教えてくれないからです。

しかし、それだけではありません。多分セグ木を初めて習って「あれはセグ木の問題ですよ」って言われてもそれをどう使うのかは一気に理解しにくいです。しかし、もしあなたがこんな問題を(*韓国語です)悩んでみたことがあるなら、もっと答えに接近しやすいとおもいます。簡単にネタばれをすると、セグ木のノードに1つだけ保存するのではなく、各区間の様々な要素(が何かは自分で考えてください。)を保存して、アップデートの時に次の段階に進んでも最大限問題が発生しないようにすることが核心です。

どうですか？応用することはできるでしょうか？

実はですね、私もセグ木のこと、大嫌いです。もし私がお母さんになったら、私の子供には「セグ木のような悪い子とは遊ばないで！」と教育します。(笑)それはなぜかと言ったら実装の難しさもありますが、応用の膨大さがもう一つの大きな原因でしょう。おそらく赤コーダーだとしても、競プロで使われるすべてのセグ木の応用を知っているとは思いません。

あなたが1、2回解いてみた問題、1、2回実装した資料構造だからといって、あなたがすべてを理解するわけではありません。 この点に気をつけながら、いつも初めて学ぶ気持ちで新しい問題を悩んで学べば、はるかに良い成果を得られると思います。

2.5. 数学もはっきり！

結局ですね、競プロにして数学の要素も大きい部分です。動的計画法の漸化式やグラフ理論、幾何や整数論などがあるでしょうね。これらの勉強もせめて競プロで使われるほどは勉強して置いたら役に立ちます。

もちろん、いくら私が数学が好きだとしても、競プロに数学が事実上すべてである問題が出るのがそんなに良いとは思いません。 それならAtCoderではなくOMCに出なければなりません。そして実際の大会でそれほどの問題が出ることもほとんどありません。 しかし、数学的な概念をある程度知っていれば、はるかに簡単に接近ができる問題や時間を減らしたりするなどの問題がかなりあり、これを簡単に解くためには数学の勉強も必須だと思います。例えばこれは私の好きな問題です。(英問です。)数学的な知識と二分探索という競プロのアルゴリズムが合わせて解ける問題です。 数学が必要ですが、プログラミングの存在も一役している問題だと言えますね。 しかし、基礎的な平面幾何学を知らなければ、最初から始めるのが難しいので、結局数学能力もたくさん必要です。

もちろん、この記事の本論はあくまでは競プロですから、数学だけの勉強に夢中するのもあまり良いことではないと思います。 そうするうちに私のようになりますし、数学科に行ってしまう悲劇(?)が起こるかもしれません。

2.6. 達人たちに聞いてみて、ライバルと一緒に成長しよう！

競プロのコミュニティには数多くの達人たちがいらっしゃいます。おそらくその中にはこの文を書いている私よりずっと実力者の方も多いと思います。そんな方々がどのように勉強してきたのか、どんな問題を解いたのかをそばで見守るのも勉強に大きく役立ちます。 また、本当にわからないことがあったら聞いていただければ、快く答えてくれると思います。 何よりもその「解けた！」の楽しさを共有したい人が多いですから。

もちろん、相手は無償で好意を寄せていることは覚えておくべきです。 手伝うことが絶対義務ではないですし、助けてもらったなら感謝の挨拶もしっかりした方がいいと思います。

そして、自分がどんな実力であれ、似たような実力の人々にも出会うことができます。 善意の競争をするライバルがいれば、自分と相手の両方がシナジー効果によって大きな成長を収めることができます。 もちろん勝負に執着しすぎるのは自重しなければなりませんが。（そうでなければ私のように大学卒業さえ延々と先送りする競プロ悪鬼になります。）

3. 終えて

あなたが競プロをしようとする理由はさまざまでしょう。私のように単純に興味や競争心のためかもしれませんし、就活の準備やプログラミングの実力を伸ばすためにもするかもしれません。しかし、その理由がどうであれ、長く悩んでいた問題をやっと解いた時の「解けた！」という喜びは同じだとと思います。

まあ、「競プロ無用論」や「早くやめとくほうがいいな」っていうことも、前にも言ったように両国のコミュニティでたくさん聞ける言葉ですが、結果がどうであれ、あなたが一歩ずつ前に進むために悩んだ時間は嘘ではないと思います。そのように情熱を注いだ経験がこれからの競プロや、じゃなければ他のどの分野でも、少しでも役に立つのではないかと私は思います！その道の上に立っているみんなを心から応援します！

読んでくださってありがとうございます！