問題 E - All-you-can-eat 解説 他の回答を見つつ、公式解説の解法２に沿って回答を作成。 DP難しい。。。 fn solve(t: usize, abs: Vec<(usize, usize)>) -> usize { use std::cmp::max; let mut abs = abs; abs.sort_by_key(|x| x.0); let mut dp = vec
問題 F - Engines 解説 公式解説結構長めに書いてあるけど実装としては f64.atan2()で角度を求めてソート 連続的に取りうる組み合わせを全て試す これで で解ける fn solve(xys: Vec<(i64, i64)>) -> f64 { let n = xys.len(); let mut xys = xys; xys.sort_…
F - Enclosed Points 問題 TODO BIT 解説の前に今回のBITの使いどころについて軽く整理。 いまx座標で昇順に並べた点(例: ) があるとする。 BITを利用すると各点を原点として特定の象限に含まれる点の数を順に求めることができる。 例えば第3象限の場合は以…
E - Max GCD 問題 数列に対して、あるものにすると同時に、別の項にをするという操作をK回以下おこなって、取りうる最大のGCDを求めるという問題。 解説 ポイントは操作を行っても数列の総和は変わらず、かつ総和はGCDの倍数になっているはず、というところ…
E - Sequence Decomposing 問題 数列 が与えられたとき、数列を単調増加となるような部分数列に分けた場合に最小のグループ数を答える問題。 解説 公式解説には「広義の単調減少列の最大の長さ」を求めれば良いとあるが、ここがあまりしっくり来ていない。 …
F - Small Products 問題 正の整数K個を一列に並べたものであって、隣接して並んでいるどの2つの整数の積もN以下であるものの個数を109+7で割った余りを求めてください。 解説 公式解説にあるようにxが最後の整数となるようなi個の整数を並べて条件を満たす…
E - Friendships 問題 N頂点単純連結無向グラフで最短距離が2である頂点対がK個あるものを構築する。 解説 まず最短距離が2である頂点対が最大となるのはある１点（仮に「中心点」と呼ぶ）が他の全ての点と辺を持ち、それ以外の辺が存在しないときである。 …
D - Rain Flows into Dams 反省 二分探索で解けると思ったが、上限下限が決定できるような問題じゃなかった。 解説 に気づけたら実装は簡単。 fn solve(aa: &[i64]) -> Vec<i64> { let s = aa.iter().fold(0, |sum, i| sum + i); let x1 = s - 2 * aa.iter().skip</i64>…
AtCoder Beginner Contest 131 - AtCoder 反省 UnionFind木使うとかどうやったら思いつくんですかね…。 解説 参考: AtCoder ABC 131 F - Must Be Rectangular! (600 点) - けんちょんの競プロ精進記録 fn solve(xys: &[(usize, usize)]) -> usize { let n = …
Play2.0がついにリリースされました。早速ダウンロードしてかねてより興味のあったWebSocketで遊んでみようとしたところIteratee/Enumeratorなるものにぶち当たりました。 とりあえずソースを見てみるもののさっぱり理解できず、google先生に泣きついたとこ…
Scala Advent Calendar jp 2011の21日目の記事です。 最初に 『Scala実践プログラミング』に記載されていたCakeパターンの解説を読んで自分型の威力を思い知り、自分でも簡単な例で実践してみました。お題となる分割前のコードはこんな感じ。黒い四角がjkhl…
Scala Advent Calendar jp 2011の21日目の記事です。 最初に 『Scala実践プログラミング』に記載されていたCakeパターンの解説を読んで自分型の威力を思い知り、自分でも簡単な例で実践してみました。お題となる分割前のコードはこんな感じ。黒い四角がjkhl…
:powerモード使ってます。 scala> val code = "println(\"Hello, World\")" code: java.lang.String = println("Hello, World") scala> val Some(trees) = intp.parse(code) trees: List[intp.global.Tree] = List(println("Hello, World")) scala> val req …
先日Gnome3がリリースされた。ネットの評判を眺めてるとどうも芳しくはないようだが、個人的には気に入っていてすでにノートPCもデスクトップもGnome3になってしまっている。もちろん不満が全く無いかといえばそんなことはなく、細かい不満はいくつもある。 …
なにげなくScalaのコンパイラのソースを眺めていたときに見つけたコード // src/compiler/scala/tools/nsc/util/trace.scala object trace { def apply[T](msg: String)(value: T): T = { println(msg+value) value } // ... } なんてことないけど気の効いた…
常日頃名古屋鉄道（名鉄）で通勤しているが、JRに遅れることはや数年、名古屋市営地下鉄とともについにIC乗車券（通称manaca）が導入された。 そして前回やっと解像度がまともに表示できるようになったと、喜びの報告をしたVAIO YにはPaSoRi（ICカードリーダ…
去年VAIO Y(VPCY2)を買いました。 さっそくDebian(squeeze)を入れたもののKMSが有効だと起動時に画面がブラックアウトしてしまうという症状に遭遇、やむなくKMSを無効にして*1Xのドライバもvesaにしてどうにか使用していました。新しいカーネルがリリースさ…
@mzpさん主催の非公式名古屋Scalaに行ってきました。 前半は@yoshihiro503さんによるモナド講座。後半はCoq、F#、AmazonEC2、MessagePackなど「り、りろんはしってる」な話が飛び交ってました。モナド講座のなかでfor文のifはfilterが必要だったり、先頭に置…
(この記事は Scala Advent Calendar jp 2010 の5日目です。)Scala+Androidで過去にはまったことなどを小ネタとして紹介します。 Androidに限らず、JavaのライブラリをScalaから使用する上でも役にたつかも。 java.lang.Classのインスタンスを取得する Scala…
先週土曜日(10/9) [twitter:@mzp]さん主催の名古屋Hackathon「ラムダ村」にいってきました。自分はScala組([twitter:@maeda_],[twitter:@a_hisame],[twitter:@RKTM],[twitter:@fumokmm],[twitter:@papamitra])に参加しました。 最近はプログラミングというと…
前回(第11回)の名古屋scala勉強会の前半はfor式を肴にモナド三昧。『ふつうのHaskell』を発売直後*1に買ったものの途中で投げ出した自分はやっぱりチンプンカンプン。でもまぁチンプンカンプンなりにいろいろ教えてもらったので、それを頼りになんとかモナド…
