07/17(月)

日曜日から起き続けている。

午後7時にコードゴルフ大会が終了した。結果は3チーム中で最下位。初動で全然陣地が広がっていなかったのがつくづく痛い。自分がUCを一時離脱して参加していたら何か変わっただろうか？ただそれで初見のEsolangたちと強制的に格闘させられるのも大会の醍醐味だろうし、しかもそれが上手くいって細い道をかなり辿れたので、満足感はかなりあった。

しばらく余韻に浸りながら、公開された他チームのコンテスト中のやり取りを見ていた。WriteUpは、少なくとも今日はちょっと手が回らない。また後日。

日付が変わるまでは先週の週記を書いていた。うっかり徹夜してしまったのですぐ眠気が限界に達するだろうなと思っていたが、案外目が冴えていた。ただそもそも全然書き進められていなかったため普通にやっていては間に合わない。何があったかだけ記録して細かい記述を飛ばしまくり、何とか体裁だけ整え日付が変わる直前に投稿した。

今日は祝日だったが、明日から集中講義である。教室や時間を再確認しておいた。数学科の集中講義は基本午後3時から3時間なので助かる。昨年末受講した文学部の集中講義は1限から4限までみっちり行われてかなり大変だった。

atgolferのbot用Twitterアカウントがロックされた。一応ログインすると過去のツイートは見られるようだし、またkotatsugame_tが巻き添えを食らうこともなかったのは良かったものの、これからどうやって更新通知を流したものか。

atgolferの最近のツイートを眺めつつ少しだけコードゴルフをしていたところ、さすがに眠気の限界が訪れたようで椅子の上で少し寝てしまった。慌ててシャワーを浴び、布団に入って午前3時就寝。

07/18(火)

午前10時半に目を覚ましてうっかりそれからずっとなろうを読んでしまった。集中講義のため午後3時をめがけて登校。月曜日が祝日だったため今日にずれてきたインターン先の定例会については欠席の連絡を入れてある。

集中講義について。タイトルは「深層学習の数理」で、以下に講義資料が掲載されている。

http://ibis.t.u-tokyo.ac.jp/suzuki/lecture/2023/index.html

初日の今日は深層学習の概観や基礎の話だった。No Free Lunch Theoremは格言みたいな主張をしているのにちゃんと定理であるという点を面白く感じている。不完全性定理と同じ立場かもしれない。つまり、単なる格言として消費されがちで内容まで深く踏み込まれないということ。

ニューラルネットワークの万能近似能力を保証する定理は、存在だけ聞いたことがあったが今回Cybenkoによる証明の概略を知れてよかった。シグモイド関数の引数の係数を大きくしてステップ関数を作り、それを足し引きして三角関数を作ることで、連続関数のフーリエ展開した形を実現するというもの。ReLU関数も正と負を足し合わせればステップ関数ができるのでOKということらしい。

……というのが前半の話。後半は眠気に負けてうつらうつらしてしまった。講義終了後、リニューアルオープンした理薬食堂で夕食を摂った。広くて綺麗だが人が少ない今はむしろ寂しさを強める要素になっている。また眠すぎて食欲があまりなかった。

帰宅途中、ポツポツと雨が降ってきたかと思うと一気に土砂降りになった。雨合羽は持っていたのにこうもタイミングが悪いと無力。雨宿りできるような場所もなかったためそのまま家まで原付を走らせたが、体の前面が見事にびしょ濡れになってしまった。帰宅するなり慌てて服を脱ぎ捨て、そのままシャワーを浴びた。

Amazonの定期おトク便で月一で買っているペットボトルのお茶がもう底をついてしまった。6月末に手動で買い足したのにこうなってしまうとは、消費スピードが速すぎる。とりあえず配達頻度を2週間に1回にしておいた。

午後9時就寝。

07/19(水)

午前4時から2時間くらい起きてなろうを読んでいた。その後二度寝に成功。

次は午前10時に起床。少しなろうを読んだ後インターンの作業をした。先週末からずっと後回しにしていたちょっとした問題に対応した。思ったより時間がかかって、終わったのが午後0時半くらいだった。

今日は雨が降っているので原付は使わない。歩いて川内の学食まで行って昼食を摂り、そこから地下鉄で山に登った。午後1時半過ぎに教室に到着。

