My Octopress Blog

Background

https://mcmanuslab.ucsf.edu/node/251 is a very useful information source about long non-coding RNA. Also, it is cited sometimes. However the citation format does not seem to be established.

Result

Title

The Dark Matter of the Genome or Long Noncoding RNA The Dark Matter of the Genome.

Author

The author should be Megan McSweeney as it is written in the slide.

Year

The slide says BMS265. According to https://mcmanuslab.ucsf.edu/rnas, it seems to be a course number in University of California San Francisco. BMS means Biomedical Sciences Graduate Program (https://bms.ucsf.edu/course-list). And there seemed to be BMS265 RNA wiki course around 2009 May. So the year should be 2009.

Conclusion

Megan McSweeney, Long Noncoding RNA The Dark Matter of the Genome, 2009

https://yukicoder.me/problems/2699

まず、pekempeyさんの解説にある以下の条件

0<=a1
0<=b1
a1+...+an==b1+...+bn
ai+bi<=a1+...+an for all i

をコードに落とし込むと以下のようになる。なお、a1==x, b1==y==x+sa-sbとする。

n=gets.not_nil!.to_i-1
a,b=n.times.map{gets.not_nil!.split.map &.to_i}.to_a.transpose
sa,sb=[a,b].map &.sum
p (0..10**6).count{|x|
  x+sa-sb>=0 && x<=sb && (0...n).all?{|i|
      a[i]+b[i]<=x+sa
  }
}

このコードを効率化したいわけだが、今回、範囲が

false
...
false
true
...
true
false
...

のようであるため、二分探索は使えない。別の方法で効率化を図る。

まず、少し移項すると以下のようになる。

n=gets.not_nil!.to_i-1
a,b=n.times.map{gets.not_nil!.split.map &.to_i}.to_a.transpose
sa,sb=[a,b].map &.sum
p (0..10**6).count{|x|
  sb-sa<=x && x<=sb && (0...n).all?{|i|
      a[i]+b[i]-sa<=x
  }
}

sb-sa<=x && x<=sbはxの範囲を示すから、これを使う。また、a[i]+b[i]-saは不変量なので、条件を整理する。すると、以下のようになる。

n=gets.not_nil!.to_i-1
a,b=n.times.map{gets.not_nil!.split.map &.to_i}.to_a.transpose
sa,sb=[a,b].map &.sum
p ([0,sb-sa].max..sb).count{|x|
  (0...n).map{|i|a[i]+b[i]-sa}.max<=x
}

これもxの範囲となるため、最終的に以下のようになる。

n=gets.not_nil!.to_i-1
a,b=n.times.map{gets.not_nil!.split.map &.to_i}.to_a.transpose
sa,sb=[a,b].map &.sum
p sb-[0,sb-sa,(0...n).map{|i|a[i]+b[i]}.max-sa].max+1

ここまで最適化されていれば、Rubyでも十分ACできる。

#!/usr/bin/ruby
n=gets.to_i-1
a,b=$<.map{|e|e.split.map &:to_i}.transpose
c,d=[a,b].map &:sum
p d-[0,d-c,*(0...n).map{|i|a[i]+b[i]-c}].max+1

重複を減らすと以下のようになる。

gets
m=0
a,b=$<.map{|e|e.split.map(&:to_i).tap{|a,b|m=[m,a+b].max}}.transpose
c,d=[a,b].map &:sum
p d-[0,d-c,m-c].max+1

そもそも配列を取っておく必要はなかったようだ。

gets
m=c=d=0
$<.map{|e|x,y=e.split.map &:to_i;m=[m,x+y].max;c+=x;d+=y}
p d-[0,d-c,m-c].max+1

Crystalも一応書き換えておく。

n=gets.not_nil!.to_i-1
m=c=d=0
n.times{x,y=gets.not_nil!.split.map &.to_i;m=[m,x+y].max;c+=x;d+=y}
p d-[0,d-c,m-c].max+1

最終的に関数型っぽいことはしなくても良くなったので、C言語でも書ける。以下のようになる。勿論ifはfmaxで書き換えても良いだろう。

