すこしだけ欠けたピアノの音色

競技プログラミング、始めました。

ARC152 A-C を解くための考え方

ARC152 の writer をしました、riano_ と申します。

ご参加いただいた方、またコンテスト後に問題を解いてくださった方、ありがとうございます。多くの方に取り組んでいただけるのが何より嬉しいです。

さて、ARC152 では B,C の難易度が比較的高く、苦戦された方が多かったように思います。難易度推定については(writer自身の当初の推定として)やや外してしまった部分があり、次の機会があればこの反省を活かしたいと思っています。

解法、およびその正当性は公式解説に記した通りですが、「どうやったら解ける(解法を思いつく)のか分からない」「この問題から他の問題にも通用する何らかの示唆を得たい」という声もあるようでしたので、writer 自身の考えた道筋を書いてみようと思います(この 3 問は、解法からではなく問題設定から作ったので、コンテスタントとほぼ同じ前提で解いています)。

当然ながら、思いっきりネタバレを含みますので、できれば自力で考えてみてから読んでいただけると嬉しいです。

 

A. Seat Occupation 

まず、どのような座り方をしても確実に全員座れる、という表現を、出来る限り妨害しても全員座れてしまう、と言い換えます。直感的に同じとみなせる人は特に必要ないかもしれませんが、後者の言い方をすると、誰かが座れないように意地悪をするという「目的」が明確になります。目的が明確になれば、その目的を達成するための方法を構築する、といった小問題に思考を移すことができます。

次に、座れないとしたら 2 人組で、一番厳しい状況がありそうなのは最後の 2 人組である、という点がポイントになります。これ自体は比較的易しめですが、「条件を満たさなくなるとしたらどんな場合か」を考えてその性質を捉えることは、汎用的に通用する考え方ではないかと思います(実際、B も似たような考え方だと思っています)。

 

B. Pass on Path

この問題では、第一に、二人の位置関係が二度入れ替わる必要がある、という観察が重要です。これ自体は、実験して気づいたものなのですが、実験の際に「何が不自由な点か」に着目するのがよいと思います。

仮に、すれ違いが自由だとしたら、明らかに、両者が最速で歩き続けることが最適解になります。それに対して、例えばサンプル 1 の説明通りの動かし方を考えた際、最短の時間を達成したい、という目的の障壁になっているのは、休憩所で待っている時間です。待ち時間が生じるのは、すれ違いが決められた点でしかできないからなので、そう考えると、すれ違いに着目して、その性質を洗い出したい気分になります。

このような思考は、一般化すると、「目的に対して強い制限となる箇所に注目する」あるいは雑に言うと「何がめんどくさいのかを考える」という意味で、A 問題後半の考察パターンとも近い部分があるのではないかと思います。

次に、すれ違いが 2 回あることによって、なぜ待ち時間が生じてしまっているのかを考えます。動かし方に制限を与える箇所を特定したので、次は「どう制限を与えているのか」を考えるということです。

一方、すれ違い以外はほぼ自由なので、その間は最速で動き続けることにします。これは「重要でない部分の自由度は捨ててしまう」という考え方です。重要な部分を特定できた場合、このような処理を行っておくと問題がシンプルになることが多いかもしれません。

もちろん正当性の検証は必要です。今回の場合は、どんな動きをした場合に対しても、最速で動いた後で最後に休憩所で待っているという動きに入れ替えて不都合が生じないことから、大丈夫と分かります。このように、「ある(自分で勝手に決めた)条件を満たす操作に置き換えても問題ないことを示す」というのが、問題を単純化するときの思考パターンの一つとなるかと思います。個人的な感覚としては、問題の単純化は「重要な部分を特定できている場合に他の自由度を捨ててみる」と考えて使うことが多いように感じています(仮に正当でないことが分かった場合には、新たな重要な点が見つかったということなので、それはそれで考察の助けになります)。

さて、すれ違い以外は最速で動き続けることにすると、なぜ待ち時間が生じるのかというと、どちらかが先に 2 度めのすれ違いポイントに到達してしまうからです。すると、その間の両者の移動距離(の差)を考えればよいことが分かり、解説に記したような下界が求まります。

あとは、これを達成できる方法がないかを考えればよいです。このあたりの「まずは下界(上界)を見つけ、それを実際に構築して見せることで最適性を示す」というのは、ある種の ARC 典型と呼べるものかもしれません。

