今年は長い１年だったように感じる。今年のはじめに成人式があったと思うと、かなり遠い昔のような印象を受ける。学校方面の課題をなんとかこなし続ける１年だったなあと思う。それでも、後期からは研究室に行ったり、３年になってからはプロコンやり始めた…

問題 http://codeforces.com/contest/608/problem/C 概要 n個のビーコンがあり、i番目のビーコンはは数直線上のa[i]の位置におかれ、b[i]の威力を持っている。このビーコンが作動すると、a[i]の位置から左側だけ、b[i]以内の範囲のものを破壊する。(これによ…

問題 B: ゲーム - Typical DP Contest | AtCoder 簡潔なのでまとめなくていいかと。 アイデア ゲームが進行し、Aの山の一番上がa[x]、Bの山の一番上がb[y]になっている状況を考える。 dp[x][y] := (上記のような状況での先手が取れる価値合計の最大値)として…

問題 http://codeforces.com/contest/606/problem/C 1~nまでの数字が1個ずつランダムに並べられている。これを昇順にソートしたい。1回の操作で、ある要素を先頭、または最後尾に移動させることが出来る。ソートするまでに必要な操作の最小回数は何回か。 ア…

色々あった。まず、昨日は友人に誘われてご飯を食べに行った。そこでは、色んな人の就活に対する意識だとかインターンの話だとかが聞けて、ああやるひとはやってんだなあって実感した。まあ良いモチベーションになるといいかなーと思いつつ、今の自分には技…

問題 Shredding Company | Aizu Online Judge 概要 6桁以下の数が書かれた紙がある。それを切って、いくつかの整数を作る。その整数の和がt以下になるもので、最大になる切り方を求め、その整数の組合せとその和を出力せよ。 ただし特殊な例として、どんな切…

問題 Butterfly | Aizu Online Judge 概要 n人の男とのデート予定がある。 デート予定は1時間区切りで6~22時の間で、複数の区間になることもある。 (例だとAdamは10~12,14~16でBobは12~13,18~20) それぞれの男からは全てのデート予定をこなすと満足度Liを得…

問題 http://codeforces.com/contest/599/problem/D今回はA,B,Cで3完できたと思ったらBで若干考え違いして落としてしまった。Dは考え方は合ってたけど最後の詰めが甘かった。つらい。こういう考えついた問題をACに持っていけるようにしたい。。。 概要 自然…

・問題 Dessert Witch | Aizu Online Judgeようは貪欲にやるオセロ。問題文に書かれていることを素直にシミュレーションすれば出来る。久々にこういうただただ書くのがめんどくさいやつをやった。・実装(C++)

問題 Cut the Cakes | Aizu Online Judge 問題に書いてある通り。条件がめっちゃ小さい。 アイデア 図ではそれぞれの切られた長方形がくっつけられて書かれているが、結局1回ごとのカットは識別番号iに対してのカットなので、別に長方形同士がくっついている…

・問題 http://codeforces.com/problemset/problem/596/C・概要 xy直交座標平面上に点がn個ある。x座標、y座標は共に0以上。 n個の点に、1~nの名前を付けたい。ただし条件がある： １．点(x,y)にiの名前をつけるとき、(x 要するに、1~nの名前をもつ点(x,y)を…

こういうプロコン系のオンサイトは初めて参加しました。プロコン歴はまだ8ヶ月ぐらいだし全然つよくはないけどとても楽しめました。＜予選＞ A：全完がデフォでありながら、３完しかできず300点、262位、また普段とは比べ物にならない程の参加者にビビる。(…

・問題 https://community.topcoder.com/stat?c=problem_statement&pm=14076 なんかレイアウトが崩れている気がするが...(2015/11/4 Chromeで見た)直ってた(2015/11/6) めっちゃ文章長くて問題の把握に時間かかった。そこも含めて慣れていきたい。・概要 n人…

今年も残すところ60日くらいなんだと思うと心が痛む。この時期になるとセンター試験を思い出す。身の周りに受験生が数人いるので自分に直接関係は無いけど気になる話題ではある。ただ、「あ〜懐かしいな〜xxx点だったわ〜」みたいな人はそんなに好きじゃない…

・問題 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とだけあって東京タワーとは眺めが全然違っ…

・問題分 D: 1 - AtCoder Beginner Contest 029 | AtCoder・アイデア 各桁ごとに数字の現れ方に規則性があるから桁ごとに注目して数え上げればいいじゃんってのには気づいたけどそれをうまく実装できなかった。解説スライド(http://www.slideshare.net/choku…

8月末でこんなにスッキリしていただろうかと思えるくらい過ごしやすい。夜は。 最近は甲子園が終わり(今年は自分の地元がいいとこまで行ったので結構見てしまった)、サークルも一段落して１人で引きこもり生活していたのだが、先日友達が遊びに来てくれたの…

これまでソシャゲを敬遠してきたのは、「絶対にハマってしまう予感がしていた」からであって、嫌いだったわけではないのでコンスタントにプレイしている。といってもやっているのはツムツムだけで、GWに母親に薦められてついに始めてしまったという感じだっ…

・問題 B: 難易度 - AtCoder Regular Contest 043 | AtCoder・感想 これはDPだなーとコンテスト中に問題見て思った。しかも私でもすぐ気づく感じなので、割と典型な感じの。ただ、DPを実装するにあたって、私はメモ化再起でしか書けなくて、dpの配列をforル…