本質情報メモ

beetさんが書いてたこういう系の記事をそのうち読もうとしていたら非公開になっていました。悲しいね
問題のネタバレが存在しているので、読む人は注意。
適宜更新予定

  • 木の中からいくつか辺を選ぶ時(その結果非連結になっても良い)、各頂点の次数を決めると辺の選び方は一意に定まる。例えば、n頂点の木で奇数次の頂点がk個の選び方は  \binom{n}{k}(ただしkは偶数) (例題:D - Odd Degree

グラフ

その他

  • 「添え字の和が一定のものの和」はFFTで計算できる。「添え字の差が一定のものの和」は、片方を反転させることによりFFTで計算できる。(例題:F - Substring 2)

ICPCアジア地区予選2020参加記

1日目

学生証を見せるためにZOOMにログインする。
くれそんがギリギリまで起きてこなくてビクビクしていた。

リハーサルコンテストはClarとかペナを出す練習をせずにFAを狙いに行った。
結果、AのFAをもらえた。
Dは初見だったけど頑張って解いた。

一日目は特に書くことがないね

2日目

起きた。えらいので

コンテスト開始前

ととり「僕とbin君がABのどっちかをやるのでくれそんは後ろの方を見て」
くれそん「なんで?」
と「くれそんはABをバグらせそうなので任せたくない」←ひどいね

コンテスト

Bを読み、通す(0:18)
短そうなDを読む、が、わからない。(~0:30)
Aがバグっていてつらそうなので問題を聞いて考察をする(0:30~)
くれそんがJを通す(0:46)
Aの実装を奪って通す(1:12)
Gを考える、十分条件が分かったので実装をする→よく考えると必要十分だねとなる(~2:00)
内容は忘れたけどしょーもない実装ミスでGのペナを出す→直してAC(2:09)
様々な問題を読み、考察をする(~3:00)
Iのデバッグを手伝い、ACを出してもらう(3:15)
Cは「こういうのはどうせ短手数で終わるので全探索!w」と言うとくれそんが「6手以内で終わるよ」と言うので実装を投げる。
くれそんが「ABの実装バグらせそうなのにこれやらせるの?」と突っ込んできたが黙らせる
Eの解法を生やしたり嘘だったり再び生やしたりをしてbin君に実装を任せる→デバッグを担当してサンプルが一致したので投げると1ペナが出たけど通った、偉い
コンテスト終了9分前にCが、3分前にEが通ってお祭りになった

後はすべての問題にテキトーに投げて終了。
全完であることを祈るお祈りタイム。

コンテスト後

ご飯を食べて問題解説・表彰式などを見る。 無音でひたすら顔面が流れるタイムは流石に困惑。
結果は7完で16位でした。 nowcowに負けた、おるふぇ許さん。
あとharaharaがまた近くにいた

f:id:totori_nyaa:20210317212342p:plain

なんでおるふぇがこんなところにいるの?(率直な疑問)

懇親

渾身の懇親を行った。

バイオインフォマティクス技術者認定試験を受けました

バイオインフォマティクス技術者認定試験とは?

バイオインフォマティクスの技術者であることを認定してくれる試験です.
認定してくれるんですか!?ありがとうございます!!!!!!!!!!

2019年度までは生命科学20問,情報科学20問,バイオインフォマティクス40問の合計80問でした.
2020年度からはCBT方式への移行に伴い60問になっています.

受けるまでにやったこと

バイオインフォマティクス学会が出している教科書を読みました.
生命科学に関しては大学の講義で,情報科学に関しては競プロでアルゴリズム,研究で統計がある程度わかるようになっていたので,あまり勉強することはありませんでした.
バイオインフォマティクスに関しては何もわかりませんでした.今もなんもわからんです.
特にゲノムやアミノ酸配列などのデータベースだったり,人の名前がついていたり常に選択肢に略語でしか出てこないアルゴリズムや手法が大量に出てくるので名前を覚えるのが嫌でした.
嫌だったのでやってません.
教科書は毎日寝る前に30分読むことにしていました.
過去問は試験2週間前に1年分,1週間前に1年分,前日に1年分,当日に1年分で直近の4年分をやりました.

受けてみた感想

今年から問題が20問減るので,「4分野(生命科学情報科学バイオインフォマティクス前半・後半)から均等に5問ずつ減るのかな~」と思っていたのですが,試験を受けてみた感覚や他の人のスコアから察するに,どうやら生命科学情報科学からそれぞれ10問ずつ減っており,バイオインフォマティクス関連は問題数がそのままのようです.
自分は生命科学情報科学が得点源だったのでかなり泣きました.
過去問では問題文をちゃんと読まなかったために間違えた問題が大量にあったので,一通り解き終わった後はすべての問題を見直し,4問くらいミスを発見しました.
見直し,大事すぎる.教科書に書いといてくれ~~~~

結果

正式な合否の発表は2月末の予定なんですが,もうスコアシートはもらえるんですよね.

f:id:totori_nyaa:20210216194436p:plain

流石に受かっとるやろ
おわり

追記 (2021/2/26)

合格していました. f:id:totori_nyaa:20210226152741p:plain

上位10%に入ったらしいです.やったね

2021/02/08

久しぶり!!!!!!!!!!!!!!!
あけましておめでとう!!!!!!!!!!!

人生

起きる
研究をする
疲れる

虚無streak

Submission #20050850 - CODE FESTIVAL 2014 Easy

20位ごとに入れ替わる感じ

人生2

バイオインフォマティクス技術者試験を知っていますか?
僕は知っています.

バイオインフォマティクスは全然専門じゃないんですが,生命科学情報科学の知識が多少あるので楽に合格できそうだということで受けることにしました.

最近はそれの勉強を夜寝る前に30分くらいやってから寝る生活をしています.
寝る直前にスマホやPCの画面を見ないようにするという意味も込めて.

人生3

他の大学や同じ大学の違う学科の民が卒論を提出したり発表を終えたりしている中,締め切りが遅いのでまだ卒論をまともに書き始めておりません.
卒論を終えて頭夏休みになっている人,あまりにも羨ましすぎる
熱烈研究🔥

2020/12/30

RTA in Japanを見たり、ゲームをやっていたりしたら気がついたら5時前だった。
13時からチーム練があるのでやべえと言いながら急いで寝る。
起床後、虚無でstreakを繋いでチーム練に備える。

2020-2021 ACM-ICPC Brazil Subregional Programming Contest

https://codeforces.com/gym/102861

nowcowとのチーム練。
くれそんとおるふぇが朝までゲームをやっていたせいで出られず、2チームとも2人になっていた。
問題を後ろから読んでいく。とりあえず問題文が長かったりやばそうな図がある問題を飛ばして、短めのHを読み始める。
問題の制約から適切なビット列を作成して桁DPをやればよさそうだなと思う。実装が重そうなので流石に初手からやるのはやめておこうと思い、順位表を見るとGが解かれていたのでGを解く。AC(~0:08)
Bを相方に任せてFをやる。ぱっと見丁寧に実装をするだけの問題。丁寧に実装してAC(~0:43)
相方にAを任せていたが、期待値DPの遷移が分からないらしい。自分もよくわからないので困ったねと言っていた。勉強します。
Lもまぁいつものという感じで縦横と斜め2方向に文字種別の累積和を取って、頑張る。頑張るとACが出る(~1:37)
Hは最初の方に考察をしていたので詰める。 どんなに2個の箱も、重いほうは軽いほうの少なくとも2倍の重さはあるのでテキトーにビット列に変換したくなる。なるね
nCkの中でx 以下になるような最大のビット列を作り、あとは丁寧に桁DP
互いに独立なdp1dp2を作っていたのだが、1か所dp1からdp2に遷移させており、1ペナ。実装が下手くそ(~2:17)
Eは区間に収まるような最も上の人からその区間に対するimosをやりたい気持ちになるので、ダブリング+DFSでBITでいもすをするとAC(~3:18)
Nがバグっているらしいのでコードを眺める。何でバグっているのか分からん。終わり。
コンテスト後にコーチモードをonにしてみてみると、どうやら1か所、非本質的なところで配列外参照をしていた。泣いた。
書き直したコードが通ったとの報告を受けたので、Iを読む。
根からDFSで、{それ以下が全部わかっている, 1個以外全部わかっている}をもって計算するとできそう。

これをするとmulが途中で0になった時に破滅する。

    ll mul = 1;
    for(auto i:v[p]){
        auto t = dfs(i);
        mul *= t[0];
        mul %= mod;
        g.push_back(t);
    }
    ll res = 0;
    for(auto [x,y]:g){
        res += (((mul * modinv(x))%mod) * y)%mod;
        res %= mod;
    }

こんな感じに左右から積を取っておこう。

    vector<ll> l,r;
    l.push_back(1);
    r.push_back(1);
    for(auto i:v[p]){
        auto t = dfs(i);
        g.push_back(t);
    }
    for(int i=0;i<(int)g.size();i++){
        l.push_back(l.back() * g[i][0] % mod);
        r.push_back(r.back() * g[(int)g.size()-1-i][0]% mod);
    }
    reverse(all(r));
    ll res = 0;
    for(int i=0;i<(int)g.size();i++){
        auto [x,y] = g[i];
        ll t = (l[i] * y) % mod;
        t *= r[i+1];
        t %= mod;
        res += t;
        res %= mod;
    }

結果は8完85位
1人足りないので、中難易度の問題を解ききる前に時間切れになってしまったし、ペナも多め。

人生

お隣の天使様の読書を再開した。
次買うラノベ何にしようかしらねと言っている。

食事とゲームをしていたら一日が終わっていた。

TwitterAPI申請が通ったのでtotori_nyaaアカウントのツイ消しを始めた。
ネットに落ちていたコードをそのまま使っただけなので何も手を動かしていないけど。
何時間か動かして5万件くらいは消せた。

研究していなくてピンチ!これからやります。
こどふぉのGood bye 2020は出ません。