この問題では、すれ違い 2 回の間の時間調整こそが本質と、ここまでの考察で分かっていますので、その片方をスタート地点にしてしまうのが最もシンプルです。ここはやや直感的ですが、本質の問題の前に、最初のすれ違いのための時間調整の問題を追加するのは明らかにめんどくさい、と考えてこの方法に思い至りました。あとは実際に手を動かして確かめてみれば、正当な解法にたどり着くことが出来ます。

 

C. Pivot

この問題では、直感的に gcd っぽいと思った人も一定数いるのではないかと思いますが、一旦その感覚は排除して考察を進めてみます(本番では、そういう直感でショートカットするのはとても大事だと思います)。

まず、よく分からない式で操作が与えられているので、実際に操作を試してみます。すると、この操作が、ある値を選んで反転させる操作であることが分かります。

これを前提として、まずは「簡単に達成できそうな値は何か」を考えてみます。数列の最大値または最小値を選ぶと、その差を d として、ちょうど d ずつ数列の最大値がずれていくことが分かり、d で割った余りによってこの操作だけで達成可能な値が変わってきそう、ということが理解できると思います。

別に最大値を選ぶ操作でなく、a_2 を選ぶ操作を考えてもよいのですが(その場合は間に最小値か最大値での操作を挟まないと永遠に行ったり来たりになるのでやや複雑です)、とにかく「ある種の操作だけで出来ることは何か」を考えてみると、逆に「他の操作で何を達成したらよいのか」が見えてくるのではないかと思います。

d で割った余りを調整する問題としてとらえてみると、あとは例えば a_2 を選んだ時に余りがどう変わるか、はすぐに計算して求めることが可能です。ここでもう一つの問題は、その操作が繰り返し行えるかどうかです。先ほど少し述べたように、単に a_2 を選び続けると、反転を繰り返すばかりなので実質的な意味のある操作になっていません。

ここを、間に最大値を選ぶことでクリアする(d で割った余りを変えずに、同じ操作を繰り返せるようにする)部分は、個人的にはややひらめきを要求しているポイントなのですが、例えば、なぜ繰り返せないか(繰り返しても意味のある操作にならないか)を考えるなどすると、中身が反転しているからだという点に気づくことができそうです。中身の反転は操作 1 回ごとに起きているので、それを元に戻すためには別の値で一回操作すればよく、d で割った余りには影響を与えてほしくないと考えると、最大値で行うのがよい、となります。

ここはある程度天下り的ですが、「こういう操作ができるとしたら解けるが、できないか」と考え、それを実現するための条件からその候補を絞っていくことで、ひらめきが要求される幅を縮めることは可能です。

こういう操作ができるとしたら解ける、の部分、すなわち今回では、余りの調整は(操作が任意回なら)gcd 単位、というのは、どちらかというといわゆる典型に分類されると思います。このような問われ方自体は例が少ないかもしれませんが、例えば、互いに素なら mod 逆元がある、というような数えきれないほど使われている事実の背景を知っていればこの部分はクリアできるはずです。

 

■ 最後に

試行錯誤を、恐れないでください。特に格上の問題に挑む時には、これまで述べたような手掛かりを使っても、まっすぐに正解にたどり着けない場合の方が多いと思います。しかし、何度間違った道に進んでも、たった一つ正しい道を見つけさえすれば問題を解くことは可能です(そして、多くの問題で別解というものが存在するように、正しい道自体ただ一つではありません)。トライ&エラーのセンスを磨くことと、無心でそれを繰り返すこと、その両方が何より大切だと思っています。

 

 

長くなってしまいましたが、ここまでお読みいただきありがとうございます。

少しでもこの記事がお役に立てれば幸いです。

AtCoder 橙になりました

 

初めまして、または、お久しぶりです。riano_ です。

ついに目標としていた AtCoder 橙になることができました!

 

めちゃくちゃ嬉しいです。ただ、正直に言うと悔しさもあります。

初めて橙に「リーチを掛けた」と言えるのは、

2021/12/05 の ARC131 で rating 2379 になった時でしょうか。

その時から実に 8 ヶ月、2400 の壁はあまりにも遠く感じました。

 

ただ、停滞の理由、そしてこのタイミングで壁を破ることが出来た理由は、

実は分かり切っています。

問題を解かなければ、成長はおろかレートの維持さえ難しい。

逆にちゃんと取り組んでいれば、ゆっくりとでも、成長はしていくものです。

 

