/ 最近 .rdf 追記 編集 設定 本棚

脳log[20230902]



2023年09月02日 (土) [AtCoder] 今日は THIRD プログラミングコンテスト 2023 アルゴ(AtCoder Beginner Contest 318)があった。トップページの煌めく Kaggle Grandmaster の文字がおしゃれですね。CSS Animation で2秒のうち一瞬だけ可視不可視を切り替えてるっぽい? そういうの初めて見た。あ、任意色も任意の色をまとってアピールしてる! コンテスト成績証自分のすべての提出。ABCDE の5完は前回と同じ。同じなんだけど、前回は早解き失敗でまさかの緑パフォだったのに、今回は早解き成功で青パフォ。何この天国と地獄。あと1問解ければ解決だね(できるならね)。以下 ABCDE のふりかえりと F の精進について。■A 問題「Full Moon」。制約を見てだめな気がしたから計算で解いたけど、全探索することもできた。でもミスが怖いという点では大差ないかも。A 問題の提出にドキドキはいらないんで、もうすこし容赦してほしい。■B 問題「Overlapping sheets」。Tangency of Cuboids を覚えていますか? 私は覚えています。でもあちらは E 問題 (黄 diff) でこちらは B 問題。もうすこし容赦してください。でも今日のは灰 diff だなあ。3次元と2次元という以上の落差が謎。■C 問題「Blue Spring」。ふりかえり中に気がついたけど、アオハル=18切符ってことね。ソートして高額区間を優先して貪欲にシミュレートした。■D 問題「General Weighted Max Matching」。つい最近 ABC313-B「Who is Saikyo?」と ABC317-C「Remembering the Days」で制約が小さいからと雑に DFS を書いて TLE を出したことを覚えています。雑に書いた DFS の計算量には階乗がでてくるみたい? AC 解答も順列の全探索だったから階乗でいけないことはないと思うんだけど、Ruby では書き方によりダメということか。今日はきっちりメモ化再帰を書きました。D 問題ならそれくらいはね。■E 問題「Sandwiches」。同じ数ごとに添字を集めて昇順または降順で添字の和と添字の個数をメモしながら数えた。添字の和と個数がわかれば作れるサンドイッチの数がわかるし、添字の個数がわかれば除外すべきサンドイッチの数がわかる。■時間内に解けたのはここまで。それぞれの問題に費やした時間が A=3分、B=4分、C=7分半、D=6分半、E=10分。■F 問題「Octopus」。解答の方針は立ったけど1時間以上あっても解けなかった。このややこしい問題が時間内に解ける未来が見えない。方針はこう。X 座標の左端からスタートして右に向かって移動するタイムラインを再生する。時刻の幅が広いので局面が変化するタイミングで刻んでお宝をつかんでいる時間を数える。局面の変化っていうのは距離で並べたお宝が入れ替わること。つまりお宝の順番を固定して考えられるように時間を刻んだということ。お宝の並びが決まれば対応する腕の長さが決まり、お宝をつかんでいられるたったひとつの区間が求まる。それら N 個の区間と現在の時間の区切りの共通部分を答えに計上する。サンプルの2が親切だけど、タイムラインのスタート地点はよく考えよう。X.zip(L).map{|x,l| x-l }.min が十分。Ruby だから関係ないんだけど、制約が 61 ビット使うといっているので 10 倍 100 倍してテキトーに小さい数を初期値にすることをためらってしまった。それが WA の理由のひとつ。もうひとつが等距離にあるが右にあって近づいてくるお宝と左にあって遠ざかっていくお宝の扱い。近づいてくる方を短い触手に割り当てる方がお宝がつかめる可能性を高める。いやいやいやそんなんわかりませんて。ランダム入力を何十回試してもそれによる不一致は出てこないんだよ。まあ、無限ループなのでいずれ見つかるんだけど。■今日の日記にここまででタコの腕とタコの触手が出現しているけど、問題文ではタコの足になっている。実際のところタコのあれはなんなんだろう。「タコの足の本数は何本?タコの足の数はなぜ8本なの?腕が再生して96本! | BIJOH [ビジョー]」を読むと腕と足は間違いではないが触手には言及がない。触手について「無脊椎動物の体の前端や口の周辺にある糸状またはひも状の突起。先端に多くの感覚細胞が分布し、触覚や捕食の働きをする」と明鏡国語辞典に書いてあるのを読めば当てはまるような気がするが、違うと言われれば糸でもひもでもないからかなあとも思う。でもそんくらいしか違わないよね。ナチュラルに触手ってワードが出てくると、すわエロアニメによる刷り込みかという警戒心が働くのだけど、別に不自然な言葉選びではなかったのではないか。でもそれをここにこうして書くのはダメだと思う。