2022年度東京農工大学工学部知能情報システム工学科編入体験記

2022(令和4)年度東京農工大学工学部知能情報システム工学科数理情報工学コースの編入試験を受験し、合格することができました！
受験者は33名、合格者9名で倍率は3.7倍でした。
友人によると今年は例年より受験者が少し多かったようです。

併願状況

高専での成績

高専によって試験の難易度等がかなり違うのであまり参考にはならないと思いますが、電子情報工学科で席次は15～17位、平均点は85±2くらいでした。
その他の実績はパソコン甲子園2019プログラミング部門本選出場、ICPC 2020 Asia Regional出場です。

受験までにやったこと

数学

編入数学過去問特訓を2周と、専攻科の過去問5年分、筑波の過去問10年分、農工大の過去問10年分を解きました。
農工の数学は毎年同じような問題が出るので過去問をとにかくやりました。ここのフォームで申請すると過去問へのリンクがもらえます。本当に感謝しています。
数学は1問が重いので、計算ミスができるだけなくなるように練習しました。また、本番では大ポカをやらかしそうな気がしたので、60分で全問解答して30分で見直しができるように時間に気を使いながら解くことを心がけました。
非斉次二階線型微分方程式は右辺が訳の分からない形になっている場合があるので、最終手段としてロンスキー行列を用いた解法についても練習しておきました。

英語

筑波の受験用にTOEICの勉強をしたのと、受験1ヶ月前からDuo3.0を2周して阿佐谷英語塾の長文問題を10問ほど解きました。
正直これでは不十分だと思います。長文問題は146問公開されているので万全を期すなら70問くらいやるべきだったと思います。

物理

配点も低かったのでそれほどやる気もなく、農工大の過去問を10年分と、友人と勉強をしていたときに一緒に解いた名工大の過去問3年分くらいしかやりませんでした。
変な問題が出れば解けないし、解ける問題が出れば解けるという感じだったので解ける問題が出ることを祈っていました。

専門

これも農工大の過去問を10年分と筑波の過去問を5年分やったくらいでした。
プログラミングの問題は競技プログラミングでさんざんコードを書いてきたので変な問題がでなければ大丈夫だろうと踏んでいて、2進数の計算や離散数学、デジタル回路はそこまで難しくなかったので過去問をやっているうちに思い出せました。

受験前日

新幹線はスマートEX早特21で予約しました。21日より前とかなり早いタイミングで予約しなければいけないのがネックですが、学割よりも安く2021年時点では最安値で新幹線の席を確保する手段です。

ホテルは農工大の最寄り駅東小金井駅から1駅の武蔵境駅前のホテルメッツ武蔵境を予約しました。かなりいいホテルです。僕が予約した部屋のテレビにHDMIケーブルがついていたのでPCをテレビに繋いでアニメを観ていました。
ホテルの近くにはマクドナルド、はなまるうどん、ガスト、松屋、イトーヨーカドーなどがあり食事は外で取りました。朝食、昼食はイトーヨーカドーで購入し、夕食は松屋で食べました。松屋はたった80円でサラダもつけられるし、味噌汁はデフォルトでついてくるので最高です。松屋しか勝たん！

受験当日

1日目

大学で試験を受けるのは初めてだったので一応スーツで試験を受けに行ったのですが、周りがみんな私服でビックリしました。
一緒に受けた同じクラスの友人も私服だったので、事前に連絡取っておけばよかったかなと思いました。 試験開始時間が8:30とかなり早く寝坊しないかビクビクしていましたが普通に起きられました。

数学

大問1

いつも通り2変数関数の極値を求める問題でした。特に言うことはありませんが、計算ミスなしで突破できたのは良かったと思います。

大問2

かなりうろ覚えですが、1変数の積分が2問だったはずです。パッと見で面食らいましたが、落ち着いて式を分離することでよく見る形に帰着できるのでなんとかなりました。
見直ししたときに大変な間違いをしていることに気づいて[2]を解き直す羽目になってかなり焦りましたが、すぐに修正できました。

大問3

何度か見たことのある最小の固有値に属する(x,y,1)の形の固有ベクトルを求めよという問題だったはずです。
一度解き終わって解答を確認したときに固有値を求める時点で間違えていることに気づき、また解き直す羽目になりました。速攻で解き直して事無きを得ました。

大問4

いつもの非斉次二階線型微分方程式でした。右辺は特に難しくもなく推測できる形だったので楽勝〜〜〜と思って解いたのですが、見直してみると特性方程式の解を求める時点で間違えていたことに気づき、急いで直しました。この時点で試験終了5分までだったのでかなり焦って過呼吸になりながら解き直していたら、最後の条件に合う定数を求めるところで試験が終了してしまいました。


1問毎にはそれほど時間がかからなかったので見直しする時間を多く確保することができました。見直しができていなかったらマジで終わっていたので本当に良かったです。
大問4の最後だけが解き切れませんでしたが、それ以外は合っているはずなので部分点がつくと信じて9割という感じでした。

英語

大問1

イギリスの大学の入学者数には性差がなくなってきているが、受験する学科(?)は性差があり、実際にこのようなデータがある。みたいな感じの長文問題でした。
分量はA4片面程度でそれほど多くはないです。
[1]の日本語訳がうまくできなかった以外は多分できていたと思います。

大問2

通信制大学の歴史と実態、それがもたらすメリット。みたいな感じの長文問題でした。
分量はA4両面程度でした。
こっちの問題は全部選択式だったはずです。雰囲気で読んで雰囲気で解きました。大体合ってると思います。

大問3

最近はコロナのために多くの学校が遠隔授業をするようになったが、遠隔授業に対して対面授業のメリットを2つ英語で書けという問題でした。
リアルタイムで議論が活発にできることと、特別な機器が必要ないので困窮学生に優しいという旨の文章を本当に拙い英語で書きました。採点官の方、本当にごめんなさい......。


