週記(23/04/02)：色変記事

今週のまとめ

会社の倉庫見学へ
色変記事書いた
ABC296バチャ。出てたらかなり冷えてた

です。

(本文中にABC296 D, E, Fの解法を含む話題が出てくるのでご注意ください。)

4/3(Mon)

前々週、前週の週記で書いたとおりAHC019の結果は59位でした。ちょっと不完全燃焼感が残るので振り返って次につなげたいですね。

AHC019疲れ？で仕事をこなすので精一杯で夜にシルエット作って遊んでました。

こんなシルエットも

ちゃんと作ってくれます(笑)

4/4(Tue)

日記の前半編を書いてました。

最初の方針は良かったのですが振り返ると2日目(3/19)から本質的な改善を生み出せないまま終わってしまいました。

4/5-6(Wed-Thr)

茨城にある倉庫と翌日に埼玉にある取引先訪問に行ってました。

見てきた倉庫についてはYouTube動画を見てもらうのが分かりやすいです。最適化案件の宝庫で取り組んでみたいですね。

4/7(Fri)

AHCに没頭していたら…体がたるみ切ったので久しぶりにランニング。

どれくらいたるんだかというと…ここ3週間の

体重の増加率 > AHCレートの増加率

なんですねぇ。恐ろしや。

夕方「40歳を前にAtCoderで青コーダになった話」をアップ。Twitterでいろんな方から反応をいただいて嬉しい限り。

4/8(Sat)

ABC296のバーチャル参加

Dでドはまりして3完、パフォーマンス947相当と久しぶりの冷えっぷり。時間の使い方含めてアルゴはボケています。日曜のABC297で青⇒水になりそうな予感…。

Dは最初、[math]m=\lfloor \sqrt{M} \rfloor [/math] として [math]X[/math] は [math][M, (m+1)^2][/math] まで見れば十分…で約数列挙してチェックしたらTLE。当然すぎる。

考え直して[math]f(a,b)=ab-M[/math]を0以上の範囲で最小値を求めればよくて[math]a[/math]を固定すると[math]b=\min(N, \lceil M/a \rceil)[/math]と決まります。ここまでは良かったのですが[math]a[/math]の範囲が広いのでダメだ…で固まってしまいました。

諦めてEへ行ったのですが[math]a\leq b[/math]とすると[math]a[/math]は[math][1, \sqrt{M}+1][/math]まで見れば十分でした。

「E – Transition Game」はiからA_iに有向辺を張ったグラフを考えると閉路上のノードはどんな[math]K[/math]に対してもうまく開始ノードを選べば[math]K[/math]回後にそのノードに行けます。逆に閉路にないノードは十分大きな[math]K[/math]を取られるとそのノードにいることはありません。

というわけで閉路を構成するノードをカウントすればOKでSCCを使えば楽…と思ったものの手持ちのライブラリになくググって調べている間にTime up。ちゃんとライブラリ化しないと。

終わった後に「F – Simultaneous Swap」も解いてすんなりAC。サンプルが優しい。

多重集合として一致しているか？をまず見て、一致していれば転倒数を考えて、転倒数の偶奇が一致していれば同時に揃えることができます。ただ、同じ要素が複数あれば偶奇を調整できるのでこの場合もYesになりますね。

前週の週記: 「AHC019参加記(後半編)」
翌週の週記: 「幻の水青反復」