naoppyの日記

自分が欲しいなと思った記事を書きます。

あたまの体操 楕円の軸並行矩形

傾いている楕円の外接軸並行矩形を計算するのは大変な気がする。 そこで、外接という条件を緩くして楕円を内包する軸並行矩形を計算することを考える。

まず、x2/a2+y2/b2=1がθ傾いている楕円の外接矩形は非常に簡単に、2a x 2bの矩形がθ (0<=θ<=pi/2) 傾いているもので与えられる。

傾いている楕円の外接矩形

そして、この矩形に外接する軸並行矩形を計算する。簡単な行列計算で、外接する軸並行矩形の一番上のy座標は y=asinθ+bcosθ、一番右のx座標は x=acosθ+bsinθ になる。

点対称なので、これで終わりだ。 次にこうして得られた軸並行矩形の評価に移る。面積をどれだけの比率で近似できているかを考える。

まず、楕円を矩形で近似した部分は楕円の面積が pi a b であるのに対し、矩形の面積が 4ab なので、比率は pi/4 である。 次に傾いた矩形を軸並行矩形に近似した部分は 矩形の面積 4ab に対し、軸並行矩形の面積が 4(acosθ+bsinθ)(asinθ+bcosθ) なので比率は ab / {sinθcosθ(a2+b2) + ab} となる。 これはθ=0, pi/2 で最大値 1 をとり、θ=pi/4 で最小値 2ab/(a+b)2 をとる。これがよろしくない。a=bのときは1/2で済むが、|a-b|が大きくなればなるほど、悪化してしまう。 まとめて、楕円からすると、比率にして (pi/4) * ab / {sinθcosθ(a2+b2) + ab} となる。

aとbの差がそこまで大きくない、傾きの小さい楕円ならいいが、45度に近い楕円だとa=bでも円より1/2の面積率になり、a<<bの極限では0になってしまう。

では次の方法、直接外接する軸並行矩形を楕円から計算することを考えるが、これはまだ考えてないので誰か考えてみてください。

円と軸並行矩形の当たり判定 (Circle to AABB)

先に結論を書きます。 円を中心が (x, y) 半径 r で軸並行矩形の中心が (cx, cy) 横幅が w 縦幅が h とすると、

bool HitTestCircle2AABB(float x, float y, float r, float cx, float cy, float h, float w)
{
    float dx = std::max(0.f, std::abs(x - cx) - w);
    float dy = std::max(0.f, std::abs(y - cy) - h);
    return dx * dx + dy * dy <= r * r;
}

導出

アイデア1

idea1

赤の長方形+青の長方形+緑の円4つで判定する

尤も単純な方法。円の個数が多いので効率が悪い。 図形の左右及び上下の対称性に注目して効率化を図る。 絶対値をとることで右上のみに限定させると以下が得られる。

アイデア1 (改良ver)

idea1(improved)

これで赤い長方形+青い長方形+緑の円1つになった。

アイデア1はこれ以上改良できない(たぶん...)

では、アイデア2を紹介する。

アイデア2

円の中心から 最も近い軸並行矩形の外周との距離を求めて、半径以内ならOK。とする。

idea2

この最近傍点からの距離って求めるのが難しそうな気がしたんですけど（僕だけ？凸射影みたいなのって大変そうなイメージがった）流石に図形が単純なので、最近傍点やそこへの距離は簡単に求まります。

例えば x軸での最近傍点までの距離 dx は

max(max(0, x - (cx + w)), max(0, -x + (cx - w)));

で求まります。 dyも同様に計算して、 dx2+dy2<=r2の判定だけで終わります。

アイデア2 (改良)

maxは可換で結合則も満たす(可換半群)ので順番を入れ替えて

float dx = max(0, max(x - (cx + w), -x + (cx - w)));

max(x - (cx + w), -x + (cx - w)) という部分は加減算が4回あるわけですが、第一引数と第二引数の符号の不変部分と反転部分に分けると (x - cx) は反転して、-w は不変であることがわかります。 よって、

float hoge = x - cx;
float dx = max(0, max(hoge - w, -hoge - w));

とすれば加減算を1回減らせますね。 さらに、max(z1 + w, z2 + w) == max(z1, z2) + w より

float hoge = x - cx;
float dx = max(0, max(hoge, -hoge) - w);

までできます。 max(z1, -z1) == abs(z1) より、

float dx = max(0, abs(x-cx)-w)

までできました！もちろんこれはアイデア1の改良と同じく対称性を利用しただけなので最初からこれ思いついとけよって話ですね。何を長々と解説してるんだという話ですが、言い訳をさせてください。 最初私は min(max(0, ...), max(0, ...)) だと思い込んでいて、その場合の式変形はこのプロセスを通らないとかなり難しいです。そして意気揚々とこの記事を書いたところ、max(max(0, ...), max(0, ...))であることに気付いて全部修正した結果、こんな駄文を書き連ねることになってしまいました。かなしいね。 最後まで読んでいただきありがとうございます。