日本語訳と英作文が壊滅していたので体感6割よくて7割といった感じでした。

物理

なんかめちゃくちゃ難しかったです。

大問1

重心を原点に置いた木の棒に、重心から距離aの位置に棒に対して垂直に速度vでボールをぶつけたときの棒の運動についての問題でした。
本当に全然分からなかったので、頭が真っ白になりました。とりあえず反発係数と運動量保存の式だけ書いて後は白紙です。

大問2

[1]は面電荷密度βの半径aの薄い円盤の中心を貫くようにz軸をとったときのz>0の任意の点での電界と電位を求めよという問題でした。
最後の電位を求める積分が分からなかったのでそこだけ空欄でした。
[2]は覚えていませんが、すごく簡単な教科書レベルの問題だったと思います。


大問1で完璧に破滅したので体感5割くらいでした。

アンケート

試験が終わった後、面接を円滑に進めるためのアンケートに答えてくださいとGoogle FormのQRコードを渡されました。
本当にこれ通りに面接が進むのでちゃんと解答しましょう。聞かれる項目は
- 併願校
- 農工大をどのように知ったか
- やってみたい研究、配属を希望する研究室はあるか
- 説明会に参加したことはあるか
- 学科のWebページを見たことはあるか
- 博士(前期/後期)まで進学する予定はあるか
- コンテスト等の実績はあるか
というようなことでした。
特に合否には関係ないらしいですが、実績欄に何か書いた人は(おそらく)その話を振られるので変なことを聞かれたくない人は書いておくといいでしょう。

2日目

試験開始時間は9:30で1日目よりは余裕がありました。 面接があるためかこの日はみんなスーツでした。

専門

この年も大問1は必答、大問2,3から1問、大問4,5から1問選択という方式でした。

大問1

[1]はいつもどおり2進数の計算でした。
[2]は集合の演算の問題でした。対称差がなんなのか知りませんでしたが、演算子が⊕だったのでXORだろうと思って解きました。後で調べたら合ってました。

大問2

[1]は入力が4,5,7の倍数のときは1を、そうでないときは0を出力する4入力のデジタル回路を考える問題で、いつものように真理値表とカルノー図を埋めるだけでした。
[2]は1の累積カウントが2の倍数になったとき or 0の累積カウントが4の倍数になったときに1を、それ以外のときは0を出力する状態機械を考えるという問題でした。
(1)は出力が与えられて、それを出力するのような入力例を1つ答えよ。
(2)はこれの状態遷移図をミーリ形で書け。
という問題でした。
ミーリ形がなんなのかわかりませんでしたが、入出力を書けと書いてあったので、エッジに入出力を書いておきました。後で調べたら合ってました。

大問3

見てません。なんかめちゃくちゃめんどくさい電気回路の問題だったらしいです。

大問4

親の顔よりみたダイクストラ。
グラフを隣接行列で書いて、一回手で実行してv1からv7の最短経路と重みを求めて、プログラムの穴を埋めるという問題でした。
例年よりかなり簡単だったと思います。

大問5

見てません。なんかすごく簡単な電磁気の問題だったらしいです。

わからない言葉が2つもできてきたので不安でしたが、あとで調べたら合っていたので10割です。

面接

この年は受験者が多かったので数理情報工学コースの受験者は二つのグループに分けられて、面接会場の控え室まで案内されました。
遠方からの受験者のほうがより早く面接に呼ばれるらしいです。 控え室では電子機器の使用の一切を禁じられるので、なにか紙の本を持っていくといいでしょう。
面接自体は3分くらいで終わりました。
会議室のような部屋に1人ずつ呼ばれて、入室してから受験番号と名前を言ってから席につきました。 面接官は2人でおそらく志望学科の教員だと思います。
最初に「試験はどうでしたか？」と試験の出来を聞かれました。 英語と物理は破滅していた感触があったので、「数学と専門はかなり手ごたえを感じていますが、英語と物理は全然できませんでした」と答えました。 「物理は難しかったですか？」とだけ聞き返されたので、おそらく試験の点数はこの時点で出ていたのではないかと思います。 次に「博士まで行くつもりはありますか？」と聞かれたので「修士までいくつもりではいますが、博士まで行く経済的な余裕はないので、今は博士まで行くつもりはありません」と返しました。 おそらく面接で聞きたいのはこの2つだけで、あとはコミュニケーション能力が欠如していないかとう社会性診断だと思います。
あとはアンケートの項目通りに1,2個質問をされただけでした。
実績欄にパソコン甲子園プログラミング本選出場とICPC Asia大会出場と書いたのでICPCの話は振られるかなと思って身構えていたのですが、 「パソコン甲子園って甲子園でやるんですか？」と聞かれて、なにかカマをかけられているのかと思いました。「会津大学が主催している高校生向けのコンテストで——」と答えると「ほー」という感じの返答をされたので、本当に知らなかったのだと思います。 面接が終わったらすぐ開放されました。一緒に受けた友人と話ながら駅まで戻って、その足でそのまま筑波に向かいました。東小金井から筑波まではまあまあ遠いので結構しんどかったです。

終わりに

英語と物理が破滅していたので落ちたと思っていたですが、受かっていて本当に嬉しいです。ここに落ちていたらおそらく全落ちだったので安心しました。
反省点としては英語と物理をもっと勉強しておくべきだったと思いました。特に英作文は本当に壊滅していたので英作文はやるべきでした。
農工大の数学は過去問だけやっておけばいいレベルなので、過去問特訓2周目の時間を英語と物理に当てるべきでした。
以前、教員に「得意科目をいくら勉強しても満点より高い点数は取れないから苦手を潰す勉強をしたほうがいい」と言われたのですが、本当にそうだと思います。
今大学編入の勉強をしている方は、得意科目の勉強はほどほどにして、早めにそれ以外の科目の勉強をしましょう。
入学意思確認書の提出が7/30(金)までだったので東工大などを受ける方は気を付けてください。
　　

