ごらくらいふ

プログラミングしたりゲームしたり

2024年のイベントを参加を振り返る

備忘録 雑記

2024年もお疲れ様でした。大晦日はソシャゲがたくさんタスクがやってくる。 だから2025年にこぼれました。まだ…！まだ日は昇っていないから…！！

ということでイベント参加を振り返っていくよ。

今年はGoogleカレンダーの他、Twitterのハイライト欄に貯まった予定ツイも見てみた。（固定ツイートにするとハイライトに貯まっていく）

コンサートイベント

ハッハッハ。カウンター壊れちゃったか？25件ってあるぞ？

シンデレラガールズが小さい箱を使ってツアーを6公演、初星学園が3種の公演をそれぞれ3件の地方で(3x3=9 公演)打ってるからですね。現地参戦は関東公演ばかりなので、ほとんど配信で見ている。それを差し引いても 10件あった。

イベント

  • 01月: ややとみのイベント
    • 夜の部 現地
  • 01月: ほのけ写真集イベント
    • 現地
  • 02月: この木なんの木 リアイベ
    • 現地
  • 02月: きが抜けない リアイベ
    • 現地
  • 03月: 声優グランプリｐｒｅｓｅｎｔｓ春のメルヘンティーパーティー
    • 夜の部 現地
  • 03月: AliceEyez ファンミーティング
    • 2部 現地
  • 04月: へんぼっけ 春の幸せ劇場2024
    • 両部 現地
  • 05月: 朗読劇「若きウェルテルの悩み」
    • 月曜昼 現地
  • 05月: 技術書典16
    • 現地一般参加
  • 06月: トゲガール リアイベ2nd 綺麗な薔薇と嗜む会
    • 両部 現地
  • 06月: 蒸汽電影都市
    • 昼の部 現地
  • 06月: 舞台「LIAR GAME マーダーミステリー」
    • 土曜 両部 現地
  • 06月: AliceEyez Ciel コラボファンミーティング
    • 2部 現地
  • 07月: シャニアニ2nd舞台挨拶
    • 1~3部 現地
  • 07月: Flowers AliceEyez コラボファンミーティング
    • 2部 現地
  • 08月: これがきたはら リアイベ
    • 両部 現地
  • 08月: C104
    • サークル参加
  • 09月: 名作朗読劇「少年探偵団」
    • 木曜 現地
  • 09月: へんぼっけ 秋の幸せ劇場2024
    • 両部 現地
      • 確か時刻間違えて1部に入場しそこねた気がする
  • 09月: シャニアニ2nd 3ç«  舞台挨拶
    • 1~3部 現地
  • 09月: シャニアニ2nd 3ç«  キャストトーク付き
    • 現地
  • 10月: ベルガモ朗読祭
    • 土曜 両部 現地
  • 11月: 技術書典17
    • 現地 サークル参加のお手伝い
  • 11月: えりち写真集 特典ブロマイドお渡し会
    • 現地
  • 12月: えりち写真集 お渡し会
    • 3部 現地
  • 12月: 人狼バトル ナイトメアプリンセス 1st
    • 2部 現地
  • 12月: アイマスEXPO
    • 両日
  • 12月: AliceEyez ファンミーティング
    • 2部 現地
  • 12月: えりち写真集 店舗特典お渡し会
    • インフォスクエアの部 現地

大なり小なり合わせて29件。今年はほんとたくさんイベントがあった。 特に幸村さんが舞台に立つ機会がわっと増えたのが印象的。

合わせて54件。個別にカウントすれば52を越えているので、週に1回イベント参加してるようなものだった。

もうね、そらそうなる。「見る」って決めちゃってる代わりに、グッズの具合で調整している感じ。ただ、昨今のチケット代が盛り盛り増加しているので、2025年は手が届かなくなるかもしれない。物価が1.5倍になるなら給料は2倍になってくんなきゃなー。

↓2023年の振り返り。

yajamon.hatenablog.com

アイマスエキスポへ一般参加するにあたっての準備（荷物チェックリスト）

アイドルマスター 備忘録

いよいよ、明日から2日間にかけてアイマスエキスポが開催される。

idolmaster-official.jp