実は午後1時から談話会ということで集中講義の外伝みたいなものが行われている。講義が始まるのが午後3時からなのでそれまで2時間の会だろう、それならまあ始め30分いなくても平気かな～と考えていたのに、実は1時間だけの会だったことが判明。ちゃんと調べておくべきだった。スライドも共有されなかったらしいし何もわからず終わった。残念。

合間の1時間はなろうを読んで過ごし、講義開始。今日からゴリゴリの数学が始まった。特に解析系の話が多くて、専門外なので非常に苦しい。

ニューラルネットワークの汎化性能を評価する話で、Rademacher complexityというのを学んだ。関数の集合（と固定された入力の列）があったとき、どんな $\pm 1$ の乱数列に対してもそれを良く再現する、つまり出力列との内積を大きくできるような関数が集合から用意できるなら、その関数集合の複雑度を大きいとする定義。直感的な説明でかなり飲み込みやすい。

この複雑度が大きいと学習データにのみ特化してしまい汎化性能で劣るようだ。ニューラルネットワークについての計算も実際に行われたが、上界にパラメータの絶対値が登場した。昨日のCybenkoの定理ではパラメータを大きくしてステップ関数を作っていたので、なるほど関数を忠実に近似しようとすると汎化しないということになる。これも納得できる。

後半はまた眠気に負けてしまった。たっぷり寝たはずなのに月曜日の徹夜の反動が残り続けている。

講義後はすぐ仙台駅まで出て2週間ほど前に買いそびれた切符を買った。乗車券は前回往復で買ってあったので、今回は特急券だけ購入。学割を使う必要がないから券売機で十分で、並ばずすぐ買えた。

切符を購入。行きは買えたが帰りはギリギリ一か月以上先なので買えなかった。
週記（2023/07/03-2023/07/09） - kotatsugameの日記

駅前のロフトの8階にある大戸屋で夕食を摂った。健康志向。このフロアは飲食店が集まっていたはずで、学部1年生の時にここでラーメン屋に入った記憶があるが、今はマッサージ店やらヘアサロンばかりで飲食店は大戸屋しか残っていなかった。フロア自体歩いている人が全くおらず寂しい感じ。

食事 pic.twitter.com/IXgPz4nSQa
— こたつがめ (@kotatsugame_t) 2023年7月19日

ゲーセンに行って10クレだけプレイした。今日はアイマスとのコラボイベントの最終日。何とかマップを走りきることができた。

無慈悲な集金マップ終わり pic.twitter.com/fxIkSdETZo
— こたつがめ (@kotatsugame_t) 2023年7月19日

アイマスとのコラボイベントのマップを走る日だった。205マス×9というとんでもない状態になっている。イベント終了まで時間的余裕がない。イベントアイテムはできるだけ全回収したいのだ。
週記（2023/06/19-2023/06/25） - kotatsugameの日記

途中でカメラアプリが起動しなくなったのでスマホを再起動した。実は密かにどれだけ再起動せずにいられるかチャレンジしていた。記録は稼働時間4876時間ということで、どうやら昨年末から今日に至るまで一度も再起動していなかったらしい。

カメラが動かなくなったため再起動 pic.twitter.com/pC85TCcxwV
— こたつがめ (@kotatsugame_t) 2023年7月19日

午後11時前に帰宅。シャワーを浴びて少しだけ日記を書いた。午前1時半過ぎに就寝。

07/20(木)

今日の中途覚醒は午前8時から1時間半ほどだったらしい。この間はいつものようになろうを読んでいた。

午後2時に起床して登校。今にも雨が降りそうな曇り空の中家を出て原付を走らせていたら、数分で急な土砂降りに見舞われた。タイミングが悪すぎる……！火曜日は帰り道だったから何とかなったが今日は行きの道中だから大変。慌てて近くの駐輪場に入り屋根の下で雨合羽を着た。大学に着いてみると合羽の中に入り込んだ雨の雫で腹のあたりのTシャツや下着がずぶ濡れになっていた。

集中講義3日目。内容が難しくてほとんどわかっていない。一つだけ、深層ニューラルネットワークで多項式を作れるという話を覚えている。これもパラメータの絶対値がかなり大きくなるようで、昨日の話によれば汎化しないということになる。

多項式を作れるということは変数の積が計算できるということだが、それには $2xy=(x+y)^2-x^2-y^2$ を用いるようだ。聞いていて、いわゆる「理論的には可能」な方法だと感じた。Kaggleでは何らかの積をそれ自体特徴量として使うことが多いらしいから、内部で積を計算してもらうのはなかなか学習してもらえないのだろう。

