2024-09 月記
最近月記をいくつかの理由のもと英語で書いていましたが、今月分は日本語で書くことにしました。ちなみに理由は英語能力が向上したからではありません。最近だと”equal contribution”がパッと出てこず自分に失望しました。
教習所
普通免許を取ろうと思って、8/2から定期的に教習所に通っていましたが、ようやく仮免許が取れました。
ただ、これだいぶ危うい取得でした。
仮免許の取得の為には、筆記と実技の両方が私の所では必要で、筆記は丸暗記で済むので何とかなりましたが、実技がギリギリでした。
ウィンカーの出し忘れで5点減点、障害物を避ける際の進路変更における安全不確認で5点減点、そして交差点を時速14kmで走って20点減点でした。全然気付いてなかった……。
教習所は今の時期混んでいるらしく、最終的に免許が取れるのは11月の終わり頃の予定です。
文化祭
友人の妹さんの伝手で、洗足の文化祭に行きました。確かこれは3度目なのですが、今年も相変わらず楽しかったです。
https://sites.google.com/view/iroha2024/home?authuser=0
一般公開されているものではない為、内容はあまり書かない方が良さげなので書きませんが、初めて見た書道部のパフォーマンスは遠目からでも滅茶苦茶に格好良かったです。美術部も相変わらずレベルが高くて感動でした。
多分未来においては写真なども変わってしまうでしょうが、このリンクに今年の代らしき方々が写っていました。
https://www.senzoku-gakuen.ed.jp/life/club_activities.html
そして件の妹さんは絵を描いていらっしゃるんですが、本当に非常に絵が上手くなっていてビックリでした。昔何度か絵の話をした方がありますが、もう今となっては私なんか足元にも及ばないレベルですね。
あのような絵を見られて、心の底から幸福でした。本当に嬉しかったです。
JAG合宿
ICPC OB/OGの会が主催するJAG合宿に参加しました。
競プロを沢山してきました。
1日目
Bは、自分の初動が最悪でした。簡単に言えば下図内部の格子点の数を数えろという問題なのですが、これを深く考察せずに「簡単!」と言ってチームメイトに丸投げした結果、沼に引きずり込んでしまいました。
これやっぱり普通に難しいというか、方針を間違えると地獄です。多分、正解はx軸方向に走査して、validなy座標の個数を数え上げ、最後に灰色部分を引くという方針なのですが、半円や四分円毎に考えるという方針を伝えてしまいました。こういうのは全く解けていないのと同義なので、軽はずみな発言に伴う重い責任を知りました。
Hで、Fenwick_treeを書く必要があったもののkactlの実装があまりに短くてビビりました。チームメイトに写経してもらったら一瞬で終わりました笑
Iは、スポーツクライミングの順位を決定せよというABC-Aレベルの問題だったのですが、情報伝達ミスでペナを出しました。こういうの本当に勿体ないので、非常に反省しました。私はもっとちゃんと人の話を聞くべきですし、確認を怠らないことも必要です。
ところで、チームメイトの一人が今年あたりから競プロを始めた方なのですが、Jでめっちゃスムーズに二次元累積和を実装していて驚きました。昔の私とかその頃絶対そんな芸当できてなかったと思います。相当な努力をされていて感動しましたし、3日間色々と助けられました。本当にありがたいことです。
2日目
Bは、良い括弧列にするには何個の書き換えが必要か求める問題で、比較的早くから感覚的には解けていたのですが、それを数式に起こすのがド下手くそすぎてあんまり貢献できませんでした。
Cは、紙幣の値段を自由に決定できる時に、A円・B円・C円を払うのに必要な紙幣の枚数を最小化せよという問題でした。例えば6000円・11000円・15000円ならば、現行の紙幣で2枚+2枚+2枚で払えて6枚が最小です。単に自分が解けたからという理由だけですが、この合宿で一番印象に残っています。
解説で言及されていない方法で解いたので少し述べておきます。まず、紙幣の値同士の比は素数で良いです。1円より真に大きい最小の金額(p円)の紙幣を決め打った時、解はA/p円・B/p円・C/p円の場合の答えにA%p+B%p+C%pを足したものになります。
ここで、解はpopcount(A)+popcount(B)+popcount(C) (1円札・2円札・4円札・8円札……)で抑えられるので、A%p+B%p+C%pがそれ以上大きくなった時点でその解は最適ではありません。
そのようにしてかなりの候補が枝刈りできます。また、本質的に枝刈りが困難なケースでは、最終的に同じ場合の問題に帰着されることが多いので、メモ化再帰にすると通すことが出来ます。
人生で初めてFA (First Accepted)をとれて、とても嬉しかったです。ただ、よくよく他の参加者のお話を聞く限り、dpでもっと計算量保証をした上で解けるそうです。力不足ですね。
Gは、長さ1の棒A1本・長さ2の棒A2本・長さ3の棒A3本で沢山三角形を作ってねという問題で、所謂簡単枠なのですが、無駄に頭を壊して困りました。全探索で良かったそうです。愚かでした。
Kは、区間[L,R]のいずれの値も割り切らない値の内k番目を求めよという問題で、これも比較的解かれていたのですが、全く思考がまとまらず駄目でした。xがその条件を満たす⇔floor((L-1)/x) = floor(R/x)で、この商を全探索すればいいだけだったのですが……
Nは、チームメイトのお陰で解けました。
DAG上の最長路の数え上げがスムーズに出来たのは良かったですが、「この素数判定の処理をする時、絶対試し割りをしちゃダメだよ?」と念を押されたのにも関わらず、普通に試し割りをしてTLE (Time Limit Exceeded)なんで???みたいな大馬鹿をしていてアホでした。ごめんなさい。
3日目
A,Bは、簡単でした。BFSの実装如きでかなり詰まりましたが。
Gは、aとbからなる秘密の文字列Sに対して、”? aba”などと送るとabaがSの部分文字列かどうかを返してくれる時、Sを特定せよという問題です。
チームメイトのお陰で本質的に解けていて、S=”aaba”の時、
? a → Yes → “a”
? aa → Yes → “aa”
? aaa → No → “aab”
? aaba → Yes → “aaba”
と一文字増やしていけば大まかに良いです。後は乱択をして確率を抑えたり左右両側に文字を足すなどすればいいだけでした。
しかし、この方針でやってずっとWAが出ていました。辛かったです。そしてこれが尾を引いて3日目の成績が一番悪かったです。最終日もBronze圏内くらいには入りたかった……
未だに原因は分かっていないというか、恐らく永遠にそれを解明する機会を失ったのですが、多分空文字列を送ってInvalidな操作をしていました。こういうのは悔やんでも悔やみきれないので、どうにか避けたいです。
とりあえずの再発防止策として、インタラクティブな問題ではWAが出たからといってassertに引っかかっていないとは限らないということを認識することでしょうか。まぁこれが真かどうか分かっていないんですが(?????)
Kは、マージテクを頑張ると解けました。
色々な方とお話出来てありがたかったです。
コミュ障なのでちょっと疲れましたが……
また、運営等に携わって下さった方には本当に感謝しております。
ありがとうございました。
本
友人の勧めで、本を色々読みました。
もし僕らのことばがウィスキーであったなら
村上春樹さんの紀行文を読みました。
お酒は相変わらず嫌いですが、その魅力に恋焦がれて探求せんとする人々のことなどは好きになりました。
面白い本でした。
星を編む
冒頭数ページの、話の本筋と全く関係ない箇所で随分沈んでしまいました。
この本で最初のパートで恐らく打ち立てられている命題に対し、「恵まれた運を僻まれる居心地の悪さを感じ、それを行動に反映させつつ、一方でその幸福を精一杯に享受し続ける」というのを一応の解答として生きています。
まぁ友人には（意訳として）そんな気にするなみたいに言われましたが。
ただ、それはそれとして結末はとても面白かったです。まだ第三章を読み残しているので、来月あたりに読みます。
研究
詳しくは書きませんが、今月および先月は修士の研究で沢山悩みました。
研究で、誰かの役に立ちたいです。
勉強
格子手術について勉強していました。
嶋田 義皓さんの「量子コンピューティング」という本や、以下の辺りを読んでいました。
https://www.ohmsha.co.jp/book/9784274226212/
https://shota.io/2017/12/24/surface-code.html
いい加減に表面符号の理解をしたいですね。
この月記の最後に、人間関係に関する悩みとして、相手に対して別に言わなくていいことが心の中に生じた際、それを言った方が誠実なのか、言わない方が誠実なのか、最近分からなくなって来ました。自分は隠し事が下手なので、よく言って後悔してます。
臨機応変に対応出来れば良いんでしょうが、（この類の状況に限らず）大抵の場合にコミュニケーションの選択をミスっていそうで自分に呆れます。
私と良く喋る友人達は、この辺り諦観しつつも、なお私と話してくれている節があり、非常に感謝しています。
ごめんなさい。
いつもありがとう。