AGC022Cを解くのが流行っているので流行に乗った

こんなことに時間を使ってないで研究しろ

問題
C - Remainder Game

ソースコード
Submission #2409669 - AtCoder Grand Contest 022


メモ:

15:50 それでは、問題やります
15:52 問題を読んで入力しました(IMEが壊れた...)
15:53 とりあえず各操作は最大1回、greedyに最大のkを決めて好き放題判定していくだけ, nはnかn/2以下にできる
15:54 IMEが壊れてやりにくすぎる、再起動します
15:56 なんかおかしくて再起動ができない
15:58 もどってきました
16:01 最短路のor取るだけな気がしてきた

7 5
3 1

16:04 greedyの2択がめんどいんだよな
16:06 全部管理すれば良い、解けた
16:13 サンプルが通らんよ
16:15 なんでWAなんだよ 2ケースだけだから変なものあるんかな
16:18 どうせ-1のケースでしょ→やっぱりな

典型要素:

  • 2^nで1回ずつ使うやつはgreedy
  • 両側貼り合わせ
  • パソコン操作

両側貼り合わせって要は「スタートからここまで行く方法に関する情報」「ここからゴールまで行く方法に関する情報」をなんかして持っておいて途中の判定とかに使うやつなんですけども、これはAGCでばかり見ます。

圧倒的に遅いんですけども、どこが遅いのかよくわからん(最初のパソコン壊れによる消耗はかなりあるけどもそれでも遅い)。やっぱりAGCはダメですね。

2018年の目標

"一年は目標に始まり反省に終わる。"
  ーー Tozan Southerpacks

書きなぐりと言われても否定できませんが、今年の目標も書いていきましょう。全然意識してないから達成できないんだという話はしてはいけません。

競技プログラミング

枠の数が正常のオンサイトに出る

4年連続でいけたら一流の競技プログラマーでしょ。

なんか大会で優勝する

国内オンサイトかな? ひそかに狙っていきたいと思いますが、ちゃんと個数は確保されるんですかね?

天才以外お断り問題たちに光明を見つける

なんかAGCの問題への見方に変化があると嬉しいですね。

お勉強

研究

1本は雑誌に投稿したいので頑張ります。2本目が収拾つくとなお良いですね。
将来的にどの分野に進みたいかをちゃんと考えられるようにしておこう。

英語

去年はVocabularyの一年でした。当然speakingが今至急なのでspeakingを鍛える。ひとまず海外に行っても研究生活とか困らずできるレベルになるのが目標です(がこんなのどうやって評価すればいいんだ)。
あとwriting、時間との相談要素もありますが、AtCoderの問題文英訳でも関わったりとかもしたい。

他の言語

ロシア語を中級レベル目指そう。なんかあんまり国内で人気のない言語をまともなレベルまでわかるようになろう。

市町村系

また変な場所を目指して旅に出る

ここで言わなくてもやります。

🐺

🐺

いやこれ書く必要ないわ

2017年の反省

"一年は、目標に始まり、反省に終わる。"
  ーー Tozan Southerpacks

冗談はさておき、半ば無茶振りのような今年の目標を一つ一つ振り返っていきましょう。

競技プログラミング

Div1 Hard のAC数を450以上にする

2013年以降の CF の Div1 コンテストは全部 Virtual Participation する

OpenCup にちゃんと出る

ちゃんと出たかな? きわどいところだけど、自分では頑張ったつもりなのでぎりぎり合格点。
最近の目標はjapan02に勝つことですが、自分のできることが限られすぎていて勝敗への影響があんまり大きくないです。安定性への影響はあるかも。

枠の数が正常のオンサイトに出る

DCJ笑 マジ何なんだあれ

自分でも良問と思える問題を3問以上作る

作問は向いてないのがわかったのでもう作問を目標にするのはやめます。

TC Highest 2800以上、CF Highest 2800以上、AtCoder Highest 3200以上

笑 というか笑ってばかりいないでTCとかCFをやれというはなし 絶対真面目にやればこの二つはいけたでしょ

学業

研究して院試して卒業する

多分ヨユー 卒業する前に一本投稿できるとなお良いけど、間に合うか微妙

非ネイティブとしては申し分ない程度の英単語力と、まあ全般的になんとかやっていける程度の英語力をつける

英単語力はもういらんわ 文語的な単語はネイティブと勝負できるね
結局何年経とうとspeaking力だけはどうにかなる下限で選択肢が減りまくりなのでこれだけは何とかしないといけないんだけど何ともできないから助けて
海外のPhDも学校選べば英語力の観点ではspeaking以外は無問題だしspeakingだけ何とかなれば*1もう問題ないでしょ 研究頑張ろう

その他

Youtube 動画...?

時間帯効率が悪い、おふざけ動画垂れ流しのほうが100倍楽。

市町村系とか

四国一周しました
房総一周しました
四国の話はこのブログの変な場所に、房総の話はここに書いてあります(ついでにここにテヘランの話も書いてあります)
やっぱり実際にいくと知見が広がるのでおすすめですが、四国は離島も大切なのでそこが難しいですね。今度は離島に行きたい。

DP未難25

まとめ

競技プログラミングに関しては、やっぱりゴールがないのがなあ。もう半ば引退ムードに近いのですが、この前やり残したこと(国内オンサイト優勝)があることに気づいて、企業コンテストは得意だしせめてそのぐらいは達成してから引退しようという気分です。
あとはまあ語学力と研究と市町村の3つなんですけど、語学力は相も変わらず speaking 力が足を引っ張りすぎていて解決策がなさすぎるのが困りもので (Discordチャンネルにもっと人が欲しいなぁ)、研究はまあ頑張る他なくて、残りは市町村ですかね。市町村に関しては、また未踏の地に行きたいですね。予定では来年の春には三陸に遊びに行く予定です。

*1:なっていません。IELTS 6.0です。

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