とはいえ、少し時間差みたいなのもはある気がしていて、

例えば6月から急に解く量が増えていますが、

6/19の ARC 142 では大敗していたりします。

これはかなり悔しかったのですが、「精進は遅効性」と言い聞かせて続けた結果、

その後は(大勝利というほどではないのですが)

手堅く橙 perf を 3 連発して無事に橙になることができました。

 

ちょうど明日から社会復帰をしなければいけませんので、

問題を解くペースはまた少し落ちてしまいそうですが、

まだまだ頑張っていきたいと思っています。

 

 

 

さて、前置きが長くなってしまいましたが、

せっかくの機会ですので思っていることを書いていこうと思います。

 

 

■ バチャについて

 

先ほどの Heatmap を見ると、極端に問題を解いていない時期があります。

サボっていたと言わざるをえませんし、実際レートも停滞しているのですが、

唯一ほめられることは、

「この期間も AtCoder の rated は全部出て、レート 2300 を割らなかった」

ということだと思っています。

 

コンテストに長く出ていなかったら、

危機感を持って精進量を増やすこともなかったかもしれません。

レートが 2200 くらいまで落ちていたら、

橙になるまでの道はもっと遠かったことでしょう。

 

ではなぜそうならずに済んだのかといえば、

「最低限週 1 ペースでのバチャを続けていた」というのが最大の要因だと思います。

幸いにも一緒に走ってくれる人がおり、感想戦まで行うことで、

サボってしまった時期にも最低限の実力維持、

そして精力的に取り組んでいるときには最も効率の良い精進となりました。

 

何より偉大なのは習慣化です。

そしてもう一つ、感想戦をすることで他の人の解法が勉強になったり、

自分が解説することでより鮮明に問題をとらえることにも繋がりました。

 

このバチャ無しでは、今回の結果は得られなかったでしょう。

本当にありがとうございます。ぜひこれからもよろしくお願いします。

 

 

■ 解けることと腑に落ちることの差について

 

似たようなことはいくらでも言及されている気もしますが、

ついつい忘れてしまいがちなので書いておくことにします。

(この章は主に、将来の自分への自戒です。)

 

問題を解ける(AC を得られる)ことと、

その解法や正当性が腑に落ちることには大きな差があります。

これは何も、腑に落ちていなければ意味がないというわけではありません。

コンテスト本番では、格上の問題を「腑に落ちなくても」通せればよいのです。

結果を求める以上、

正当性を気にしすぎてはいけないタイミングも間違いなく存在しています。

 

一方で、少なくとも同色以下の問題については、

通した後に腑に落ちるところまで理解しておくことが、

再現性を高めるために必要不可欠だと考えています。

 

僕がこだわっていること

(もしかしたら、こだわり過ぎているかもしれないこと)、

それは「ひらめきに再現性を持たせる」ことです。

競プロでは、発想を問われる問題も多く出題されます。

では、発想とはなんでしょうか。

僕はそれを「知識の解像度」なのではないかと思っています。

 

知っているつもりであることを、再度問いかけてみること。

それは容易なことではありません。

しかし無意識にしていることを言語化できたとき、

それは無意識では手の届かない難問に挑むための武器になることでしょう。

 

自分の実力より少し上に手を伸ばすとき、

人は最も真剣に自信の「最善手」を考えるのだと思います。

そしてその時こそが、

当たり前だと思っていたことの本質を掘り下げる最大のチャンスです。

 

幸いにも、競プロの問題はとても解きつくせないほど多くあります。

思考力の続く限り、何度でも「少し上」に手を伸ばし、

その思考の結晶を道標に発想力を磨いていきたいと思っています。

 

 

■ あとがき

 

ここまでお読みいただきありがとうございます。

また、すでに述べたバチャなどをはじめとして、

twitter上での議論や、はたまた(勝手な)ライバル意識など、

多くの方々のおかげでここまで来られたと思っています。

本当に感謝でいっぱいです。

 

競プロに対しても、たまに嫌になるときが無いとは言えませんが、

ここまで夢中になれる趣味に出会えたことも貴重だと思いますし、

何よりまだまだ楽しみ足りないですので、

もっともっと問題を解いていきたいと思います。

 

最後に一つ、自分の中で悔しいのは、

もう 8 ヶ月以上も赤 perf を出せていないことです。

去年の年末と比べて僕は強くなったのでしょうか。

橙 perf 以上を取れる割合は、確かに上がりました。