同じ集中講義を受けている学生の中に学部4年生のころ院試ゼミを一緒にやっていた友人がいた。かなり久しぶりに会うなと思ったら、実は昨年1年間休学していたらしい。その間いろいろ面白い経験をしてきたようだ。学食で夕食を摂りつつ、いわゆる「積もる話」というのを思う存分繰り広げた。

午後8時を過ぎて帰宅。うっかり3時間ほどなろうを読んでからシャワーを浴びた。

atgolferのロックが解除されているように見える。実はつい昨日異議申し立てをしたばかりなので、かなり対応が早くてびっくり。TLを見ていた感じ結構な数のアカウントがロックされていたようだから、解除の基準もゆるゆるだったのかもしれない。

Universal Cupの公式Discordで、07/29に予定されていた次回のコンテストがキャンセルとなったこと、これをもって第一シーズンが終了したことが告知された。結局自分たちのチームはトライアルラウンドの第0回とTTPCで解いた東工大セット以外すべてに参加できたらしい。upsolveどころか日記に書く感想すら全然追い付いていないが……。

夜中はDiestelの演習問題2.17と格闘していた。結構前のセミナーで他の人が担当していた問題。後半はともかく前半に歯が立たないらしい。何種類かの失敗した証明が送られてきていて、これまで気力が湧かずずっと放置していたが、いよいよ自分でも考えてみることにした。しかしダメだった。

ゴミを出して布団に入り、1時間ほどなろうを読んで寝落ち。午前4時半くらいだった。

07/21(金)

午後1時起床。購買に行ってお菓子やラノベを買ってきた。

家に「Blade Rondo -Grim Garden-」の徴税剣というカードが1枚届いた。実は先週開封した段階ですでに1枚足りていなかったのだ。サポートに連絡したら送ってもらえた。

このとき開封した段階で足りなかったことを証明できないので「自分で無くした」と言った。単に自分が不利益を被るだけの嘘で、結果的には無料で送ってもらえたのだが、存在しない自分の過失に対し寛大な対応をしてもらったということでちょっとモヤモヤが残ってしまった。やはりどんなことでも、たとえ自分を利するものでなくても嘘はつかないほうが良い。

改めて登校し集中講義最終日へ。実は先ほど課題レポートの内容がClassroomに投稿されていた。5題の中から1問選んで解答する方式で、3題は調べたことを書いたり自分の意見を述べたりするやつで2題が計算問題となっている。ポエムで単位は取りたくないし計算問題の片方はゴリゴリの解析で手が出そうにない、ということで取り組む問題が自動的に決定し、それは講義二日目まで分かっていれば取り組めそうとも判明した。ということで今日はほとんど話を聞かず、ずっと問題と格闘していた。

学食で夕食を摂って帰宅。食事している最中にレポート問題を解く有効そうな解法を思いついたので、帰宅してしばらくはそれを詰めていた。見事解けたのでレポートの清書を始めた。

しばらくして午後9時20分になり、yukicoder 398に出た。

yukicoder contest 398 - yukicoder

Aは頑張って実装。Bはdp。Cは二分探索。Dは初めて大小関係が定まるインデックスを決めるとその左の文字集合がわかり、あとは集合のサイズだけ持って桁dpできる。 $N$ と $M$ が異なるので少し面倒。

EはなんだかよくわからなかったがbitDPの制約なので解法をそれに決め打って考えた。提出戦略は常に直前までの結果を見て決められるので、次に提出する問題と何回まで乱択するかを決めるたび実際に確率計算を行いながらどのタイミングで乱択に成功するか全部試し、以降の期待値をdpテーブルから求めた。

Fは例えば $B_1$ 円の割引 $A_2$ 回と $B_2$ 円の割引 $A_1$ 回が交換可能なので、割引額が高い方に寄せるべき。よって $B/A$ が最大のものが $(A_1,B_1)$ だとすると、それ以外の2種類はそれぞれ高々 $A_1-1$ 回しか割引を受けなくてよい。その回数を $O(A_1^2)$ で探索すれば解ける。

