2023/08/07
記憶が欠落
ABC271-Cの”Manga”を解く。ぱっと見、どうやら貪欲法ぽいぞと思った。とりあえず思いついたもの（入力Aを、後半に被っている巻数の単行本を追いやり、前半に残った単行本が配置されるように並べ替える（Bとする）。1〜Nまで、i巻目は読めるか？という判定を行う。Bにiが含まれる場合は読める。含まれない場合は、Bの末尾から2つ削除できるか判定し、削除できる場合は読める。どれにも該当しない、つまり読めない場合はi-1を出力して終了する。）を提出したものの、9WAで不正解。
うーん？となり、しばらく考えてみると盲点に気がついた。Bにiが含まれる場合…の部分を高速化するために、操作を始める前にsetにBの要素を投入したものを用意していた。ところが、Bの末尾から二つ削除する操作を行う際、setからも消えなければならないものがそのままになっていた。
要は、巻数ごとに単行本の個数を管理しなければならなかった。multisetの出番という感じだが、あいにくPythonにそれは無い。標準ライブラリのcollectionsにCounterという似たようなデータ構造があるので、これを代わりに使うことにした。
Counterを使った実装に切り替え再度提出したが、3WAで不正解。提出結果からWAになっているテストケースの名前を見てみると、04_max_xx.txtとなっていた。max？なんだそりゃと思ったが、後から思えばこれは結構大きなヒントだった。
コードと睨めっこしても埒があかないので、バグを疑ってassertを追加したコードを提出した。これがREになれば何かバグがあるということになるが、残念ながらバグはなかった。再び考える。考えたことを整理するために、コードにコメントを多めに書くことにした。しばらくして、Counterを使った実装の問題点に気がついた。
処理の内容を文に書き起こしてみると、「1〜N巻までi巻目が読めるか判定し、読めない場合はi-1を出力して終了する」となる。では、1巻目からN巻目まで全て読むことができる場合はどうなるだろうか？「読めない場合はi-1を出力して終了する」つまり、全て読むことができる場合は何も出力されないのだ。気がついたときは「ひえ〜〜〜」となった。恐ろしい
読めるかの判定を行う範囲に、絶対に読むことのできないN+1巻を追加して、N巻まで読める場合にも出力されるようにすると、ACすることができた。最初のCounter解でWAになっていた、〜¥max¥〜とは、N巻まで全て読める場合という意味だったらしい。
こうやって書き起こしてみると、結構長い戦いだったな…
https://atcoder.jp/contests/abc271/tasks/abc271_c CounterAC解: https://atcoder.jp/contests/abc271/submissions/44371770 初期解（WA）: https://atcoder.jp/contests/abc271/submissions/44371174 初期Counter解（WA）: https://atcoder.jp/contests/abc271/submissions/44371272
2023/08/08
13時ごろに起きる。
予定があるので早めに起きたものの、琵琶湖大花火大会が行われる影響で道などが混んでおり、安全上よろしくないということで予定がなくなってしまった。早起きの意味…
エアコンの洗浄業者が来た。エアコン内部に高圧洗浄機のようなものを当てると、濃いコーヒーのような、真っ黒の液体が出てきた。ひえ〜。業者の人曰く、使用年数的にはマシな方らしい。今回はカビなどが詰まって風が出なくなってしまっていたのだが、洗浄が終わるともう風がビュンビュン出てくる。業者の人が測ったデータを見ると、洗浄前は風速2m/sだったのが洗浄後には5m/sになっていた。ほげ〜〜〜
エアコンが効くようになり、QOLが大幅に向上した。汗だくになりながらPCをいじったりすることが無くなった！最高
JOIの参加登録をした。
琵琶湖大花火大会を見る。4年ぶりの開催ということで、とても楽しみにしていた。大きめ花火が炸裂すると、大きな音と衝撃が伝わってくる。この感覚も久しぶりだ。外に出て花火を見物して、2万箇所くらい蚊に刺されるのも厭わないつもりだったが、この文を書いている時点では刺された痕跡は一つも見つかっていない。蚊に人気が無い
ABC273-Dの“LRUD Instructions”を解く。壁の座標をいい感じに持って、伝家の宝刀二分探索をする。グリッドの外に行ってしまう場合の処理が面倒くさそうだと思ったけど、グリッドの外を壁とみなして、番兵として持つことで実装を簡略化することができた。いい感じ。
「このy座標のマスにある壁のx座標」と「このx座標のマスにある壁のy座標」をdefaultdictで持つよう実装した。二分探索を行うためには、壁の座標が含まれる配列をソートしなければならない。defaultdict.values()を使ってそれぞれソートすればいいものを、なぜか「入力で与えられた壁を順番に見て、その壁の座標が記録されている配列をソートする」という方法で行なってしまった。この方法だと、例えば壁の全てが同じy座標（縦に一直線に並んでいるイメージ）にある場合、無駄に何回もソートを行うことになってしまい、TLEする。
最初は「入力が遅いのかしら〜？」とか呑気なことを考えていたが、そもそものアルゴリズムがカスだったということで…。ちゃんとやりたいことを明確化して（この場合は、座標が記録されている配列をソートしたい！）それに見合った処理を行いたいわね…。あとソートは重たい操作なので複数回繰り返すのには慎重になるべき。
CPythonと比べてPyPyは非常に多くのメモリを使用することがあるが、この問題への提出では差が小さかった。そんなこともあるのね
https://atcoder.jp/contests/abc273/tasks/abc273_d AC解: https://atcoder.jp/contests/abc273/submissions/44394083 TLE解: https://atcoder.jp/contests/abc273/submissions/44393814
ABC270-Cの”Simple path”を解く。普通の幅優先探索で最短経路問題を解いたら良い。この問題は練習のためにC++で実装した。
https://atcoder.jp/contests/abc270/tasks/abc270_c
https://atcoder.jp/contests/abc270/submissions/44396936
ABC273-Dの”Root M Leaper”を解く。練習のためにC++で実装した。幅優先探索な感じがしていたが、距離がsqrt(M)なマスに飛ぶ方法がわからず解説を読んだが、それもよくわからず他の人の提出を読んで理解した。そもそもマス目がそんなに大きくない（1 <= n <= 400）ので、全探索で「原点からの距離がsqrt(M)なマスの座標」を求めることができる。求めたものは、「あるマスと、そのマスとの距離がsqrt(M)なマスの座標の差」として使うことができるので、これを使って幅優先探索を行った。
スタート地点からの移動回数を記録する二次元配列を初期化するための二重ループで添え字の条件を間違えており（j < nがi < nになっていた）、配列外参照でメモリ破壊を起こし、C++の洗礼を受けた。なんか変だな〜とprintデバッグをしたら、いじっていないNが突然-1になってびっくりした。隣のメモリに配置されていたらしい。
これはPythonやSafeなRustだけを書いていたら無い体験で、なかなか面白く感じた。とはいえ、コンテスト本番でこのようなことになってしまったら困るので、何か対策を知りたい。調べてみると、gccに添字の境界チェックを自動的に挿入させるオプションがあることがわかった。試しに前述の配列外参照を起こすコードをコンパイルして実行してみると、「何行目の部分で配列外参照が起こったぞ！！」エラーが出て実行が中止された。これは良い。配列外参照への対応はわかったので、他の未定義動作への対処も調べてデバッグ方法を確立したい気持ち。
https://atcoder.jp/contests/abc272/tasks/abc272_d https://atcoder.jp/contests/abc272/submissions/44397598
2023/08/09
なんだか眠れなかったので、寝る前にABC271-Dの”Flip and Adjust”を解く。和をxにできるか？のDPをやった後、DP配列を後ろから見て復元したものを出力した。良い感じ
https://atcoder.jp/contests/abc271/tasks/abc271_d https://atcoder.jp/contests/abc271/submissions/44398513
14時ごろに起きる。
外出マン。食事をとる時間がなかったので、ローソンでサンドイッチを購入した。コンビニのサンドイッチ食うの久しぶりだな…。
外出先の建物のネット回線が、Broad WiMAXなる、WiMAX版ソフトバンクAirみたいなやつになっていた。Webサイトを徘徊するくらいなら十分な帯域（20Mbps位）はあるものの、光回線と比べて遅延が大きい（60ms位）ので、Splatoonのような低遅延が要求されるゲームなどは厳しいのではないかと感じた。コンセントを繋ぐだけで使える！というのは、大変手軽で良いと思うのだけど、その利点が裏目に出る場合もあるので難しい。自分の考え的には、初期コストが多少かかってでも光回線を引き込む方が全体的に楽なんじゃないかな〜と思った。結構子供が集まる場所ということで、問題が起こったらネット回線については検討するらしい。
ファミマでおやつを購入する。今ファミマではいろいろなものを（大体）40％増量するキャンペーンを行っていて、数量限定でファミチキがデカくなっている。去年かにも同様のキャンペーンがあって、その時はスパイシーチキンが大きくなっていたような。あんまちゃんと覚えていない。
でかいファミチキ、でかい。普通のと比べると食べ応えがあって良いわね。追加でお金を出したらこのサイズになる的なのを年中やって欲しい気持ちがあるが、それはそれで厳しいのだろうな。たまにキャンペーンで売られるからこそ的な。
スプラをやる。カタログレベルが43になった。
ABC270-Dの”Stones”を解く。とりあえず、「取れるだけ取る」という貪欲法を提出してみたけど、WAになってしまった。反例も思いつかず解説をチラ見してみると、「この問題を貪欲法で解くことはできません」とはっきり書いてあってひっくり返った。ちゃんと反例も載っている。下の方に目をやるとDPという文字が見えたが、そっちの方向でもうちょっと粘ってみようということで一旦解説を閉じた。
時間がヤバいぜ！ねむる
2023/08/10
18時ごろに起きる。
台風が来ている！台風7号が関西や東海あたりに来るという予報が出たのを受けて、東海道新幹線が13〜16日の間に計画運休を行う可能性があるという発表が出た。自分は12日に東海道新幹線で東京に行く予定があるので、うお〜ギリ外れたという気持ちに。ちょっとして、多くの人が利用するお盆シーズンに直撃するのもあり、自分が利用する12日に人が集中するのでは？という懸念が出てきた。やーね
妖怪PCいじいじ。昨日に続いて、ABC270-Dの”Stones”を解く。しばらく考えたものの良い方法が浮かばなかったので解説を見た。DPの遷移の式がいかつく見えたけど、ちゃんと読んでみたらそんなに難しくなかった気がする。DP難しい…
ABC200-Dの”Happy Birthday! 2”を解く。TLにこの問題の言及が流れてきたので、せっかくだし解いてみることにした。合計の余りがXになる選択が何通りあるかをDPで求めて、2通り以上ある余りからDP復元を行う。選択を復元するコードを再帰関数で書いたのだけど、これが結構ごちゃごちゃした実装になってしまい細かいバグを何個も埋め込んでしまった。難しい
https://atcoder.jp/contests/abc200/tasks/abc200_d https://atcoder.jp/contests/abc200/submissions/44444539
2023/08/11
18時ごろに起きる。
妖怪PCいじいじ。
ABC268-Dの"Unioque Username"を解く。標準ライブラリに順列を作ってくれるものがあるので、これを使って全探索を行う（1 <= N <= 8なので、N!の計算量でも大丈夫）。
順列を作ったら、間に挟むアンダーバーを再帰関数で全探索。何回かWAを出したりしながら、後はTLEを無くすだけという所までこぎつけた。しかし、思いつく高速化（文字列の結合を再帰関数の一番内側のみで行う）を試してみてもTLEが取れない。再帰関数は遅いと聞くが、とりあえずPyPyで投げてみたらあっさりACした。1 <= N <= 8なのでそんなに影響しなかったのかもしれない。
https://atcoder.jp/contests/abc268/tasks/abc268_d https://atcoder.jp/contests/abc268/submissions/44466248
明日のMMA Contestに行くために、具体的な経路の検討を行う。とりあえず東京駅から中央快速線、京王線に乗って調布駅に行き、そこから歩くという事で固まった。早い時間に起きないと間に合わないので、頑張りたい気持ち。
2023/08/12
眠れず、6時頃に活動を再開する。
MMA Contestが行われる電気通信大学へと向かうべく、移動を開始する。久しぶりの長距離移動。ほえ〜
参加記を書くと思うので割愛
初めてのオンサイトだったけど、とても楽しいものになった。競プロerを初めて肉眼で観測した。
2023/08/13
8時ごろに起きる。
なぜか健康的な時間に起きた。昨日の外出でたいへん疲れており、今日は何もする気が起きない。足首が痛い
スプラトゥーンのフェスに参加する。今回は愛陣営で参加した。トリカラバトルに参加してみるも、同じ陣営同士のマッチングばかりで面白くない。フェスの貢献度も上がらないので、時間を食うだけである。試合は楽しいが。そんなわけで、もっぱらフェスマッチ（普通のナワバリバトル）に参加していた。ノーチラスがいい感じに使えたという気持ち。えいえんの称号を獲得したところで眠くなったのでやめた。
