AOJ 2642 Dinner

自炊する日をの日間(日は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>…

JOI夏季セミナー2017 チューター参加記

昨日までの5日間八王子の大学セミナーハウスでJOI夏季セミナーにチューターとして参加していました。 僕はMLPの「劣モジュラ最適化と機械学習」を担当しました。 5日間とにかく色んなことがあってある意味生徒として参加した時以上に濃い時間を過ごした(?)の…

AOJ 2450 Do use segment tree

重い。ただただ重い。 #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 …

JOI 春合宿 2013 Day2

2時間45分で全完。 取れる問題ちゃんと取れたので良かった 建設事業 平面走査 + segtree + Kruskal + 貪欲 典型盛り合わせみたいな問題で難しいとは感じなかった。 struct edge{ int from,to; ll cost; edge(){} edge(int from,int to,ll cost):from(from),t…

解き初め JOI 2012春 Building 2

解き納めにするつもりやったのにくだらんバグで6分間に合わんかった…。 典型の組合せで綺麗。好き。 今年は最後の一年やから何事も悔いのないように全力でやり切ります。 難易度12は残り3問。 int N; int H[100100]; vector<int> up[100100]; vector<int> down[100100]</int></int>…

JOI2016 予選

JOI

最後のJOI予選、やるだけセットやったのに誤読で時間消費してデバッグギリギリ間に合わんかった。 しかもバグは2箇所!が|になってただけ。クソクソクソクソ。死にたい。 本選、春まで死ぬ気で問題解きまくる。 予選満点ちゃうかっても代表にはなったるからな…

PCK 2015 本選 参加記

激冷え。

PCK 2015 予選

PCK

9AC1WAでした。8間に合わなくて速度不足を痛感。本選までもっと実装力も発想力も鍛えます。 1~7を自分が解いて9をeyさんが解いて10を二人で解きました(eyさんが最初に解いたがWAが出て自分がデバッグした) 8ほぼ書き終わってたのに間に合わなくて辛い(Trieで…

AOJ 2436 Card

AOJ

だいぶ想定解まで迫ったものの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 …

AOJ 2256 Divide the Cake

AOJ

ケーキの端にイチゴが乗ってる時(sample1)の対処をメモ。 len(Y)は片方を(0,Y)に固定したときに等分できる右側の部分の長さを返す関数。 ただ、(0,Y)にイチゴがあると色々面倒なので+eps,-epsの2つに分けて処理した。 誤差怖かったけど通ったので良かった(…

AOJ 2313 Box Witch

AOJ

個人的にハマるポイントが山ほどあったので戒めのメモ。 まず、自分のライブラリはverify済でも信用してはいけません (まぁこれはverifyした後にちょっとわかり易くしようと書き換えた自分が悪いのでなんとも言えませんが) (でもまさかadd_edgeが間違ってる…

AOJ 2439 Hakone

AOJ

良問DPとして有名な箱根駅伝。結構考えましたがわからず解説を読んでしまいました。 JAGの解説が少しわかりにくかったのでここにまとめておきます。 順位表の'-'は確定するので無視します。 現在の中継地点の順位表を1位から順に見ていって、前の中継地点で…

閉路の偶奇

グラフの閉路を検出するのはDFSなりベルマンフォードなりで適当に出来ますよね。 今日奇数長の閉路の検出が出来ずに困ってしまったのでメモ。 全然今まで気付かなかったのですが 「偶数長の閉路しかない⇔2部グラフ」 です。あとはこれより、2部グラフかどう…

Counting Sort

ちょいちょい勉強したことでも書き留めておこうと思います。 Counting Sortというのを知りました。 sortなんてquick sortとmerge sortだけ知ってりゃ十分やとか思ってたんやけど、CFでこれを使う問題が解けんくて悔しかったから書いときます。 この方法は数…

JOI 春合宿 2010 Day 3

JOI

何日か前にやったのに書くの忘れてた 本選会場 うまいこと待ってやれば、最小全域木のコスト分しかかからない。K個まで分割することが許されるので、全域木に含まれる辺からコストの大きい順にK-1個とって木をK個に分割してやればいい。 int N,M,K; struct e…

JOI 春合宿 2008 Day 3 Origami

JOI

問題文はちゃんと読みましょう Origami,簡単だけど5ではないでしょ…— おくら (@okuraofvegetabl) 2015, 2月 22 ええええええええええ辺の長さ20cm以下とか聞いてないぞおおおおお— おくら (@okuraofvegetabl) 2015, 2月 22mapで数えるだけの問題を2次元座圧+…

JOI 春合宿 2010 Day 2

JOI

はい、2日目。 足し算 繰り上がりがあって、和が10を超えない時 繰り上がりがあって、和が10を超える時 繰り上がりがなくて、和が10を超えない時 繰り上がりがなくて、和が10を超える時 に場合分けしてやった。 最後に残った繰り上がりの1を忘れていてWAをは…

JOI 春合宿 2010 Day 1

JOI

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 2015 本選参加記

JOI

昨日までJOIの本選に参加していました。 結果からいうと一応通過しました。 去年こんな感じで(JOI 2014 本選 - (#・∀・)) この時の悔しさを噛み締めながら一年やって来たので、通過できたことは素直に喜びたいと思います。 2/7 potetiと一緒に新神戸から新幹…

2015年の目標

CF:赤 TC:赤 PCK:金 JOI:メダル獲得 IOIに行く

2014年を振り返って

一年前に 2014年 今年の目標 - (#・∀・) という記事を書きました。残念ながら全く目標を達成できませんでした(CFに関してはgood bye 2014で達成できたはずなのにくだらないミスでチャンスを逃しました)来年はかならず目標を達成して見せます(目標は来年発表…

PKU 3272 Cow Traffic

PKU

問題概要 N頂点のDAGが与えられる(多重辺アリ).入次数0のノードからN番目のノードまでの全てのパスを考える. それらのなかに最も多く含まれている辺の、含まれている回数を求めよ 辺a->bが含まれる回数は(始点からaまでのパスの総数)*(bから終点までのパスの…

PKU 3252 Round Numbers

PKU

問題概要 [Start,Finish]で、二進数で表記した時に0の数が1の数以上になるような数の個数を求めよ桁DP。やるだけ。なんでこれが8なんだろう(この前8のad-hocが自力で解けなかった) dp[i][j][k][l]:=今上からi桁目で、0の個数-1の個数がjでkはずっと上限でき…

Codeforces Round #284 B Name That Tune

問題概要 N種類の曲があり、それらを順番に流す。聞いている側が曲名が分かり次第流す側に伝える。 流す側は伝えられたらすぐに次の曲を流す。 各曲には認知度p[i]があり毎秒ごとにp[i]%の確率で、そこから1秒で曲名がわかる。 また、各曲の歌詞には曲名がは…

PKU 3612 Telephone Wire

PKU

クリスマスですね。日本語の解説記事がなかったので。 まずは普通に dp[i][j]:=i番目のポールを高さjにする時のそこまでのペナルティの合計の最小値 (不可能なときはINF)として漸化式をたててみると dp[i][j] = min{dp[i-1][k]+abs(k-j)*C | 0 となりますが…

JOI 2015 予選参加記

JOI

はい、というわけでもちろん今年も参加しました。 が、残念な結果に終わったので本選まで今まで以上に精進しようと思います。 適当な解説を書きます。テンプレはいつも通り省略してます 1.水道料金 (Water Rate) やるだけ。 int A,B,C,D,p; int main() { cin…

PCK 2014 本選 参加記

PCK

先日、PCK2014にチーム「三上」として参加してました。 色々あったので、箇条書きでつらつら書いておきます。 こんなにどうでもいいことをだらだら書いているのは、自分が読み返した時にいろいろ思い出せるようにするためです。冗長でごめんなさい。 Day 0 …

SRM 509 Div1 Med Palindromization

SRM

問題概要 回文をつくろう3280 -- Cheapest Palindromeに文字をchangeする操作が加わっている。 基本的にはその問題と同じように区間DPをする。 ただしchangeが加わっているため、changeしてからerase,みたいなことができる。 まずchange操作はワーシャルフロ…

SRM 512 Div1 Med SubFibonacci

SRM

問題概要 問題文を読んでください。まず数列を二つに分けて、それぞれの最大値の合計の最大値を求める。 分けたあとの数列の任意の2組を取ってきて、小さいほうを初項、大きいほうをx番目として、フィボナッチ数列を計算して、含まれる要素の数をかぞえる。(…

SRM 523 Div1 Med BricksN

SRM

dp[W][H]:=上からH段目まで横幅Wのブロックの置き方 #include <cstring> using namespace std; typedef long long ll; #define MOD 1000000007 class BricksN { public: ll num[55]; ll dp[55][55]; ll rec(int W,int H) { if(H==0||W<=0)return 1ll; if(dp[W][H]!=-1</cstring>…