ライブもあればEXPOエリアなる同人誌即売会等のスペースもあり、コミケとライブが合わさったような大規模イベントだ。

こういうイベント参加ではチェックリストを作っているのだが、せっかくだから公開してみようと思った。 まんまコミケ用とライブ用のリストが合成された内容になっている。

事前確認

  • 現地の天候
    • æ™´ã‚Œ
    • 最高気温11℃程度
    • 最低気温2℃程度
  • 移動経路

服装

  • 寒さ対策
    • [ ] ヒートテックインナー
    • [ ] あったかいアウター
    • [ ] 手袋
    • [ ] 帽子
    • [ ] ネックウォーマー
    • [ ] 雨具
      • [ ] 合羽

持ち物

  • 貴重品
    • 財布
    • 携帯
  • 外出用
    • [ ] バッテリー
    • [ ] 充電ケーブル
    • [ ] 常備薬
    • [ ] 折りたたみバッグ
  • 寒さ対策
    • [ ] ホッカイロ

思い出用

  • [ ] デレスポARのコンテンツをダウンロードしておく

ライブ観賞用

グッズ

  • [ ] 法被
  • [ ] フルグラフィックTシャツ
  • [ ] フルグラフィックブランケット
  • [ ] アクスタ
  • [ ] ぬいぐるみ

その他考えたこと

  • 水筒は持っていかない：重量物になるため。廃棄できるペットボトル飲料を買っていきたい。たためる水筒も温かいものには不向きだろう。

Nintendo Musicはノンストップライティングに最適ではないか

雑記

2024-10-31 に、Nintendo Musicなるアプリがリリースされた。

www.nintendo.com

売りの一つに、「ながさチェンジ対応楽曲」がある。これは曲中のループを調整して楽曲の長さを 15分/30分/60分 に変更するものだ。

ノンストップライティングとは、15分間書き続ける執筆エクササイズで、ながさチェンジは都合よく15分を提供している。

ゲーム音楽とは、ループが前提である。繰り返し再生に耐えうるものだ。つまり、作業用BGMとして最適だろうということ。しかしそれは1曲としては短いことを意味する。

単曲ループだと都度フェードアウト→突然曲再生の繰り返しになってしまうが、「ながさチェンジ」を使うことで「15分間のひとつの曲」を提供し、この問題を解決してくれるのだ。

早速、星のカービィをベースにノンストップライティング用のプレイリストを作ってみた。 ながさチェンジ対応曲の次に、都度「カービィのダンス」を入れている。これはボスを倒したあとに流れる短いジングルのようなものなので、タイマーのアラームの役割を果たしてくれる。

まぁノンストップライティング自体を頻繁にやってない問題があるんだけども。（前回が去年の11月だった）

時間の決まってる準備運動なんだからちゃっちゃとやればいいのにねぇ。

AHC036に参加した

AtCoder 作業メモ programming

思考の過程を書き残しました。

問題

atcoder.jp

  • N 個の都市と M 本の道路からなる平面グラフがある
  • 都市に入るための信号状態「青」「赤」がある
    • 青の場合のみ都市に入れる
  • 各都市の信号は、信号機の状態を表す配列 B および、 その制御配列A によって管理される
    • B が都市のidを含むとき、その都市の信号は「青」である
    • A の制御配列から部分列を B に転写することで信号を制御する
  • 具体的な信号制御の方法
    1. A から連続する範囲を選ぶ(RangeAと呼称)
    2. B から RangeA と同じ長さの連続する範囲を選ぶ(RangeBと呼称)
    3. RangeBの内容をRangeAで上書きする
  • 都市の番号リストでできた旅行計画があり、その順序で都市を訪問したい
    • 対象都市の数を T とする
  • 出力の最初にだけ、配列Aの内容を自由に変更できる
  • 信号制御か移動を 10^5 回以下の回数実施できる
    • 都市を移動する際、移動先の都市の信号は青でなければならない
  • 旅を成功させつつ、なるべく少ない「信号操作の回数」を求めたい
  • 着目した制約
    • N == 600
    • T == 600
    • A の長さ LA は N <= LA <= 2*N
    • B の長さ LB は 4 <= LB <= 24

