見出し画像

INTERNET (01/08)

はるふぃ

・今日は一日中家にこもって自堕落な生活を送っていたので短めの日記。昼に起きて、午後はシャニマスのTwitter企画にかじりつき、夜は競プロのコンテストに出ていた。

・まずは競プロの話から。AtCoder Beginner Contest 234、結果はABCDEFの6完だった。Fでペナを出してしまいレートが微減、厳しい世界だ。

A - Weird Function

・整数$${t}$$が与えられるので、関数$${f(x)=x^2+2x+3}$$に対して$${f(f(f(t)+t)+f(f(t)))}$$を求める問題。

・やるだけではあれど、こういうタイプの問題がAに出るのは結構目新しい気がする。「関数が実装できますか？」を問うの面白いね。


B - Longest Segment

・2次元平面上にある$${N}$$個の点が与えられるので、最も距離の長い点対間の長さを求める問題。

・$${N}$$の制約が$${2\leq N\leq 100}$$と小さいので、$${O(N^2)}$$全探索でよい。堅実なB問題って感じで好き。


C - Happy New Year!

・10進法表記で$${0,2}$$のみを使って表現される正整数のうち$${K}$$番目に小さいものを求める問題。$${1\leq K\leq 10^{18}}$$なので愚直なことはできない。

・よく考えると、$${0,2}$$のみからなる$${N}$$桁の整数は$${2^{N-1}}$$個あるので、$${2^{N-1}\leq K<2^N}$$となる$${N}$$を求めることによって桁数が分かる。あとは上の桁から順に決めていけばよい。

・解いてから気付いたけれど、$${0,2}$$をそれぞれ 'a' や 'b' などに置き換えれば、「'a'と'b'のみからなる文字列のうち、辞書式順序で$${K}$$番目のものは何？」というよくある問題になる。


D - Prefix K-th Max

・$${(1,2,\cdots,N)}$$の順列$${(P_1,\cdots,P_N)}$$が与えられるので、$${P}$$の先頭$${i}$$項のうち$${K}$$番目に大きい値を$${i=K,\cdots,N}$$に対して順に求める問題。もちろん愚直にやるとTLEする。

・とりあえず$${i=K}$$のときの答えは愚直に求めるとして、$${i}$$のときの答え$${{\rm ans}_i}$$が分かっているときに$${i+1}$$のときの答え$${{\rm ans}_{i+1}}$$を高速に求めたい。$${P_{i+1}<{\rm ans}_i}$$のときは話は簡単で、答えは変わらず$${{\rm ans}_{i+1}={\rm ans}_i}$$である。一方、$${P_{i+1}>{\rm ans}_i}$$のときは順位の変動が起き、新たに第$${K}$$位となるのは、すでに登場した値のうち$${{\rm ans}_i}$$の次に大きいものの値になる。

・そこで、$${1,\cdots,N}$$のうちどの値がすでに登場したかを管理しておき、順位の変動が起きるたびにしゃくとり的に$${{\rm ans}}$$を更新していけば計算量$${O(N)}$$でこの問題を解くことができる。

・終わったあとに解説を読んだら想定解はプライオリティーキューを使った$${O(N\log N)}$$なのだそうだ。別解を思いつけて少し嬉しい。


E - Arithmetic Number

・整数$${X}$$が与えられるので、10進表記に各桁が等差数列をなすような整数（問題では「等差数」という名前が付いている）のうち$${X}$$以上で最小のものを求める問題。$${X}$$の制約は$${1\leq X\leq 10^{17}}$$．

・とっかかりをつかむのが難しかったが、よく考えると等差数の数自体がめちゃくちゃ少ない。各桁の数字は$${0}$$から$${9}$$のあいだに収まっていなければならないので、公差$${d}$$を$${d>0}$$の範囲でなるべく小さくしたところで最大で$${10}$$桁の数$${9876543210}$$までしか作ることができない。

・実際に確かめると、17桁以下の等差数は数百程度しかなかったので、単純に等差数をすべて生成して、$${X}$$以上で最小のものを答えればよい。


F - Reordering

・とってもいい問題だった！　というより中難度典型という意味で教育的？