しかし赤 perf を取れる爆発力は、下がってしまったかもしれません。

まずはもう一度、赤 perf を取ることから。

いつになるかは分かりませんが、それが次に踏み出したい一歩です。

 

 

2022.07.31 by riano

 

yukicoder 2016 Countdown Divisors の手で出来る証明

(注)この記事はネタバレを含みます。

 

先日の yukicoder で面白い問題が出ました。解いていない方はぜひ解いてみてください。

yukicoder.me

 

解説では、ある程度の範囲の全探索によって正当性を示していますが、ここではこの問題が「数学の試験」であったと仮定して、紙と手だけで出来る証明を書きます。(本質はほとんど変わりませんが、一応 N の上限に関わらず示せているという差分もあります。)

 

整数 x に対する答えを f(x) とおきます。

まず、1から17まで手で実験します。

すると、x=1,3,4,5,7,8 で答えが 1 、それ以外で 2 であることが分かります。

特に、9<=x<=17 で答えが全て 2 です。

f(x)=f(x-d(x)) であること、および

x-d(x)>= x-2*sqrt(x) >= x/2 (2 つめの等式において x>=16 を仮定)

を用いると、18 以上の任意の x について、x-d(x) に変換していく過程で必ず 9<=x<=17 であるタイミングがあります。以上から、x>=18 において全て f(x)=2 が示されました。

Grundy 数をなんとなく理解したい

■ はじめに

この記事は、Grundy 数について「Nim の各山の石の数の xor=0 でなければ先手必勝」「Nim でないゲームでも、Grundy 数を定義して xor=0 でなければ先手必勝」くらいの知識から、なぜそうなるのか、また Nim でないゲームに拡張できるのはなぜか、を直感的に理解した解釈を書いたものです。たぶん、あまり厳密ではありませんのでご注意ください。(ご指摘は歓迎しています)

なお、Nim というゲームについては既知とします。

 

■ Nim で 2 つの山しかない場合の必勝法

まずは簡単な場合を考えます。

山が 2 つの Nim においては、「両方の山を同じ数にして相手に渡す」ことが必勝法です。直感的に明らかかもしれませんが、これがなぜ「必勝法」として機能するかを考えてみましょう。

まず、「両方の山が同じ数」というのは、ゲームの最終形である、石がすべて無くなった場合にも当てはまる性質です。したがって、石の数が全体として減っていくことを考えると、常に「両方の山が同じ数」で渡し続ければ、最終的には「両方の山が 0 個」で渡すことになり、勝利することが出来ます。

次に、「両方の山が同じ数」という状態で相手に渡した場合、相手から「両方の山が同じ数」で返ってくることはあり得ません。さらに、「両方の山が同じ数」でない状態で返ってくれば、「両方の山が同じ数」にして渡すことが必ず可能です。

まとめると、ある時点の盤面について、「性質 A」があり

1. 「性質 A」はゲームの終着点の「負けの盤面」の状態にも当てはまる

2. 「性質 A」の盤面から 1 手で「性質 A」には遷移できない

3. 「性質 A」でない盤面からは必ず 1 手で「性質 A」に遷移できる

の 3 つの条件によって、「性質 A を満たす盤面で相手に渡し続ける」ことが必勝法として機能することが保証されます。もちろんここでは、「性質 A」とは「両方の山が同じ数」ということを表しています。

 

■ 寄り道:非自明な必勝法の構築への応用

Nim の場合は必勝法がよく知られています(?)が、そうでないゲームにも、上記の 3 つの条件と、盤面がループしないという条件によって必勝法を構築できる場合があります。ネタバレ防止のため、問題名が見えないようにしていますが、リンクを踏む場合はご注意ください。

例題

 

■ 山が 3 つ以上の Nim への拡張

山が 2 つであれば、必勝法はかなり直感的でした。3 つ以上での必勝法を自力で見つけ出すことは相当困難であると思われますが、しかし、「xor=0 で渡す」という必勝法が知られています。先人の知恵はすごいですね。

ここでは、「xor=0」が上で挙げた 3 つの条件を満たすことを確認しましょう。

1. 「性質 A」はゲームの終着点の「負けの盤面」の状態にも当てはまる

は自明です。

2. 「性質 A」の盤面から 1 手で「性質 A」には遷移できない

もほぼ自明です。「xor=0」の状態から、いずれかの山の石の数を a→b に変えると、全体のxor(=X とします)は X から X^(a^b) になります。X=0, a!=b ではこれは 0 にはなりません。