とにかく次の経路の信号を青にする

  • A の長さは N 以上が保証されているので、都市idの順番と一致させる（雑実装）
  • 現在地から次の目的地までの経路をBFSで探す
  • 経路内の都市を1つたどるたびに信号制御を呼び、1都市ずつ移動していく
  • 所感
    • ビジュアライザを見れば、みるからに無駄な信号を点灯していると分かる
    • 10000ターンを超え、アニメーションGIFも保存できない
      • これはWebビジュアライザの不具合だった
  • seed0: 6_107
  • Score: 356_812

https://atcoder.jp/contests/ahc036/submissions/57132486

信号の位置を固めよう

  • 信号がまばらに点灯しているのは明らかに無駄だ
  • BFS中に近傍を漁るBFSを書いてみた
    • ブドウみたいに玉状に都市の信号が青になるイメージ
  • 信号は集まったが、なんだかバグってるらしい
    • 実際頭がこんがらがってくる
  • seed0: 4_806
  • Score: Wrong Answer

https://atcoder.jp/contests/ahc036/submissions/57137842

単純実装の派生で、折り返しだけ短縮してみる

  • 大雑把な実装として、とにかく信号機の数だけむやみに制御していた
    • 必要なのは 0 だけなのに、 01234 と転写していた
  • 1つずつ点灯していけば、経路が点灯するはずである
    • それを再利用することにした
  • 目的地への移動中、信号が点灯していない場合のみひとつだけ信号をつける
  • 次の目的地へ折り返す場合に若干信号制御が不要になった
  • seed0: 5_621
  • Score: 301_334

https://atcoder.jp/contests/ahc036/submissions/57138920

目的地から点灯済みまで逆引き

  • 過去の経路が再利用できるようになった
  • つまり、目的地から点灯済みのいずれかに接触できれば更に短縮できるはずだ
  • 経路探索を出発地から目的地へのBFSとしていたが、逆方向にしてみた
  • 折り返し時のスコアが改善した
  • Seed0: 5_020
  • Score: 247_081

https://atcoder.jp/contests/ahc036/submissions/57139467

ところで、全部の都市の信号を制御する必要あるのか？

  • たとえば旅行計画を洗ってみると当然のように都市は重複している
    • 別にすべての都市を巡らなければならない制約はない
    • N == 600 と T == 600 で誤解されそう
      • 全都市を目的地にする問題もあるにはあるだろうが
  • 使う都市の信号だけ制御すれば、制御枠に余りが出る
    • 直通の信号経路を余り枠に押し込められる
  • そのためには、実行前に行動を検証しなければならない
  • 分析のためコマンドの組み立てと実行を分離した
    • 実行速度やメモリ使用量はとくに問題にならなかった
  • とりあえず、Seed0で70都市くらいは空くらしい
    • 経路の最適化がもっと必要そうだ
  • Seed0: 5_015
  • Score: 247_280
    • HashSetのRandamStateでぶれているようだ

https://atcoder.jp/contests/ahc036/submissions/57164634

移動経路に信号の点灯状態を巻き込むの面倒だな…せや！直前の経路のどこかに当たればええ！

  • 点灯してる範囲にだけ移動しようとする実装はむやみに複雑さがあった
  • 直前の旅が完了してるということは、既存の信号制御枠で到達できるということである
    • 経路のどこかに到達すれば信号制御枠を圧迫しない
      • 余り枠で直通の制御列が埋められる！
  • あと、そろそろ1マスずつじゃなくてまとめて点灯したいな
    • まず経路を信号制御枠にまるっと転写する
    • 次に、信号機の数を上限に経路パターンごとのインデックスを貼る
      • HashMapを使う
        • 10,20,30,40,50 の経路を転写したとして、 20,30 で 1 (信号制御枠上のインデックス始点)を得るようにしたい
      • LB は4~24なので、 (n*(n+1))/2 より、ある固定区間で10~300のパターンが生まれる
        • 注目する範囲が1つずれることに信号機の倍数分増加
        • 都市の数は600が上限
          • 単純計算 4~24倍
          • 2400~14400
            • 逆経路のパターンを考慮しても更に2倍程度
          • あれ？大したことなさそう？
  • Seed0: 4_785
  • Score: 236_088
    • 総合では減りがよくない
      • 序盤こそ効いてるが、入り組んでくると細かく信号を叩いている