Gは $k$ 回操作しても $X\ge 0$ であるような確率をすべての $k\ge 0$ に対して求めて足し合わせればよい。その確率は、 $k=0$ の場合は当然1である。 $k\ge 1$ の場合、確率変数の和の分布が畳み込みになることを思えば、0以上1以下で値1を持つ関数 $1_{[0,1]}$ を $k$ 回畳み込んだものを $0$ から $N$ まで積分することで計算できる。

ところで、この関数は実はつい昨日集中講義で扱われた。B-spline基底とやらの話で、以下の論文の式4.28に $k+1$ 回畳み込んだものが表示されている。

https://www.sciencedirect.com/science/article/pii/019688589290016P

off-by-oneを適切に処理すれば、求めるものは $1+\sum_{k=1}^{\infty}\frac{1}{(k-1)!}\sum_{j=0}^k(-1)^j\binom{k}{j}\int_0^N(x-j)_+^{k-1}\mathrm{d}x$ である。ここで $(x-j)_+$ は $\max(x-j,0)$ のこと。

無限和の入れ替えを大丈夫だと信じ、 $1\le j\le N$ を一つ固定して計算してみる。積分範囲を $j$ から $N$ に調整することで $(x-j)_+=x-j$ とできるから、計算する値は $\sum_{k=j}^{\infty}\frac{1}{(k-1)!}(-1)^j\binom{k}{j}\int_j^N(x-j)^{k-1}\mathrm{d}x$ 。

定積分が非常に簡単な形となって、 $k\leftarrow k-j$ としつつ $\frac{(-1)^j(N-j)^j}{j!}\sum_{k=0}^{\infty}\frac{(N-j)^k}{k!}=\frac{(-1)^j(N-j)^j}{j!}e^{N-j}$ まで整理できた。 $j=0$ もほぼ同様で、外にあった $+1$ を巻き込むことで同じ形になる。これが答えである。

73分で全完し2位。Gはひたすら運がよかった。解説を見たら頭が良すぎて横転。

全完後はレポートの清書に戻り、今度は午後11時半からCF #886 div.4に出た。

Dashboard - Codeforces Round 886 (Div. 4) - Codeforces

Aは $\max(a+b,b+c,c+a)$ のことを $\max(a+b,a+\max(b,c))$ と書いてしまい1WA。最悪。Bは $a\le 10$ を抜き出して、 $b$ の最大値を求めて、そのインデックスを調べて……とひたすらだるい。Cはよい。Dはソートして尺取り。

Eは真面目に二次方程式を立てて解こうとしたら計算を間違えるし、修正したらオーバーフローしてしまうことが明らかになるし、散々だった。 $w$ でそのまま二分探索すればよい。

Fは頻度配列にしてからジャンプをシミュレートすれば調和級数で $O(n\log n)$ になる。Gは $x,y,x+y,x-y$ のそれぞれについて値が一致する点のペアを数えればよい。Hは重み付きUFに見えたが、辺が最初からすべて与えられているので単なるdfsやbfsで十分。

AのペナよりEで時間を取られたのが響いて61位。これでもHackで上の人が落ち10位ほど上がった結果の順位である。

www.youtube.com

TLを見たりYouTubeを見たりしつつレポートを書き進めていた。とりあえず選んだ問題への解答は完成。追加で日記に書いたようなことを講義の感想として書いておいた。ポエムは書かないと言っていたが、まあ1問解いてあって感想だけで単位を取ろうというわけではないのだから、と自分の中で折り合いがついている。読み返してチェックし提出。

シャワーを浴びて日記を書き布団に寝転がった。昨日取り組んでいた演習問題についての論文が見つかったらしく、新たな証明が送られてきたので読んでいた。午前7時半くらいに寝落ち。

07/22(土)

午後4時に起きて昨日の証明を誤字に苦労しつつ読み進め、正しいことを自分の中で納得した。2時間半くらいでまた就寝。

午後8時起床。食事して午後9時からABC311に出た。

Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311） - AtCoder

Aはよい。Bはコードで一か所 $N$ と $D$ を間違えていたがサンプルで気づけた。Cは同じ頂点を2回訪れるまで辺を辿り、そこから一周した。Dは停止できるマスをBFSで探索しつつ通過したマスを数える $O(NM(N+M))$ 。

Eは正方形の左上を固定すると、右・下に向かってどれだけ穴が空いていないマスが続くかと1マス右下のマスに対してどんなサイズの正方形が作れたかを見ることで今作れるサイズが計算できる。これを右下から順に行えばよい。