3. 「性質 A」でない盤面からは必ず 1 手で「性質 A」に遷移できる

はどうでしょうか。少しだけちゃんと検証する必要がありそうです。

現在の X における最上位 bit を 2**k (累乗) としましょう。全体の xor がこの bit を持つことから、いずれかの山にある石の数は、この bit を持っています。この山の石の数を a とします。このとき a → a^X という手を打てれば、全体の xor を 0 に出来ることになります。そして、それには a>(a^X) であればよいです。

a^X について、反転する最上位の bit は 2**k であり、a はもともとこの bit を持っていたことから、a より小さくなることが示せます。以上で、条件 3. も確かに満たしていることが確認できました。

したがって、「xor=0」を用いた必勝法は確かに成立している、と納得できるような気がします。

 

↓ 条件 3. の確認の例題

 

■ Nim でないゲームへの拡張

Nim でないゲームについても、Grundy 数という概念を用いて「xor=0」 による必勝法を構築することが出来る場合があります。

ざっくり言うと、

1. 先手と後手が同じ盤面を共有し、同じ盤面に対しては同じ手を打てる

2. 盤面が不可逆である

くらいが Grundy 数を適用できる条件と認識しています。(適用できるだけであり、それが問題を解くのに有用かどうかは別問題です:後述)

各盤面に対する Grundy 数は、これまたざっくり言うと、

「その盤面から 1 手で到達可能な盤面の Grundy 数の Mex」とされています。Grundy 数を用いる(特に、a という数を割り当てる)ということは、ある盤面を「Nim における a 個の石の山」とみなすということです。これが正当であると納得するには、また少し思考を要するように思います。

まず、Grundy 数の割り当て方より、a の盤面から 1 手で 0,1,2,...,a-1 の盤面に遷移できることは保証されています。これは、a 個の石の山と同じ性質であると言えます。

しかし、Mex で割り当てましたので、a より大きい Grundy 数(b とします)が割り当てられた盤面にも遷移できる可能性があります。これでは、Nim とは別のゲームになってしまいそうです。Grundy 数を割り当てたゲームが Nim と等価であると納得するには、このような手が実質的に無意味であることを示すことが必要になりそうです。

まずは、必勝側の打ち手を考えましょう。必勝側は、a→b とするような手を選ばなくても、全体の xor を 0 にできます。これは、上で示したように Nim の手の範囲で必勝手が存在することが保証されており、さらに Nim の手と等価な手は全て実行可能であることも保証されていることから言えます。すなわち、必勝側にとっては a→b のような手を打つ必要がありません。

次に、必敗側はどうでしょうか。Nim の範囲の手では負けるのは分かっているのですから、紛れを求めて a→b のような Nim ではあり得ない手を打ってみたくもなるでしょう。しかし、これをした場合、次の必勝側の手で b→a という手が可能なのです。すなわち、全く同じ状況に回帰してしまいます。しかも、ゲーム自体は不可逆という仮定がありますから、いずれはこのような手も打つことが出来なくなります。以上から、必敗側の抵抗としても a→b のような手は無意味とわかりました。

もう一つのポイントは、a→a 、すなわち同じ Grundy 数への遷移だけは明確に排除されているということです。このことが、必勝法構築の条件 2. (すなわち、xor=0 から xor=0 に 1 手で遷移できないこと)を保証しています。

これらによって、Grundy 数を割り当てることのできるゲームが、Nim と実質等価なゲームであると納得できそうな気分になりましたので、ひとまず飲み込んでおくことにします。

 

■ Grundy 数の有効性とは

最後に、Grundy 数を考えることが有効な問題はどんな問題か、を考えてみます。それは一言で言うなら、「独立した山(とみなせるもの)がいくつもあり、各手番でそのうちの一つに対して手を打つ場合」だと思っています。

例えば山が 1 つであるような場合は、もちろん Grundy 数を定義することはできますが、特にそれによる嬉しさは無いように思います。しかし Nim のように、山が複数ある場合には、その全体を一つの状態量で表せてしまえるという点が非常に強力な武器となりえます。さらに言えば、xor 演算によって、2 つの山でも 3 つの山でも、1 つの山と同等の状態量で表せますので、全体の中からいくつかの山を取り出して、それを都合よくひとまとめに考える、といったことも可能です。このことは特に、山が途中で分裂してしまうような場合に、分裂した 2 つの山を xor というツールによって 1 つの山と同一視し、再帰的に Grundy 数を計算するような場合に強力な威力を発揮します。

