表題の通りGSoC 2020にProposalが採択されました。 summerofcode.withgoogle.com Applyするに当たってたくさんの過去の参加者のブログを参考にさせていただいたので、僕も応募までに何をしたかを軽く記録しておきます。 Proposal 最終的に提出したProposalが…
3Aの振り返りメモです、20erの方の参考になれば幸いです。 3Sについてはこちらをご覧ください理学部情報科学科3S - okura diary 対象読者誰？みたいな内容になってますがただのメモなのでご了承ください。 3Aの概観 各授業の詳細 月2 言語モデル論 月4 連続…
昨日CPU実験の最終発表会があり、無事CPU実験を終えることができました。このエントリはその振り返り、感想、ポエムです。 やった内容をつらつらと書いているだけなので真ん中のほうは面白くないと思うので細かい内容に興味無い方は読み飛ばし推奨です。 細…
この記事はISer Advent Calendar 2019の1日目として書かれました。 最近ライブラリの剪定をしているときに「そういえばWavelet Matrix実装してないなぁ」と思ったので実装してみたら想像以上にシンプルで驚いたのでそれについての軽い解説を書きました。競プ…
書かないと記憶の彼方に消えてしまうと思うので簡単な振り返りメモです。 対象読者 : そこのあなた 後輩に有益かどうかはわかりません。2Aについては同期のブログ kammer0820.hatenablog.comが詳しいです。 課題のネタバレなどはなるべくないように注意した…
理学部情報科学科の関数論理型言語プログラミング実験の最終課題でリバーシAIを実装したので過程のメモです とりあえず僕が提出したものはここにあげてます。 github.com言語は関数論理型なら相談すれば許可されるようでしたが僕は諸々のインターフェースが…
自炊する日をの日間(日は0-indexed)とし、とおくと幸福度は よってkを固定した時、P*i+C[i]が小さいものから順にk個選ぶのが最適。ちゃんと定式化するの大事… ll N,P,Q; ll C[500100]; vector<ll> vec; int main(){ scanf("%lld %lld %lld",&N,&P,&Q); ll sum = </ll>…
昨日までの5日間八王子の大学セミナーハウスでJOI夏季セミナーにチューターとして参加していました。 僕はMLPの「劣モジュラ最適化と機械学習」を担当しました。 5日間とにかく色んなことがあってある意味生徒として参加した時以上に濃い時間を過ごした(?)の…
重い。ただただ重い。 #define MAX_N 200100 #define MAX_LOG_V 20 const int SIZE = 1<<19; struct node{ int l,m,r,sum,lazy,ig; node(){ l = m = r = sum = ig = 0; lazy = INF; } node(int _ig){ l = m = r = sum = 0; lazy = INF; ig = _ig; } }; node …
2時間45分で全完。 取れる問題ちゃんと取れたので良かった 建設事業 平面走査 + segtree + Kruskal + 貪欲 典型盛り合わせみたいな問題で難しいとは感じなかった。 struct edge{ int from,to; ll cost; edge(){} edge(int from,int to,ll cost):from(from),t…
解き納めにするつもりやったのにくだらんバグで6分間に合わんかった…。 典型の組合せで綺麗。好き。 今年は最後の一年やから何事も悔いのないように全力でやり切ります。 難易度12は残り3問。 int N; int H[100100]; vector<int> up[100100]; vector<int> down[100100]</int></int>…
最後のJOI予選、やるだけセットやったのに誤読で時間消費してデバッグギリギリ間に合わんかった。 しかもバグは2箇所!が|になってただけ。クソクソクソクソ。死にたい。 本選、春まで死ぬ気で問題解きまくる。 予選満点ちゃうかっても代表にはなったるからな…
激冷え。
9AC1WAでした。8間に合わなくて速度不足を痛感。本選までもっと実装力も発想力も鍛えます。 1~7を自分が解いて9をeyさんが解いて10を二人で解きました(eyさんが最初に解いたがWAが出て自分がデバッグした) 8ほぼ書き終わってたのに間に合わなくて辛い(Trieで…
だいぶ想定解まで迫ったもののO(N^4)から落とせず、解説を見てしまった。 桁数でまとめる発想がなかったのは頭悪すぎたので反省 typedef long long ll; #define MOD 1000000007 const int SIZE = 100100; ll inv[SIZE+10],fac[SIZE+10],facinv[SIZE+10]; ll …
ケーキの端にイチゴが乗ってる時(sample1)の対処をメモ。 len(Y)は片方を(0,Y)に固定したときに等分できる右側の部分の長さを返す関数。 ただ、(0,Y)にイチゴがあると色々面倒なので+eps,-epsの２つに分けて処理した。 誤差怖かったけど通ったので良かった(…
個人的にハマるポイントが山ほどあったので戒めのメモ。 まず、自分のライブラリはverify済でも信用してはいけません (まぁこれはverifyした後にちょっとわかり易くしようと書き換えた自分が悪いのでなんとも言えませんが) (でもまさかadd_edgeが間違ってる…
良問DPとして有名な箱根駅伝。結構考えましたがわからず解説を読んでしまいました。 JAGの解説が少しわかりにくかったのでここにまとめておきます。 順位表の'-'は確定するので無視します。 現在の中継地点の順位表を1位から順に見ていって、前の中継地点で…
グラフの閉路を検出するのはDFSなりベルマンフォードなりで適当に出来ますよね。 今日奇数長の閉路の検出が出来ずに困ってしまったのでメモ。 全然今まで気付かなかったのですが 「偶数長の閉路しかない⇔2部グラフ」 です。あとはこれより、2部グラフかどう…
ちょいちょい勉強したことでも書き留めておこうと思います。 Counting Sortというのを知りました。 sortなんてquick sortとmerge sortだけ知ってりゃ十分やとか思ってたんやけど、CFでこれを使う問題が解けんくて悔しかったから書いときます。 この方法は数…
何日か前にやったのに書くの忘れてた 本選会場 うまいこと待ってやれば、最小全域木のコスト分しかかからない。K個まで分割することが許されるので、全域木に含まれる辺からコストの大きい順にK-1個とって木をK個に分割してやればいい。 int N,M,K; struct e…
問題文はちゃんと読みましょう Origami,簡単だけど5ではないでしょ…— おくら (@okuraofvegetabl) 2015, 2月 22 ええええええええええ辺の長さ20cm以下とか聞いてないぞおおおおお— おくら (@okuraofvegetabl) 2015, 2月 22mapで数えるだけの問題を2次元座圧+…
はい、2日目。 足し算 繰り上がりがあって、和が10を超えない時 繰り上がりがあって、和が10を超える時 繰り上がりがなくて、和が10を超えない時 繰り上がりがなくて、和が10を超える時 に場合分けしてやった。 最後に残った繰り上がりの1を忘れていてWAをは…
5時間ちゃんと時間測ってやってみた。 JOI ポスター なんか昔解いた気がするけどまぁやるだけ。 適当に再帰で書きました。 時間かけすぎた気がする。 string rec(int N,int K) { string ret; if(!N)return "J"; if(K>=(1<<(N-1))) { rep(i,1<<(N-1))ret+='I'…
昨日までJOIの本選に参加していました。 結果からいうと一応通過しました。 去年こんな感じで(JOI 2014 本選 - (#・∀・)) この時の悔しさを噛み締めながら一年やって来たので、通過できたことは素直に喜びたいと思います。 2/7 potetiと一緒に新神戸から新幹…
CF:赤 TC:赤 PCK:金 JOI:メダル獲得 IOIに行く
一年前に 2014年 今年の目標 - (#・∀・) という記事を書きました。残念ながら全く目標を達成できませんでした(CFに関してはgood bye 2014で達成できたはずなのにくだらないミスでチャンスを逃しました)来年はかならず目標を達成して見せます(目標は来年発表…
問題概要 N頂点のDAGが与えられる(多重辺アリ).入次数0のノードからN番目のノードまでの全てのパスを考える. それらのなかに最も多く含まれている辺の、含まれている回数を求めよ 辺a->bが含まれる回数は(始点からaまでのパスの総数)*(bから終点までのパスの…
問題概要 [Start,Finish]で、二進数で表記した時に0の数が1の数以上になるような数の個数を求めよ桁DP。やるだけ。なんでこれが8なんだろう(この前8のad-hocが自力で解けなかった) dp[i][j][k][l]:=今上からi桁目で、0の個数-1の個数がjでkはずっと上限でき…
問題概要 N種類の曲があり、それらを順番に流す。聞いている側が曲名が分かり次第流す側に伝える。 流す側は伝えられたらすぐに次の曲を流す。 各曲には認知度p[i]があり毎秒ごとにp[i]%の確率で、そこから1秒で曲名がわかる。 また、各曲の歌詞には曲名がは…
