終業式が終わりました
長かった5年間も一区切りです！
高専では公立高校に進学していたらありえないくらいたくさんの貴重な経験ができました。
特に高専プロコンに出たこと、小学生にプログラミング教室を開いたこと、めちゃくちゃパワポ作ったこと。これらが印象的です。
友だちや先輩、先生などにも本当にお世話になりました（私の人生、本当に人間関係に恵まれています…！）
進学先でもいろんなことに好奇心を持って、挑戦を忘れない日々でありたいです。
長かった5年間も一区切りです！
高専では公立高校に進学していたらありえないくらいたくさんの貴重な経験ができました。
特に高専プロコンに出たこと、小学生にプログラミング教室を開いたこと、めちゃくちゃパワポ作ったこと。これらが印象的です。
友だちや先輩、先生などにも本当にお世話になりました（私の人生、本当に人間関係に恵まれています…！）
進学先でもいろんなことに好奇心を持って、挑戦を忘れない日々でありたいです。
試験が少なすぎて4連休になりました。時間があるので普段はあまり参加しないコドフォに出てみました。
バブルソートを行います。操作回数が\(\frac{n(n-1)}{2} - 1\)以下となる配列ならYESを、そうでなければNOと出力しなさい。という問題できた。
バブルソートのスワップする回数が最悪\(\frac{n(n-1)}{2}\)であることを知っていれば、そのようなケースの配列と一致しているかを確認するだけですね。知らなくても滅茶苦茶ググってバブルソートの交換回数（転倒数と言います）を求めるプログラムを探せば難なくACできます。
しかし私はこの問題を解く直前、下のツイートのような問題を作問しておりまして、まんまと引っ張られました。
この前のコドフォのA問題、これに引っ張られて2WAした（） pic.twitter.com/WuyS5YVELD
— んぐ (@ngng628) September 25, 2020
流石に2WAしたのは僕の落ち度ですけど…w
結局僕はググってFenwick tree (BIT)による計算方法をコピって通しました。今後このようなことがないようライブラリ化しました。よければ見てください
struct FenwickTree {
int n;
vi bit;
FenwickTree(int _n) : n(_n), bit(n+1, 0) {}
void add(int i, int x) {
if (i == 0) return;
for (int k = i; k <= n; k += (k & -k)) bit[k]+=x;
}
int sum(int i) {
int s = 0;
if (i == 0) return s;
for (int k = i; k > 0; k -= (k & -k)) s+=bit[k];
return s;
}
int lower_bound(int x) {
if (x <= 0) return 0;
else {
int i = 0; int r = 1;
while (r < n) r <<= 1;
for (int dist = r; dist > 0; dist >>= 1) {
if (i + dist < n and bit[i + dist] < x) {
x -= bit[i + dist];
i += dist;
}
}
return i+1;
}
}
};
int InversionNumber(const vi& v) {
const int n = len(v);
FenwickTree fw(n);
int ret = 0;
rep (i, n) {
ret += i - fw.sum(v[i]);
fw.add(v[i], 1);
}
return ret;
}
「転倒数を求めよ」という問題以外で使えるかは分かりませんが…反省の意味も込めて。
目は通しました。左辺を \(i\) の関数に、右辺を \(j\) の関数にするタイプの問題かなぁと考えていたんですが、そう簡単には移項させてくれませんでした。
仕方がないので本番では先にC1を通すことにしました。時間があれば解けただろうなーというレベルの問題なので悔しい
DeepLがいきなり「ピカチュウ」とか言い始めたのでびっくりしました。原文読んだらちゃんとピカチュウって書いててさらにびっくり。てかよくよくタイトルみたらPokémonって書いとるやん。
ポケモン好きなので問題になるのは嬉しいのですが、プレッシャーにもなるので解くのはちょっと焦りました。
問題をよく読むとAtCoderでやった問題だ！となりました（全く同じ問題なかった？）。配列の極値を求めて、あとは偶奇や最初の山谷に気をつけて良い感じに足し引きすれば答えが求まります。
DPで解く解法もあるみたいですね。僕はできません。
\(q = 0\)で良かった～～～！
「5年生になったらテスト楽になるよー」と先輩からよく言われてましたが、僕もついに！
実際7教科（中学の期末より少ない…！）しかなかったし、今回はシルバーウィークを途中に挟んだのでまーじで楽だった。
テスト勉強は大分余裕がありましたが、結局テスト前日にしか勉強しないのは流石といったところ。すっかりこの環境に毒されてしまいましたね。高専はこれといった大きな試験が5年生までないので、勉強に関しては「60点以上をとれればなんでもいい」という考えになってしまいがちです。
まあでも5年生は単位を落とさず卒業できれば勝ちですからね。ドイツ語のテストがかなーり怪しいですが、別に良いのです。少々単位落としても留年はしません！
結果は期待せず、そのそも気にも留めず、気楽に待ちたいと思います。