tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

100年分の一次遷移の観察

この記事は 今年読んだ一番好きな論文2017 Advent Calendar 2017 - Adventar の13日目の記事です。

はじめに

こんにちは、tozangezanです。Twitter上で🐺でも学部生でも参加できるそうなので、参加してみることにしました。

このブログの他の記事をみればわかると思いますが、普段はプログラミングコンテストで時間を溶かしたり、各地に(コンテスト目的で)遊びに行ったりしています。ただ、僕の専攻は生態学なので*1、今回は生態学に関連する論文です。

論文の概要

Buma, B., et al. 2017. A foundation of ecology rediscovered: 100 years of succession on the William S. Cooper plots in Glacier Bay, Alaska. Ecology, 98(6), pp. 1513–1523.
です。内容を簡単に表すと、100年以上前に氷河が溶けた土地で植生がどう変化していくか(一次遷移)を数十年間調査していた調査区域を、このたび再発見したので追加で調査することで100年以上の一次遷移の観察結果を得ましたという話です。一次遷移を定点観測した研究の中では最長のものの一つとこの論文では主張しています。

遷移...?

まず、一次遷移という言葉がありますが、これは何でしょうか?
ここで扱う遷移というのは、ある土地における(しばしば年単位での)植物相の変化を言います。よく高校生物の教科書で例として登場するのは、火山活動によって地表が溶岩に覆われた場所から、コケ類などが他所から移入し、しばらく生えたり枯れたりすることで薄い土壌ができます。すると草本類が生育するようになり、より地中の栄養が増えていきます。栄養が増えることによって低木が成長できるようになり、しばしば新たに住み始めるようになった鳥などによって種子が運ばれるなどして、高木が成長可能になる土地となる、という数百年にわたる時間変化です。これは一次遷移です(下図を参照)。