ICPC2020 国内予選参加記

niu_mogu_moguでniuezとplayrollerで組んで参加しました.

コンテスト前

なんかずっと微熱が出てて一週間くらい寝込んでいた。
一週間まるまる欠席してたけど、PCR検査の結果が出るまでの期間は公欠にできるらしい(ホンマか？)
当日は熱も下がってきていたので出るか～～～～～～～～～～～～と言いながら準備をした。
事前練習の(僕が解ける難易度の)問題が全て解かれていて、提出してACをもらうまでの流れを練習できなくて微妙に困った。仕方がないのでhelpを1333回くらい読んだ。

コンテスト

過去問を見る限り、僕には頑張ってもDくらいまでしか通せなさそうだったので、僕とplayrollerでA～Cくらいまでをやっつけようということになった。
コンテストが始まった瞬間、アクセスできなくなって、僕何かやっちゃいました？と思ってかなり焦ったけど、チームメイトに連絡したら同じ状況らしいので少し安心。
いつのまにかコンテストが始まっていたので、僕がA、playrollerがB、niuezがCから後ろを見る。
勝手がよくわからないままやっていたらＡを通すのに10分くらいかかってしまった。まあ、ペナを食らうよりはマシなので……。 ちょっと遅れてplayrollerがＢを通してくれたので一緒にCを見る。
にうが方針を投げてくれていたので、それを元にして考える。愚直に2回約数列挙だと時間がかかりすぎそうだけどもしかしたらいけるかもということでplayrollerが試しに実装してみるとやっぱりダメそうな感じらしい。
ちょっと考えても冴えた方法が思い浮かばなくて、微妙に困ったのでとりあえず小手先の高速化をしてみることに。
とりあえず、pが素数、2つもしくは3つの素数の積の場合だけ別で処理して、あとはwを約数列挙で全探索、hとdはsqrt(p/w)に一番近い約数の組を選んだ時にw+h+dが最小になるのでそのようにすると、待てるくらいの実行速度になるので待つ。解答を投げてみるとcorrectが返ってきたので、そのまま通す。明らかに犯罪っぽい気がしたけど、ルール上問題ないので問題なし！
Cが解けたのでDを読み始めたけど、よくわからない。わからね～～～～～～と唸っているうちにniuezがEを通す。すげー。
しばらく考えてわからなかったので夕飯を食べる。夕飯を食べてもわからないものはわからない。困った。
どうにもならなかったので、一応他の問題を見てみる。その時点でまだ通してない問題は一通りみたけど、普通によくわからかった。Ｈなんすかあれ。
他の問題は手を出しても太刀打ちできないことが分かったのでＤに戻る。しばらく考えたけど、よくわからなったので、机に突っ伏して、机と椅子を温めていた。
もう残り時間全然ないな～～と思いながら順位表を眺めていたところ、niuezがFでペナを出しまくっていることに気づく。がんばれ～～～と届かない応援をしていると、コンテスト終了間際になってniuezがFを通す。今日のヒーローはお前や！！！！！！！
最終結果はABCEF 5完で25位。

まとめ

かなりいい結果を残せたんじゃないかと思う。僕自身もぶっ倒れていたわりにはまともに近い動きができていたので良かった。 チームメイトの二人にはかなり心配をかけてしまっていたはずなので、ここで謝っておきます。ごめん。
あとかなり土壇場で出れそうなので出るわとか言ったのに温かく迎えてくれたので、ここで感謝しておきます。ありがとう。

SNCTプロコン春合宿コン'20 解説

Twitterでtesterの方による解説ツイートがある1のですが、もしかしたらTwitterをやっていない人がいるかもしれないので2、一応ここに解説を書いておきます。
コンテストへのリンク
https://www.hackerrank.com/contests/snct-spring20/challenges
提出したコードは下のほうにまとめてあります。
目次

1. εrr-r

A 円で A円より高い物を買うことはできません。
したがって、 A \lt Bなら"Error"を、そうでないなら A-Bを出力すればいいです。

2. αειου

母音は a, i, u, e, oの5つです3 前から文字列を見ていって、今見ている文字が母音ならカウンターに+1するなどして数え上げればいいです。
C++ならrange-based forを使うと楽に書けると思います。

3. ασδα

同じ品種のりんごは食べられないので、幸福度の最大値は各品種のりんごの美味しさの最大値の総和です。
したがって、品種 A_iのりんごの美味しさの最大値を配列かmapかなにかで持っておけばいいです。
美味しさが負のときは食べないほうがいいので握りつぶしてかまいません。

4. Ϟϟ

九九の票を睨むと Xは2つの整数 p,qを用いて X = pqと表せることが分かります。
これを変形すると p = \frac{X}{q}となるので pが整数となるような qを探せばいいです。 このような qは Xの約数に限られるので、 qを 1から \sqrt{X}まで動かして Xを割り切れるか試していけば,すべての (p, q)の組を列挙することができます。

5. Ξητ

まず、明らかに小さい数から取っていったほうがいいので Xの列をソートします。 また、 Aより大きい数しか選べないため、 Aが2つ以上あっても Aが2回以上選ばれることはありません。
したがって、重複を取り除いても答えは変わらないので重複を取り除いておきます。
ここで、 1に続く数が 13と 1333しか無い場合、大きい方である 1333を取ったほうが答えは大きくなります。したがって、
dp[i][b] := i番目の数までみて、最後に取った数の末尾の数字が bであったときの得点の最大値
とおけば、dpで答えが求められます。

6. ΣΜμ