https://atcoder.jp/contests/ahc036/submissions/57179168

経路を一筆書きにする

  • ひとつの目的地に着くまでの移動、信号制御と区切って実装していた
    • 繋がっている経路を、目的地を境に細切れに信号制御しているのは無駄だった
  • 移動経路の決定とコマンドの組み立てを分離しているので、楽に実装できる
  • ついでに、B をまんべんなく使えるよう小手先の調整をした
  • Seed0: 4_198
  • Score: 184_755

https://atcoder.jp/contests/ahc036/submissions/57180069

信号制御枠の余り枠を使う(+バグ修正)

  • (バグ修正)使わなくなった信号機を再利用するはずが、意図しない信号機を使っていた
    • 細切れ信号制御のとき、点灯済みの経路を再利用しやすくなったらしい
  • 信号の点灯が必要になったとき、経路のインデックスを探すが当然みつからないこともある
  • 見つけられなかった経路を、制御枠の余りに突っ込めばスコアは良くなる
  • 未発見の経路の登場回数を計上し、高頻度のものから補充してみる
  • 信号制御枠の多いseedでよく効いた
  • Seed0: 3_661
  • Score: 141_256

https://atcoder.jp/contests/ahc036/submissions/57182631

長い未発見経路の価値を重くする

  • 深く考えていないが、短距離の出現頻度が高まることは容易に想像がつく
  • 細かく信号を制御してもスコアが悪化することに変わりないので、経路の長さをそのまま重要度に反映させた
    • いくつか未使用の信号制御列が出ており、悩む
  • Seed0: 3_471
  • Score: 134_376

https://atcoder.jp/contests/ahc036/submissions/57183543

ちょっと先を見越した経路を探索してみる

  • 最初はとりあえず目的地への最短経路を探し、以降は次の目的地から直近使った経路へ逆方向に最短経路を探している
  • まあまあ良くなったが、なんだかのたうち回るような経路を移動している
  • たとえば現在地と目的地、その次の目的地の3点の中央になる都市から、それぞれの最短経路を探すと共通部分が増えるのではないか
    • 中心は面倒だから、重心にしよう。足して割るだけだから。
  • 重心から近い都市を探す方法
    • 10x10(と端っこ)の区画に都市を分類して、重心の所属したグループを全探索し、もっとも近そうな都市を選ぶ
  • 結果、スコアは悪化した
    • 重心という平均的に距離が伸びる経路が展開された結果、信号操作の回数が増えざるをえなかった
  • Seed0: 4_023

システムテスト

  • 2024-09-02 現在、待ち中。

Todoほか考えたこと

  • 今回ターン数が多いからアニメーションgifの添付は難しいね
  • 中央に集まってから散っていく電鉄スタイルはどうか
  • 座標情報から幹線を定めていく幹線道路スタイルはどうか
  • これ、圧縮アルゴリズムが関連ネタかなぁ
    • 最短じゃなくても圧縮しやすい経路にしていいのがミソ
    • 頻出する経路を再利用すれば、制御枠に空きができるか？
  • 折り返し、無駄にしてるな？
    • 1,2,3,4,5 と 5,4,3,6,7 という経路が連続しているとき
      • 7つの信号機がある場合、無駄にならない制御列は 1,2,3,4,5,6,7 になる
        • 実際の移動経路の7つ分は 1,2,3,4,5,4,3 になる
        • これは、折り返しに1手増やすことになる
          • 最良でもしかしたら600手減るかもしれない
    • あんまりうまくいかなかった
      • 効くのは本当に序盤の序盤だけかも
  • 使われてない信号制御列がある
    • まったく使われない経路は謎
      • 信号制御枠の詰め直しをすれば改善したか？
  • 各都市同士の最短距離を出す？
    • それって最初の実装とほぼ一緒では
    • それが最速、最低頻度の信号制御であることは事実
  • 信号機をフルに使った場合、各点から行ける範囲を出す？
    • 経路の単純化に使えそうなんだけれど、いまいちアイデアにならない
  • もっとも最適解が出しやすい簡単な問題ってなんだ？
    • 2つの都市を往復し続ける問題
      • 1,2,_,_,_
    • 一つになった移動経路が信号制御枠に収まっている
      • 目標都市がすべて隣接していて必要な分点灯しては移動を繰り返すだけ
  • 移動経路の断片が、なるべく大きな状態ですべて信号制御列の上限に収まれば良いわけだが…
    • 伸びても大丈夫な経路とか、分割してでも経路パターンを減らした方がいいとか、難しい
  • ある2つの経路の断片があったとき、共通部分があるのなら B の端を使えば共有しやすい
    • 共通部分が B の中央あたりにあると、余剰スペースが断片化する
      • 結果手数が増える
    • 折り返し以外で経路を共有することあるか？
  • なんかAHC開催期間中のABCが怪しい(ヒントになる)気がするんだよな
    • 木の無駄なノードを捨てたりする問題とか