例題

 

(おわり:考えが深まったら書き足すかもしれません)

お読みいただきありがとうございました。

MojaCoderでコンテストを開催しました!【MRC003】

 

お久しぶりです。riano_です。

MojaCoderにて、milkcoffeeさんとコンテストを開催しました!

 

↓解説もこちらのページに乗せます

milkcoffee & riano Contest 003 | MojaCoder

 

milkcoffeeさんとの開催はもう3回目になりますが、

毎回多くの方にご参加いただけて嬉しい限りです。

本当にありがとうございます。

 

また、milkcoffeeさんには毎回楽しませていただいていますし、

今回全体テスターを引き受けてくださったnok0さんにもかなり助けられました。

心強かったです。本当にありがとうございます!

 

以下、各問題やコンテスト本番の感想です。

(ネタバレを含みます)

 

■各問題について

 

A: Polygon Locus (300点 / milkcoffeeさん)

各xに対して、下限が一定、上限が単調になるため

成立可能性が単調となり、二分探索が可能となります。

シンプルにしていい問題だと思いました。

1問目にしてはやや難しかったですね。

 

B: 3-philia, 3-phobia (400点)

3回目ということで、3にちなんだ問題を作ってみました。

3の問題だったので300点にしようかと思ったのですが、

後半の証明がやや難しかったですね。

 

C: RGB Slimes (500点 / milkcoffeeさん)

個人的にはめちゃくちゃ好きな問題でした。

ちなみに、今回最初にお互い出した案の中で

唯一最終的に生き残った問題です。

なかなか気づけなくて、気づいた瞬間はかなり快感だったのですが、

有名事実でもあったようですね。

 

D: Tetrahedron (600点)

シンプルな設定ながら、解法はなかなかに泥臭い問題です。

僕自身はかなり苦労して解いたのですが、

解けてみると典型感もあり、

どれくらい解かれるのか想像もつきませんでした。

 

E: River Crossing (700点)

C問題、500点のつもりで出しましたが、最終的にこの位置に来ました。

有名なパズルの一般化で考えた問題で、

サンプルをヒントにいろいろ考えてもらう形式になっています。

僕はこういうパズル系が一番好きなので、

多くの人に解いていただけると嬉しいなと思います。

 

F: XOR Operation (800点 / milkcoffeeさん)

原案から3段階くらい進化して出来た問題です。

正直、過程を見ていてさえも難しい問題だと思ったので、

初見ではかなり難易度の高い問題ではないかと思います。

どれくらい解かれるんでしょうか。

 

■コンテスト本番の感想

思ってたより難しくてごめんなさい!!!

なかなか解かれなくて冷や冷やしていました。

後半、けっこう面白いのでぜひ解いてみてください!

 

 

今回もご参加ありがとうございました!

また開催する機会があれば、ぜひご参加いただけると嬉しく思います。

 

by riano_

高熱を出しながら考えていたこと - 少しだけSFっぽいかもしれないお話

突然ですが、人類最大の発明は何かと聞かれたら、あなたは何を挙げるでしょうか。

蒸気機関、電気、あるいは農耕…様々な答えが考えられるでしょう。

 

それら全て、正解なんだと思います。

ですが僕が選ぶとしたら迷いなくこう答えます。

それは「文字」であると。

 

 

この3日間弱、新型コロナウイルスのワクチンの副反応なのか、

あるいは単に体調を崩したのか、

一時は40度近い高熱にうなされていました。

ほぼ何もできずに過ごしていたわけですが、

それでも意識はある以上、どうしても何かは考えてしまうものです。

(もちろん半分くらいの時間はそんな余裕もなくただただ苦しんでいましたが。)

 

深く鋭い思考は、出来そうもありません。

しかし飛び石の上を渡るような、

ふわふわとした軽い思考には、むしろ適していたかもしれません。

これから書くのは、裏付けなど全くとっていない、

そんな発散した思考を書き連ねた空想のお話です。

 

 

さて、なぜ「文字」を人類最大の発明だと思うのか。

それは、人類が寿命という制約を打ち破る一つの手段であったと思うからです。

我々が享受する現代の科学文明は、1人の天才によって築かれたものでも、

一時代で築かれたものでもありません。

アインシュタインほどの天才でさえ、