いくつか例をつくってみると、一番右側の部分列をどれだけ伸ばしても最小値の最大値は大きくならず、反対に真ん中の部分列を短くすると最大値は小さくなる場合があることが分かります。 したがって、一番右側の部分列は区間[N, N]で固定するのが最適です。あとは最適な aの位置を探索すればよく、これは A_1から A_Nへの累積和と A_{N-1}から A_1への累積maxを持っておけば O(N)で求めることができます。

Submissions

1. εrr-r

#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;

int main(){
    int A, B;
    cin >> A >> B;
    if(A < B) cout << "Error" << endl;
    else cout << A - B  << endl;
}

2. αειου

#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;

int main(){
    int N;
    string S;
    cin >> N >> S;

    const string vowels = "aiueo";
    int counter = 0;
    for(auto& c : S){
        for(auto& vowel : vowels){
            if(c == vowel)  counter++;
        }
    }

    cout << counter << endl;
}

3. ασδα

#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;

int main(){
    int N;
    cin >> N;

    valarray<i64> max_delicious(0l, 100010);
    for(int i = 0; i < N; i++){
        i64 A, B; 
        cin >> A >> B;
        max_delicious[A] = max(max_delicious[A], B);
    }

    cout << max_delicious.sum() << endl;
}

4. Ϟϟ

#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;

int main(){
    i64 Q, X;
    cin >> Q >> X;

    int counter = 0;
    for(i64 q = 1; q*q <= X; q++){
        if((X % q) != 0) continue;
        i64 p = X / q;
        if(p <= Q && q <= Q) {
            if(q*q == X) counter += 1;
            else counter += 2;
        }
    }

    cout << counter << endl;
}

5. Ξητ

#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;

int front(i64& x){
    i64 d = 1;
    while(d * 10 <= x) d *= 10;
    return x / d;
}

int back(i64& x){
    return x % 10;
}

int main(){
    i64 N;
    cin >> N;
    vector<i64> X(N);
    for(int i = 0; i < N; i++) cin >> X[i];

    sort(X.begin(), X.end());
    X.erase(unique(X.begin(), X.end()), X.end());

    valarray<i64> dp(0l, 10);
    for(int i = 0; i < X.size(); i++){
        int b = back(X[i]);
        int f = front(X[i]);
        dp[b] = max(dp[b], dp[f] + X[i]);
    }

    cout << dp.max() << endl;
}

6. ΣΜμ

#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;

int main(){
    int N;
    cin >> N;
    vector<i64> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];

    vector<i64> sum(A), MAX(A);
    for(int i = 0; i < N-1; i++) sum[i+1] += sum[i];
    for(int i = N-3; i >= 0; i--) MAX[i] = max(MAX[i], MAX[i+1]);

    i64 ans = 0;
    for(int i = 0; i < N-2; i++){
        ans = max(ans, sum[i] + MAX[i+1] + A[N-1]);
    }

    cout << ans << endl;
}

途中で下書きが吹き飛んでしまってキレながら書いたので雑なところがあるかもしれませんが、ゆるしてください。

  1. https://twitter.com/ecto0310/status/1237007779597938689?s=20↩

  2. いないだろ↩

  3. yは母音！(素振り) ちゃんと問題文で定義してくれ↩

AtCoder Grand Contest 034 A - KenKen Rase 解説

パッと見解けなくてビビってしまった
問題リンク : https://atcoder.jp/contests/agc034/tasks/agc034_a

問題概要

一列に並んだ N個のマス目があり、左からAマス目とBマス目に駒が置かれている。
各マスには.か#が書かれており、#が書かれている、もしくは他の駒が置かれている場合、そのマスに駒を置くことはできない。 駒を右に1か2マスだけ動かせるとき、Aマス目に置かれていた駒をCマス目に、Bマス目に置かれていた駒をDマス目に移動させることはできるか。

制約

1 \le N \le 200,000
A,B,C,Dマス目は#でない
A \lt B, A \lt C, B \lt D

考察

A \lt B, A \lt C, B \lt Dをいい感じに使うんだろうなという気がする。
まず C \lt Dの場合について考えてみる。
例: A#B.#..#.#C..#D
このようなマス目を考えると、Bマス目の駒を先にDマス目まで移動させてしまえば、Aマス目からCマス目まで駒を動かす時に他の駒の位置を考える必要はない。 したがって、##のように駒を置けないマスが連続していない限り、題意は達成可能であるとわかる。
次に、 C \lt Dの場合について考えてみる。先の例の Cと Dを入れ替えてみる。
例: A#B.#..#.#D..#C
実際に動かしてみると、題意が達成不可能なことがわかる。これはなぜかを考えると、
Bマス目の駒ををどのマスに動かしても、Aマス目の駒からみて##のように駒を置けないマスが連続してしまうためであることがわかる。 したがって、...のように駒を置けるマスが3つ以上連続している区間が(B-1)-D間に存在していればいい。

Submission

#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back

int main(){
    int N, A, B, C, D;
    string S;
    cin >> N >> A >> B >> C >> D >> S;
    A--, B--, C--, D--;
    bool ok = true;
    for(int i = A; i < C; i++){
        if(S[i] == S[i+1] && S[i] == '#') ok = false;
    }
    for(int i = B; i < D; i++){
        if(S[i] == S[i+1] && S[i] == '#') ok = false;
    }
    if(C > D){
        bool pass = false;
        for(int i = B-1; i < D; i++){
            if(S[i] == S[i+1] && S[i] == S[i+2] && S[i] == '.') pass = true;
        }
        if(pass == false) ok = false; 
    }
    
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}

けんちょんさんの記事を参考にして書いたらパクリみたいになってしまった。

AtCoderで水色になるまでにやったこと

その他

やっちゃ〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
きちゃ〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
遂に!
f:id:UGIS:20200217192049p:plain AtCoderで水色になりました!!!!!!!!!!!!!!!!!!!!!!!!!
(水色になるまでにこんなに停滞した奴なかなかいないでしょ)
n番煎じです。通過儀礼みたいなところがあるので(?)水色になるまでにやったこととか,すこしポエムとかを書きます.