m,c,d,x,y;
main(){
for(scanf("%d",&x);~scanf("%d%d",&x,&y);c+=x,d+=y)if(m<x+y)m=x+y;
x=0;if(x<d-c)x=d-c;if(x<a-c)x=a-c;
printf("%d\n",d-x+1);
}

以上、不変量を見つけてまとめることで計算量が減ってコードも短くなる過程を楽しんでいただけたなら幸いです。

数学ガールの秘密ノートポータル https://www.hyuki.com/girl/note.html

※cakesをブラッシュアップしたものが書籍になります(書籍化完了後の巻については、cakesは雰囲気を掴むための参考。巻によっては章の順序が違う場合すらあります)

cakes番号	巻名	URL	立ち読み
1	式とグラフ	https://note1.hyuki.net/	cakes https://cakes.mu/posts/435 達人出版会のサンプル http://tatsu-zine.com/books/mathgirl-himitu-formula-graph
2	整数で遊ぼう	https://note2.hyuki.net/	cakes https://cakes.mu/posts/966
3	丸い三角関数	https://note3.hyuki.net/	cakes https://cakes.mu/posts/1534
4	数列の広場	https://note4.hyuki.net/	cakes https://cakes.mu/posts/2093
5	微分を追いかけて	https://note5.hyuki.net/	cakes https://cakes.mu/posts/2658
6	ベクトルの真実	https://note6.hyuki.net/	cakes https://cakes.mu/posts/3337 SBクリエイティブ http://ul.sbcr.jp/MATH-8232-0
7	場合の数	https://note7.hyuki.net/	cakes https://cakes.mu/posts/4620 SBクリエイティブ http://ul.sbcr.jp/MATH-SJddk
8	(指数と対数)		cakes https://cakes.mu/posts/5506
9	(フラクタル)		cakes https://cakes.mu/posts/6259
10	(不等式)		cakes https://cakes.mu/posts/7139
11	ビットとバイナリー	https://note11.hyuki.net/	cakes https://cakes.mu/posts/7990 SBクリエイティブ http://ul.sbcr.jp/MATH-oPU7T
12	行列が描くもの	https://note10.hyuki.net/	cakes https://cakes.mu/posts/8952 SBクリエイティブ http://ul.sbcr.jp/MATH-PAwkh
13	やさしい統計	https://note8.hyuki.net/	cakes https://cakes.mu/posts/10035 BOOK WALKER https://bookwalker.jp/de7becb42b-6efd-45d7-8c23-41b3df8d3995/
14	積分を見つめて	https://note9.hyuki.net/	cakes https://cakes.mu/posts/11042 BOOK WALKER https://bookwalker.jp/de8a8b19a1-3ae8-4ce0-aeeb-48ddb16f990a/
15	波の広がり		cakes https://cakes.mu/posts/11927
16	数を作る		cakes https://cakes.mu/posts/12710
17	広がる複素数		cakes https://cakes.mu/posts/13400
18	論理と証明		cakes https://cakes.mu/posts/14173
19	いにしえの数学		cakes https://cakes.mu/posts/15062
20	整数に誘われて		cakes https://cakes.mu/posts/16037
21	関数を手がかりに		cakes https://cakes.mu/posts/17155
22	無限を探そう		cakes https://cakes.mu/posts/18339
23	関数を組み立てよう		cakes https://cakes.mu/posts/20592
24	群とシンメトリー		cakes https://cakes.mu/posts/21961
25	学ぶための対話	https://note12.hyuki.net/	cakes https://cakes.mu/posts/23227
26	確率の冒険		cakes https://cakes.mu/posts/24645
27	分数を極める		cakes https://cakes.mu/posts/25944
28	放物線をつかまえて		cakes https://cakes.mu/posts/27403

まあ、cakes番号と書籍番号の対照表を(私が)ほしかっただけなんですけどね–;;;

現在

A13 / TL40 / WL21 です

20190211

Trainer Level 39

20190418

TL40

20190611

会社で嘔吐し12・13が有給にww

20190613

