・問題 Differential Pulse Code Modulation | Aizu Online Judge元の数列x(size y_0=128から始めて、y_1=y_0+C[k_1], ... , y_n=y_n-1+C[k_n]という容量で数列yを決定する。この過程で、yの値が0未満になるときは0、255より大きくなるときは255にyの値をそ…

・問題 Edit Distance (Levenshtein Distance) | Aizu Online Judge 前期の授業でやったレーベンシュタイン距離。・アイデア 空の文字列の状態から考えて、s1のi文字目までの部分列とs2のj文字目までの部分列に対して、挿入・削除・置換のいずれかの操作を行…

・概要 E: 常ならずグラフ - CODE FESTIVAL 2014 決勝 | AtCoder数列が与えられるので、大小がジグザグになるように数列の要素をいくつか削る。その削って条件をみたすようになったグラフのうちで要素が最も多いものの要素の個数を求める。・アイデア 数列の…

昨日は３時に寝た。月曜だけは１限から授業があるので一週間の中で一番早起きを強いられるのだが、今日は7時半ぐらいにすっきり起きられた(寝ていたい気持ちもあったが)。いつもは即目覚ましを止めてまた寝てしまうので、それよりは段違いにすっきりしている…

・問題 Pollock's conjecture | Aizu Online Judge・アイデア つい先日解いたコイン問題と全く同じ。クエリが複数あるが、どの数に対してもやるdpはかわらないのでクエリ処理に入る前に１回だけ最初にdpを回して用意しておく。・実装(C++)

・問題 D: へんてこ辞書 - AtCoder Beginner Contest 030 | AtCoder・アイデア まず、色々例とかを紙に起こしてみて有向グラフみたいイメージで考えられるんじゃないかって思った。 そして、かならず１つはループが生じるということもわかった。なぜなら木に…

・問題 Longest Increasing Subsequence | Aizu Online Judge特にいうこともない。解説は蟻本とこれ(http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=DPL_1_D)に投げる。 fillとlower_boundめっちゃ便利。(両方algorithm)・実装(C++)

・問題 Knapsack Problem | Aizu Online Judge前の問題から若干問題を変えて、１つの商品を何個でも入れることができるという制約に変わった。・考え方 前の問題に倣い、 dp[i][j]:=品物1~iの中から選び、ナップサックの大きさがjの時に入れられる商品の価値…

・問題 0-1 Knapsack Problem | Aizu Online Judgeいわゆる普通のナップサック問題。制約とかも普通。・考え方 dp[i][j]:=品物(i-1)まで入れるかどうか決まっていて、その時の重さがjの時の価値合計の最大値と定義して、全てやり終わった後にdp[N][i]の列をi…

DP力を高めるためにせっかくいい問題集があるのだから使ってみるという試み。今日からこれをやっていこうと思う。2日後にはコンテストなわけだが。。。・問題 Coin Changing Problem | Aizu Online Judgec1,c2, ... ,cm円というm種類のコインを使い、n円を支…

タイトルの通り。というか強いとかじゃなくて、説明を読んですんなり理解できるレベルになりたい。 この前のこどふぉも3完に終わり、4問目は想定解はDPでした。その問題の反省の記事を作ろうとして、いま解説記事などを読みながらでも理解できなくてつらい。…

最近涼しくなってきて過ごしやすいけど家から出たくない気持ちが強まってきた。 この前、高校の同級生が東京に来たので出かけてきた。スカイツリーの展望台に実は１回も行ったことがなかったので行ってきたけど350mとだけあって東京タワーとは眺めが全然違っ…