問題 https://atcoder.jp/contests/abc167/tasks/abc167_c 解法 解法としては各本を買う/買わないで全探索するとO(M2^N)で解けます。 C_n A_n_mは型としては[(Int, [Int])]になります。各要素の(Int, [Int])は単位元を(0, 要素が0の無限リスト)、演算をfstは足す、sndはzipして各要素を足すとするとモノイドになりそうですし問題を解くのに使えそうです。このようになる(Int, [Int])のnewtypeは(Sum Int, Ap ZipList (Sum Int))になります。ApはApplicative fとMonoid aからMonoid (f a)を作るnewtypeです。ZipListはpureをrepeat x、liftA2をzipして関数適用というApplicative実装を持つListのnewtypeなのでApと組み合わせると欲しいMonoidが得られます。 ところでnewtypeの変換にはcoerceという関数が便利です。安全に変換できる

問題 https://joi2019-yo.contest.atcoder.jp/tasks/joi2019_yo_e 解法 まず{(L,R)}の前処理をします。 サイズNのリストを用意して自分が入っている区間[L,R]のうちRが最大のもので初期化をします。どの区間にも入っていなければ0です。 ただ普通に実装するとO(MN)で間に合わないので工夫が必要です。 まず{(L,R)}(以後LRと呼ぶ)をR→Lの優先順位で降順ソートします。 次に用意したリストを右から埋めていく(既に埋めた所は埋めない)をしていくとO(N)となり間に合います。 疑似コードは以下のような感じです。 let m_list = make_vec(init=0,len=N); my_sort(LR) // my_sortはLRをR→Lの優先順位で降順ソートする関数 let cur = N; for (l, r) in LR { for i in range(l,min(cur-1, r)) { m_list[i] = r; }

競プロで標準入力のパースがめんどうだったのでマクロ作りました。 AtCoderのRust(1.15.1)でテスト済みです。 ソースコード https://github.com/kgtkr/procon-lib-rs/blob/master/src/parser.rs 使い方 事前準備 標準入力を全て読み込む let text = { let mut s = String::new(); io::stdin().read_to_string(&mut s).unwrap(); s }; 例 入力値 5 10 20 1 a 2 b 3 c 4 d 5 e 1 2 3 4 5 input!(text=> (n:usize) (a:i64 b:i64) {n;list:(i64,#)} (arr:[i64]) ); assert_eq!(n, 5); assert_eq!(a, 10); assert_eq!(b, 20); assert_eq!(list, vec![(1,"a"

AGC024-A Fairnessの考察を頑張って書いたので残したいなと。 解説の解き方とは全く違う解き方をしたけど答えは同じになったので数学って凄いなと思いました(こなみ) あとwolframalphaってのが凄い。 複雑な式変形とか漸化式も自動で解いてくれる。競プロでDPしたい時とか使えそう。 って事で考察です。 k回操作後のa,b,cの値をそれぞれ fa(k),fb(k),fc(k) とする a,b,cはfa(0),fb(0),fc(0) を表す事とする 操作を行っていくとa,b,cはそれぞれ fa(0),fb(0),fc(0)=a,b,c fa(1),fb(1),fc(1)=b+c,a+c,b+c fa(2),fb(2),fc(2)=2a+b+c,a+2b+c,a+b+2c fa(3),fb(3),fc(3)=2a+3b+3c,3a+2b+3c,3a+3b+2c fa(4),fb(4),fc(4)=6a+5b+5c,5a+6b+5c,5a+5b+6c となっていく fa(k),fb(k),fc(k)のa,b,cの係数を (fa(

ABC100で水色になりました。せっかくなので色々振り返ってみようと思います 競プロを始めるまで 主にWebプログラミングをやってました。というか今もやってますし、ずっとこっちがメインです。 Webと競プロはかなり文化が違うので競プロはかなり戸惑いました。 かなり昔にpaizaとか少しやった記憶ありますが全く解けませんでした。 初めてのコンテスト 初めてのコンテストは9/23の「CODE FESTIVAL 2017 qual A」、たまたまTLに流れて来たちょくだいさんのツイートに反応したらリプとフォロー貰えて嬉しかったので試しに参加してみました。 言語はJS、結果は1完で初期レート14。流石に無理だと思いしばらく競プロは放置していました。 初めてのABC 12月頃になると、何故か競プロerとかなり関わるようになりました。そして12/23に始めてのABC、「ABC083」に参加しました。 結果は3完。思っていたより解けたので楽しくなってきてABCは毎回出るようになりました(今の所ABCは皆勤です)。途中でAPCも出ました。 Rust

初めに けんちょんさんの↓の記事の10問をScalaで解いてみました https://qiita.com/drken/items/fd4e5e3630d0f5859067 せっかくScalaで書くので変数の再代入、破壊的変更とfor/whileを一切使わずにやってみます。 テンプレート object Main{ def main(args: Array[String]){ if (sys.env.getOrElse("TEST", "")=="1"){ println(test()); }else{ val input=io.Source.stdin.getLines().mkString("\n"); println(solve(input).trim()); } } def solve(input:String):String={ input.split(" ").map(_.toInt).sum.toString() } val tests=Li