Fは条件の「右下」を「右」と勘違いして時間を溶かした。後者の場合はグリッドのどの列も白マスいくつかの下に黒マスが並ぶような形をしていて、その境界が右の列に行くほど広義単調に上がっていくことが必要十分条件。正しい問題でも前半は同じで、後半は境界がすぐ左の列に比べ1行下がることを許容するという風になる。

Gは最小値を固定すると $R$ に含められるマスがわかり、その条件下で内部の整数の総和を最大化する問題になる。今 $A$ が負にならないので $R$ としては極大なものだけ考えればよく、ヒストグラムの最大長方形を求めるアルゴリズムで列挙できる。ここに $O(NM)$ かかり、最小値の固定は $O(\max A)$ なので間に合う。

Exはとりあえず $O(NX^2)$ の木dpを書いたもののそこからどうにもならなかった。列が上や下に凸だったりすれば畳み込みが $O(X^2)$ から落ちるようだが、見つかった実装を貼ってみたらサンプルで落ちたので、とりあえず上に凸ではないらしい。

Concave Max Plus Convolution | Library

Fで誤読した上、Gの最大長方形も思いつくまで時間がかかったり実装に失敗して1ペナ生やしたりで時間がかかってしまった。7完32位。Dではマスのフラグを通過と停止で別に管理していたが、実はまとめても良いようだ。1回通過したマスに後から停止してもそこから新たなマスに行けることはない。

コードゴルフはCまで。BはRakuで文字列のbitwise ANDを利用するコード。CはRubyで書いてPerlに負け。AはRubyとPerlで34Bを作ったがPerlの33Bが出た。