https://media1.britannica.com/eb-media/97/95197-004-7F9B8F09.jpg
(https://www.britannica.com/science/ecological-succession より引用)

これはしばしば否定的な意見もありますが*2、どういう環境にどういう植物種が存在するかを考えるにおいては、非常に重要な傾向です*3

一方で、二次遷移というのもありますが、これは山火事が起こった後など、土壌が存在している状態から遷移が始まるパターンで、こちらは栄養分が十分であったり、土中にすでに種子が存在してたりするために、一次遷移よりも短時間で遷移が進みます。普通こちらの方が頻繁に見られます。

https://media1.britannica.com/eb-media/98/95198-004-2619E3FA.jpg
(https://www.britannica.com/science/ecological-succession より引用)

今回の研究は、一次遷移を追ったものなので、最初土壌は存在しません。生物種の移入と土壌を蓄積していくことによって、ようやく遷移が進みます。

どうやったらこんなこと調査できるのか?

上にも書いたように、遷移の研究というのは百年単位での時間を追う必要があります。「今から100年間調査できるわけねーだろ頭冷やせ」と思いますよね? しかし、上手いことして100年間使わずとも100年分の遷移結果を見ることはできます。

f:id:tozangezan:20171203174653p:plain

火山の噴火の時期とそれぞれの噴火においてどこが溶岩に覆われたかの記録があれば、異所的だが同時的に「噴火からの年数ー植生」の対応を見ることができ、長期間にわたる調査をしなくとも遷移の様子がわかるとされ、国内でも調査が行われてきました(参考: https://www.jstage.jst.go.jp/article/vegsci/29/2/29_KJ00008519581/_article/-char/ja/)。

しかし、この方法には問題点もあります。一つ目の問題点は、同所的でないために、環境の差、それも地形や水の量などが異なり、それぞれ別の環境に適応した種が入ってきている可能性があること。もう一つの問題点は、仮に全く同じ初期条件であったとしても、「どちらの種が先に移住してきたか」などによって行き着く先が大きく変わる可能性があることが挙げられます。下の図は、遷移そのものの図ではありませんが、わかりやすくたとえたイラストです。

f:id:tozangezan:20171206003242p:plain
上の図は、ある種が移入すると、その種が自種が有利なように環境を作り変えることにより、後から競合種が入れなくなるということ*4を、ゲームが好きな人(左)とパーティーが好きな人(右)のどちらかが偶然先にテナント募集の店に移入してくることにより、各自が好きなような店に作り変えることで、後から移入してきた人が定着できなくなる様子を示しています。

このような初期状態のランダムな微小差から数十年後の植物相に大きな違いを生む場合は、異所的で同時的な調査の結果をそのまま遷移の結果と解釈することは、不適当だと考えられます。優占種A→優占種B→優占種A→優占種Bという遷移を起こすと思われていたものは、偶々Aが優占した後そのままの場所と、偶々Bが優占した後そのままの場所を交互に見てしまっただけかもしれません。

こういった問題点を解決する方法として今回登場するのが、特に頭のいい方法とかではなく、時間の暴力です

調査地

Google マップ

このあたりに調査プロットが8個あります。周囲から到達が困難であるため、人間活動はほぼありません。

1916年にWilliam S. Cooperという人が9個のプロットを設定し(そのうち1個は侵食で消失しました)、その時は氷河が溶けて地面が露出してから17〜37年経っていました。Cooperはこのプロットで調査を続け、その後は彼の弟子であった Donald B. Lawrence が調査を続けていました。しかしながら、Lawrence の死後、後継者に引き継ぐことがかなわず、調査プロットの位置はわからなくなってしまいました! 今回の研究は、このプロットの箇所を見つけることから始め、後世に残すために記録すると同時に、植物群集の構成や土壌の物質構成を調査し、地形や地面が露出してからの年数がどのような影響を及ぼしているかを明らかにしようというものです。

調査結果

調査プロットを探し当てることに関しては、こんな感じだったようです。

After some difficulty, plots were redis- covered using the original compass directions from Cooper (1923),

お疲れ様です。ところでプロットの詳細な位置は、幸い石に色を塗って印をつけたようで、それで正確に再現ができたようです。よかったですね。
そして以下の画像が定点観測をした写真です。(1879年に氷河が解けた場所)

f:id:tozangezan:20171206225333p:plain

かなり綺麗に遷移が進んでいることを実感できる写真だと思います。それにしても一次遷移は最初の草地ができるまでが本当に長いですね。ここだけで70年近くかかっているのではないでしょうか。

という表面的な話はこのくらいにしておいて、実際に植生変化がどの程度起こったのか、定量的に見ていくとこのようになりました。

f:id:tozangezan:20171207000250p:plain

まず全体的な傾向から。今回の調査によって増えたのは右の3列、100年以降の点です。ここで明らかになったのは、100年以上経ったときは、もはや最初の数十年の差は重要ではないことです。
紫色の線について: 出現する総種数は、年を経るごとに大きくなっています。ただし、これだけで安易に生物多様性が上昇したとはいえません(後述)。
オレンジ色の線について: Salix(ヤナギ)の割合は、最初は(ないので)同じですが、ある程度以上に上昇すると、後に100年が経過しても割合が減少しません。その一方で、50~60年程度経過した時点でヤナギの割合があまり高くない場所では、植生遷移が進みSalixが他の種にとってかわられています。
緑色の線について: 遷移初期に生えるバラ科の草本やコケ類(、それからヤナギ)などの割合ですが、遷移が進むとともに減少していき、2016年になるとヤナギ以外は存在が確認されなくなっています。遷移初期にバラ科の草本やコケ類が多い場所では、ヤナギが生えにくいことにより、後々高木が優占する環境に遷移しやすいということです。

種多様性に関して

f:id:tozangezan:20171207003752p:plain:w300
いずれの数値も、高い方が種多様性が高いことを表しています。PIEは「ランダムに2個体とってきたとき、その2個体が違う種である確率」、ENSは「PIEが同じで、出現頻度が等しくなるように種を割り振るとしたら、何種が存在することになるか」という値です。
なぜ種数が増加しているのに多様性が減少しているのかというと、一部の優占種が増加する一方で、多くの種は希少で、限られた場所にしか生息していないことに因ります。

土壌の状態

時間が経つにつれ窒素量が増加するが、ヤナギが優占しているプロットにおいては窒素量が低く、結果としてC:N比が高くなる傾向にありました。

結論

数十年の差は、100年以上経つ頃にはほとんどなくなる。

おそらく、最初の方が植物の1世代が短いために違いが大きく見えるのですが、徐々に1世代の長い植物が優占するにつれ、小さな年数の違いが影響しなくなる、地理的な影響の方が大きい違いを起こしている、などに起因するものだと思われます。

ある時期の植生の違いが大きく影響している。これは地理的な違いが原因。

ヤナギ優占の領域では、その後の植物の置きかわりが少なく、ヤナギが優占したままです(ただし、このまま永遠にヤナギ優占かどうかはまだわかりません)。そうでない領域では、いずれトウヒ属が成長するということです。

これら2つの結果について、原因として考えられる環境の違いについても触れられています。これらは、種子の移入速度と、氷河の後退速度の関係が原因だと議論されています。この場所を優占しうる植物としては、もっとも遷移初期に現れる特性を持ったヤナギ属、比較的遷移初期に現れるハンノキ属、遷移後期に現れるトウヒ属の三つとされますが、ヤナギ属はこの中でももっとも種子が軽く移入率が高いです。氷河の後退速度がハンノキ属・トウヒ属の種子拡散速度よりも速い時は、余った場所にヤナギ属だけが入ることになり、結果的にヤナギ属の優占を引き起こします。ヤナギ属優占では、光制限などによって新たにトウヒ属などの実生が成長しにくいことにより、なかなか遷移が進みにくくなります。しかし氷河の後退速度が早くなければハンノキ属も移入が可能となり、ヤナギ属の優占が抑えられ、その後トウヒ属が現れることができます。

光制約によって成長の遅い遷移後期種が加入できない状況は、この「初期状態の小さな違いがしばらく経ったときに大きな違いになる」例だと考えられます。これは同時的で異所的な遷移の研究が検出できないことですね。priority effect (早い者勝ち) も光制約など、こういった原因によるものが多いのでしょう。

ヤナギ属の優占場所は、生産性が低い。

この違いを生み出しているのは、ハンノキ属のフランキア共生菌でしょうかね。国内でも窒素固定のためにハンノキ属を育てることも行われているくらい(参考)なので、これは生産性が高そうです。
これに対してヤナギ属は、窒素固定力が低く、ヤナギ属優占の場所では窒素量が他と比べて顕著に少ないです。

100年は短い。もっと長いスパンで調査する必要がある。

ヤナギ属が存在する状態では本当に永遠に他の植物が優占種にならないのか? トウヒ属が優占した後、トウヒ属にさらに取って代わる植物が存在するのか? 再び撹乱が起きたらどのような反応をするのか?
まだまだたくさん未解決の問いは残っていますし、一応世界一長期間にわたって調査されてきた一次遷移の調査プロットといわれています。どうか、これからも頑張ってください。

おわりに

卒論の提出期限が近いのに、一体何をやっていたのでしょう。しっかり論文を読み込んでから何を書くかピックアップして、他の研究をあさったりして、お絵描きをして、大変なアドベントカレンダー企画でした*5

研究といえば、最近研究室で料理をするのにハマっています。普段はうどんを茹でて気が向いた具材(スパゲッティのソースとか、お茶漬けとか、豆腐とか)とかを入れて美味しいか美味しくないかをやってるんですが、この前はすき焼きのタレを入手したので普通に鍋をやってみました。普通に美味しいです。生協で買うより安いのが重要。
研究室料理アドベントカレンダーとかがあったら面白いかもしれませんね。

f:id:tozangezan:20171211163742p:plain
*6
大変だったので賞ください(クズ)

*1:大概ここで驚かれます

*2:山火事や倒木や土砂崩れなどが、ランダムに起こることによって再びこの遷移の途中段階の場所を作り出すので、遷移というのは終わりがあるものではありませんし、このような途中段階に適応した植物というものが存在できるのは、こういう大小様々な撹乱のおかげです。

*3:理論系の研究をしているので数式で何かを説明されるのが好きなのですが、そういう人へのオススメとして、Michel Loreau の From Populations to Ecosystems Theoretical Foundations for a New Ecological Synthesis という本を挙げておきます。遷移の話は6章で扱われています。

*4:実はこういうことを数理モデルを用いることでも考えることができて、これは僕の研究テーマの一部です

*5:今までで一番大変だったアドベントカレンダー企画は去年のCompetitive Programming Advent Calendarで海外参加者とかを集めてみんなにインタビューして、それを記事にまとめたものでした。その次に大変だったのは一人で25記事書いたやつでした。

*6:The American Naturalistでよくある尺余りを絵で埋めるやつ

競技プログラミングの裏技!? 誰が解いたかの情報から問題の傾向は予想できるか?

adventar.org
もうちょっといいネーミングは無かったのでしょうか。

おことわり

今回の記事にデータ源として登場する人は、新AtCoderのコンテストに20回以上参加した人のうち、だいたいレートが2700以上とかの人だけです。

APIとかの使い方がわからないので、手作業で集められる範囲で許してください。

はじめに

ある程度プログラミングコンテストに出ていると、限界を感じます。具体的には典型を全部把握していて過去に見たことがあるような問題ならゼロ時間で解けるのに、ある程度典型から外れた瞬間全く解けなくなるというやつです。AGCやCode JamのRound 3以降で顕著です*1
だいたいそこからできることというのは、爆速でコーディングを上げる能力と、ズルです。ただしAGCにおいてはコーディング量が元から少ないので、爆速でコーディングして変わる時間がほぼありません。困りました。残された道はズルです。

ズルと言ってもやってはいけないズルとそうでないズル、あとグレーゾーンなズルがあります。グレーゾーンなズルは白黒はっきりさせたくないのでここでは割愛します。やってはいけないズルというのは、他の人と解法を共有する・サブ垢を作ってACしたものだけを送ることでペナルティを解消する・ジャッジキューをつまらせて他の人を妨害して順位を上げる、などです。やってもいいズルというのは、戦略の中に収まるものから順に、証明しないで正しいと思う・順位表を見て解いている人の集合から問題ジャンルを予想する・定数倍改善・input解析(この二つは最近結構難しいです)・嘘だとわかっているがどうせ落とすデータはないだろうと思って提出する・OEISを見る・問題名やキーワードを検索し、同じ(部分)問題を探す、とかでしょうか。

嘘解法対策などは、昔に比べたらどこでもある程度対策されていると思われます。しかしながら未だに変なオーダーで解いたり、TLEした1ケースはどうせ○○だからあらかじめこのケースだけ埋め込んで置けばOKとか、変な解き方をすることは十分可能です。現に僕はAtCoderでよくtesterをしているのですが(これは言ってもいいよね)、tester中に思いついた変な解法を出すことで、「じゃあこういうケースを足してこれを落とそう」とか「問題設定をちょっと変えてOEISに出てこないようにしよう」といった改善がされることも多いです。

OEISについてだけは少し触れておきましょう。OEISは、使い方に慣れてないと見落としが多いかもしれません。たとえば、そのまま実験した結果だと検索しても出てこないけど2^nで割ったら出てくるとか、(2^n)(n!)で割ったら出てくるとかはよくあります。2変数の数列(さすがに(i≤j)となる(i,j)のペアにしか定義されないものがほとんどです)も実はOEISに相当数入っています。いろいろ割ったり足したり引いたり掛けたり差分を取ったり2変数のものを1次元に押しつぶしたりして、いろいろ検索を掛けてみることはとても大事です。

それでは本題に入りましょう。

本題

過去の「Aさんが問題Bを解けたかどうか」データから、特徴を見つけていきましょう。統計に弱いので*2、変な方法でもお許しください。生データは欲しい人がいたらあげます。

使ったもの

  • AGC001~019とMujin, Code Festivalの予選二年分の各問題に対し、AtCoderのレート上位で20回以上コンテストに参加した人が「開始1時間以内に解いた」「1時間経ってから解いた」「解けなかった」に分類したデータ
  • 欠測値があるデータにおいて主成分分析するRのライブラリ
  • 時間

結果の鑑賞

とりあえず鑑賞してください。

データシートの様子

f:id:tozangezan:20171209165032p:plain

PCA 1軸/2軸

f:id:tozangezan:20171209165252p:plain

さすがにわかると思いますが1軸はだいたい問題の難度に対応していて、これを見ることは今回の趣旨ではない上、問題についた配点をみればいいだけの話なので、この軸は無視しましょう。

PCA 2軸/3軸

f:id:tozangezan:20171210002122p:plain

よくわからん... 一部やたらと遠くに位置していることがわかると思いますが、なぜだかわかりません(antaさんはわかる気がする)。不思議ですねえ。
不安定感というか、独特の解き方になっている人が外側にいるのかもしれません。この人たちが解いているかどうかはあまり参考にできないということでしょうかね。

PCA 3軸/4軸

f:id:tozangezan:20171209165751p:plain

何か特徴があるのかないのか、よくわかりません。問題のほうの外れ値も調べてみればわかると思いますが、別に変な問題とは思えないものばかりでした。

クラスタリング

PCAで出てきたうち2~6軸でWard法を使いました。こういうことって統計的に正しい操作なのかなあ

f:id:tozangezan:20171209165912p:plain

わりかしこれは、僕が順位表を眺めるときに使う戦略(この人が解いてたから自分も解けるはず)に近い気がします。真ん中の僕がいるあたりが低配点・典型系の安定性が高い人で、右側の人が高配点か非典型に強い感じですかねえ。左側の人たちはそれぞれの距離がかなりありますが、それもなんとなく納得いきます。

クラスタリング 問題

同様のことを問題についてしました。

f:id:tozangezan:20171209170355p:plain

ここで注目して欲しいのは、複数回writerをやった人の回が、別に近い場所にいるわけではないということです。若干DEGwer回とsemiexp回がそれぞれの中でまとまっているようにも見えるのですが、気のせいの範囲だと思います。

参考 AGCを2回以上開いた人
sugim48: 2, 4, 6, 8, 16
DEGwer: 3, 9, 15
yutaka1999: 10, 14
semiexp: 11, 17
maroonrk: 13, 18

まとめ

仮説1. 「誰が」解いているのかを見る価値はあるだろう

僕のフィーリングでしかなく根拠は特にありませんがなんか変なことしたらきちんとした数値として出てくるかもしれません。上の結果だけでも、例えばクラスタリングの木で遠く離れた人が解いていても特に気にしない、とかには使えそうです。
現に個々人の「知識量」とか「実装の速度」とかを知ってると、この人が解いたから変な知識ゲーではない、とか、この人が一瞬で解いたから実装が少ない、とかはありそうです。なんどもコンテストに出ることで世界中の多くの人の問題の解き方データベースを貯めることにより、競プロ力も上がるかもしれません。これ以上書くと順位表非公開コンテストとか増えそうだからこれくらいにしておこう。

仮説2. writerと参加者の相性というのは、思っているほど大きくはない? writerによりけりという可能性もある

writer によりけりという説を推していきます。少なくとも僕はDEGwerセットが苦手だと感じているし、semiexpセットとかsnukeセットとかは得意だと思います。
それに、明確にwriterが偏った問題ジャンルを出すこともあります。AGCでない例を挙げますが、tozangezanというwriterが難問枠で数え上げ以外を出したことがあったでしょうか。あったら教えてください。

おわりに

いかにも即席感溢れるAdvent Calendar記事なのは、3日後に控えた 今年読んだ一番好きな論文2017 Advent Calendar 2017 - Adventar にも参加予定でこっちばっかり真面目にやってるからです。許してください。3日後に各記事はこれよりずっと中身がある記事だと思うので是非とも読んでくれたらと思います。投票とかあったら投票協力してね!(クズ)

データ

やっぱデータ置いとこ→ advent calendar - Google スプレッドシート
このレート帯でAGC皆勤賞が居ないのは、面白いかもしれません。

*1:TopCoderTCOのR2,R3以降はそうかもしれません。少なくともSRMのMediumまではパターン系問題がごまんとあります。

*2:生態学やってて統計に弱いのはいかんでしょ

DDCC 2017 決勝

ブログを最近書かなさすぎで変な広告まで登場する有様なので、渋々記事を書く。

A

まあこれは良いでしょう。

int main(){
	int a;scanf("%d",&a);
	int A=0;
	int B=0;
	for(int i=-100;i<100;i+=a){
		for(int j=-100;j<100;j+=a){
			if(i*i+j*j<=10000&&(i+a)*(i+a)+j*j<=10000&&i*i+(j+a)*(j+a)<=10000&&(i+a)*(i+a)+(j+a)*(j+a)<=10000)A++;
		}
	}
	for(int i=-150;i<150;i+=a){
		for(int j=-150;j<150;j+=a){
			if(i*i+j*j<=22500&&(i+a)*(i+a)+j*j<=22500&&i*i+(j+a)*(j+a)<=22500&&(i+a)*(i+a)+(j+a)*(j+a)<=22500)B++;
		}
	}
	
	printf("%d %d\n",A,B);
}

B

よく考えて解いてないのですが、制約から素因数分解ができないとわかるので、GCDとLCMに収まると思えばこのくらいしか選択肢がありません。

long long p[110000];
long long gcd(long long a,long long b){
	while(b){
		a%=b;
		swap(a,b);
	}return a;
}
int main(){
	int a;
	long long b;
	scanf("%d%lld",&a,&b);
	for(int i=0;i<a;i++)scanf("%lld",p+i);
	long long ret=1;
	for(int i=0;i<a;i++){
		long long g=gcd(b,p[i]);
		ret=ret/gcd(ret,g)*g;
	}
	printf("%lld\n",ret);
}

C

これについて何も書かないとこの記事の存在意義がないので、これについては何か書きます。

もし辺を編集することが全くできないのなら、この問題は簡単で、1回DFSをするだけで良いです。(ある頂点から始めて、今までにたどった重みの和を持ちながら辺をたどっていきます。辺の行く先がすでに通ったことがある頂点だったら、その頂点までの重みの和と今回の和が同じかどうかをチェックします。全部同じだったら全部の閉路について和が0です。)
辺を編集する場合ですが、基本的に編集する代わりにその辺を見なければいいです(全部の頂点に和が計算できていれば、そこの辺のコストは差で計算できます)。ただ、変なたどり方(毎回頂点1からDFSするとか)をすると、その辺が存在しないことで到達不可能な頂点が出てきてしまったりしてまずいので、必ずその見ない辺の行き先からDFSをスタートする必要があります。(行き先からDFSをスタートすると全頂点に値がつけられるというのは、強連結性のおかげです。)

さて、一番本質ですが、この同じ行き先の辺を消すパターン全てを1回にまとめて判定することができます。というのも、別に辺を消す処理が頂点までの和の値とかに影響を与えることはないので、実際にたどってみて「この辺が存在するとマズイ!」って時だけ消したことにすればいいからです。
で、消す辺がどれかとかが重要なのではなく、消す必要がある辺が1個以下であることが大事で、各頂点からDFSをしていき、消すべき辺が1個以下なことが1回でもあったらYESです。そうでなければNOです。

下の実装ではよく整理していないせいで逆辺を辿っていますが、上に書いた解法と何ら変わりありません。辺の向きを全部逆にしただけだと思います。

vector<pair<int,int> > g[310];
vector<pair<int,int> > rev[310];
long long deg[310];
int v[310];
int T;
bool dame=false;
int cnt=0;
void dfs(int a){
	v[a]=1;
	for(int i=0;i<rev[a].size();i++){
		int to=rev[a][i].first;
		if(v[to]){
			if(to!=T&&deg[a]+rev[a][i].second!=deg[to])dame=true;
			else if(deg[a]+rev[a][i].second!=deg[to])cnt++;
			continue;
		}
		deg[to]=deg[a]+rev[a][i].second;
		dfs(to);
	}
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q,r;
		scanf("%d%d%d",&p,&q,&r);p--;q--;
		g[p].push_back(make_pair(q,r));
		rev[q].push_back(make_pair(p,r));
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++)deg[j]=v[j]=0;
		T=i;
		dame=false;
		cnt=0;
		dfs(i);
		if(!dame&&cnt<=1){
			printf("Yes\n");return 0;
		}
	//	printf("\n");
	}
	printf("No\n");
}

まとめ

まあこんなんで3位で10万円分のパソコンが買えるというのは不思議だと思っているのですが、後から振り返ってみるとCの思考の分量というのは決してやるだけ、無ということはなくて、ただやるべきことが瞬時に見えていた感じがします。Div1Easyみたいな難しくないものを高速で解くのは昔から得意なんですが、それが如実に結果に反映される問題セットでしたね。
Dみたいなのは日本人はみんな苦手でかつ難易度を過小評価されがちな問題なので、セットとしての解かれなさもよく分かります。

それより、何か10万円強くらいのパソコンでおすすめのものがあったら教えてください。切実。

todo

hogloidの 個人的良問リスト - hogloidのブログ を解いたら消していく
解いた日付
難度 (1)~(5)
面白さ [1]~[5]
他に良問まとめがあったらコメントしてくれると助かります

http://www.codeforces.com/contest/258/problem/D 2017/07/25 (3) [3]
http://codeforces.com/contest/193/problem/D 2017/07/26 (2) [3]
http://codeforces.com/contest/121/problem/E
http://codeforces.com/contest/191/problem/D
http://codeforces.com/contest/183/problem/D
https://community.topcoder.com/stat?c=problem_statement&pm=12378&rd=15487
https://community.topcoder.com/stat?c=problem_statement&pm=12379&rd=15487
http://www.usaco.org/index.php?page=viewproblem2&cpid=225
http://www.usaco.org/index.php?page=viewproblem2&cpid=229
http://www.usaco.org/index.php?page=viewproblem2&cpid=231
http://codeforces.com/contest/264/problem/D
http://codeforces.com/contest/264/problem/E
http://codeforces.com/contest/261/problem/C
http://codeforces.com/contest/261/problem/D
http://codeforces.com/contest/261/problem/E
http://codeforces.com/contest/266/problem/E
http://codeforces.com/contest/269/problem/D
http://codeforces.com/contest/269/problem/C
http://main.edu.pl/en/archive/oi/19/fes
http://main.edu.pl/en/archive/oi/19/lit
http://main.edu.pl/en/archive/oi/19/odl
http://main.edu.pl/en/archive/oi/19/tou
http://main.edu.pl/en/archive/oi/19/bon
http://main.edu.pl/en/archive/oi/19/sza
http://main.edu.pl/en/archive/oi/19/squ
http://main.edu.pl/en/archive/oi/19/wyr
http://joi2013ho.contest.atcoder.jp/tasks/joi2013ho4
http://joi2013ho.contest.atcoder.jp/tasks/joi2013ho5
http://main.edu.pl/en/archive/oi/19/hur
https://community.topcoder.com/stat?c=problem_statement&pm=12364&rd=15488
http://codeforces.com/contest/273/problem/C
http://codeforces.com/contest/273/problem/D
http://codeforces.com/contest/273/problem/E
http://www.usaco.org/index.php?page=viewproblem2&cpid=248
http://www.usaco.org/index.php?page=viewproblem2&cpid=249
http://main.edu.pl/en/archive/oi/19/pre
http://main.edu.pl/en/archive/oi/18/kon
http://main.edu.pl/en/archive/oi/18/pio
http://main.edu.pl/en/archive/oi/15/pod
http://main.edu.pl/en/archive/oi/15/tro
http://main.edu.pl/en/archive/oi/15/kup
http://main.edu.pl/en/archive/oi/18/prz
http://main.edu.pl/en/archive/oi/18/sej
http://codeforces.com/contest/280/problem/D
http://main.edu.pl/en/archive/oi/18/rot
http://codeforces.com/contest/280/problem/C
http://main.edu.pl/en/archive/oi/18/imp
http://main.edu.pl/en/archive/oi/18/met
http://main.edu.pl/en/archive/oi/18/pro
http://main.edu.pl/en/archive/oi/17/kor
http://codeforces.com/contest/283/problem/C
http://codeforces.com/contest/283/problem/E
http://joisc2013-day3.contest.atcoder.jp/tasks/joisc2013_cake
http://joisc2013-day1.contest.atcoder.jp/tasks/joisc2013_communication
http://joisc2013-day1.contest.atcoder.jp/tasks/joisc2013_collecting
http://joisc2013-day2.contest.atcoder.jp/tasks/joisc2013_mascots
http://main.edu.pl/en/archive/oi/17/klo
http://codeforces.com/contest/277/problem/E
http://main.edu.pl/en/archive/oi/17/owc
http://main.edu.pl/en/archive/oi/17/tel
http://codeforces.com/contest/286/problem/A
http://codeforces.com/contest/286/problem/B
http://codeforces.com/contest/286/problem/D
http://main.edu.pl/en/archive/oi/16/gas
http://main.edu.pl/en/archive/oi/16/baj
http://main.edu.pl/en/archive/oi/16/kon
http://main.edu.pl/en/archive/oi/16/arc
http://main.edu.pl/en/archive/oi/16/lyz
http://main.edu.pl/en/archive/oi/16/slw
http://main.edu.pl/en/archive/oi/16/wsp
http://main.edu.pl/en/archive/oi/15/blo
http://main.edu.pl/en/archive/oi/15/rob
http://main.edu.pl/en/archive/oi/15/bbb
http://codeforces.com/contest/295/problem/D
http://codeforces.com/contest/295/problem/E
http://codeforces.com/contest/150/problem/E
http://main.edu.pl/en/archive/oi/14/drz
http://main.edu.pl/en/archive/oi/14/grz

ICPC2017 国内予選 参加記

f:id:tozangezan:20170716111237p:plain

気がついたら年齢的にもICPCの参加リミットを超えてしまった。年を重ねるにつれ、目標を達成してしまうし、目標になるものも減ってきてしまうのが、競技プログラミング(に限らないけど)の難しいところ。

その昔、こんな目標を持っていた。

  • IOIに参加してメダルを取る
  • ICPCに参加してメダルを取る
  • 海外オンサイトに参加する

もちろんIOIは2012年の時にまあなんとかして代表になって銀メダルを取ったし、ICPCですら2014年の時に運もあって銀メダルを取ったし、この二つは年齢的にも引退なのでもう仕方がない。海外オンサイトはいつまでも出られるので、これは目標にできるか?と思いきや、FHC2015、DCJ2016ときてまたDCJ2017でも進出し、やはり数回出場すると目標としていまいちインパクトに欠けて、やる気が出ない。これだけのために必死に問題解き続けられるかと言われるとそんなことはないと思う。

じゃあここまでくると目標というのはどういうものが考えられるかと言うと、

とかなんだけども、TopCoderは廃れて目も当てられないし、Codeforcesはゴミみたいなセットが増えすぎでいちいちやる気を削いでくるし、AtCoderは過去問練習で上位に来た無能を真っ向から潰しにかかってくるセットばっかりだし、海外オンサイトで入賞は有名人たちの争いだし、なんか以前の目標に比べて遠すぎる。

もっと現実的かつ練習が要求されて見返りも結構ある目標が立てられるといいんだけどもなあ。赤中上位だけどtargetには届かない、そんな人たちを集めてリーグ戦とかやって欲しい。chokudaiさんお願いします。

関係ないけどOpenCupのおかげで今もチーム戦に参加できるのは嬉しい。制限なしのチーム戦の真面目なコンテストとか出てきてくれないかなとも思ってる(ロシアにはあるよね)。

純粋培養競技プログラマが基本情報技術者試験を解いてみた話

参考:
d.hatena.ne.jp

こんにちは。たまには有機的な投稿をします、tozangezanです。

twitter基本情報技術者試験、というものが話題に上がっていたので、過去問を解いてみることにしました。

筆者紹介

大学4年。中学2年のときに競技プログラミングを始める。インターンに行ったことがある。競技プログラミング以外の用途でもプログラムを書く(研究でシミュレーションをするため)。
パソコンの中のことやネットワークのことについて勉強したことはなし。離散最適化に興味なし。

DEGwerと違い、理学も工学も専攻していません(ポイント)

使用した問題

http://www.fe-siken.com/kakomon/29_haru/
ここに上がっている、平成29年度春の午前試験を解きました。

結果

46問正解/80問 です。ボーダーが6割らしいので、ぎりぎり不合格です。

感想

アルゴリズムの問題が1桁問しかない!
全般的に知らない語彙が多すぎます。具体的にはパソコン系単語とビジネス系単語だと思います。DEGwerも言っていましたが、まだ英語をカタカナにしたものは意味が想像つくので(たとえばニッチャとか生まれて初めて見た4文字ですが、nicheに-erをつけただけだと思うし、nicheという単語は生態学を専攻している人が知らないわけがありません)、まだなんとかなります。問題は、技術に関する知識が文字どおり0(特にネットワーク関係は、「パソコンの右上か左上に扇のようなマークがあり、これを押すとネットにつながる」くらいの知識しかないので、どうすることもできません)なので、問題文から推測しようがありません。
特にDMZにネットワークを置く問題とか、なんで韓国と北朝鮮の国境地帯にサーバー(あのディスクが3枚つながったやつです)を置くのかしか頭に残りません。
ビジネス関連単語も、発音はできるが全く意味がわからない日本語で構成されており、正気を疑います。

採点してみる。なんか最初の方間違えまくってるやんけ! → どれもこれも単語の説明問題でした(完)

面白かった問題

問30. 唯一解きがい(手の動かしがい?)がありました。

問69. ここまでくると、経済学の問題じゃないですかね。

結論

一般常識 + 最低限の英語力 + 競プロ風味の算数 では通らないこともあります。多分わからない問題の乱択の結果のブレが、合否を分けるラインです。
じゃあ競技プログラミング基本情報技術者試験の役に立たない? そんなことはないと思います(わずかだとは思いますが)。そんなことで一番伝えたいのは、
情報系専攻は基本情報の役に立つ。

回答

間違えた問題の回答には、・がついています。



























四国フォトギャラリー

2017年2月に四国に行きました。そのとき撮った写真のうち、見せたいものをただひたすら張り続けます。

f:id:tozangezan:20170220143959j:plain
番号が汚い

f:id:tozangezan:20170220151334j:plain
ラスボスがいそう

f:id:tozangezan:20170220181135j:plain
高松からは離島行きフェリーがたくさんある

f:id:tozangezan:20170220192413j:plain
セルフの醍醐味

f:id:tozangezan:20170221085950j:plain
さぬきうどん駅

f:id:tozangezan:20170221104443j:plain
徳島。駅の隣に山がある

f:id:tozangezan:20170221132720j:plain
f:id:tozangezan:20170221132810j:plain
サラダ

f:id:tozangezan:20170221133335j:plain
阿波池田。寂しすぎる

f:id:tozangezan:20170221142611j:plain
f:id:tozangezan:20170221143223j:plain
大歩危

f:id:tozangezan:20170221153217j:plain
ゆるして

f:id:tozangezan:20170221155818j:plain
日本一駅間が短い

f:id:tozangezan:20170221173917j:plain
はりまや橋

f:id:tozangezan:20170222090526j:plain
土佐湾

f:id:tozangezan:20170222092755j:plain
大都会予土線

f:id:tozangezan:20170222100512j:plain
f:id:tozangezan:20170222101938j:plain
四万十川

f:id:tozangezan:20170222102852j:plain
f:id:tozangezan:20170222102859j:plain
半家 はげ

f:id:tozangezan:20170222165503j:plain
四国一箇所巡り

f:id:tozangezan:20170222183619j:plain
願い事

ごはん
f:id:tozangezan:20170220144959j:plain
f:id:tozangezan:20170220185253j:plain
f:id:tozangezan:20170221112257j:plain
f:id:tozangezan:20170221115627j:plain
f:id:tozangezan:20170221175540j:plain
f:id:tozangezan:20170221180045j:plain
f:id:tozangezan:20170222122930j:plain
f:id:tozangezan:20170222175746j:plain

おまけ

B: flagpoles
差を取ると本当に簡単。

long long p[11000000];
long long lf[210];
long long lv[210];
long long rf[210];
long long rv[210];
long long sv[210];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetNumFlagpoles();
	if(N<=2){
		if(I==0){
			printf("%d\n",N);
		}
		return 0;
	}
	N--;
	if(N<T){
		T=N;
		if(I>=T)return 0;
	}
	int L=(long long)N*I/T;
	int R=(long long)N*(I+1)/T;
	int n=R-L;
	long long now=GetHeight(L);
	for(int i=0;i<n;i++){
		long long tmp=GetHeight(i+1+L);
		p[i]=tmp-now;
		now=tmp;
	}
	long long left=0;
	long long right=0;
	for(int i=0;i<n;i++){
		if(p[i]==p[0])left++;
		else break;
	}
	for(int i=0;i<n;i++){
		if(p[n-1-i]==p[n-1])right++;
		else break;
	}
	long long ma=0;
	long long val=0;
	for(int i=0;i<n;i++){
		if(i==0||p[i]==p[i-1]){
			val++;
		}else{
			val=1;
		}
		ma=max(ma,val);
	}
	if(I==0){
		lf[0]=p[0];
		lv[0]=left;
		rf[0]=p[n-1];
		rv[0]=right;
		sv[0]=ma;
		for(int i=1;i<T;i++){
			Receive(i);
			lv[i]=GetLL(i);
			lf[i]=GetLL(i);
			rv[i]=GetLL(i);
			rf[i]=GetLL(i);
			sv[i]=GetLL(i);
		}
		long long ret=0;
		long long nc=0;
		long long nl=0;
		for(int i=0;i<T;i++){
			ret=max(ret,sv[i]);
			if(nc==lf[i]){
				ret=max(ret,nl+lv[i]);
			}else{
				nl=0;
				nc=rf[i];
			}
			long long TL=(long long)N*i/T;
			long long TR=(long long)N*(i+1)/T;
			if(TR-TL==lv[i]){
				nl+=lv[i];
			}else{
				nl=rv[i];
				nc=rf[i];
			}
			ret=max(ret,nl);
		}
		printf("%lld\n",ret+1);
	}else{
		PutLL(0,left);
		PutLL(0,p[0]);
		PutLL(0,right);
		PutLL(0,p[n-1]);
		PutLL(0,ma);
		Send(0);
	}
}