ニュートンやマクスウェルの架けたはしごの上からでなければ

相対性理論など一生涯のうちに思い至ることはなかったでしょう。

 

文字という力で世代間を繋ぎ、

そうして気の遠くなるような長い年月をかけて

積み上げられてきたのが現在の文明なのでしょう。

 

それでは、今後の人類文明の行く先はどうなるのでしょうか。

例えば全人類を絶滅させてしまうような核戦争の恐怖や、

地球環境そのものの持続可能性といった脆弱性

あるいはいつの日か訪れるかもしれない巨大隕石など、

「外なる脅威」はいくらでもあるように思えます。

 

ではそれらを全て乗り切ることができれば、

人類文明は順調に発展を続けられるのでしょうか。

僕が思うには、おそらくそうではありません。

かつて文字によって打ち破った寿命という制約が、

再び人類に歯止めをかける日が訪れるかもしれません。

 

人類文明は、現在でも急速な発展を続けています。

そして我々の世代は、過去のあらゆる世代によって架けられたはしごの上から

それをわずかでも伸ばして未来へとつなげるのでしょう。

このはしごこそが文字の力であり、

一から発明するというコストを破壊する人類の力の源泉です。

 

しかし、その力は、コストを0にしてくれる魔法の力ではないのです。

再発明するのとは比較にならないほど効率的ではありますが、

教育という時間のコストを払って我々ははしごの先端にたどり着きます。

では文明がもっと成長したら?

おそらくそれを理解するために要する時間は比例して増えていくでしょう。

 

例えばそれにまるまる一生分の時間がかかるようになったとしたら、

それ以上文明を積み上げることは困難になります。

ましてや、人間が生きるためには様々なものを消費します。

全人類平均して一人の人間が生きていけるだけの生産を確保しながら

はしごを登り切らなくてはいけないのです。

さもなければ、文明は縮小に転じるでしょう。

 

全員が登り切る必要はない?

確かにそうです。

しかし、全人類とまでは言いませんが、

大半の人間には8分目くらいまでは登ってもらわないといけないのです。

民主主義というトリガーの引かれた世界で、

大多数が科学を無価値だと思えば、それは容易に捨てられてしまうでしょう。

(仮にそのような局面が訪れるとしたら、

 民主主義という制度自体が民意によって投げ捨てられる方が早いかもしれません。)

 

 

つまり文明そのものの大きさが、

文字の力をもってしても人間に扱いきれる限界に達してしまったとき、

人類の発展は止まってしまうかもしれません。

 

それが嫌だとしたら、すぐに考えられる方法は2つでしょうか。

もちろんどちらも空想上のお話です。

1つは、寿命という制約を真に破壊すること、

つまり不老不死という人類積年の夢を実現することです。

もう1つは、教育にかかる時間を徹底的に破壊すること、

例えば人類文明のデータベースを脳にリンクさせてしまうように。

(もちろん、とてもとても嫌な方法であると思います。)

 

当然ながら、このどちらかが僕の生きているうちに実現することは

ほとんどあり得ないと言っていいように思います。

それでは、我々の世代は何もできないのか。

しかしそういわれると、それはちょっと違うのではないかとも思います。

 

例えば医療の発展によって、あるいは公衆衛生によって、

人類は寿命という制約を少しづつ緩めてきた過去があります。

まったく知らないで言いますが、

おそらく教育手法だって相当の研鑽を経て、

少しづつ効率よく進化してきているのではないでしょうか。

そうした地道な積み重ねは、いつか来る(かもしれない)

人類文明の臨界点を少しだけ遠ざけているのかもしれません。

 

そうして少しずつ限界を遠ざけ、

同時に少しずつ伸ばしていった叡智の先に、

未来の人類が真にこの問題を解決する日が訪れたなら。

それは紛れもなく、21世紀の人類にとっても大きな勲章になるのではないでしょうか。

 

MojaCoder でコンテストを開催しました!【MRC002】

お久しぶりです。riano_ です。

このたび、MojaCoder という自作問題を投稿できるサイトで、

milkcoffee さんと共同でコンテストを開催しました。

ご参加いただいた方、本当にありがとうございます。

せっかくなので感想を書いてみることにします。

 

■ 各問題の解説まとめ

 

以下のリンクの通りです。ご質問は twitter までお願いします。

A- Gears

B- Long Digits Number

C- Never Surrender

D- A+BC

E- One-way and Once a Way

F- Binary-Search Game

 