・文字列$${S}$$が与えられるので、$${S}$$の空でない部分列を並べて得られる文字列の総数を求める問題。例えば$${S}$$が 'aab' なら、'a' を2個、'b' を1個使ってできる文字列は何通り？　という問題になる。

・同じ種類の文字が複数あるので難しいが、「$${{\rm dp}[i][j]=i}$$種類目の文字まで並べたとき、長さがちょうど$${j}$$であるような文字列の総数」とするDPで解くことができる。

・$${i}$$種類目までの文字からなる長さ$${j}$$の文字列の隙間に$${i+1}$$種類目の文字$${k}$$個を新たに挿入するとき、できる文字列は

$$
{\rm dp}[i][j]\times {}_{j+k}{\rm C}_k
$$

通りになる。よって、状態数が$${O(|S|)}$$、遷移が$${O(|S|)}$$なので計算量は$${O(|S|^2)}$$となる。俗に挿入DPといわれるやつだ。

・ここまでを30分で思いついたのだが、PyPyで提出したらTLEしたので無駄に時間を溶かしてしまった。悲しい。


＊　＊　＊　＊　＊


・2022年1月8日の話をするなら！　シャニマスのリプライパーティーの話は避けて通れないよな！！！

・大晦日から続いてきたシャニマスのTwitter企画のフィナーレとして、メッセージをつぶやくとアイドルから直接リプライが届くとかいう狂った企画が開催された。イベントコミュ「#２８３をひろげよう」の中のストーリーをなぞるように現実世界で行われたこの企画。フィクションとリアルの狭間を低空飛行で走り抜けるようなイベントで、覚悟はしていたけれど想像の10倍くらいすごかった。

シャニマスのアイドルで埋まるトレンド

・「『リプライパーティー」と銘打ってはいるものの、するとしても一般の人のメッセージを引用リツイートするとかでしょ？』という事前の予想を完全に裏切り、本当に公式アカウントが直接リプライを飛ばしていて、開始早々おったまげる。

・何がすごいって、必ずしも優等生的な質問が採用されるわけではなくて、あくまで「そのアイドルがリプライを返したいと思ったであろうツイートにリプがくる」、というポリシーを貫いていること。

・だってこんなツイートが採用されると思わないじゃん。

・全部のやりとりにコメントしていくとキリがないので、ハイライトだけ。

・めぐるツイートの個人的第1位はこれ。うどんに「お」をつけるところとか、絵文字を付けたあとに「これはラーメン！」と続けるところとか！　めぐるらしさが全開で本当に好きだ。

・雛菜ツイートはどれも名作揃いで選ぶのに苦労したけど、これが一番かな……。巷で「インターネット強者」と言われているのも納得で、リプライのかわし方が本当に賢い。

・今回誰よりも大暴れしていたのが千雪さん、あざとすぎる……。G.R.A.D.編のラジオ番組のやりとりを彷彿とさせるようなリプライ、かなり好き放題やっていて「酒入ってる？」と言われる始末。本当に面白い。最近の千雪さんは初期とは比べ物にならないくらい個性が強くなっていて、やっぱり第一印象って信用できないなあ、という気持ちになる。

・シャニマスリプパのダークホース枠こと芹沢あさひ。飛び入り参加を宣言したはいいものの開始早々にふらふらと外に消えていき、帰ってきたと思ったらこのリプライである。ハッシュタグなし、そっけない文面、でも雪だるまを本気でもらいたいことが伝わってくるの、すごい。やっぱり公式が一番解像度高いんだよなあ……

・TLのオタクたちが芹沢あさひを釣ろうとあの手この手でおもしろ写真を投稿する流れ、好きすぎる。

・「ハッシュタグをつけろ」と言われて「#」だけ書き残すの、最高かよ。

・リプライパーティー、とっても楽しい尖った企画だったのでぜひまたやってほしい。というかこの企画の裏で動いている運営スタッフの苦労に思いを馳せて、お疲れ様です……という気持ちになった。面白い企画を本当にありがとうございました。


＊　＊　＊　＊　＊


・おまけ：限定凛世さん、230連でようやく引けた！！（9日朝の出来事）


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