C: number_bases
事前にくり上がりがある場合ない場合どっちも用意しておく。

int X[1100000];
int Y[1100000];
int Z[1100000];
int LL[210][2];
int RR[210][2];
int DD[210][2];
int KK[210][2];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetLength();
	if(N<T){
		T=N;
		if(I>=T)return 0;
	}
	int L=(long long)N*I/T;
	int R=(long long)N*(I+1)/T;
	int n=R-L;
	for(int i=0;i<n;i++){
		X[i]=GetDigitX(i+L);
		Y[i]=GetDigitY(i+L);
		Z[i]=GetDigitZ(i+L);
	}
	int DL=0;
	int DR=-1;
	int dame=0;
	int KR=0;
	for(int i=0;i<n;i++){
		DL=max(max(DL,Z[i]+1),max(X[i]+1,Y[i]+1));
		if(KR+X[i]+Y[i]>Z[i]){
			int nr=KR+X[i]+Y[i]-Z[i];
			if(DR==-1||DR==nr){
				DR=nr;
			}else{
				dame=1;
			}
			KR=1;
		}else if(KR+X[i]+Y[i]==Z[i]){
			KR=0;
		}else{	
			dame=1;
		}
	}
	if(DR!=-1&&DR<DL)dame=1;
	LL[I][0]=DL;
	RR[I][0]=DR;
	DD[I][0]=dame;
	KK[I][0]=KR;
	DL=0;
	DR=-1;
	dame=0;
	KR=1;
	for(int i=0;i<n;i++){
		DL=max(max(DL,Z[i]+1),max(X[i]+1,Y[i]+1));
		if(KR+X[i]+Y[i]>Z[i]){
			int nr=KR+X[i]+Y[i]-Z[i];
			if(DR==-1||DR==nr){
				DR=nr;
			}else{
				dame=1;
			}
			KR=1;
		}else if(KR+X[i]+Y[i]==Z[i]){
			KR=0;
		}else{	
			dame=1;
		}
	}
	if(DR!=-1&&DR<DL)dame=1;
	LL[I][1]=DL;
	RR[I][1]=DR;
	DD[I][1]=dame;
	KK[I][1]=KR;
	if(I==0){
	//	printf("%d: %d %d %d %d\n",0,LL[I][0],RR[I][0],DD[I][0],KK[I][0]);
		//printf("%d: %d %d %d %d\n",1,LL[I][1],RR[I][1],DD[I][1],KK[I][1]);
	//	fflush(stdout);
		for(int i=1;i<T;i++){
			Receive(i);
			for(int j=0;j<2;j++){
				LL[i][j]=GetInt(i);
				RR[i][j]=GetInt(i);
				DD[i][j]=GetInt(i);
				KK[i][j]=GetInt(i);
			}
		}
		bool ok=true;
		int dl=0;
		int dr=-1;
		int kr=0;
		for(int i=0;i<T;i++){
			if(DD[i][kr]){
				ok=false;break;
			}
			dl=max(dl,LL[i][kr]);
			if(dr!=-1&&dr!=RR[i][kr]&&RR[i][kr]!=-1){
				ok=false;
			}else if(RR[i][kr]!=-1)dr=RR[i][kr];
			kr=KK[i][kr];
		}
		if(kr)ok=false;
		if(dr!=-1&&dl>dr)ok=false;
		if(!ok){
			printf("IMPOSSIBLE\n");
		}else{
			if(dr==-1)printf("NON-UNIQUE\n");
			else printf("%d\n",dr);
		}
	}else{
		for(int i=0;i<2;i++){
		//	printf("%d: %d %d %d %d\n",i,LL[I][i],RR[I][i],DD[I][i],KK[I][i]);
			//fflush(stdout);
			PutInt(0,LL[I][i]);
			PutInt(0,RR[I][i]);
			PutInt(0,DD[I][i]);
			PutInt(0,KK[I][i]);
		}
		Send(0);
	}
}