やったこと

灰 〜 茶まで

  • A,Bあたりをいっぱい解いた
    この辺はプログラミングそのものや使ってる言語に慣れてきたあたりで卒業できました.今はもっと厳しいと思います

茶 〜 緑まで

  • Cを埋め始めた
  • PCKの予選に出た

平成の頃はCまで30分くらいで緑パフォが出たんですよね...
個人的にPCKの過去問をやったのは早解きに効いたと思います.

緑 〜 水まで

800 〜 1000 まで

  • Cをほぼ埋めた
  • Dを埋め始めた
  • JOIの予選に出た
  • 某ITエンジニア・プログラマ専門の総合求職・学習サイトでSランクになった

この頃はCを20分くらいで通せるようになるとパフォが1000くらい出たので, C早解きとDを通せるようになることを意識して問題を解いていました.
JOIの難易度5あたりまでを半分くらい埋めました.JOIの問題は教育的な問題が多いのでオススメです. 記憶が曖昧ですがこの頃はCSAとかも埋めてた気がします. 2019年の1月くらいに競プロerの間で某に殴り込むのが流行っていたので流行に乗ってSランクを取りにいきました.(これのせいでSランクのボーダーが上位2%になったのはあまりにも有名)

1000 〜 1219まで

2019年5月 〜 9月

  • Dを半分くらい埋めた
  • Vのヲタクになった
  • 開発をした
    このあたりはテストでコンテストに参加できなかったり,Web開発をしたりで競プロのモチベが無だったんですが,ちょこちょこDを埋めたりしていました.

9月 〜 12月

  • ISUCONに出た
  • 庭(ライブラリ)に木(データ構造)を生やした
  • PCK予選の6〜7問目くらいまでを埋めた
  • AOJ - ICPCの200点くらいまでのやつをちょっとやった
  • PCK本選に出た

ISUCONは興味があったので先輩と出てみたんですが,ほとんど椅子を温めていました.
このあたりはコンテストに出ても全然レートが上がらないし,E問題全然ようにならないしでうつになっていました.
なのでAtCoderから一旦離れて,AOJに篭ったりライブラリ整備をしたりしていました. ライブラリ整備はかなり楽しくて,コンテストで使う機会はほとんどなかったんですが, アルゴリズムやデータ構造を考えるときの基本的なアイデアや気持ちといった知見が得られたので良かったと思います.
PCK本選に出たのはかなり良い体験だったと思います.当日はTwitterでよくみる競プロer実在してるやんけ,スゲ〜〜〜って言ってました. 本選ではかなり冷えてしまったし,クラスメイトがモバイル部門で優勝したので,このあたりから自分もなんか実績作らないとやべ〜〜と焦りを感じていました.

12月 〜 今

1月の中頃まではこどふぉとか出て精進してるのに,コンテストで冷えまくってhighestから100以上下げていて,競プロつまんね〜〜〜って言ってました.
冷えているときは競プロのモチベがほぼ0になっていたので数学に逃げたり,前々から興味があった機械学習に入門したりしていました.結果的に数学をやったのはかなり効いたと思います.
特に数学ガールの秘密ノート/学ぶための対話を読んでからは,
- 自分は何が分からなくて分からないと言っているのか
- どうやったらその発想に到れるのか
を納得できるまで考えるようになったので,解けない問題に出会ったときの経験値の量がかなり上がった気がします.
他にも気をつけるようになったこととして,
- コンテストのすべての問題を読むようにした
- コンテスト中に解けた問題数+1問解くようにした
の2つがあります.
すべての問題を読むようにしたのは令和ABCになってからDにちょっとむずかしめの数学問が出て解けないということがあったからです.
Dで詰まると実質10分でコンテストが終わってしまってつまらないので,5〜10分考えて何も思いつかないなら次の問題を見るようにしました.
また,Dまで早解きすればギリギリレートが上がるくらいだったのですが,正直早解きでレートを上げるのも限界に来ていましたし,解ける問題だけ一瞬で解いてコンテストを終えるのもつまらないので,コンテスト後にDまでか解けなかったらEを,Eまでしか解けなかったらFを解説ACするようにしていました.これはかなり効いたと思っていて,コンテストでしか問題を解いていなくても解ける問題が少しずつ増えていくのでちょっとずつでも経験値が溜まっていきます.
あとは,にうくんに「こどふぉでろや」と言われたのでこどふぉに出ました.Div.2でA,B早解きしたら水色になれたので緑あたりで伸び悩んでいる人にオススメです(モチベに効きます)
こどふぉではAtCoderでよく見るパズル問題をあまり見ないのでパズルが苦手な人はこどふぉの方が楽しいかもしれません(ただしコンテストに参加するのが難しい)
前のコンテストの前日に劇場版 ハイスクール・フリート 4DX版を観ました.テンションがぶち上がったので,これがコンテストでのパフォーマンスにつながったと勝手に思っています.
最後にこれはマジで何も関係がないと思うのですが,コンテスト当日の夕方にじょえチャンネルbotをデプロイしました.
な　に　こ　れ　笑
f:id:UGIS:20200217222246p:plain twitter.com
自分でもなんでこんなものを作ったのかよくわからないんですよね.ほぼ思いつきの勢いだけで作りました.
ちなみにアイコンは手書きです(雑さが出た方がいいかなと思ったので)
じょえチャンネルbotはこれからも機能を追加する予定なのでお楽しみに！

水色になるまでに学んだこと

頑張ってるつもりなのに成長が見えないとつまらない