おまけというか、軸並行矩形(AABB)の実現の2種類についてちょっと触れておきます。 AABBを中心と幅で持つ方法と、対角線上の2点の座標(右上と左下)をもつ方法があると思います。 前者はオブジェクトが頻繁に動く際、中心位置のみの更新なので楽です。 後者の場合、直感的にオブジェクトを配置することができますが、移動がある場合2点とも更新なので面倒です。 当たり判定処理に関してはほぼ変わりません。 個人的には中心と幅を持つ方がいいかなと思います。

クーポンコレクター問題を解き明かす！

この記事は 物工/計数 Advent Calendar 2023 - Adventar の一部として書かれたものです。 数式部分に興味のある方は前半を飛ばしてください。

導入

ずんどうねこって知ってますか？

ずんどうねこ

この可愛すぎるキャラクターはずんどうねこと言い、とっとさんのTwitterで毎日更新されています！ 僕はずんどうねこを3年以上前からかなり推しているのですが、今年とても嬉しいことが起こりました。

なんと、かわいすぎるラバーストラップ（全６種）が一回300円のガチャガチャに登場したんです！！！！！！！！ これは集めるしかない！！！と僕と彼女は池袋へ繰り出しました。

ご飯屋さんの待ち時間に、全６種をコンプリートするのにかかるお金の期待値について考えていました。 これはクーポンコレクター問題です。 クーポンコレクター問題とは、N種類あるクーポンを全てコンプリートするために、何回購入しないといけないか？という問題です。 詳しい定式化は後程します。 かかるお金はコンプリートするのにかかる回数の期待値x300円で出せますね。 ご飯屋さんの待ち時間の間に頭の中で解けて、期待回数は14.7回、かかるお金の期待値は、4410円となります。 たった6個のガチャでも15回程度かかるんだ…ｶﾞﾁｬｺﾜｲってなりつつ、次のアイデアが湧いてきました。

「彼女と来てるんだから、お互いの出なかった分を分け合えば二人の期待回数の和は減るのでは？」というものです。 これはクーポンコレクター問題の拡張版で、N種類のクーポンをmセット集めるときの回数についての問題となります。 これはマルコフ連鎖で解けそうだなというところまで考察しましたが、その時は具体的な解を得られませんでした。

ここまで気持ちを準備して、いざガチャガチャ屋にいくと…

売り切れてました～～～～～～～～～～～～～～～～～うわあああああああああああああああああああああ

後でクーポンコレクター問題について調べていくと、確率論の基礎的な内容が詰まったおもしろい話だったのでここにまとめる次第です。

大まかな定式化

ここから数学パートです。

クーポンコレクター問題とは、 N 種類のクーポンがそれぞれ、確率 p_i で出現するときに、クーポンをコンプリートするまでに買う必要のある回数の確率や期待値について考える問題です。 クーポンは以下、 {1, 2, \dots, N} としてよく、 \sum_{i=1}^N p_i = 1 です。 クーポン列が与えられるときにいくつまで見れば全て出現するかと言い換えることもできますね。

このクーポンコレクター問題はいくつかの種類にわけられます。

  • すべての確率が等確率の場合
  • 確率がそれぞれ異なる場合 (レアなクーポンがある場合)

また、問題の拡張として

  • クーポンがいくつかのまとまりで来る場合
  • クーポンを1セットではなくmセット揃える場合

などが考えられます。 以下ではそれぞれの場合について、期待値の証明などを与えます。

1セット、等確率の場合

X を確率変数で、1セット揃うまでの購入回数とします。 X_i を確率変数で、 i-1 種類揃っている状態で、 i 種類揃うまでの購入回数とします。

明らかに X = X_1 + X_2 + \cdots + X_N ですね。

各 X_i は独立なのは明らかです。 X_i について、 i 種類目を得る確率は \frac{N-i+1}{N} ですので、 X_i はパラメータ \frac{N-i+1}{N} の幾何分布に従います。

よって、

E[X] = E[X_1] + E[X_2] + \cdots + E[X_n] \\ = 1 + \frac{N}{N-1} + \frac{N}{N-2} + \cdots + \frac{N}{1} \\ = N \left(\sum_{i=1}^N \frac{1}{i}\right)

となります。

他、マルコフ連鎖を用いても証明できますが、その場合方程式を解くのが面倒なのでこちらが楽です。

その他の話題として、 \sum_{i=1}^N = \frac{1}{i} は N \rightarrow \infty の時、