D: broken_memory
落ちた。不必要にデータを送りすぎた。(700回ですむところを調子に乗って送りまくってしまった)

E: nanobots
smallは分割統治であることは有名。largeはたくさんスライスしてランダムに割り振ってsmallと同じことをする。

const long long mod=1000000007;
long long ret=0;
void count(long long L,long long R,long long lm,long long rm){
	if(L>=R)return;
	if(lm>rm)return;
//	printf("%lld %lld %lld %lld\n",L,R,lm,rm);
	if(Experiment(R-1,rm)=='T'){
		ret=(ret+((R-L)%mod)*((rm)%mod))%mod;
	//	printf("%lld %lld\n",R-1,rm);
		return;
	}
	if(Experiment(L,lm)=='E')return;
	long long M=(L+R)/2;
	long long left=lm-1;
	long long right=rm+1;
	while(left+1<right){
		long long mid=(left+right)/2;
		if(Experiment(M,mid)=='T'){
			left=mid;
		}else right=mid;
	}
	ret=(ret+left)%mod;
	//ret=(ret+(M-L)%mod*((left-lm+1)%mod))%mod;
	count(L,M,max(1LL,left),rm);
	count(M+1,R,lm,left);
}
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetNumNanobots();
	long long R=GetRange();
	int BK=min((long long)R,2000000LL);
	
	//count(1,R+1,1,R);
	srand(1145141919);
	for(int i=0;i<BK;i++){
		int tmp=rand();
		long long left=R*i/BK+1;
		long long right=R*(i+1)/BK+1;
		if(tmp%T==I){
			count(left,right,1,R);
		}
	}
	if(I==0){
		for(int i=1;i<T;i++){
			Receive(i);
			long long tmp=GetLL(i);
			ret=(ret+tmp)%mod;
		}
		
		printf("%lld\n",ret);
	}else{
		PutLL(0,ret);
		Send(0);
	}
}

21位。なんで通ったんだろう。アイルランドでも頑張ります。