これは競プロじゃなくてもそうなんですが,自分の成長が見えないとマジでつまらないです.
つまらないときは適当にVの配信漁ってヘラヘラしてるほうが万倍マシなレベルでつまらないんですが,こういうときこそ成長するチャンスだと思っています.
停滞してしまうのは今までと同じやり方じゃダメだということだと思うので,こういう機会に自分の精進の仕方を見直してみるのがいいと思います. ただ,やり方を変えても結果が出始めるまでに少し時間がかかるので,この間にやめてしまわないことが重要です.
また,競プロはレートによって自分の相対的な強さを認識できる分,それの変動を自分の成長の指標にしてしまいがちです.僕も昔はそうでした.
レートの変動を成長の指標にしてしまうと,たまたま難しかったり,自分が苦手だったりする問題が出たときにレートが下がってモチベが下がりがちなので,自分の中でレート以外の成長の指標を持っておくのがいいと思います.僕はバチャでの完数とかn完までの時間を指標にしています.

納得するまで考えた方がいい

試験勉強とかだと多少わからないことがあっても試験のために一瞬だけ暗記してしまえば,もう一生問われることがないことがそこそこあるのでそれでもいいんですが,競プロだとなんとなくわかった程度で放っておくと似たような問題に出会ったときに解けないというツケが回ってくるので納得できるまで考えた方がいいです.僕は昨日の自分がこれなんでなんですかって突っ込んできそうなところを全部説明できることをゴールにしています.

特別得意じゃないことでも続けていればある程度のところまでいける

別に数学とかパズルが得意じゃなくても,異常精進しなくても,ダラダラでも続けていればある程度のところまでいけます.
途中でつまらなくなってしまっても結果を出したいなら頻度が落ちてもいいので続けましょう.
僕は一回やめてしまうと一生戻ってこれなくなるタイプの人間なので,これからもなんとかやめずに続けていけたらなと思います.

PCK2019予選・本選解説

解説

パソコン甲子園2019に参加して来ました。
弊学で行われた成果報告会の為に解説を書かされたのでここに公開しておきます。
僕が実際に参加したときに解いた問題しか解説は書いていません。ご容赦ください。

ここに書いた内容はすべてここにあります
GitHub - ugis70194/PCK
ジャッジを通したい方はこちらから
AOJ-PCK(パソコン甲子園過去問)

予選問題

予選 1問目 柴犬の数

問題

公園に4種類の柴犬がいます。 柴犬の数はそれぞれ、R, B, W, Gで与えられる。 このとき、柴犬の総数を求めるプログラムを作成せよ。
ただし、1 \le R,B,W,G \le 100を満たす。

解説

R, B, W, Gすべてを足したものを出力すればよい。
時間計算量のオーダーはO(1)となる。

コード

#include<bits/stdc++.h>
using namespace std;

int main(){
    int R, B, W, G;
    cin >> R >> B >> W >> G;
    cout << R + B + W + G << endl;
}

予選 2問目 アスキー文字

問題

コンピューター内部ではアルファベットの大文字'A'から'Z' に連続してそれぞれ数値の65から90が割り当てられており、同様に、小文字'a'から'z'にそれぞれ数値の97から122が割り当てられている。
数値Nが与えられたとき、アルファベットの大文字であれば1を、小文字であれば2を、それ以外であれば0を出力するプログラムを作成せよ。 ただしNは1 \le N \le 127を満たす。

解説

if文を用いて、Nが大文字の範囲内なら1を、小文字の範囲内なら2をそれ以外なら0を出力するようにする。
時間計算量のオーダーはO(1)となる。

コード

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin >> N;

    if(65 <= N && N <= 90) cout << 1 << endl;
    else if(97 <= N && N <= 122) cout << 2 << endl;
    else cout << 0 << endl;
}

予選 3問目 ２の累乗

問題

数値Nが与えられる。
N以下の数の中で最大の2の累乗を求めるプログラムを作成せよ。ただし、Nは 1 \le N \le 10^{6} を満たす。

解説

数値のbit表現を利用する。
bit表現においてbitが一つだけ立っているときは、10進数では2の累乗になる。
したがって、立っているbitを左にずらしたときに与えられた数より大きくならなければ、bitを左にずらし続ければよい。 時間計算量のオーダーはO(\log_2 N)となる。

コード

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin >> N;

    int ans = 1;
    while(N >= (ans << 1)) ans <<= 1;
    cout << ans << endl;
}

予選 4問目 集会所

問題

東西に一直線に伸びる道路に沿った村がある。
最も西の地点を0番目として、等間隔に東に向かって順に地区番号が与えられている。 ある時刻に一斉にすべての村人が自分の家から集会所に向かったとき、全員が集まるのに必要な時間が最小になるような場所に集会所を建てることにした。
家の立っている地点の番号が与えられたとき、最適な場所に集会所と建てた場合に、すべての村人が集会所に集まるのに必要な時間の最小値を求めるプログラムを作成せよ。
ただし、家の数Nは 1 \le N \le 1000 を、家が立っている地区番号x_iは 0 \le x_i \le 2000 を満たす。
集会所はすで家が立っている地区に建ててもよい。 また、すべての村人は隣の地区まで1分で移動できるものとする。

解説

集会所にたどり着くのに最も時間がかかるのは西の端か、東の端の家に住んでいる村人なので、そこだけ考えればよい。
そして、集会所がこれら2つの地区のちょうど真ん中に建っているとき、村人全員が集会所に集まるまでにかかる時間が最小になる。
したがって、西の端の家から集会所までの距離と東の端から集会所までの距離のより大きい方が最小の時間になる。
時間計算量のオーダーはO(N)となる。

コード

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> X(N);
    for(int i = 0;i < N; i++) cin >> X[i];
    int MIN = *min_element(begin(X), end(X));
    int MAX = *max_element(begin(X), end(X));
    int m = (MIN + MAX) / 2;
    cout << max(abs(MIN - m), abs(MAX - m)) << endl;
}

予選 5問目 ねこのあな

問題