シンデレラガールズのアクアシティお台場コラボに行ってきた

雑記 小旅行

お台場のあれ（背面）

先日、アクアシティお台場で開催されているシンデレラガールズとのコラボイベントに行ってきた。

www.the-chara.com

東京公演メンバーがメイドジャージ衣装を着ているポスター。

UNIT LIVE TOUR ConnecTrip! 東京公演に合わせてのイベントで、ポップアップショップのほか、「東京ラーメン国技館 舞」ではコラボメニューが展開されていた。

もともとはライブ現地のタイミングで行こうと思っていたが、昼公演参加の都合であまり余裕のある日程が組めなかった。今回はそのリベンジである。 まぁコラボ期間も後半戦になれば同じ目的の者たちでごった返すこともないから、良かったのかもしれない。

少し厚い雲からぽつぽつと小雨を避けつつ、昼を少し過ぎた頃に到着した。

目的はなんといっても担当アイドルが仕事をしている様子を収めることにある。 今回のコラボに合わせて衣装が描き下ろされた。ずばりメイドジャージである。

ポジパのパネル

日野茜のパネル。可愛い。

可愛い。単にメイド服では特色が出ないと思ったのか定かではないが、確かにこれまでなかった衣装である。だいぶパッションに寄った印象があるが、こちらとしては「良いんですか？！」というものだ。 まぁアイドルといえばレッスンは当然するし、レッスンとなればジャージも着るだろう。細けえことはいいか！

そして、

コラボメニューを求めてラーメン国技館へ。

招き猫がたくさんで圧巻。

さて、この日のお腹事情を少し書いておくと、実は直前に健康診断を受けている。お昼の受診なので朝は絶食である。 そしてこやつ、「どうせ出かけるなら予定つめちゃおう！」などと行って映画の梯子をしてから受診している。（ちなみにコードギアス奪還のロゼとルックバックを観た。）

いい～～匂いがするんだ、ポップコーンの。ポテトの揚がった香りが掠めるんだ、鼻を。絶食で血糖値は落ち着いたかもしれんが食欲で血圧上がるんじゃないかと思った。

そんな食欲が選んだのは

魯肉豚骨醤油ラーメン

神仙 × ポジティブパッション コラボの「魯肉豚骨醤油ラーメン」になった。

空きっ腹に甘辛い肉と豚骨醤油スープが染みる染みる。ごちそうさまでした。

腹を満たしたのち、ポップアップショップに寄ってみた。

結構完売してる。いいこっちゃ。

展示品は撮影OKとのこと。SNS風クリアスナップはちょっと欲しかったね。

というわけで戦利品。

ネックストラップは割と良いんじゃないかと思うのだが、スマホは重いし鍵をぶらさげるわけでもなし、意外と使い所に困る。 キャラキーホルダーを付ければよかったのだと気づいたのは帰宅してからのことだった。

そんなこんなでアクアシティお台場を満喫してきた。食欲が納まらずタコベルで胃に追加投入したり暴食したりもしてました。

コラボは 2024/07/07 （日曜）が最終日なので、まだ行ってなかったりコラボ麺食いに行くかぁって方は、駆け込みまだ間に合いますよ！

お台場のアレ（正面）

Thino(旧Obsidian-memos)の代わりにQuickAddを使うようにした

Obsidian 雑記

