AtCoder Beginner Contest 158 E - Divisible Substring
問題ページ
愚直に考えると、
0~N-1の範囲で、部分文字列の左端と右端を選んで、その部分文字列が P で割り切れるか、全ての(左端、右端)の組で判定する。
計算量はO(N^2)で、N <= 2*10^5 より間に合わない。
計算量をO(N)程度に落としたい。
S=123456789として、 部分列3456と、部分列789は、何らかの関係があると直感的に考えられるので、それを利用して計算量を落とすことを考える。
ここで、
「 部分列S[l:r]がPで割り切れる 」
とは、
「 (S[l:] - S[r:]) / (10**(r-l)) がPで割り切れる 」
ということである。
また、
(a - b) % P = 0 のとき、 a % P = b % P
であるので、
・Pが10と互いに素である時は、S[l:]をPで割った余り = S[r:]をPで割った余り をSの右端から数え上げる。
・Pが10と互いに素でない時は、あるS[i]がPで割り切れるばあい、そのS[i]を右端に含む部分列全てがPで割り切れるので、それを数え上げる。
でOK。どちらの場合もO(N)なので間に合う。
解答
自分向け競プロ手順書
コンテスト中のミスが目立つので、解くときの手順書を用意した。
個人的に、以下のミスが目立つ
- 問題を読み違える
- 制限を見忘れて、方針を間違える
- typoや使う変数を間違える
- ミス→焦る→ミス の無限ループ
実装に入る前
- 手はキーボードかメモ以外に置かない（机の上から手を下ろさない。関係ないことをしない。集中力を切らさないためには意外と重要）
- 問題を読む
- 条件（制限）を見る
- 入出力例をみる
- ここまでで問題で何を問われているかを理解する
- 解法のロジックを考える。ここでは愚直解を考える。
- ここで重要なこととして、問題の理解があっているかを確認する。ここで問題が理解できていないと、これ以降で全て意味がなくなるため。
- 愚直解の出し方が分かれば、自作のケースの正誤判定に使えるので、愚直解は必ず考える。
- また、制限などからボトルネックを見つけ出す。（愚直解だとO(N2)なので間に合わない～とか）
- 図＋文章でメモをとる＆とったメモは残す（実装後に理解が間違ってるとか気付くタネにするため）
- 制限などから解法を考える。
- 重複するが、図＋文章でメモをとる＆とったメモは残す
- 小さいケースで、処理を一つ一つ丁寧に見ておきメモを残しておくと、デバッグの時に使える
- テストケース以外に、扱いやすい例やコーナーケースも自作し、そちらでもロジックを考える/あっているか試す。自作ケースの正誤判定は上で求めた愚直解が使える
- N=1,2,3,...のようにある変数について、いくらかの程度の範囲で確認し、規則などが見つからないかも確認
- 提出用のコードではなく、規則発見用のコードは書いてもよい
実装中に気を付けること
- 空白行を入れすぎない（視界に入る量が減るので、ミスを身をとしやすくなる）
- 不要な変数を残さない（間違えて使ってしまうのを避けるため）
- 同じような変数名を複数使わない（補完でバグらせることがあるので）
- このへんをきちんと意識しないと、デバッグの時にうまくいかなくて、全部書き直しとかやりがち
- インデックスについて、毎回-1するような実装にしない。事前に引いておく。多くはindex out of rangeになるが、ならないと見つけるのが面倒な場合がある
実装がおわったらデバッグ
- 使ってない変数などは削除する
- まずはテストケースを流す
- 問題なければ、答えが明らかな自作ケースを流す
- こちらもある程度連続した範囲を試す。
- 提出前にデバッグ用のprint等を削除する/コメントアウトする
想定する出力がでてこなければ
- 実装前のメモを見直し、やりたいこと（問われていること）の理解が問題とあっているかを確認
- 問題がないのであれば実装が間違っている。次いで、メモを見直してロジックを確認する。
- 注意点は実装前と基本同じ。
- ここで注意したいのが、焦らないこと。提出前位に問題が見つかって良かったと考える。
- 手はメモかキーボードの上。水を飲んだりリラックスして焦りを解消するのもあり。
- ロジックに問題なさそうなら実装を確認する
- インデックスが間違ってないか
- 使う変数を間違ってないか確認する。特に不要な変数を残していたり、似た名前の変数を複数使ってエディタの補完で間違える、というのをやりがち。
- サンプルとprint文で、想定の処理の流れになっているか確認する。これをやるために、解法を考えるときのメモをみる
- 提出前に消すこと
提出後WAだったら
- 焦らない。ここでも手はキーボードかメモ以外に置かない。水を飲んだりしてリラックス。
- WAの数などから、ロジックがそもそもあってないとか、部分的な想定の漏れがあるかなど候補を挙げる
- デバッグで変数の値を動かしたりして、手で解いた時の解と一致するか確認する。
- 愚直解を利用して、自作ケースの解が間違っていないか、もう一度確認する
- 連続値以外にも、飛び値も入れてみる。MODの忘れなどが見つかるかもしれない
05/07のバチャコン
今日も灰灰茶緑水水。
問題ページ
https://kenkoooo.com/atcoder/#/contest/show/32e8a4f0-132c-4d2d-84d6-d3b9daaf124a
緑までの４完。Static Sushiが難しかった。６問目も後で解いておく。
3問目
解けたけど時間がかかってしまった。RLの部分に子供が集まるので、どういう条件でどちらに何人集まるかて確認する。 文字列を先頭から見ていってRLの切り替わりの位置と、それまでに何人子供がいるか確認するような実装にしたが、Rだけ確認したあとにLを反対から見ていく、の実装にした方が楽だったかも。
4問目
K<= 5がみそ。長さが最大で５文字まででいいので、そこまでを全部書き出してソートしたものからK番目を出力すればよい
5問目
時計回りにx番目まで行って、次に反時計回りにy番目まで行って、をxとyについて全探索しようとした。もちろんO(N2)なので間に合わない。
解説を見ると、「x番目まで食べに行けるときに、いずれかまで食べに行って初期位置に戻ってきたときに得られる最大カロリー」（往復側の食べ方と呼ぶことにする）を事前に求めておく。次にyを決めれば、xの方面にはyの手前まで食べに行けるので、yの手前までから往復側の食べ方の最大値と和をとる、をすべてのyについて確認して最大を選べばよいらしい。
計算量削減ができなかったが、考えてみるとなるほど納得がいくものだった。コンテスト中には思いつきそうもないが、～～～までで最大のもの、発想できるようになりたい。
05/05のバチャコン
今日も灰灰茶緑水水。
https://kenkoooo.com/atcoder/#/contest/show/6c335dc6-7c7e-446c-90fc-92680f984c65
誤って茶の問題を飛ばしてしまった。 問題を見るに二つの紙幣の数を全探索（残りの紙幣はNから引くとわかる）で間に合うはず。 集中力切れで水の二問目が時間内に終わらなったが、とけたのでまあよしとする。
考え方のメモ
問題４
無色について、何色にするかは重要ではなく、赤をX個、緑をY個食べると以後その色は食べない、という縛りで、赤＋緑＋無色がX+Yになるまでポイントの大きいものから食べるとよい。
問題５
各クエリに対して毎回コストを調べるのは無駄なので、先頭からマス目Pまでのコストを累積和でとっておいて計算。
問題６
手を動かせば、切り取りうる部分列の数が、Σk (k=1~N)であることは分かる。
ある数字cを含まない数を全体から引いてあげるとよい。cが出てくるindexを記録しておいて、その間で作りうるcが出てこない部分列の個数を全体から引いてやる。
indexをバグらせて時間がかかったが、方針は比較的早い段階でたった。
05/04のバチャコン
競プロの練習に、できるだけ毎日バチャコンをやることにした。いつまで続くかな？
難易度は、灰灰茶緑水水で、緑までは早解き＆水もなるべく解く感じの練習
問題 https://kenkoooo.com/atcoder/#/contest/show/2bc092d1-573f-40db-a225-e9fad66e6d91
問題１
整数をひっくり返したものと比較するだけ。
問題２
自分の手札を大きくする方ほうが、「場に残っているもの中から最も大きいものを選ぶ」である。
毎回場からMAXを探して取り場から消す、をやると、探索でN、消す操作でもそこそこかかるのでよくない。
事前に大きい順に並び替えて、頭から交互に取っていき、最後に差をとるでOK。
問題３
各都市（スタート地点も都市と考える）を、位置の順にソートして、都市間の距離を求めて、それぞれについて最大公約数を求める。
gcd(a,b,c) = gcd(gcd(a,b), c) を理解していれば問題ない。math.gcdを使って1RE(python3.4ではfractions.gcd)
問題４
割と悩んだ。サンプルが豊富だったので何とかなった。
最大は全ての点を直線に並べたものなので、sumをとればいい。
最短については、最長辺をまず配置し、その端点から折り返しで反対の端点に戻ることができるか考える。ある辺は角度をつけると、x軸方向について、0~(辺の長さ)に収まる。なので、最長辺以外の辺では、x軸方向について、0~(sum(D) - max(D))までを作ることができるとかんがえた。（証明はできてない）。
なので、min = max(0, D - (sum(D) - max(D)))
問題５
これは一週間前に解いたので、解法を覚えていた。
L ~ R に完全に収まる = L~Lを走る + L~L+1を走る + ... + L~Rを走る + L+1~L+1を走る + L+1~Rを走る + ... + ... + R~Rを走る
のように、L~Rのいずれかで走り出し、Rまでで止まるもの、と考える。
これを累積和で、
accum[L][R] : L始まりで、Rまでのいずれかで止まる電車の本数
のように持っておいて、各クエリに対し、出発位置をL~Rまで動かして本数を足し合わせるとOK
問題６
円形に並べている問題は、直線（配列）に分解＆初めの左に末尾の値を、終わりの右に初めの値を置くとよい。
今回は配列の左側の末尾と初めの動物について、４通り考えて、与えられた証言通りに並びを作っていって、右側の末尾と初めの動物と最初に仮定した動物が一致するなら、その動物の並びを出力。どの場合も一致しないなら-1でOK
AtCoder Beginner Contest 165 C - Many Requirements
コンテスト中に考えたこと
- A_i <= A_i+1
- N,M <= 10 なので、雑に全通り考えると1010 <- 間違い
- 得点の高いものから貪欲でいけるかも？試してみるか <- まずは証明しましょう
どうすれば解けたか
- A_i <= A_i+1があるので、単調非減少だから、 1010 ではない ことをちゃんと考える。（すべて書き出すをやればこの勘違いは解消できたはず）
- 例以外にも自分で配列なり入力なりを作っていじってみる
- 例１あたりであり得る配列をすべて書き出せば、あるNとMについて、何通り作りえる考え出すことはできたはず
あとはDFSで配列作って、Q個の条件を確認して一番高い得点を答えにするだけなので、実装は楽な問題だった。
解答 atcoder.jp
AtCoder Beginner Contest 158 E - Divisible Substring
難しかった。
[ポイント]
・123456789みたいな数字について、12345 = (123456789 - 6789) / 10**4 の発想
- これめっちゃ頭いいと思った
- 累積和ではないけど累積和風味の発想がおもしろい
・余りの問題は、計算過程から余りをとっておくと高速化できてよい。
- 大きな値同士のmodを何度もとる、とかならちょっと問題かもしれんが、おおよその場合に有効
・コーナーケースを漏らさない（Pと10が互いに素でない場合）