中が行き止まりになっている横穴がある。この横穴は猫がちょうど一匹入れるくらいの横幅で、奥行きは100匹の猫が入るのに十分である。 横穴に出入りした猫のリストが与えられるので、リストの先頭から順に見ていったとき、それより後ろを見なくても誤りと判定できる最初の位置を求めるプログラムを作成せよ。 ただし、猫は100匹いて、1から100までの番号が与えられているものとする。 i番目に横穴に入った猫の番号がa_i、出た猫の番号が-a_iで与えられる。
また、リストの長さLは 1 \le L \le 10000 の範囲で与えられる。

解説

明らかに誤りなのは、リスト上で

  • 既に横穴に入っている猫が横穴に入ったとき
  • 一匹も横穴に入っていないのに猫が出てきたとき
  • 一番最後に入った猫でない猫が出てきたとき
  • 横穴に入っていない猫が出てきたとき

の4つの状況が起こった場合である。
横穴はスタック構造になっているのでスタックと配列を用いてシミュレーションをすればよい。 配列は今その番号の猫が横穴に入っているかどうかのフラグを管理するために用いる。
上記4つをスタックと配列の操作に直せば以下のようになる。

  • 今見ている値に横穴に入っているフラグが立っている
  • スタックのサイズが0なのに今見ている値が負
  • スタックの一番上の値といま見ている値に-1をかけたものが異なる
  • 今見ている値に-1をかけたものに横穴に入っているフラグが立っていない

したがって、これらのパターンを検知するようにアルゴリズムを組めばよい。 リストを最後まで見る必要がある場合があるので、時間計算量はO(L)

コード

#include<bits/stdc++.h>
using namespace std;

int main(){
    int L;
    cin >> L;
    vector<int> C(L);
    for(int i = 0; i < L; i++) cin >> C[i];
    vector<int> in(L+1,0);
    stack<int> s;

    int ans = 1e9;
    for(int i = 0; i< L; i++){
        if(C[i] > 0){
            if(in[C[i]]) ans = min(ans, i+1);
            else in[C[i]] = 1, s.push(C[i]);
        } 
        if(C[i] < 0){
            if(s.size() == 0) ans = min(ans, i+1);
            else if(in[-C[i]] && s.top() != -C[i]) ans = min(ans, i+1);
            else if(!in[-C[i]]) ans = min(ans, i+1);
            else in[-C[i]] = 0, s.pop();
        }
    }

    if(ans == 1e9) cout << "OK" << endl;
    else cout << ans << endl;
}

予選 6問目 床

問題

博士の家の床には正方形のタイルが敷きつめられている。はじめに部屋の適当なタイルをひとつ選び、以下の方法で色を塗っていく。

  • タイルを塗る色を、赤、黄、青の順に変えていき、青の次はまた赤から始める。
  • すでに色を塗った領域の隣に正方形を追加し、そこに色を塗る。それらを合わせた領域が長方形になるようにする。正方形を追加する方向は、東、北、西、南の順に変えていき、南の次はまた東から始める。

最初に赤く塗ったタイルから東をxの正の方向、北をyの正の方向として、東西方向にx個,南北方向にy個移動したところにあるタイルの色を求めるプログラムを作成せよ。
ただし、x, yは -10^{6} \le x, y \le 10^{6} の範囲で与えられる。

解説

正方形の大きさはかなりの速さで増加していくことが分かる。
正方形の一辺の長さは1, 1, 2, 3, 5 ...となっている。
これはフィボナッチ数列であるので、i個目の正方形の一辺の長さは動的計画法を用いて高速に求められる。 最初に赤く塗ったタイルの左下端を原点(0,0)として、i個目の正方形の左下端の座標と右上端の座標をもっておけば、 座標(x,y)の位置のタイルが何個目の正方形に属しているかがわかる。
したがって、i個目の正方形の左下端の座標と右上端の座標、面積、色を最初に赤く塗ったタイルから順に求めていって、 座標(x, y)が正方形の中に入っているか逐次判定すればよい。
フィボナッチ数列は2の累乗よりもすこし増加量が小さいので時間計算量はおおまかに \log (max(|x|, |y|)) 程度となる。

コード

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

struct coor{
    pair<i64, i64> x, y;
};

