2年ぶりの復活
前話
突然ですが、自分の競技プログラミングにおける復習方法をお話します。
自分はここ2年ぐらい、非公開の日記を書く習慣がありました。
そこで日々解いた問題について、次同じ問題に遭遇した時にちゃんと解法の再現が可能か？という着眼点で整理し、実装ミスの反省や、より良い実装方針があったかどうかなどと合わせてメモを残すようにしていました。
この日記による運用も長く続いていましたが、後から見返す時に探し辛かったり、また、日付を跨いで関連知識がバラバラに存在するよりは一箇所に集約してた方が使いやすいよねという思いがあったりで、今年2月過ぎからはscrapboxに自分用の競プロwikiみたいなものを作る運用を始めました。
その期間での僕のAtCoderのレートは、1990(3/12)→2263(9/20現在) と200近く伸びたので、自分にあった復習法/学習法であるように感じています。
それはそれとして最近は日記を書くモチベが薄れており、とはいえ解いた問題の投稿は何からの形でしたいな、Twitterは微妙でどうしようかと思案していたところ、最近自分のブログを読み返していて良いなと思ったので実験的に復活させてみることにしました。
精進の中身を定期的にアウトプットすることで、怠けてしまうのを避けようという魂胆もあります。まずは3日おきとかを目安にしてやってみることにします。続くかどうかは実際にやってみた感触で決めます。
ちなみに Problem Solving というのは韓国の競技プログラマーのブログで良く見られる文化で(PSと略されることも多い)、2年前これをパクりたくなった経緯があったりします。
BOJ 21725 - 더치페이
割り勘問題。制約から常にYesであることが言えます。
— sigma (@sigma425) 2020年7月1日
このツイートがやけに印象に残っていて、今年高校の友達との卒業旅行でやったり、何ならこのアイデアを題材として、会社の研修(同じ班の人間にオタク語りするの辛かった)で、精算方法を出力するコードをJSで熱烈に実装したりしたという思い出があります。
本問題でも、これを集合のマージをする度にやっていけば良いです。
XXII Open Cup, Grand Prix of Daejeon
E. Yet Another Interval Graph Problem
最小重みでどう取り除くか？よりも、最終形のグラフでどれだけ最大重みを残せるか？みたいに考えた方が分かりやすく感じました。
この言い換えを経由した後に、左から右端を固定した $O(N ^ 2)$ のDPを考えると割と素直に解法出てくると思います。添字周りで1ペナ。
区間の交差を扱う問題では、どこに区切り入れるか？みたいに考えるってことなのかな(言語化下手な気がする)。DPで順に値を固定して計算していくためには、互いに素みたいな状態を作りたい→区切りを入れる、という方が解法の筋としては通ってるかも。
A. Points
$x$ の和が最大値となる場合について考えると、$u _ {y} + v _ {y} \le u _ {x} + v _ {x}$ つまり、$- v _ {x} + v _ {y} \le u _ {x} - u _ {y}$ が成り立つ。クエリ先読みして、$- v _ {x} + v _ {y}$ と $u _ {x} - u _ {y}$ の値を座圧して、その区間における座標の最小値と答えをセグ木に乗せると解くことが出来ます。
典型詰め合わせのような問題で面白いですね。
ACPC 2020 Day 1(農工大セット)
AOJ 3194 - P進XOR
4の倍数毎に見るとXORが0になる奴、一般化できることに考えが及んでなかったです。当時もハッとしていたはずですが、3年経ってまたハッとしてしまいました。
AOJ 3195 - Road and Telepoter
コストが2つの1次関数の和で表される時、極端な値のみ調べれば良い、いつもの。
AOJ 3199 - 移動の最小化
区間の端点は点がある位置だけ試せば良く、尺取を頑張る…(2ペナ)
多分もっと簡単な実装方法はあるんだろうけど(想定は二分探索をしていた)、パッと見で尺取が見えてしまうし、これぐらいの実装は正確かつスピードも上げて実装できるようになりたいですね。
Codeforces Round 898 (Div. 4)
全体的に英文が短くて読みやすく、面倒要素を増やして生成された簡単枠というよりも、分かってれば軽実装で済むような問題で、解いていて気持ち良かったです。二分探索の右端ミスという典型ミスを踏んでしまったのは反省です。
G. ABBC or BACB
こういう問題で実装方針上手く引けるか？みたいなのは完全に慣れだと思っていて、その観点で良い問題だなと感じました。落ち着いてDPを書く判斷が出来たのは満足。
H. Mad City
似たような問題設定についてUCで見た気がするけどなんだったかな…(UCも復習しないとですね。。。)この問題では相手よりも早くサイクルに辿り着ければOKで、全部BFSだけで判定することが出来ます。
yukicoder contest 405 技術室奥プログラミングコンテスト#7 Day1
Bは約数を引くだけという結論が一見非自明で面白いと感じました。Cは未証明…
No.2485 Add to Variables (Another)
1つ前の問題と同じコードで通りました。
無の操作回数を固定すると、他の操作の回数が一意に定まります。全てに1足す操作の処理は簡単なので、一旦放置してその他の操作について考えます。
階差を取ると、数列に+1したり、-1したりする操作に言い換えることが出来ます。多項係数の式を考えると操作回数を階乗し、逆数をとった総和のような物が分かればよいので、これを値として持ったDP(dp[i] := i回操作した時に対応)を考えると、素朴に $O(NM ^ 2)$ になって、畳み込みをすることで $O(N M \log{M})$ になって解くことが出来ます。
畳み込みで解けると見てしまった後でも、かなり時間がかかってしまい反省ですが、寧ろ良い練習が出来たと前向きに捉えることにします。
AtCoder Beginner Contest 321
F問題多少のロスがあったものの、UCでチームメイトに教えて貰った戻すDPでパパっと通せたのは、upsolveの甲斐があって良かったです。それ以外はなんとも微妙な出来でした。C問題は上限書かないってことは上限少ないんだろうと未証明でDFSを書いていたのですが、冷静になると $2 ^ {10}$ で抑えられるのは盲点でした。
E - Complete Binary Tree
本番ではよくこの実装で通しきったな…みたいなコードになってしまいましたが、時間かければ通せる筋力というのは強みかもしれません。
その提出では桁DPをしてしまったのですが、頂点 $x$ から $k$ 回下に降りて到達する頂点は区間を形成するので、簡単な算数で求めることができます。
solve関数のようなインターフェースを整えると重複(正確には深さが違うので重複ではないですが)を取り除く時も混乱しなくなるので、こういった見通しを立てるのは大事だなということを強く実感しました。
G - Electric Circuit
基本方針と、集合の代表元(例えば最小値)を固定する発想はあったのですが、上手くまとめる事ができませんでした。
解説で $f$ と $g$ の積で表されているところで、正しく連結性を考慮した値を1つ固定したら、もう片方は連結性を意識しなくて良いことに気付けませんでした。