■ 小学生並みの感想

 

MojaCoder でコンテストを開催するのは 3 回目ですが、

毎回本当に楽しませてもらっています。

多くの方にご参加いただけて、嬉しい限りです。

本当にありがとうございます。

 

ちなみに、MRC ( milkcoffee and riano Contest ) の開催は 2 回目ですが、

コンテスト中に順位表を眺めながら通話するのが恒例となっています。

自分の作った問題を解いてもらえるのは本当に楽しいですね。

 

■ riano_ 作問の裏話(注:ネタバレを含みます)

 

Never Surrender

bit DP の問題です。

制約から大体解法の検討はつくと思うのですが、

(そういう意味では今回のセットで一番取っ掛かりやすい問題かもしれません)

最後に残る全域木のなかで主要な部分だけを自由に決めていい、

というところがちょっと嬉しい気分になったので出題してみました。

 

One-way and Once a Way

「一筆書き」をテーマに作ってみました。

面白そうなテーマがあると、

問題を解くやる気が上がる気がするのは僕だけでしょうか。

最初は別のところに使おうかと思っていたのですが、

期限までに解けなかったのでこちらでの出題としました。

(僕はいつも問題を適当に思いついて、解けたら作問ということにしています)

 

問題の内容としては、

ARC に似たような問題(というか部分問題?)があるのですが、

それに気づくこと自体も個人的にはかなり時間を要しました。

それを前提としてさらに丁寧に場合分けして帰納的に求めていきます。

正直めちゃくちゃ難しいと思います。解けた人はすごいです。

 

Binary-Search Game

個人的に大好きな問題ができました。

「最適に行動したときの確率」という

一見どう手を付けたらよいのかわからないものを聞いているのですが、

適切な言い換えと、最善手の決め打ちをすると解法は実にシンプルです。

 

実は最初は「 N 枚から偽物を確実に特定するために何円必要ですか」

という問題のつもりだったのですが、

途中でなぜか「勝率の最大化」という発想が降ってきました。

 

そして、解いてみると実は全く同じ問題になってしまって本当に驚きました。

こういう「気づいたときの快感」みたいなものを共有できるのが

作問・コンテスト開催の何よりいいところだと思います。

(相当な難問になったので、何人に共感してもらえるかはさておき…)

 

■ テスターをした感想

 

milkcoffee さんの問題、面白いんですよね。

今回も、一足先に楽しませていただきました。

 

Gears は簡単枠ではありますが、一瞬累積積的なものが頭をよぎります。

ちゃんと気づけるとほっとする問題でした。

 

Long Digits Number も、答えがとてもきれいで面白かったです。

最初10のままやろうとして、1の位で場合分けを生じさせてしまい、

想定解を聞いてやや敗北感を感じました。

そして、サンプルがおしゃれです。

「C0FFEE」がちょうど10で割り切れるの、いい感じすぎませんか?

ちなみに Blue と Cyan に気づいた方はどれくらいいるでしょうか。

 

A+BC、これは難しかったです。

N*sqrt(N) の全探索解法がすぐに見えるのですが、

DP を工夫すると N*logN のきれいな形になります。

前者の解法や、そこから派生する嘘解法(探索範囲をいい感じに絞る)を

できるだけ落とすために制約の調整をがんばりました。

(提出欄に嘘解法作成を頑張った形跡が残っています)

想定解がきれいな問題は、解けると嬉しくていいですね。

 

■ コンテスト本番の感想

 

E が全然解かれなくてずっとひやひやしていました…

chinerist さんありがとうございます!!

部分問題が既出なので少し過小評価してしまったかもしれません。

ごめんなさい。

 

F は N^3 の DP が想定解なのですが、

答え埋め込みで通された方も多かったです。

正直全く想定していなかったので、なるほど頭いい!と思ってみていました。

(考察の途中で、5 乗 DP が出来るようになるのでこういうことができます)

答えになるパターンを全列挙して O(1) で通している方もいて、

完敗という気分です!

 

■ おわりに

 

ここまでお読みいただき、ありがとうございます。

MRC、楽しんでいただけたでしょうか?

実力は( Solver としても Writer としても)まだまだではありますが、

この楽しさをみなさまと分かち合っていけるのなら、

こんなに嬉しいことはないと思います。

 

「解けた!を私も作りたい。」

そんな想いを運んでくれる MojaCoder と、全ての受け手への感謝を込めて。

 

2021.07.19 by riano