int main(){
    i64 X,Y;
    cin >> X >> Y;
    vector<i64> fib(500);
    fib[0] = fib[1] = 1;
    for(int i = 2; i < 500; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    coor now = {{0, 1}, {0, 1}};
    i64 way = 0;
    i64 color = 0;
    int i = 1;
    while(i < 500){

        //cout << color << " -----" << endl;
        //cout << now.x.first << " " << now.x.second << endl;
        //cout << now.y.first << " " << now.y.second << endl;

        if(now.x.first <= X && X < now.x.second 
        && now.y.first <= Y && Y < now.y.second){
            cout << color+1 << endl;
            return 0;
        }
        
        coor next;
        if(way == 0) {
            next.x.first = now.x.second;
            next.x.second = next.x.first + fib[i];
            next.y.first = now.y.first;
            next.y.second = next.y.first + fib[i];
        }
        if(way == 1){
            next.x.second = now.x.second;
            next.x.first = next.x.second - fib[i];
            next.y.first = now.y.second;
            next.y.second = next.y.first + fib[i];
        }
        if(way == 2){
            next.x.second = now.x.first;
            next.x.first = next.x.second - fib[i];
            next.y.second = now.y.second;
            next.y.first = now.y.second - fib[i]; 
        }
        if(way == 3){
            next.x.first = now.x.first;
            next.x.second = next.x.first + fib[i];
            next.y.second = now.y.first;
            next.y.first = next.y.second - fib[i];
        }

        now = next;
        i++, way++, color++;
        way %= 4;
        color %= 3;
    }

    cout << 0 << endl;
}

本選問題

本選 1問目 目盛りのないストップウォッチ

問題

目盛りのないストップウォッチがある。このストップウォッチには、0を示す目印と針が一つずつついている。
針は最初目印を指しており、ストップウォッチを起動すると時計回りに回転し始める。
針が目印からa度回転した時の経過時間がt (1 \le t \le 1000)秒であると分かっているとき、針の角度がrの時の経過時間を求めるプログラムを作成せよ。
ただし、0 \lt r \lt 360であるとする。

解説

針の角度がr の時の経過時間を T とすれば、
a : t = r : Tが成り立つので、 T = \cfrac{rt}{a} となる。
したがって、 \cfrac{rt}{a} を出力すればよい。
時間計算量のオーダーはO(1)となる。

コード

#include<bits/stdc++.h>
using namespace std;

int main(){
    long double A, T, R;
    cin >> A >> T >> R;
    cout << setprecision(8) << R*T / A << endl;
}

本選 2問目 ガソリンスタンド

問題

このガソリンスタンドには1からNの番号が割り当てられたN (1 \le N \le 10)個のレーンがある。
ガソリンスタンドに入場した車は、並んでいる車が最も少ないレーンを選び列の末尾に並ぶ。 もし、そのようなレーンが複数ある場合は最も番号が小さいレーンの末尾に並ぶ。
レーンの先頭の車から給油を行い、給油が終わると車はレーンから出ていく。
一度レーンを選んだら車は他のレーンに移ることはなく、並び順が変わることもない。
レーンの数、入場した車と給油が終了したレーンの情報が与えられたとき、給油が終了した車のナンバーを順番に出力するプログラムを作成せよ。 ただし、情報の数Mは2 \le M \le 10000であるとする。

解説

各レーンはキュー構造になっているので、N本のキューを用いてシミュレーションをすればよい。
時間計算量のオーダーはO(M)となる。Mの上限は10000なので十分高速である。

コード

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;

    vector<queue<int>> lanes(N);
    for(int i = 0; i < M; i++){
        int b, n;
        cin >> b >> n;
        if(b == 0){
            n--;
            cout << lanes[n].front() << endl;
            lanes[n].pop();
        } else {
            int lane = 0;
            int len = 1e9;
            for(int l = 0; l < N; l++) {
                if(len > lanes[l].size()){
                    lane = l;
                    len = lanes[l].size();
                }
            }
            lanes[lane].push(n);
        }
    } 
}

本選 3問目 海苔

問題

二枚の長方形の海苔があります。
二枚の海苔それぞれの左端の座標の幅と高さが与えられたとき、重なっていない部分の海苔の面積を出力するプログラムを作成せよ。
ただし、海苔の左端の座標x,y、幅w、高さhは(0 \le x, y, w, h \le 1000)の範囲で与えられる。

解説

全体の面積から重なっている部分の面積を引けばよい。
簡単のために、より左側にある海苔を一枚目の海苔とする。
そうすれば、海苔の重なり方は3通りになる。　　 重なっている幅はx+w - XとWの小さい方か、その小さい方が負になる場合は0になる。 重なっている幅と高さはそれぞれ独立に求められるので、それぞれ独立に求めて重なっている面積を計算すれば良い。
時間計算量のオーダーはO(1)になる。

コード

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main(){
    i64 x, y, w, h;
    i64 X, Y, W, H;
    cin >> x >> y >> w >> h;
    cin >> X >> Y >> W >> H;

    if(x > X) { swap(x ,X), swap(y, Y), swap(w, W), swap(h, H); }
    i64 width = max(min(x+w - X, W), 0ll);
    if(y > Y) { swap(x ,X), swap(y, Y), swap(w, W), swap(h, H); }
    i64 height = max(min(y+h - Y, H), 0ll);

    cout << (w*h + W*H) - 2*(width*height) << endl; 
}

本選 4問目 へびの脱皮

問題

頭から尾にかけて一列にならんだマル(o)とバツ(x)からなる模様のへびが発見された。
このへびは脱皮のときに、2つのマルが並んだ部分の間すべてが伸びることで成長する。新たに加わった箇所にはマル、バツ、マルが並んだ模様がつく。
へびの模様と脱皮の回数が与えられたとき、この回数だけ脱皮した後のへびの長さを求めるプログラムを作成せよ。
ただし、へびの長さ Lは 1 \le L \ le 100、脱皮の回数 Nは 1 \le N \le 50であるとする。

解説

たとえば、長さ３のへびoooが１回脱皮すると、左から1番目と2番目、2番目と3番目のマルの間にマル、バツ、マルが並んだ模様が加わるので、
脱皮後のへびはooxoooxooとなる。
もう一回脱皮するとooxooxooxoooxooxooxoo となり、へびの長さは21となる。
ここで長さを増加する箇所(マルが隣り合っている箇所)の増え方に注目する。
マルがとなりあっている個数を Aとすると Aは脱皮の度に2倍になる。すると、 [tex: A{i+1} = 2A{i}]という漸化式が成り立つ。この漸化式の一般項は[tex: A_N = A_0(2N - 1)]で与えられる。
へびの長さの増加量はその3倍なので N回の脱皮で伸びる長さは 3A_Nとなる。
したがって、最初のへびの長さを L_0とすれば N回脱皮した後のへびの長さ L_Nは[tex: L_N = L_0 + 3A_0(2N-1)]となる。 最初にマルがとなりあっている個数を数えるのに O(L)時間かかるので、全体の時間計算量オーダーは O(L)となる。

コード

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

i64 POW(i64 x, i64 n){
    i64 res = 1;
    while(n){
        if(n & 1) res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}

int main(){
    i64 L, N;
    string snake;
    cin >> L >> N >> snake;

    i64 A = 0;
    for(int i = 1; i < L; i++) {
        if(snake[i-1] == snake[i] && snake[i] == 'o') A++;
    }

    cout << L + 3ll*A*(POW(2, N) - 1ll) << endl;
}

最後に

来年度はICPC出るぞ出るぞ出るぞ