Obsidian-memos という Obsidianプラグインがv2.0へバージョンアップしたことに合わせ、 Thino というものに改名、変質した。課金導線も整えられており、マルチレイアウトに始まりローカルサーバーが建てられるようになっていたりと、（人の褌でよくもまぁそこまでできるなという気持ちもあるが） アプリケーションの上にプラグインでもう一つアプリケーションが乗っているような状況である。

自分の用途としては、デイリーノートの特定の見出しにちょっとメモを追加できる機能こそが求められていたので、Thinoのような多機能は求めるところにない。なので、QuickAdd というプラグインを使ってみることにした。

github.com

note.com

QuickAdd で一行メモを使うまでの手順はこちらの記事が参考になった。

自分の場合、 Journals という見出しを Tweets として運用している。 よって、以下では「一行メモ」のことを「呟き」と呼称する。

Obsidian-memos とはどんなプラグインだったか

GitHub - Quorafind/Obsidian-Thino: A quick capture plugin for Obsidian, all data from your notes.

Obsidian-memos(現Thino)とは、デイリーノートに呟きを追記するためのUIを提供するプラグインだった。 入力用のテキストボックスのほか、過去の呟きが時系列を遡るように列挙され、個別に編集することもでき、過去どれだけ呟いたかGitHubの草のように表現していた。 まるでTwitterで呟くかのように雑多に書きこむ事ができた。

QuickAdd を使ってみて

  • タイムスタンプが HH:mm:ss 表記に対応していてよい
    • いくらか自由にフォーマットを指定できる
    • memosでは、 HH:mm に固定されていたため、秒単位で書き込んでいると表示に不整合が起きることもあった
  • 検索性、あるいは一覧性は下がった
    • ビューワーが無いため、スクロールで振り返るような使い方ができなくなった
    • Vault内検索で path:daily section:(Journal) などとすれば、呟きの検索は可能だ
  • 専用の呟きペインが無いのは手軽さが減少したかも
    • ポップアップした入力欄に書き込むので、呟くことに集中させられる圧を感じなくもない

過去の呟きを収集する実装を想像してみる

ここで一旦、Obsidianプラグインとしてどのように過去の呟きを収集していたのだろうかと想像してみたい。

  1. 今日を起点にデイリーノートを取得する
  2. そのファイルから、対象の見出し以下にあるコンテンツを抽出する
  3. コンテンツからフォーマットに合致する行を抽出し、整形して表示する
  4. ひとつ前のデイリーノートを取得し、同様に繰り返す

この繰り返しはいつまで続くだろうか。デイリーノートが見つからなくなるまで？工夫すれば、ペインをスクロールする必要が発生するまで？まぁこのあたりが順当なところだろう。

プラグインにとって、ひとつのデイリーノートに呟きがあるかは未知だ。 Obsidianを通して書き込むことができ、読み込むことができても、そのファイルを所有しているわけではない。プラグインが稼働していない間にファイルが変更される可能性があるのは原則だ。

たとえばこれまでデイリーノートを毎日書き込んできて、ある日 Obsidian-memos(Thino) を入れたとする。そのデイリーノートには呟きはないのだから、プラグインが起動するたびに全件のデイリーノートを読み込む恐れさえある。

まぁ、人間はたかだか100年も生きられるか分からないので、デイリーノートは36500ファイル、その半分を超えられるかも疑わしい。全件読み込むコストなんて屁でもない。ブロックサイズ4KBなら、1万件で 40MB くらいなものだ。 だが、なんだか気持ち悪くないか？

過去の呟きをどう見ていくか

過去の呟きをスクロールして見ていくというのは無駄が多い。直近のものからしか遡れないし、目的の言葉があるなら検索したほうが速いからだ。

しかし、機能としてできなくなった事を「あれは無駄だったから」などといって慰めるのはみっともない強がりというもの。代替手段はあるはずだ。

Daily Notes Editor プラグインを使う

github.com

これはデイリーノートを一枚のペインでインラインに表示し、表示だけでなく編集できるプラグインだ。デイリーノートがまるまる見えるので呟き以外の情報をまとめている人にさらに便利かもしれない。

