三角数
Atcoderの過去問をぽちぽち解いているのですが、ARC129-C "Multiple of 7"は三角数の有名な性質を知っていたので気持ちよく解けました。
問題としては、任意の連続部分列を取ったときに7の倍数になるような場合がn通りあるような1~9の数字列を一つ構成せよということですね。
まず、7が単にm個並んでいる数字列を考えましょう。このとき、どこからどこまで区切っても、明らかに7の倍数です。よって、m(m+1)/2通り7の倍数になる区切り方があります。
このm(m+1)/2はm個のものから2個選ぶ場合の数ですが、三角数とも呼ばれています。
三角数には、以下の定理があります。
この定理を使って、問題を解けないか考えてみましょう。
i番目の三角数をt[i]とします。今n=t[i]+t[j]+t[k]と表せたとしましょう。このとき、"777…77177...77177...77"という数字列を考えます。ここで、最初は7がi個、次は7がj個、最後は7がk個並んでいます。1で区切られた各区間、任意の切り出し方をして得られた数字列は7しか含まないので、必ず7の倍数になります。これはt[i]+t[j]+t[k] = n通りあります。従って、ほかに7の倍数となる切り出し方がなければいいです。このとき、1を一つだけ含む切り出し方は明らかに7の倍数になりません。なので、1を二つ含む区間が7の倍数になるかを考えます。
よく知られていることとして、1001は7の倍数です。また、999999=1001×999も7の倍数です。
よって、1001×1000000-999999＝1000000001も7の倍数です。同様にして、1と1の間に0が6で割って2余る回数続く数は7の倍数です。逆にこれ以外は7の倍数にならないことも簡単にわかります。また100…001が7の倍数ならば、明らかにそれに1を足した100…002は7の倍数になりません。
よって、jが6で割って2余るならば、77…77177...77277...77を、それ以外なら77…77177...77177...77を出力するようにプログラムを組めばいいです。
三角数の数論的性質を使って解けたので、個人的に楽しい問題だと感じました。
ARC114-EとAGC049-Aの類似性について
こんにちは，関西（にいた）組合せゲーム理論徒ことCOOH2です．ARC114に参加しました．Bで時間がかかった挙句CDが相性悪くて解けなかったため大幅にレーティングを落とすことになり残念です．本番中は十分な考察の時間を取れませんでしたがEは自力考察で通せたためこちらから取り組んだ方がよかったかもしれません．
さて，そのARC114-EですがTLでも何人か指摘しているとおりAGC049-Aが利用できます．私もその方法で解いたので紹介したいと思います．
問題として与えられる方眼紙を考えます．このうち，黒マスが二つあり，この二つを結ぶ線を対角線とする長方形を考えることができます．ここで，この長方形の内部を通る直線を選択したときに操作は終了します．この長方形のことを便宜上「灰色長方形」と呼びます．（下図，黒色＆灰色の長方形）
ここで，問題の言い換えを考えます．直線を選ぶごとに元の紙の一部が捨てられていきます．言い換えれば，直線を選ぶごとに「選ぶことのできる直線」が減っていく，より突き進めると，「直線を選ぶごとに何本かの直線が削除されていく」ということになります．灰色長方形の内部を通る直線を選択した時，操作が終了するので言い換えればすべての直線が削除されます．また，灰色選択肢の外部を通る直線を選択した場合は，自分自身と，それよりもさらに外側の直線が削除されます．例えば，左から二つ目の直線を選択すると，そこから左側の紙が削除されますが，これは左から一本目と二本目の直線が削除されたと見做せます（下図参照）．
ここで直線の個数だけ頂点を持つグラフを考えます．それぞれの直線に対して頂点を対応付けます．直線Aを選択したとき直線Bが削除されるときに，頂点Aから頂点Bに有向辺を引きます．
このようにすると，有向グラフがあって，操作ごとに頂点を一つ選び，選ばれた頂点と，そこから到達可能な頂点をすべて削除するとき，操作回数の期待値はいくつか，という問題に帰着されます．これはAGC049-Aです．入力データの制約が異なりますが，同じ解法を利用して解くことができます．具体的には以下の通りです．
それぞれの頂点に注目して，その頂点に到達可能な頂点の個数（自分自身を含む）の逆数の総和がAGC049-Aの解でした．元の問題に戻って考えると，それぞれの直線に着目して，その直線を削除するのは，灰色長方形の内部を通るすべての直線（縦向きも横向きも）および，その直線と平行で，灰色長方形とその直線の間にある直線です．この個数は各直線に対して直ちに求められます．直線の本数は(H＋W-2)本しかないので，十分速く解が求められます．
案外綺麗に解が求まったので，コンテスト中にこちらに注力できなかったのは残念でした．最近はARCでもあまりレーティングが伸びなくなってきたので，AGCに特化したいという思いが芽生えていますがさすがに回数が少ないのでもうしばらくはARCも出続けようかと思います．
Grundy数の話
Grundy数（グランディ数）という重要な概念がある。
組合せゲーム理論の概念なのだけど競プロでもよく出てくるから、今更自分が解説しなくても世には素晴らしい解説記事がいっぱい溢れていると思うのでそっち方面の話はしないけれどもここで言いたいのはその名称についてだ。
Grundy数という名前だから当然Grundyさんが発表したのだと皆は思うだろうしそれは一面では正しいのだけど実はGrundyさんのちょっと前にSpragueさんという人もこれを発表している。なのでSprague数になっていてもおかしくはなかった。有名にならなかったのはSpragueさんが東北の数学誌にドイツ語（？）で出していることとか、第二次世界大戦前夜という当時の情勢の結果だろう。なのでGrundy数と呼ぶのではなくSprague-Grundy数と呼ぶべきという意見もある、ほかにもそれを略したSG数、G-value、Nimber、エネルギーなどなど、実は様々な表現をされているのがこの概念だ。組合せゲーム理論を研究していると、そんな風に色んな形でGrundy数が現れるので面白くもあり、ややこしくもある。競プロ界隈ではあまりGrundy数以外の表現を見かけないような気がするので、わかりやすい反面、Spragueさんのことを思うとちょっと複雑な気持ちにもなるのだった。
組合せゲーム理論屋が競プロを始め、青コーダーになった話
初めまして、COOH2という名前で競プロ（Atcoder）をしている組合せゲーム理論の研究者です。組合せゲーム理論の問題しかない有志コンテストをいずれ開きたいという野望を持っています。
先日Atcoderで青色になったので色変記事なるものを書いてみようかと思い、ブログを始めました。このブログでは競プロや組合せゲーム理論に関する記事を書いていこうかと思っています。
・始めるまでの能力
高校時代から部活でゲームプログラミングをしていたのでプログラムの経験はありました。Visual Basicを当時は使っており、C++の経験はあまりありませんでしたが、参考資料もC++の方が豊富なので競プロではC++を使っています。
研究者として組合せゲーム理論の造詣は深いです。アルゴリズム系の研究集会とかも顔を出すことがあるのでそっちの知識も多少はありました。
・始めるきっかけ
研究者一本だと不安定なので手に職をつけるという意味でも競プロに興味があり、高校の後輩であるレッドコーダーのjoisino君と会ったときに聞きたいことを聞いてみました（以下はあくまで再現であり実際の会話の文脈を完全に保っているかは保障できません）。
Q.競プロ興味あるけどあまり重箱の隅をつつくようなオーダー下げコーディング(nの3乗をnの2.97乗に下げるような）はしたくないし知識ごりごりにため込まないといけないのもしんどいんだけどそのあたり実際どうなの？
すると、
「そこまで重箱の隅をつつくような問題はAtcoderにはあまりない。想定解法の次に早いような手法でも間に合う」
「確かにABCは知識を抑えている必要があるけどAGCの方が数学パズル要素が強い」
「COOH2さんだったらAGCだけ普通にやってたら橙くらいまでは行くんじゃないですか？」
というような感じの（繰り返しますが一年以上前なので一部曖昧です、あしからず）ありがたいお告げをいただいたのでやってみることにしました。
・コンテストに出だしてから青に入るまでの変遷
AGC037(19/08/17) パフォ：1124 レーティング：122
初めてのAGC。標準入出力くらいは普段使わないので調べておいて、結果A1完のみ。Cも方針は見えていたけど競プロ的な考え方に適応していませんでした。さすがに多少は競プロの練習積まないといけないかと思うとちょっと面倒になってしばらく放置。
AGC043(20/03/21) パフォ：1438 レーティング：554
やっぱり競プロが気になって再びのAGC参加。またA1完だったがやはりBも方針が見えるので精進をもうちょっとやればぐいと伸びる気もする。このころからちょっと過去問を解きだします。
4月はちょっと忙しくなったものの5月に入ってまた一日一問以上を目安に解くようになりました。
AGC044(20/05/23) パフォ：―― レーティング：554
一問も解けずNo sub撤退。特に難易度が高くレーティングシステムに悪影響を与えたか何かで、ご存じの通りここからAGC参加にレーティング下限が設定されるようになります。
この時点でARC級はほとんど開催されておらず、必然AGCに出たければABCに出てレーティング下限に入るしかなくなったのですが、私の特性として、数学SSS、アルゴリズムA、実装C みたいなとてもいびつなパラメーター割り振りです。
・本職で数学を扱うので難易度の高い問題も時間をかければ解けることがある。
・まだ練習量が足りていないので早解き用の回路は育っていない。
→ABCとの相性が最悪
というわけなんですね。
で、どうなったか。
ABC174(20/08/02) パフォ：1176 レーティング：711
ABC176(20/08/22) パフォ：1080 レーティング：781
ABC178(20/09/13) パフォ：1046 レーティング：823
始めたてなのでレーティングは伸びていますが水色入りも怪しいような状況。始めた頃よりむしろ悪化してる。しかし、緑に入ったあたりでARC再開の報を聞きそちらにチャレンジすることにします。
ARC104(20/10/03) パフォ：2016 レーティング：1121
いきなりパフォが1000くらい違う件。この頃になるとARCの過去問バチャで橙パフォが出たこともあったので期待はしていたのですがここまではっきり違いが出てくれてよかったです。
ARC105(20/10/12) パフォ：1898 レーティング：1277
引き続き好調で水色に滑り込み、翌週のAGCのレーティング制限を突破します。それまでも変動なしで出ていましたが久しぶりのRated。
AGC048(20/10/18) パフォ：1757 レーティング：1357
Dでまさかの知ってる組合せゲーム理論の問題が出て解けました。しかしドツボにはまってAを落とすという痛恨の失態を犯しBCも解けず、パフォとレーティングはさほど伸びず。Dが載っている組合せゲーム理論の教科書をTwitterで紹介したらプチバズりました。
ARC106(20/10/24) パフォ：1671 レーティング：1403
ARC107(20/10/31) パフォ：1632 レーティング：1434
AGCだけ出るという戦術を取れるようになりましたが、ARCでもある程度レーティングが稼げる感じなので引き続き出続けました。
AGC049(20/11/15) パフォ：2100 レーティング：1544
やはり長時間コンテストは性に合っているというようなBC2完。しかしAを落とすのはよくないですね。それでも自己最高パフォを出せました。
ARC108(20/11/21) パフォ：984 レーティング：1485
AB2完。終了4分後くらいにDが通りました。悲しい。100分コンテストはきつい……初の冷えも体験して気落ちします。とはいえ気分を切り替えて翌週もARCにチャレンジ。
ARC109(20/11/28) パフォ：2276 レーティング：1615
ABCD4完。Dはかなり怪しい通し方をした自負があります（場合分け24通りとかいろいろ）。いや普段から怪しいのですけど。問題の相性がよかったようでみんな解けてるのでは？と思ったけど思ったほどおらず、過去最高パフォで一気に青入りしました。120分だったし、やっぱり100分コンテストより長いコンテストの方が相性がよさそう……
・やったこと
継続は力なり？ということで5月初めから毎日1AC以上を続けていたら200日を超えました。茶diffや灰diffだけ通している日もありますが多くは緑以上です（最近忙しくて灰茶が多い）。
自力ACにはそこまでこだわっていません。プログラミングの基礎的な内容(mapとか)を知らずに問題が解けなかったようなこともあり、今は問題を解くことと解説を見て知識を蓄えることを並行するのがよいと考えています。
・目標
組合せゲーム理論がせっかく競プロでしばしば扱われる題材なので、研究者としてはもっとブームを巻き起こしたいと思っています。
joisino君の予言もちゃんと達成したいので色としては橙を目指したい。
・感想
やはり日ごろから数学の研究をしていることは大きなアドバンテージになると思います。エンジニアの方でも競プロに来ると苦労するみたいな話も聞きますがエンジニアをするよりも数学の研究をしている方が相性がいいのかもしれないと思いました。
ただ、競プロ的な考え方に慣れる必要があると思います。問題によって、数学的なアプローチと競プロ的なアプロ―チ両方あり、かつ数学的アプローチでやると危険な問題（最近なら、ARC108-Aとか）をしっかり競プロ的アプローチから解けるようになるのが大事だと感じました。
