初めまして。競技プログラミングの宣伝に来ました。
東工大附属のアドベントカレンダーDAY15
12/15/2023
この記事について
の15日目の記事です。感想は#豆腐アドカレで投稿してくれると嬉しいです。
完全に内輪向けで書いた記事なのでいろいろおかしかったりするかもしれませんが優しい目で見てください。
はじめに(自己紹介)
はじめましての方は、はじめまして。
豆腐𝕏界隈新人1年の YOSSHIPAOPAO と申します。
普段、 映像とか Web関係で遊んだりとか、あと競技プログラミングをしたりしてます。
創研の弟燕祭で クイズラリー用のWebサイト作ったりしました。 俺の好意で 今も一応遊べるのでぜひ、、、
新人の新人でなので、ほとんど誰も僕のこと知らんと思います。 もっと絡んできてくれるとうれしい！！！！！！！！！！魂の叫び！！！！！！！！！
競技プログラミングの強さはまだ全然くそ雑魚で AtCoder(後述)で緑
AJL(後述)で高１で37位
JOI(後述)二次予選の通過発表が記事の投稿日だそうです。
ドッキドキですよドッキドキ
競技プログラミングって？
競技プログラミングとは プログラミングを使って、時間内により多くの問題を解くことを競う競技です。
難しそう、、、って大体のひとが思うと思いますが、実際はそんなことないです。（そんなことあります）
競技プログラミングはゲームです。パズルゲームの感覚で解くことができます。 詳しくは後で語ります。
数学とかの論理的思考（？）が得意で、１年の「工業情報数理のプログラミングがある程度理解できてれば情報科の人でなくても楽しめると思います！！！
わからない人でも、最初のほうはやってることはそこまで難しくないので、ぜひやってみてください。
問題文を正しく読み取る国語力のほうが大事
例題
問題文の要約
ある村N人の年齢が与えられるから、N人それぞれすべての人の年齢の差の最大値を求めよ
例
A=3 4 5
回答：2 1 2
それぞれ|3-5|=2,|4-5|=1,|5-3|=2となる。
単純な解法
N人全員を見て、年齢の差を計算する。
コード例
for i in range(N):
ans = 0
for j in range(N):
ans= max(ans, abs(A[i]-A[j]))
print(ans)
ちょっと工夫した解法
その村の最大年齢と最小年齢との差を求めるだけでいい。
コード例
maxA = max(A)
minA = min(A)
for i in range(N):
ans = 0
ans=max(ans, abs(maxA-A[i]))
ans=max(ans, abs(minA-A[i]))
print(ans)
こんな風に単純な解法だとTLE(時間制限超過)になってしまうことがあります。
※コンピューターは1秒間に10^8~9回程度の計算しかできない
そこで、計算量を減らす工夫をします。
主にこの、計算量を減らす工夫が競技プログラミングの醍醐味です。
実際に始めるとなると 、 日本だと AtCoder、世界最高峰の競技プログラミングサイトです。
ここでは AtCoder Junior League(AJL)というものをやってます！！！
中学や高校ごとにチーム分けして普段のコンテストの成績で競ってます。
われらが東京工業大学科学技術高等学校は53位(12/12現在)...ほとんど僕だけです、、、
今年度はもう数回しかありませんが、来年度もしあったら一緒にやってくれる人募集中！
あと1000人に到達したら現地開催の大会ができるみたいな話を聞いたので今からでも！！！！！！
https://twitter.com/atcoder/status/1734059295308931239
や、高校２年生以下限定ですが 情報オリンピック(JOI)があります。
ほかにも、東工大主催の Super Con というスパコンを使った競技プログラミング大会や、
海外だと、 Codeforcesや TopCoder、 IOI(JOIの世界大会版 )などがあります。
メリット？
とーふ生はどーせ現金な性格なので報酬がないと始めることはないでしょう。
そんな人のためにメリットを突きつけて始めさせてやろうかと思います。
推薦に使える！！！(JOI/JOIG)
詳しくは この記事 を見ればわかりますが情報オリンピックの成績が推薦の条件（や評価基準の一つ）になってる大学が多々あります！！！！
ほかにも例えば、われらが東工大は Super Conを主催してて、それが総合型選抜に使えると公式で言ってたり、、、
就職に使える！！！(AtCoder)
気が早い気もしますが就職にも使えるそうです！
AtCoderは競技プログラミングの力（アルゴリズムとか）を就職に使えるような環境を作ってくれてます。
AtCoder Jobsというサイトで、企業に応募することができたり、 企業がAtCoderのコンテストを開催していたりします。
お金になる！！！
トップ中のトップの人になると大会で賞金がもらえたりします。
トップ中のトップの人はね、、、
楽しい！！！
やっぱゲームは楽しいですよね！！！！！！！
人生幸せ万々歳
ほかにも情報系の学部に行くなら多分アルゴリズムとかデータ構造の予習になるんじゃないですか、そこら辺の一般高校生なので知りませんけど。
参考?: https://info.atcoder.jp/utilize/jobs/rating-business-impact
何が楽しい？
先ほど競技プログラミングはパズルゲームの感覚で解くことができると言いました。
これ、どういうことかというと、さっきの例題のように、問題を解くことだけで見たらそこまで難しくないのですが、
もっと効率的に解くというのが競技プログラミングの醍醐味です。
そのために、パズルのパーツアルゴリズムを覚えて、それを組み合わせて問題を解いていきます。
これがまあ、楽しいんですよね。
パーツ紹介のコーナー
二分探査
二分探査とは、ソートされた配列に対して、ある値が存在するかどうか(ある値以下の値どこまであるか)を探索するアルゴリズムです。
例えば、[1, 2, 3, 4, 5, 6, 7, 8, 9]という配列に対して、3以下の値がどこまであるか、つまり3以下の値が何個あるかを調べます。
二分探査は値の境界が存在する範囲をだんだんと狭めていくことで、境界を求めることができます。
灰色を未確定、赤色を値以上確定、青色を値未満確定として 実際にシミュレーションしてみると、
よって、3以下の値は3個あることがわかります。（実際の挙動とは少し違いますが、イメージはこんな感じです）
例題
要約すると、xxxxxoooooやxxoxoxxxooxoのような文字列でxoやoxのように隣り合わせになっている場所を一つでも見つける問題。
ただし、直接文字列を見ることはできず、20回までn文字目がoかxかを聞くことができる。
また、1文字目はx、最後の文字はoであることが保証されている。
さらに、文字列は最大200000文字まである。
解法
200000を20回で？？？？となるが、これは2分探査の考えで解くことができる。
xをFalse、oをTrueとして、実際にシュミレーションしてみると、
以上、質問3回で答えを求めることがで来ましたね。
そしてこれ、さっきと同じことしてますよね。
こんな感じで、二分探査は長さNの配列に対して、log2(N)で値を求めることができます。
200000の配列に対しても、log2(200000)は約17.61なので、18回で答えを求めることができます。
こんな感じで、一見違うような問題にこんな感じでパーツを当てはめることができます。
これが楽しいんですよ。
DP
DPとは、動的計画法のことです。
動的計画法とは、配列にここまでの答えを保存していって、それを使って次の答えを求めるアルゴリズムです。
実際に、 Frog 1という問題を解いてみましょう。
問題文の要約
N個の足場があり、カエルが足場1からスタートして、足場Nまで行きたい。
カエルはすぐ横の足場に移動するか、一つ飛ばして移動することができる。
これを繰り返して、上下運動を最小にしてNまで行きたい。
解法
例えば足場3から4に行くとき、足場1=>2=>3=>4というルートと、足場1=>3=>4というルートがある。
ただ、足場1=>2=>3=>4というルートは、足場1=>3=>4というルートよりも上下運動が多いため、考える必要がない。
そのため、dpという配列に、3まで到達するための最小のコストを保存していく。
こんな感じでシミュレーションしていくと、
このように、コスト4で到達できました。
もうちょっと例題
要約：(??) (?みたいな文字列の?を(か)に置き換えて、正しい括弧列にする方法の数を求めよ
これだと()()()や(())()みたいなのが正しい括弧列になる。
これ二文字目の時点で答え二つあるじゃんと思うかもしれませんが、DPの強みはこれからです。
答えの保存の仕方を少し工夫してみましょう。
dp[i][j]にi文字目まで確定させた状態で、j個の開き括弧があるような括弧列の数を保存する。
jは"("の場合空き括弧が増えるので+1、")"の場合減るので-1となる。
"?"の時は、"("と")"の両方の場合を考えるので+1と-1の両方を考える。
これを実際にシミュレーションしてみると、
最後の文字の時点で空き括弧が0個であるような物の数が答えとなるので、
正しい括弧文字列は2個と求められました。
難しいDPはもっとすごいことしてくるので覚悟が必要です。
ちなみに、えびまさんがもっとわかりやすく解説してるの動画もあるのでそちらもどうぞ、、、
終わりに
豆腐生ってこういう専門の大会とかそういうのに出てる人が意外と少ない（気がするだけ？）ので、自分がやってる競技プロ仲間探しと宣伝に記事を書いてみました。
僕はくそ雑魚ですが教えられることがあったら教えるから、気軽に声をかけていいよ。
というかみんなと仲良くなりたい～～～ もっと絡んで～～～～
～～以下没～～
～豆腐幼稚園にて～
え？ストーブが壊れた！？
仕方ないなぁ～そこに名札があるでしょ
これをこうして、えいっ
📛
TOFU ON FIRE📛
ちなみに豆腐生のレスバのエネルギーで燃えてます。あったかい
いやごめん