自分の場合は中身があったりなかったりする見出しがあり、ノイズに感じるところもあった。このあたりはテンプレートの相性もあるだろう。

スクロールしてペインの末尾にいったら更にデイリーノートを読み込む挙動をしている。

この相性の悪さだ

Calendar プラグインを使う

github.com

これはカレンダーペインを表示するプラグインだが、各日付をクリックするとデイリーノートを開くことができる。

「あの日なに言ってたっけ」とダイレクトに見返すことができる。

当月であれば、クイックスイッチャーでデイリーノートを直接開くよりも手間が少ないかも。

Periodic Notes プラグインを使う

github.com

これはデイリーノートのほか、ウィークリーノートやマンスリーノートの作成を支援するプラグインだ。実はこのプラグインには「前の日(次の日)のデイリーノートノートを開く」コマンドが同梱されている。 これにホットキーを割り当てれば、次々と過去のデイリーノートをめくることが可能になる。

前述のようなプラグインが勝手に次々とファイルを読み込む仕組みに比べて、好ましいと思う。

いまのところ

QuickAdd に移行というか、呟き自体がそんなにまだない。（とりあえず新規ノート立てて雑多に書くか、ツイートしだすタイプ） 呟きはQuickAddを使いつつ、過去の参照はもっぱら検索を使っている。

AHC031に参加した

AtCoder 考え方

MC Digital プログラミングコンテスト2024（AtCoder Heuristic Contest 031）に参加したので、問題を解いた過程を記録してみた。

問題

atcoder.jp

  • W x W のグリッドで表現されるイベントホールがある
  • D 日分の予約群があり、日毎に N 件の予約がある
  • 各予約には使いたい面積がある
    • スペースの確保は長方形で行われなければならない
    • 予約スペースは被ってはいけない
    • 要求面積より余分に大きいスペースを貸し出してもよい
  • 各予約スペースを区切るためにパーティションを設置する
    • この辺の長さ 1 に応じて 設置コスト、撤去コストが 1 かかる
    • 日付をまたいだとき、パーティションに変更がない箇所はコストがかからない
    • 要求面積に満たない区画しか貸し出せなかったとき、不足面積 x 100 のコストがかかる
  • たとえ少ない面積でも、すべての予約に場所を用意しなければ WA
  • なお、初日のパーティション設置コストは特別に 0 とする
  • コストができるだけ小さくなるようにする
  • 制約
    • W == 1000
    • 5 <= D <= 50
    • 5 <= N <= 50

サンプルをベタ移植

  • ちょっと問題を掴み取れていなかったので、サンプルをベタ移植した
  • å¹…ã‚’ 1 に、高さを W のほっそい区画を全件用意するもの
  • Score: 107_822_101_150

https://atcoder.jp/contests/ahc031/submissions/51728038

すべての予約を縦割りで割り当てる

  • サンプルを基盤に、高さ W のまま、幅を調整して割り当てることにした
  • 大雑把な実装なので、最低限である幅 1 は各予約に用意する
  • 余分にスペースを確保すれば、チリツモで空間が足りなくなるので、大きい面積を要求する予約から割り当てた
  • Score: 264_827_950

https://atcoder.jp/contests/ahc031/submissions/51734984

in/0004.txt

しばらくコスト算出の実装に精を出す

  • 今回、インタラクティブ問題ではないこともありコスト算出ツールがないので自前実装した
  • 使う場面が来ればいいなという思惑
  • 不足コストは比較すればよいので簡単
  • パーティション設置のコスト算出は、ABCで解くような問題に感じて楽しかった
    • 水平方向と垂直方向に線分をわけて考える
    • 線分の始点と終点で加減算して一つの線分へ合成したり（パーティションを求める）
    • 当日と前日それぞれのパーティションの始点と終点で加減算して撤去・敷設を求めたり
