見出し画像

遠きにありて思ふもの (01/16)

はるふぃ

・土曜日にAtCoderのコンテストに出たときの話を書きそびれてしまったので、忘れないうちに書いておこうと思う。

・ABC235の成績はABCDEの5完、Fが黄diffと難しめだった上にEまでを早解きできたおかげでほぼ黄色のパフォーマンスをとることができた。レーティングが1700台に戻ってきてほくほくしている。

・F、方針はすぐ見えて実装までこぎつけたのにPyPyでTLEしてしまい、C++に書き直したらサンプルは合ったのにWAが出た。悲しい。


A - Rotate

・3桁の整数が与えられるので、各桁を並べ替えてできるすべての数にわたる和を求める問題。本番では愚直に実装したが、よく考えると入力$${abc}$$に対する答えは$${(100a+10b+c)+(100b+10c+a)+(100c+10a+b)=111(a+b+c)}$$になるから、桁の和を$${111}$$倍すればいいことを知る。これ、気が付きたかった……。


B - Climbing Takahashi

・長さ$${N}$$の数列$${H}$$が与えられるので、$${H_1,\cdots,H_i}$$が単調増加になるような最大の$${i}$$に対する$${H_i}$$の値を求める問題。愚直にシミュレーションしていけばよく、計算量は$${O(N)}$$になる。


C - The Kth Time Query

・長さ$${N}$$の数列$${A}$$が与えられるので、「整数$${x}$$が$${k}$$回目に登場するのは$${A}$$の何番目か？」という$${Q}$$個のクエリに答える問題。

・愚直にやると$${O(NQ)}$$になってTLEするが、前計算として「$${{\rm ans}[x][k]=x}$$が$${k}$$回目に登場するときのインデックス」というテーブルを事前につくっておけば計算量が改善される。Pythonなら、リストを値にもつDictionary型を用意することで$${\rm ans}$$を表現できる。計算量は$${O((N+Q)\log N)}$$になる。


D - Multiply and Rotate

・「現在の数を$${a}$$倍する」「現在の数の末尾の数字を先頭に移動させる」という2種類の操作だけを繰り返して$${1}$$から$${N}$$を作るときの最小操作回数を求める問題。制約は$${2\leq N<10^6}$$である。

・一瞬 AGC044-A / Pay to Win や ABC188-F / +1-1x2 などの数学問が頭をよぎって身構えたが、よく考えるとこの操作によって桁が増えることはあっても減ることはないので、途中の状態としては高々$${10^6}$$通りだけ考えればよい。よって、これを有向グラフの最短経路問題とみなせば、BFSにより$${O(N\log N)}$$で解くことができる。

・この問題みたいに、一見すると数学的考察を要するようて実はアルゴリズムの力だけで答えを出せるやつが結構好き。


E - MST + 1

・重み付き無向グラフ$${G}$$が与えられるので、「$${G}$$にある辺$${e}$$を追加してできるグラフを$${G'}$$とするとき、$${G'}$$の最小全域木に$${e}$$は含まれるか？」という$${Q}$$個のクエリに答える問題。ただし、最小全域木が一意でないと困るので$${G'}$$を構成する辺の重みはすべて異なることが保証されている。

・ちょっと考えて、「$${G'}$$の最小全域木に$${e}$$が含まれる」と同値な言い換えを探そう、と思い立つ。最小全域木を求めるアルゴリズムであるクラスカル法によると、すでに連結になっている頂点同士を繋がないように重みの小さい順に辺を採用していけば、それが最小全域木になることが保証されている。ということは、辺$${e}$$が$${G'}$$の最小全域木を構成する辺として採用されるためには、$${e}$$より重みの小さい辺を順に採用していった段階で、$${e}$$の両端が連結でないことが必要十分である。

・あとは、クエリを先読みして重みの小さい順にソートしておき、クラスカル法のアルゴリズムに従いUnion-Find Treeを使って連結成分を管理するのと並行してクエリに答えていけばよい。面白い問題だと思う。



＊　＊　＊　＊　＊


・夜は苦労して手に入れた凛世の限定pSSR「さよならごつこ」を読んだのだけれど、本当に素晴らしいコミュだった……！　この前読んだ「ロー・ポジション」も凄かったけど、それを大きく超えてきたように感じられる。（ややネタバレ）

・今まで、G.R.A.D.編やイベントコミュを読むたびストーリーの良さに感化され、日記に長文考察を書いてきたわけだけだが、これらのコミュの良さが「シナリオの上手さ」「お話としての面白さ」という観点からのものであるとするならば、pSSR「さよならごつこ」のほうは対照的に、繊細な心情表現やお洒落な演出で読者を魅了するタイプのお話なのだと思う。センスのある言葉選び、説明を極力排した演出、エモーショナルな音楽、そういったものがきらりと光るガラス細工のようなコミュだった。

・そんなわけだから、今回はストーリーを追うのはやめて、全編を読み通す中で受けた印象を簡単に書こうと思う。

・凛世のpSSRコミュといえば、彼女がプロデューサーに向ける好意と尊敬と羨望の入り混じった感情を描くものと相場が決まっている。身も蓋もない言い方をすれば、要するに凛世は「プロデューサーのことが好きなキャラ」だ。そのような人の話を書こうとすると、ややもすれば、ステレオタイプな描き方をされてしまいがちだし、リアリティを損なったり興醒めしたりすることにつながりかねない。実際、凛世のW.I.N.G.編を読んだ私の正直な感想は、凛世さんがプロデューサーに寄せる好意の源が分からない、それが気になって没入できない、というものだった。

・けれど、「さよならごつこ」は違った。このコミュは、凛世の抱えている、言葉にするのが難しい微妙な感情の動きを圧倒的な緻密さで描くことによって、プロデューサーに対する凛世の思慕の情に強烈なリアリティを与えることに成功しているのだ。存在しない架空の生物の話をしていたらいきなり生きた実物が目の前に現れたように、裸眼でいたところを突然解像度4Kのメガネを装着させられたかのように、凛世の感情を信じるに足るだけのディテールを突きつけられたわけである。こんなものを読まされたら、今まで懐疑的だった私だって凛世の気持ちに納得せざるを得ない。帰省先でプロデューサーのことを恋しく思う凛世の想いに心の底から共感できたし、気づけば胸の内で「分かる、分かるよ凛世さん……」とつぶやいていた。そもそも、プレイヤーの側がプロデューサーと自分を重ねてアイドルとコミュニケーションをとるはずのゲームで、プロデューサーよりも凛世のほうに感情移入してしまったのがその証拠だ。

・そういった強度の高いリアリティを支えているのが、見事な演出やセリフ回しだ。序盤と終盤が対になっている構成だったり、随所に見られる暗喩やダブルミーニングだったり、TrueEndの凛世のモノローグだったり。本当に好き。

・印象的なシーンを一つだけ選ぶとすれば、やはり神社での一幕だろう。実家に帰省してきた姉夫婦の他愛もない会話を聞いた凛世が、そのやりとりを独り言のように繰り返す。強烈だった。

凛世pSSR「さよならごつこ」より「遠きにて」

・凛世の中にほとばしる感情を表現するときに、テンプレ台詞で説明するような野暮な真似はしない、そういう書き手側の矜恃を感じる。

・ここまで書いておいてなんだが、「さよならごつこ」の良さは、こんな言葉を並べ立てたところで少しも伝わらない気がする。やはり自分の目と耳でこのカードを読んでほしい。本当に素晴らしいコミュだった。

この記事が気に入ったらサポートをしてみませんか？