SOV37でポケモンGoをやりつつSHV38でIngressをやるという廃人的行為を思いつく。ただ、周りにIngressをやっている知人は @leafaerosnow 氏のみであるため、陣営は氏と同じENL。~~ENLでのXMの利用目的から夜間飛行(花)を連想するほど私の頭は逝ってしまっているらしいってのもある~~
この日はアドベンチャーウィークの都合上50kmのボーナスのため、家から後楽園まで歩いた。ポータルがほとんどENLだったため、適当にリンクを張るだけで 一日でAccess Level 6まで 上がった。ラッキーだったと思う。

20190614

13日の時点で実際にはA7一歩手前だったため、A7になった。

20190624

AP 1.975倍 キャンペーンのおかげでA8に。脱初心者。
https://twitter.com/ingress/status/1142125061517787136

20190702

Wizarding Level 3

20190706

Rechargerメダルが金に。

20190707

WL10 (ここから急激に伸び悩む。まあゲームシステム的に致し方ない)

20190708

A9到達。

2019071x

SpecOpsメダルが金に。

20190801

WL15。無期休業。
A10到達。ポータル申請権獲得。

20190811

Sojournerメダルが金に。

20190914

Trekkerメダルが金に。山梨バス旅行中のできごとであった^^;;

20190915

Rechargerメダルが黒に。
A11到達。100日未満での達成成功。
ExplorerとTranslatorで取る予定としますか…。

2019101x

Explorerメダルが金に。
Translatorメダルが金に。
会社移転前に完了できて助かった…

20191120

A12到達。酉の市の日でした^^;;

20191211

Sojourmerメダルが白に。
夜に芝公園を徘徊。(その前にクリスマスマーケットに行ったついでにどれぐらいメダル進められそうかIntel Mapで下見しておいたんです)

20191212

神田明神を徘徊し、Pioneerメダルが金に。これで15までは確定。Sojournerを黒にできれば終わりなんですがどうですかねぇ^^;

2020011x

いつでも冒険モード実装につきWizards Unite仮復帰。

20200401

NL1331 Meetupが銅に。

20200418

コミュニティ・デイ中にWL20達成。

20200422

某公園が一面青だったためAPEXを適用しつつ焼き尽くしました(約70万AP獲得)。すみません。これでA13到達。
今こそAGにとって書き入れ時とかほざいたんは誰や苦笑
- まあ弊社はテレワークじゃないんで通勤途中はある意味しかたないが。

https://yukicoder.me/problems/no/3051

quineを生成して処理するのが一番楽なのでは。なおquine生成エンジンはrobustなもののほうが後処理が楽だと思います。

generation	machine
1	c
2	nc
3	sc
4	yc
5	gc

https://yukicoder.me/problems/no/796
和を3で割ったあまりが1で、数列のうち1要素が3…
っていうか1から100000までの和って312456超えますし…
よく見たら 相異なるって書いてない じゃん
[1]+[3]*(N-1)でいいのか。これ、国語の問題ですよね…

https://yukicoder.me/problems/no/795

テスターの感想としては、April Fool Contest向けの問題だったのではないかと思っています。まる。

なおくそまじめな実装は https://yukicoder.me/submissions/328688 です(筈)。

https://atcoder.jp/contests/abc116/tasks/abc116_d
持っている寿司のリストLと種類ごとの寿司の個数Cを用意する
おいしさの高い順にソートする
寿司を順番に見ていく。
すでに持っている寿司がK皿であるなら、
- すでにその種類の寿司を持っているなら無視する。(K皿でない場合は無視してはいけない。)
- Lを後ろから見ていき(j)、C[L[j][種類]]>1となっているものを探す。L[j]を取り除く。C[L[j][種類]]を1減らす。
見ている寿司をLに加える

このとき、「後ろから見てい」くインデックスjを最初にK-1で初期化したあとは初期化しないようにする。こうすることで、Lの各要素はたかだか1回しか舐められないことになり、十分高速となる。なおjが0未満になったら「順番に見ていく」こと自体を打ち切ることでプログラムが簡潔になる。

最初以外初期化が必要ないのは、あとから追加された寿司を取り除くことは絶対にないからである。

https://atcoder.jp/contests/abc116/submissions/4076962

https://yukicoder.me/problems/no/778

__gnu_pbds::treeで倒せます。ここでちょっとQK！の解説を参照ください。

答案 https://yukicoder.me/submissions/308223

How to Cite Mcmanuslab Long Noncoding Rna Article