Rubyはマッチングがマッチした位置を返す機能を使うだけだったが、Perlは結構面白いものが書けたと思う。「自分より左に同じ文字が出現しない」文字を探せばよく、これは実はPerlの正規表現で書ける。/.(??{$`=~$&})/である。

/./で1文字マッチした後、$`=~$&が評価される。これは「マッチした位置より左にマッチした文字列が出現するか」であり、条件の否定となっている。これが真つまり1であれば正規表現に1が埋め込まれ、そのような文字は $S$ に存在しないからマッチに失敗する。偽であれば空文字列が埋め込まれ成功。

実際には、そのような条件を満たす文字のうち最も右にあるものにマッチさせる必要がある。ここは肯定後読みに/.*/を置いて貪欲にマッチさせればよい。よって/.*\K.(??{$`=~$&})/がマッチした位置が答えとなる。

www.youtube.com

先生から複素関数論のテスト案が送られてきていたので、解いて難易度感や問題・解説の誤植についてまとめ返信した。ところでこういうことはやって良いのだろうか。もちろん内容については一言たりとも外に漏らす気はないが。ついでに昨日から今日にかけて読んだ証明に関してだったりの数日放置していたメールいくつかに返信を行った。

寝るまではずっと日記を書いていた。途中で集中を切らしハーメルンを開いたところ、数日前に日間ランキングで見つけて読もうと思っていた作品が消えていることに気づいた。ワンピース世界に古龍をクロスオーバーしたものだったはず。残念なので古龍で検索して別の作品を読んだ。

「私のヒーローアカデミア　─少女は古龍の王たらん─」。タイトル通りのクロスオーバーである。非常に強力な個性らしいしそのようなシーンもあったが、描写がなんだかあっさりしていてそれほど実感できていない。

syosetu.org

午前10時半就寝。

07/23(日)

午後5時起床。3時間ほど二度寝するかしないか迷いつつ布団でYouTubeを見ていた。

午後8時くらいに起きて外出。まずドンキでパンと野菜ジュースを買った。その後夕食のため油そば屋に向かったところなんと満員。いつも日付が変わるくらいに行くとあんまり人がいないのだが、実は大繁盛している店だったらしい。仕方ないので今日も大戸屋に行った。

ねぎ間重とせいろ蕎麦のセット。セットなのだからそれぞれミニサイズになっているだろうと思ってご飯を大盛りにしたのだが、どうやら通常サイズを二つくっつけただけだったらしい。かなり満腹になった。

食事 pic.twitter.com/sw3rAmrWDZ
— こたつがめ (@kotatsugame_t) 2023年7月23日

ゲーセンの近くまで来ていたので、せっかくだからと1時間強遊んだ。木曜日のアップデートで追加された新曲を埋めた。

午後11時前に帰宅し、シャワーを浴びて半からCF #887 div.1に出た。

Dashboard - Codeforces Round 887 (Div. 1) - Codeforces

Aから難しかった。二分探索をすると決め打って考えることに。ある数 $x$ が $k$ 日間で削除されるかは判定できるが、単調性がない。そこで「 $x$ 以下に削除されず残っている数があるか」を判定することにした。

削除されずに残っている個数 $c$ は常に $S$ における小さいほうから $c$ 番目までの要素だから、削除の操作をシミュレートできる。 $k$ 回行って $c\gt 0$ かチェックすればよい。

Bは結構すぐに閃いた。 $b$ のうち絶対値が最大の要素を見ると、それが正であれば $a=n$ だし、負であれば $a=0$ になっている。よって逆に $a=0$ または $a=n$ となるインデックスを探し $\pm n$ を置いてもよい。あとは適切に $a$ を調整すれば $n\leftarrow n-1$ とした場合の問題に帰着される。

$a=0,n$ のインデックスが複数ある場合は全部に同じ値を置きたくなるが、 $n,n-1,\dots$ と一つずつ置いて行っても問題はないようだ。このことはちょっと面白かった。

Cは最初に、左のタコから順にいくつ岩を投げるか決めていくdpを考えた。状態は今投げることになっている岩の数で、コスト1で1個増やしたりコスト0で1個減らしたりできる。その個数が $\bmod k$ で $a$ と一致するようにしながら遷移していく。

$a_i\leftarrow a_i\bmod k$ としておく。具体的には $a_i=k$ を $a_i=0$ だと読み替えておく。状態は常に $a+ck$ と書いたときの $c$ で表せるが、この変化を考えることで高速に計算できるようになった。

まず $a_i\ge a_{i+1}$ のとき、同じ $c$ に対してはコストを支払わずに遷移できる。また $c+1$ に対してはコスト $a_{i+1}-a_i+k$ で遷移できる。次に $a_i\lt a_{i+1}$ のとき、 $c-1$ に対してはコストを支払わず、 $c$ に対してはコスト $a_{i+1}-a_i$ で遷移できる。

これをまとめると、基本的には無料の遷移を行い、必要な時だけ $c$ をインクリメントしたくなる。そのインクリメントのコストを過去に遡って押し付けることで、「コストのリストに $a_{i+1}-a_i+k$ や $a_{i+1}-a_i$ を追加する」「必要になったら最小のコストを取り出して支払う」として実現できる。

Dは大変だった。2行目の初期状態を1行目と揃えておいて、どの区間の文字をflipするか考える。flipした区間の文字数だけ異なる文字のペアは増える。またflipする・しないが切り替わったタイミングでペアの数が $-1,0,+1$ する。このときの値は区間の始点であるか終点であるかに無関係なので、そこそこ独立した計算ができそう。初期状態に合わせて $k$ を調整し、そこから先ほど述べたような $\pm 1$ で調整後の $k$ を作ることにした。

まず $k\le 0$ のとき、負の寄与を行えるflip方法は1通りしかない。ABAあるいはBABの真ん中の文字をflipするものである。よって端から貪欲に操作してみるのが正当。 $k\ge n$ のときはあらかじめ全体をflipしておくと良い。その状態からさらに正の寄与を捻出するためにはAAAまたはBBBの真ん中の文字のflipを解除するしかないので、これまた端から貪欲でOK。

$2\le k\le n-2$ のときは端の2文字で場合分けすると構築できた。端にAAあるいはBBがある場合、逆の端から $k-1$ 文字をflipしてみると $k-1\pm 1$ ができて、 $k-2$ だった場合に端の2文字で $+2$ を作れる。端にABあるいはBAがある場合、その端を含むように $k+1$ 文字flipすると $k+1\pm 1$ が作れて、 $k+2$ だった場合は端の1文字のflipを解除して $-2$ できる。

残りは $k=1,n-1$ である。 $k=1$ に対してはAABや端にあるABAなどいくつか自明な構築ができて、それが不可能なのは $s$ の文字がすべて一致している場合だとわかる。これはもともと不可能。 $k=n-1$ に対しては全体をflipしてから同様の考察をすることで、 $s$ の文字が交互になっていれば不可能、そうでなければ自明な構築が可能となる。