\sum_{i=1}^N \frac{1}{i} = \log (N) + \gamma + \frac{1}{2N} + O\left(\frac{1}{N^2}\right)

となるので、

E[X] = N\log (N) + N\gamma + \frac{1}{2} + O\left(\frac{1}{N}\right) \qquad (n \rightarrow \infty)

1セット、等確率ではない場合

X_i を確率変数で、種類 i 番目のクーポンを最初に得るまでに必要な購入回数とします。 X を確率変数で、すべてのクーポンをそろえるのに必要な購入回数とします。 明らかに、 X = \max (X_1, X_2, \dots, X_N)ですね。 また、 X_i はパラメータ p_i の幾何分布に従います。 今問題なのは、各 X_i は独立ではないということです。何故なら、例えば X_i = 1 なら最初にクーポン i が出たということなので、他の X_j は1になりえないからです。 よってmaxを簡単にとれません。 ここで重要な考察として、 i \neq j のとき \min(X_i, X_j) は パラメータ p_i + p_j の幾何分布に従う確率変数になります。3つ以上のminも同様になります。

ここで、Maximum-minimums identityという恒等式を紹介します。確率変数 X_i について、以下の恒等式が成り立ちます。

\max (X_1, X_2, \dots, X_n) = \sum_{i=1}^N X_i - \sum_{i < j} \min(X_i, X_j) + \sum_{i < j < k} \min(X_i, X_j, X_k) + \dots + (-1)^{n+1} \min(X_1, X_2, \dots, X_n)

これ知りませんでした…。これを使って、maxをminに書き換えます。それぞれのminは幾何分布に従うことは説明しました。これでmaxの期待値をminを使って計算できますね！

E[\max (X_1, X_2, \dots, X_n)] = \sum_{i=1}^N E[X_i] - \sum_{i < j} E[\min(X_i, X_j)]+ \sum_{i < j < k} E[\min(X_i, X_j, X_k)] - \dots + (-1)^{n+1}E[ \min(X_1, X_2, \dots, X_n)]\\ = \sum_i \frac{1}{p_i} - \sum_{i < j} \frac{1}{p_i + p_j} + \sum_{i < j < k} \frac{1}{p_i + p_j + p_k} - \dots + (-1)^{n+1} \frac{1}{p_1 + p_2 + \cdots + p_N}

まだ汚いですね。ここからさらに変形していきます。

\int_0^\infty e^{-px} dx = \frac{1}{p}

と

1 - \prod_{i=1}^N (1 - e^{-p_i x}) = \sum_i e^{-p_i x} - \sum_{i < j} e^{-(p_i + p_j)x} + \cdots + (-1)^{N+1} e^{-(p_1 + p_2 + \cdots + p_N)x}

を使って

E[X] = \int_0^\infty \left( 1 - \prod_{i=1}^N (1 - e^{-p_i x}) \right) dx

となります。

これも、天下り的に指数分布とポアソン分布を使う天才的な証明もあるようなのですが、そちらは参考文献をご覧ください。

mセット、等確率の場合

m=2, N=6の場合が導入で述べた状況に相当しますね。

p_i を i 個購入したがmセット揃わない確率とします。 X を確率変数で、mセット揃うのに必要な購入数とします。

すると、

1 - \prod_{i=1}^N (1 - e^{-p_i x}) = \sum_i e^{-p_i x} - \sum_{i < j} e^{-(p_i + p_j)x} + \cdots + (-1)^{N+1} e^{-(p_1 + p_2 + \cdots + p_N)x}

を使って

E[X] = \sum_{i=1}^\infty i (p_{i-1} - p_i) = \sum_{i=0}^\infty p_i

という関係が成り立ちます。

では、 i 個購入したがmセット揃わない確率である p_i はどう表せるでしょうか？ p_i = i 個買ったが、どれかがmセットに満たない場合の数 / Ni ですね。

i 個買ったが、どれかがmセットに満たない場合の数は、

(x_1 + x_2 + \cdots + x_n)^i

の展開した後、どれかの指数の肩にm以上の数が乗っている項を消したあと、すべての x_i に1をいれたもの。といえます。

後程の議論を楽にするために、以下に定義する記号を使います。

\{P(x_1, x_2, \dots, x_n)\}

これは多項式Pから全ての i について、 x_i の指数部分がm乗を超えるものを除いた多項式のことを表すことにします。

さて、 S_m(t) を以下で定義します。

S_m(t) = \sum_{k=0}^{m-1} \frac{t^k}{k!}

そして、以下の式を考えます。