type PartitonEvent = (usize, usize, isize);
type AlignedPartitions = HashMap<usize, Vec<(usize, usize)>>;
fn partition_by_event(event: &Vec<PartitonEvent>) -> AlignedPartitions {
    let mut partition: AlignedPartitions = HashMap::new();

    let mut state = 0;
    let mut begin = 0;
    for (level, point, volume) in event.iter() {
        // FIXME: hardcode
        if *level == 0 || *level == 1000 {
            // 外周部は壁なのでパーティションはいらない
            continue;
        }

        if state == 0 && *volume == 1 {
            // 0から1に変わるとき線分が始まる
            begin = *point;
        } else if state == 1 && *volume == -1 {
            // 1から0に変わるとき線分が終わる
            let line = (begin, *point);
            if partition.get(&level).is_none() {
                partition.insert(*level, Vec::new());
            }
            if let Some(v) = partition.get_mut(&level) {
                v.push(line);
            }
        }

        state += *volume;
    }

    partition
}

コストについて考えた

  • コスト算出が実装できたので、手元で試行錯誤できるようになった
  • いじっては数字を観察し、コストについて考えた
    • 予約ひとつの必要とする外周の長さは、正方形に近いほうが小さい
    • 予約スペースがパーティションを共有すれば、その分コストが安くなる
    • 正方形を敷き詰めると、パーティションの置き換えが発生してコスト高になりそう
    • 最初に設置したパーティションはコストの算定外になる
  • 正方形のイベントスペースを長方形に区切って固定してしまえば、パーティションの置き換えを短辺の分だけで済ませられるのではないか

イベントスペースを長方形のセクションに分割する

  • 正方形のイベントスペースを長方形の集まりとみなすことにした
  • W は 1000 固定なので、割り切れる数はハードコードできる
  • 最も大きい面積を要求する予約を基準に、正方形の分割数を決めた
  • 未使用スペースの多いセクションから順に割り当ててみた
  • また、前日と当日で必要とするスペースが大きい方に、予約スペースをあわせてみた
  • Score: 61_243_541

https://atcoder.jp/contests/ahc031/submissions/51763370

in/0004.txt

セクションの分け方を実験した

  • 全日程を通して大きい予約を基準にセクション数を決定している
  • 日ごとに最も大きい予約を基準に分けるとどうなるか
    • -> 大半のスコアが悪化した
      • 分割数が 2 と 4 を往復したりして、都度 2000 の撤去コストが発生したりした
  • 引き続き、全日程の予約を通して最も大きいものを基準とすることにした

複数ナップサック問題？

  • 全日程を通してセクション数を統一するということは、各予約面積に割り当てる高さが固定になるということだった
  • つまり、容量1000の容器がいくつかあって、各予約が必要とする面積（＝実質は幅）を割り当てればよさそうだ
  • それは複数のナップサック問題ということか
    • それって難しいやつでは…？
  • あぶれた予約は、一番大きい予約から場所を分けてもらうことにした（雑実装）
  • とりあえずテストケースは通った
  • 多くのセクションで端まで使うことが増えたため、その分のパーティションが減らせるようになった
  • Score: 58_509_946

https://atcoder.jp/contests/ahc031/submissions/51763370

in/0004.txt

余裕のあるところに詰めてもらう（雑実装の解消）

  • どうしても余分にスペースを確保しているので、収まりきらない予約のために詰めてもらったりした
  • あぶれた予約の対処が雑だったので、丁寧に詰めてもらうようにした
    • 余分にスペースを調達している区画から削っていった
  • 塵も積もれば山となるらしく、かなりコストを削減できた
  • Score: 18_631_300

https://atcoder.jp/contests/ahc031/submissions/51766245

in/0039.txt BEFORE

in/0039.txt AFTER

システムテスト

  • 燦然と輝く TLE x3
  • 退場処分になりました
    • 200位付近だったのに
    • 2000ms 付近は危険領域だったか～
      • 信頼できるのは 10ms まで
  • 261位になりました
    • 該当部分のみ相対スコア0点になるが順位参加を許された

https://atcoder.jp/contests/ahc031/submissions/51939513

やりたかったこと

  • 前日の予約と当日の予約でどんどん大きい方を採用していったが、余分に確保しているスペースが多い予約だけを削れればパーティション構成の変更は少なかったのではないか
  • ナップザック問題を解いて最後に集まったセクションは、細切れの予約が多く余白も多々あることから、コストの少ない配置方法をさがせるのではないか

AHC 青パフォとなって水色になれました。今後も頑張ります。

https://atcoder.jp/users/yajamon/history/share/ahc031