1日1ACチャレンジ 2022-06-26の週 - イノたまごラボ・あのぶるの「こんなの作ったよ！」

最近AtCoderで本格的に*1競プロデビューを果たしました。

全体的な話はまた別途まとめるとして、毎日過去問を1問くらいは触ろうじゃないかということで1日1AC*2チャレンジというのを始めてみました。初週のくせに1日飛んでるわ2日がかりで1問解いてるわなのは思い立ったのが昨日とかだったからです。

XORの性質 A XOR B XOR A = B を使う問題。たぶん昔習ったんだろうけどこの性質は完全に忘れてた。が、やたらトリッキーな演算なので「XORの性質使ってなんぼの問題だろこれ」となり、性質が確認できればあっさりできた。

ちなみに「Nは必ず偶数」っていうポイントをあんまり深く考えないで解いたんだけど、これNが奇数だと全部掛け合わせたときに偶数になって、少なくとも同じアプローチは使えなくなっちゃうんですね。

他の作業に夢中になってたらできませんでした！😇

C問題だけど、計算量云々っていうより手順そのものを数学的に導けるかどうかが焦点。場合分けして素直に検証していけばあんまり計算量を意識する必要はなさそう。最大3手っぽいところまでは自分で気付けたんだけどな…

「マンハッタン距離」という言葉を知る。碁盤の目に沿って進む場合、最短ルートを採った時の道のりのこと。概念としてはよく使うんだけどな。マンハッタン距離N以内の範囲は斜辺が2N+1の45度傾けた正方形になる。

↓の問題を2日がかりで解いた。多分合計で4hくらいかけてる

ACが解説見た後っていう意味ではそうなんだけど、ぶっちゃけ解法は解説とちょっと違う気がするのでなんとも。漸化式作ろうとしたのはいいんだけど混乱しまくって、なんというか物理時間の方がTLE。

例によって配列が鬼門。結構カリカリにチューニングしないと2secの壁は厚い。直前の値が欲しいだけであれば安易に配列を作ってはいけない。

まぁでもこれを時間かけてでも概ね自力で解けたのはよかった。

瞬殺いえあ！だいぶ昔の問題だからか、数字上の難易度よりも簡単に見えた。これと同じ理屈を使う難しいバージョンがABC256のC問題だと思うんだけど、こっちの方が難易度推定低いんだよねぇ。

3重ループとか計算量ヤバいと見せかけて2重ループで抑えられるパターン。

*1:あのぶる定義:リアルタイムでコンテストに参加すること

*2:All Correct、準備されたテストケースをすべてパスして正解と見なされたこと https://atcoder.jp/contests/abc171/glossary