F = e^{x_1+x_2+\cdots+x_n} - (e^{x_1} - S_m(x_1) \times \cdots \times (e^{x_N} - S_m(x_N))

Fを x_i の多項式だと思うと、Fは x_i 全ての指数の肩がm以上の項を含まないことがわかります。しかし、Fはいくつかの i について x_i のm乗を超える項を含んでいます。 つまり、

F = \{e^{x_1+x_2+\cdots+x_n}\} = \sum_{i=0}^\infty \frac{\{(x_1+x_2+\cdots+x_n)^i\}}{i!}

ですね。

最後のパーツとして、以下の式が成り立ちます。

N \int_0^\infty \frac{t^i}{i!}e^{-Nt} dt = \frac{1}{N^i}

これは部分積分して漸化式を解くと正しいことを示せます。

これらを用いて、

E[X] = \sum_{i=0}^\infty p_i = \sum_{i=0}^\infty \frac{\{(x_1+x_2+\cdots+x_N)^i\}}{N^i} \\ = \sum_{i=0}^\infty \left( \{(x_1+x_2+\cdots+x_N)^i\} N \int_0^\infty \frac{t^i}{i!} e^{-Nt} dt \right) \\ = N \int_0^\infty \sum_{i=0}^\infty \left( \{(x_1+x_2+\cdots+x_N)^i\} \frac{t^i}{i!} \right) e^{-Nt} dt \\ = N \int_0^\infty \left[ e^{tx_1+tx_2+\cdots+tx_n} - (e^{tx_1} - S_m(tx_1) \times \cdots \times (e^{tx_N} - S_m(tx_N)) \right] e^{-Nt} dt

さて、すべての x_i に1をいれることを思い出して、1をいれて評価します。

E[X] = N \int_0^\infty \left[ 1 - (1 - S_m(t)e^{-t})^N \right] dt

が得られました！

これが答えなのですが、これだとどれくらい大きいかわかりずらいので、 N \rightarrow \infty で評価をすると、 E[X = N \left( \log(N) + (m-1)\log \log (N) + C_m + o(1) \right)] となるらしいです。 逆に、 m \rightarrow \infty で評価をすると mN になります。これは直感的ですね！

では最後に具体的に計算してみます。導入で述べたN=6, m=2の場合だと、24.1回。一人当たりだと12回なので、N=6, m=1の場合の14.7回よりかなり改善しています。一人800円ほど安く済む計算になりました。

その他、マルコフ連鎖でも解けますが、m, Nが小さいときじゃないと難しそう…。

ここまで読んでくれた人、ありがとう！

参考文献

https://mat.uab.cat/matmat_antiga/PDFv2014/v2014n02.pdf

TSGCTF Write-Up

TSGCTF2023に参加してました。僕と学科のCTF初心者の方と出て32位でした！ １位や３位の方はソロらしく、流石ですね。

問題の難易度が思ったより高く、Cryptoをメインに解いてました。CTF楽しいね。

Upside-Down Cake (Web, Beginner, easy)

1000文字以上の回文を送信すればいいのだが、送信できるデータ量に制限がある。回文チェックはnodejsで行われており、javascriptのガバガバ仕様を使って回文判定をすり抜ける。

const palindrome = {
    length: "1000",
    0: "a",
    999: "a"
}
const res = await fetch('/', {
    method: 'POST',
    headers: {'Content-Type': 'application/json'},
    body: JSON.stringify({palindrome}),
});
await res.text();  // TSGCTF{pilchards_are_gazing_stars_which_are_very_far_away}

Unique Flag (Crypto, easy)

flagが33文字でuniqueであることがわかっている。TSGCTF{}で8文字わかっているので、25文字がわからない。 処理を読むと25文字の中で隣接している文字の組の候補がわかる。 uniqueかつ隣接している文字の組の候補を使って25文字で作れる文字列を全部列挙して、人力でflagっぽいのを見つけた。

TSGCTF{OK,IsTHi5A_un1qUe-flag?XD}

Graffiti in the Fog (Misc, easy)

u_i, v_iが知りたいのだが、処理を読むと、u_i * vecs[0] + v_i * vecs[1] * 5 + (-250~250) * vecs[2] + (-250~250) * vecs[3]と4次元直交ベクトルvecsを使った和になっている。 よって主成分分析(PCA)で分離してやればu_i, v_iがでてくる。

ところで画像のUがx, Vがyに対応するのが普通なのにこの問題は逆になってた。そんな流派あるんか…？ 授業でPCA習ったばっかだったので進研ゼミでやったとこだあああになった。

flag
読みにくいけど、TSGCTF{CARRY_A_FLASHLIGHT_WHEN_YOU_WALK_AT_NIGHT}

この問題はkeymoonの次に解いたので、2番目に解けた。全体で5人しか解いてなかったのでｳﾚｼｲ。

感想とか

Converter, Converter2(Pwn)は解法は全部わかったんだけど具体的にどれだけメモリアドレスを動かしてNULL文字を破壊すればいいのかがわからず解けなかった、くやしい… Rev, Pwnあたりはツールの使い方がわからず全然解けなかった。 Q??odeというQRCodeの問題のfirst-bloodを狙ったけど無理だった、結局keymoonだけが解いててちいかわになっちゃった。 他のcrypto問はメンバーの方が解いてくれました。

また参加してぇ～！次回はメンバーをもうちょっと集めてわいわいしたい。

【令和四年度】阪大基礎工 編入試験 まとめ

編入

令和四年度、大阪大学基礎工学部 情報科学科 ソフトウェア科学コースの編入試験を受験しました。 前日～試験当日について書いていきます。

今年は計算機コースを6名、ソフトウェアコースを10名が受験していました。 明石高専からは内6人が受験しました。

受験の経緯

明石高専からは毎年多くの人が大阪大学を受験し合格しています。 また、東大は流石に難しすぎで、京大は化学を受験しなければいけないため、阪大に決めました。

基礎工学部と工学部はやってる内容的に基礎工学部にしました。

前日

阪大へは阪急蛍池駅からモノレールで1駅なので蛍池の東横インに泊まりました。 しかし蛍池から10分以上歩かなければならなかったため最悪でした。

ホテルを取るなら大阪梅田駅周辺のホテルを取って、当日にがっつり阪急で阪大付近の駅まで行くのが良さそうです。

筆記試験

一日目は筆記試験です。日程は以下の通りです。

f:id:naoppy_ac:20210712160605p:plain
阪大基礎工テスト日程

基礎工は受験するコースや学科によって、専門科目の有無や物理の問題数が変わるという特徴があります。

ソフトウェアと計算機コースは今年から専門科目が無くなりました。

英語

大問1 和訳 簡単でした。

大問2 長文読解 難単語の意味を4択で答える問題が多く、失敗しました…。単語力が足りませんでした。

大問3 英作 破滅しました。

数学

数学は2時間も与えられているのですが、3問しかありません。また、それらも小問数が2つや3つなので一つ一つに時間を使えます。

大問1 微分方程式

初期値が与えられたベルヌーイ型方程式を解く。そのあとx->infの極限での値を求めるのと、ある与えられた条件の時に単調関数であることを示す問題でした。

ベルヌーイ型方程式ではなくただの変数分離形だと考えて部分分数分解で解いている人も多かったです。大問1はとても簡単でした。全員10割

大問2 行列

(1) 行列Aがxy平面のθ回転行列、行列Bがzx平面でのφ回転行列であるとき、行列C=ABの行列式の値を求めよ。

明らかに1です。

(2) Cの全ての固有値とその絶対値を求めよ。

まさかの、全て愚直に丁寧丁寧丁寧に計算するだけという問題がでました。流石に綺麗な解き方があるやろと考えてしまい、解けませんでした。

ただ、固有値の絶対値が1以外にありえないことは示せたので部分点でなんとか…という感じです。 阪大基礎工らしからぬ、変な問題でした。また、小問が2つしかなかったのも悲しかったです。

大問3 確率

確率pで表が出るコインAと確率(1-p)で表がでるコインBに関しての問題がでました。

(1) AとBを同時に投げるとき、両方表の確率

(2) AかBあるいはその両方を使って、選手の権利を与える抽選を行う公平な方法を考案せよ。

これが難しかったです。とりあえず書きましたが、部分点がどれだけもらえるのかわかりません。

(3) 復元抽出でAとBのどちらかをランダムに選んでn回投げて、全部表だったときに、投げたコインが全てAであった確率。

ただのベイズの定理です。

総評として、数学は簡単な問題と難しい問題がはっきりと分かれており、しょうもない大問2-2で差がついてしまうというゴミ回でした。

物理

大問1 剛体振子と、上に滑車がついた場合の剛体振子

上に滑車がついた場合の剛体振子の運動が難しすぎてがっつり破滅しました。どうやら名門の森シリーズのやつにあったらしい？です。

大問2 交流発電機？

コイルを回転させてできる電界を求めるやつ…なのかな？解いていないのでわかりません。

大問3 熱力学 気体運動論とスターリングエンジン

大問の中で更に大きく2つに分かれており、前者は気体運動論に従って分子1個あたりのエネルギーを計算し、単原子理想気体の定積モル比熱などを計算しました。 また、二原子理想気体の自由度についても軽く聞かれました。

後者はスターリングエンジンの効率などに関する計算でした。効率の定義を忘れていたのですが、効率の定義はこうであってほしいなというように考えて書いたら合ってたみたいです。

さらに、スターリングエンジンの定積変化の部分に使う熱を再利用する場合に効率がどうなるかという問題がでました。（カルノーサイクルの効率と一致し、理論的最高になる。）

熱力学は10割いけました。

面接

面接はコースごとに行われます。計算機コースとソフトウェアコースは同じような場所で面接を受けましたが、一応面接室などは別でした。

各コース名前順に面接が始まります、聞かれたことは

  • 志望理由
  • どんな研究に興味があるか

だけでした…。その後すぐに口頭試問が始まり、8分以内に大問1と、大問2の3つの問題から1つを選択して解答せよとのことでした。

大問1

二分探索と線形探索の計算量やアルゴリズムについて説明せよ。

にぶたんは流石にできました。

大問2-1

ネットワークプロトコルの階層構造の利点と欠点について説明せよ。

大問2-2

プロセッサの発展と今後の展望について思うところを述べよ。(これは問題文覚えてないので怪しいです)

大問2-3

公開鍵暗号についての概要説明と簡単な実例の提示をせよ。

私は大問2-1を選択しました。とりあえずOSI参照モデルを全部書いて説明したあと、利点と欠点について適当に考えて言いました。 まあ悪くはなかったと思います。

結果

不合格でした…。明石高専から計算機コースとソフトウェアコースを受験した6人中、2人が受かっていました。 彼らは東大合格者です。

クラスからは基礎工に9人が出願しましたが、結局その2人以外に合格者はおらず、本命の人は誰一人受かっていませんでした。

編入は魔境。

まとめ

今年の阪大基礎工は数学の問題がとにかく微妙で大変でした。また、力学も難しかったです。

面接と調査書は満点のはずなので、そこの比重はかなり軽いと思われます。

悔しい～～～～～～～～～～～～～～～～～～～～！！！！！！！！！！！！！！！！！

【令和四年度】東京大学編入試験 まとめ

編入

令和4年度東京大学工学部 計数工学科を志望して受験してきました。 勉強法などではなく主に前日〜受験までの流れを書いて行こうと思います。

簡単な自己紹介

明石高専電気情報工学科、TOEIC875点、プログラミングとか好き

受験の経緯

4年次の夏休みから、大阪大学基礎工学部 情報科学科を志望して勉強していました。

5年生の4月末ぐらいに、「俺って東大行けるんじゃね？WowWow」という気持ちが湧き上がり、急いで過去問請求をしました。

過去問は難しかったので受験までに3年分と少ししか解けませんでしたが、傾向を知るには充分でした。

前日

フォーレスト本郷に泊まりました。東大編入受験者のほとんどがこの宿と言ってもいいぐらい高専生だらけでした。

東大の正門に近く、アメニティや冷房、机や照明もしっかりしていたのでおススメです。ただ、周りの駅からは遠いので行き帰りは少し大変です。

一次試験

受験科目などは以下の通りで、英語、数学、物理or化学の順でした。

解答用紙が回収されるのに15分ぐらい待たされます。受験の10分前には参考書をしまう必要があるので休み時間は短かったです。

英語

大問は3つあり、内容も例年通りでした。

大問1 和訳 Zoom疲れやその原因について

大問2 英訳 量子コンピュータについて、それがもたらす社会への影響

大問3 長文読解 微生物や細菌の種類について、その種類の測定法

英語は簡単とまでは言いませんが、難しくはなかったです。

数学

大問は4つで2時間、今年はすごく難しかったです。

大問1 特殊な微分方程式

誘導に従って解きます。 最後の極限値を求める問題は飛ばしました。

大問2 確率

ベイズの定理が出ました。 薬の副作用がでる確率、副作用の検査キットが間違った結果を出す確率から偽陽性率的なのを計算したりするやつでした。

途中から総和を求める部分でシグマを使うべきなのに必死に積分して爆死しました。アホすぎる…ｗ

大問3 複素関数論

A6=iとなる複素数6つを三角関数を用いず書けというとんでもないクソ問がでました。その後は普通に留数定理でしたが確率で精神を壊していたため、場合分けを忘れて爆死しました。

大問4 行列

対角成分がa、それ以外が1の行列の行列式やら固有値やら固有ベクトルを出させる問題でした。後は上三角行列の逆行列がでました。

どれも誘導0で自分で解く必要があり、普通にわからなかったです。

物理

大問1 剛体の力学

剛体球が斜面を滑り落ちる問題でした。 剛体の問題の集大成といえるような内容でした。普通に難しかったです。

定石である摩擦をFとおいて運動方程式と回転の運動方程式からFを消して～というのができれば解ける問題です。

滑り落ちない条件や、球は転がるけど円筒は転がらない(逆かも)場合の条件などが応用としてでました。

大問2 電磁気

銅線の上で導体棒を動かすときの誘導起電力などを計算する、典型的な問題が出ました。

磁束の時間微分が起電力であることから求めます。 棒に働く力(ローレンツ力)などあるあるがでました。

最後のほうに抵抗の代わりにコンデンサをつなぐとどうなるかが出ました。微分方程式を立てて解ければできます。

また、導体棒が2個になり、片方は放置し、他方を一定速度で近づける場合に放置されてる棒の速度が時間とともにどうなるかという問題がでました。 これも微分方程式を立てて解くとVo(1 - e-at)のような解がでたので、おまけにグラフも書きました。

10割いけたと思います。

大問3 マイケルソンモーリー干渉計とマッハツェンダー干渉計

な～～～～～～～～～～んもわからない！！！！！！！！

小問1がまずわからなかったので白紙です。その代わり得意な大問2にたくさん時間を使いました。

結果

一次試験に合格していました。一次試験を合格した人は20名いました。

ちなみに自分のクラスからは私を含めて4人受かっていました。バケモンでワロタ。

この段階では自分が第1志望に合格したのか第2志望に合格したのかはわかりません。

二次試験

ある程度の時間帯は指定されて行きます。面接官はL字型に並んでおり、15人ぐらいいました。

時間は一人当たり10分ほどです。

質問内容はほとんどが事前に提出した志望理由書から聞かれます。聞かれた内容は

  • 志望する学科名と志望動機
    • 緊張で計数工学科って言えなかった説があって怖い。
  • 最小記述長原理について説明して(紙の志望動機に書いてた)
    • 少し詰まったけど耐え。
  • 上に対して、それはどういう時に使うのか
    • うろ覚えだったので適当に言った。
  • データ構造やアルゴリズムを学んだと(志望理由に)書いてるけど、例えばどういうのを学んだ？
    • SA-ISがO(N)なことに感動して調べて理解した話を喋ったらウケが良かった。
  • 数理情報コースとシステム情報コースがあるけど数理の方に興味があるってこと？
    • はい。(話が早くて助かる！)
  • 何を学びたいか(うろ覚え)
    • プログラムの数理や機械学習の数理、統計など。統計は必要性を認識していて、受験後にでもすぐに自分でがっつりやる予定と、自主性と意識の高さをアピール。
  • 得意な教科と苦手な教科
    • 得意なのは電磁気、苦手なのは物理の光学や機械系。
  • 英語が苦手って志望理由書に書いてるけど、TOEICは高いのは何で？
    • スピーキング能力に限界を感じた。
  • 試験の出来や感じたことを教えて
    • 物理の三問目が何もわからなかったが、後で調べたらマイケルソンモーリー干渉計だということが分かったと、試験後に振り返ったアピールをしつつ言い訳した。
  • タイに行って学んだことに何がある？(志望理由書に書いてた)
    • 上手く答えられなかった。友達とかはできなかったの？と言われたのでSNSで中国やアメリカの方と仲良くなり、チャットしてますと言い訳。

などです。志望理由書にかなり具体的に書いた僕個人の話が聞かれてるので、他の人はあまり参考にならないと思います。

面接官は多いのですが、実際に質問するのは3人ぐらいです。 志望動機、試験の出来、得意な教科と苦手な教科などを聞く全体の進行役の人と、専門的なことを(少し試す感じで)聞く志望学科の教授と、気まずい時に喋るあと1人という感じです。

基本的にはハキハキ答えながら、志望理由書に書いた専門的な話は付け焼き刃ではないか、今の社会課題などを認識しており自分の考えを持っているか、やりたい研究や東大に入ってからのビジョンは明確か、などが問われそうです。

志望理由書からがっつり聞かれるので自分の書いた志望理由書は絶対にデータをとっておき、それをもとに対策しましょう。

結果

計数工学科に合格していました。

支えてくれた友人、Twitterにて励ましであったり、教材をギフトで贈ってくださった方々本当にありがとうございました。

これからも精進して参ります。

【令和4年度】電通大編入試験 まとめ

編入

電通大編入の学力試験を受けてきました。一類を受験しました。 主に前日～試験と面接について書いていきます。

受験の経緯

4年次より第一志望を大阪大学基礎工学部 情報科学科 ソフトウェアコースとして勉強してきました。 その滑り止めとして、ひとつ下のレベル帯である神戸大、筑波大、電通大からどれかを受験しようと考えていました。

情報系のみで考えると、大学の名前の強さは個人的には筑波>>電通=神戸だと思います。 しかし、今年は筑波と阪大基礎工の受験日が被ったため電通大にしました。

電通大の利点は東京都内であること、研究が面白そうなこと、学生のレベルが高いことなどがあると思います。

前日

調布駅の横のノービス調布というホテルに泊まったのですが、机が小さすぎて勉強できなかったのが辛かったです。 電通大前のマクドナルドで勉強していました。 調布駅から電通大までは真っ直ぐな道を進むだけなのでわかりやすかったです。

筆記試験

このような日程でした。

f:id:naoppy_ac:20210629201320p:plain
電通大テスト日程
試験と試験の間に1時間も時間があってありがたいです。

試験時間と最大点数は同じで、数学は120点、物理、英語は90点で合計300点満点です。

服装はラフで大丈夫です。冷房が寒いので上着を持っていくといいです。

数学

大問5つから4つ選択です。例年線形代数から2問、偏微分や微分、重積分、複素関数論みたいなセットが出題されており、今年もそうでした。

大問1の最後に明らかな激ムズ問題があったので大問2~5を選択しました。大問2は最後が難しかったです。それ以外は割と典型だったのでなんとかなりました。

大問選択ですが、線形代数のどちらか簡単な方を選択し片方を切るのがオススメです。複素関数論を勉強する時間がないなら線形代数2つもありですが、線形代数は時間がかかるのと、どちらか片方は難しいことが多いので大変です。

予想100/120点

物理

試験範囲に現代物理学と波動がありますが、波動は4~5年に一度レベルなので勉強をする必要があるかは疑問です。 他の大学でも波動がでない大学は多いので、電通大のためだけに波動をするのは微妙だと思います。

例年では大問1がばねに繋がれたおもりの減衰振動、大問2が電磁気（電気双極子、アンペールの法則、ビオサバールの法則、ガウスの法則など）、大問3がサイクル系の熱力学＋化学っぽい熱力学（相とか？よくわからん）です。

今年は大問1に剛体の問題がでました！時々剛体はでますが、慣性モーメントを積分で計算させるようなことは無く剛体の運動方程式を書かせ、滑らない条件を使うような基礎的な問題が多いので対策は簡単だと思います。

大問2はガウスの法則から球内の一様な電荷分布と球殻に対してEとVを出し、グラフを書かせる問題でした。電通大は時々グラフを書かせてくるので直定規を持っていきましょう。

大問3はオットーサイクルでした。簡単で助かりました。

予想85/90点

解答用紙はほぼ白紙で自由に使ってよく、裏を使用するときは「裏に続く」と書く必要がありました。

英語

例年通り大問1が長文の日本語要約の穴埋め(45点)とトピック2つの内選んで自由英作(45点)でした。

長文の単語レベルはまあまあ高かったです。自由英作は他の大学で出ないので完全にノー勉で行きました。正直採点基準がどうなっているのかわからないので本当に怖いです。

英作が壊滅だと考えて予想60/90

筆記試験全体として8割ぐらい取れたかなという感覚でした。

面接

これが気になっている受験生は多いと思います笑

服装はスーツで、6割ほどが背広も着ていましたが、暑いのでシャツのみでいいと思います。

受験番号が若い人から呼ばれていき6分の一般面接があり、その後すぐに12分の情報面接があります。 面接の部屋の前にある椅子に荷物を置いていいので、大きいスーツケースやリュックでも大丈夫です。 あと、集合時刻になるとスマホなどの電子機器を回収され、終わった後に順次返却されます。面接内容の共有防止のためです。

受験番号が遅かったのでめっちゃ待ちましたが、最後の人でも12時前には終わるぐらいのスピード感でした。 遅い人は1時間半は待つことになるのでなにか読むものを持っていきましょう！

一般面接

一般面接では2人の面接官にあらかじめ決まっているであろう質問を淡々とされ、回答に対して深堀りされたりも一切ありませんでした。

  • 志望動機
  • 電通大に入って何がしたいか
  • 得意な科目と苦手な科目
  • 将来なりたい職業など
  • 併願校と、両方受かったらどうするか(合否に関係なし)

6分なので一瞬で終わりました。質問されることがテンプレすぎる＆返答に対しての深堀りがないため緊張はしませんでした。

情報面接

情報面接も面接官は2人でした。入るとホワイトボードに問題が貼られており、10分で全部解いてください。と言われました。いわゆる口頭試問ですね。

大問は2つあり、大問1は16進2進変換、2進数の2の補数、割り算などでした。

大問2は二分探索のフローチャートの穴埋めとサンプルに対してシミュレートして実行回数を答えるやつでした。

10分は意外と短いので検算をする時間が無いです。解いている間は喋る必要は無く、ホワイトボードに書くだけでした。 10分経ったら話すこともなく終わりであっけなかったです。

最後に

結果は合格でした！

今年は一類が11人、二類が10人、三類が15人合格していました。