Weekly Report 2024/12/29〜2025/1/4

12/29(日)

ここ最近は蟻本埋めをやっている．具体的には，蟻本を読んでatcoder上の類似問題を解いている．

[AtCoder 版！蟻本 (初級編)](https://qiita.com/drken/items/e77685614f3c6bf86f44

グラフは得意なので序盤はスイスイ進んだが，これからは難しいと思う．順列全探索をする際にソートされていない配列を渡してしまって全列挙されないという罠にハマってしまった．

BFSの良い問題を解いたので紹介する．

AOJ 0503 Cup

隣にしか移動できないハノイの塔で最小手数を求める問題である．

状態数は，各カップに対してそれぞれA, B, Cのどこにいるかを持っておけば良いので，高々 $3^{15}=14,348,907$ 個である．訪れた状態をメモするとき状態を3進数で表しておけばメモリ効率が少し良くなる．

12/30(月)

家の24時間フィルターを掃除した．気分が良い．

蟻本埋めは貪欲法をやった．今日終わらせたのは，有名なコイン問題と区間スケジューリング問題である．コイン問題の類題にdpが隠れていて少し苦戦したが，自力で通した．区間スケジューリングは，終了時間の早い順に貪欲に取っていけば良い．軽く証明を書いておく．

証明

区間の集合を $I$ とし，最も終了時間の早い区間を $A$ とする．区間同士が重ならないように $I$ から区間を選んだとき，どのような選び方についても以下が成り立つ．

選んだ区間のうち最も終了時間の早いもの $B$ を $A$ と入れ替えても，選べる区間数は減らない．

なぜならば， $A$ の終了時間 $\leqq$ $B$ の終了時間 $\leqq$ 他の任意の区間の開始時間，という関係が成り立つため，区間 $A$ と重なる区間はないからである．よって， $I$ から区間を選ぶ際はまず $A$ を選んで良いことがわかる．

$I$ から区間 $A$ と「 $A$ と重なる区間」を除いたものから区間を選ぶ際も，同様の議論によって終了時間の早いものを選んで良いことになる．

区間スケジューリングに帰着して解ける問題をいくつか解いた．以下の問題は自力で解けてよかった．

https://codeforces.com/contest/528/problem/B

12/31(火)

まあ色々と掃除した．埃だらけ．蟻本埋めは「交換しても悪化しない」貪欲法をやった．年越し．

1/1(水)

dpの章に移った．とりあえず蟻本の2-3を全て読み切るが，書ける気がしない．atcoder版蟻本に載っている問題のdiffを見る限り，一旦は初級編でやめておいた方が良さそう．元日ということで初売りに行き，成人式に着ていくスーツを新調した．あとは春から一人暮らしをするので布団などを購入した.

1/2(木)

今日も初売りで色々と歩き回ったが，結局Amazonの方で買ってしまうものも多かった．まあこういうのは実際に見て回ることに意味がある．憧れていたブックタワーをAmazonで購入した．170cmくらいある割と高めのものだが，手元に置いておきたい本はたくさんあるし部屋は狭いので意外と実用性はあるのかもしれない．

1/3(金)

年末年始で色々やっていたが，ここで急にフリーとなったので爆睡．それ以外のことはしていない．ヤフーショッピングでなぜかクーポンをもらったことがあり，それで購入したラーメンを食べた．

1/4(土)

コンテストをサボって爆睡．何を思ったか典型90を埋め始め，最初の方で挫折．とりあえず簡単なものから埋めようと思って灰diffを何問か解いた．冬休みも終盤に差し掛かりなんのやる気も出ないので薄い1日を過ごした．あとからabcの問題をみたら地獄のようなdiffになっていた．Cはパッと見桁dpで，Dはかなり簡単だった．Dが緑になっているのは問題自体の難易度ではなくて，Cにある壁が原因だと思う．