AtCoder反省会~500-700点編~
黄Difに入ってから、方針の見当もつかない問題が増えてきた。
ちゃんと反省。
・AGC012-B
初見の方針
・逆に見ると塗られたとこが固定されてよさそう？
→各クエリで塗られるかどうかの判断をするなら変わりないのでは...
・うまく分割して各クエリの計算量を減らす？
→分割ができない
解説をみて
逆順にみたときの「順序」を保持しておくのか。色やクエリ処理ばかりに気を取られていた。
考えてみればこの問題で順序は重要視されるべきパラメータなので、それを量として整理していくのは比較的自然な発想なのかもしれない。
・ABC133-F
初見の方針
LCAを使うところまでは見えた。その後、「根から頂点pまでの色iの数および長さの和」を高速に求める問題に帰着されることが分かったが、そこで考察ストップ。
解説を見て
オイラーツアーなる方法をとると良い。DFSでチェックした順に配列を作る。少し調べると、LCAとRMQを結びつけるのに重要な概念のようだ。
・ABC107-D
初見の方針
こういう問題には典型(？)的に、「各要素が何回中央値となりうるか」を数えればいいと思っていた。これをやろうとすると各クエリで高速に求める系の問題に帰着されそうなのだが、累積和やセグ木を考えてもどうもうまくいかなかった。
解説を見て
まず「中央値」の解釈から考え直す必要があった。確かに中央値を固定してしまえば二分探索が可能である。しかも固定された状態なら「x以上」かどうかでまとめることで、特定の値を扱うより状態を扱いやすくなる。割と自然な発想だろう。
この考え方がさらに強力なのは「Median of Medians」のof Mediansの方でも同じように考えることで、各要素の情報量を２つまで落とすことが可能になる点である。ここまで問題を簡略化できれば、あとは典型問題に帰着される。
・ABC137-F
初見の方針
連立方程式なのでO(N^3)ならできる。a=0,1をどうにか利用する問題だとは思ったがうまくいかず。。。
解説を見て
オイラーの小定理から、x^(p-1)がほぼxによらず1という定数になる性質を使う。いや確かにそうだけど、これどうやったら思いつくんだ。。
AtCoder水色になりました
10/6のAGCで水色になりました！
というわけで、水色になるまでのアレコレを書いていこうと思います。
普段はこういう記事は書かないんですが、自分の中でひと段落ついた感じがあるので振り返りのつもりで書きます。ネット上に似た記事はごまんとあるので特に面白くないかもしれないです。
自己紹介
現在東大の学部4年生で、普段は物理学を勉強しています。
小中高大すべて公立で育ちました。高校まではプログラミングの存在自体知らなかったです。パソコンどころかスマホもなかったし。
それでも高校までで数学は結構真面目にやってて、受験時代は「大学への数学」を好んでやっていました。一回だけ学コンで満点取って景品もらえました。
とは言っても別に数学ガチプロってわけではありませんでした。むしろ受験の時は「いかに時間のかかりそうな難しい問題を解かないか」を考えていた気がします。
入試本番の数学は60~70点くらいだった(よく覚えてない)ので、東大の中では数学力は平均くらいかなって思ってます。
AtCoderに出会うまで
大学に入ってから授業でプログラミングをやる機会は何回かありました。でもいまいち面白さがわかりませんでした。「アルゴリズム入門」という講義があって、その時に動的計画法というワードが出てきたことは覚えてるんですが、結局これで何をするんだって感じになって興味が湧かなかったんですよね。
ぼーっとした3年間を過ごして気がついたら4年生。周りの人間は就活で忙しそうにしていました。
流石にこのままではいけないなと思い、何かを始めようという気になりました。
そこでなぜプログラミングを選んだのかはよく覚えていません。でも気付いた時にはProgateでPython入門をやっていました。
Pythonにしたのは、「今一番アツい言語！」と謳うサイトが多かったからです。ミーハーなので。
実際Pythonにしたのは正解だったと思います。わかりやすい。授業でC言語をいじってた時はポインタの仕組みとかがよくわからなくて挫折してしまったので。
基本文法を身につけたあとは、適当にWebアプリ作ってみたりスクレイピングやってみたり色々手を出しました。
技術が身についてきた感じはあったのですが、「じゃあこれで何をするんだ」状態になっていました。つまりモチベーションを保つものが欲しかったわけです。
そんな時にAtCoderに出会います。わからない文法を検索かけて記事を漁っている時に「AtCoderみたいな競技プログラミングではよくやる手段で〜〜」みたいな記述を目にしたのがきっかけでした。
競技プログラミング、これは面白そうだぞと思いその日のうちにAtCoderに登録しました。今年の6月のことでした。
緑色になるまで
最初は入出力で手間取ったりしていましたが、しばらくしたら時間をかければABCのDまでは解けるようになっていました。慣れの問題でしょうね。
出るたびにレートが+100とか上がっていったので、「これ自分天才なのではw」と得意げになっちゃってたりもしました。痛い。
そしてコンテストに出ているうちに自分に足りない知識も見えてくるようになりました。主には、
・キュー、スタックなどのデータ構造の知識
・DPをはじめとする、高速化のテクニック
・グラフ理論の知識
でした。いずれもほぼ1から身につけないといけなかったので苦労しました。
それでもこれまで培ってきた数学の素養のおかげなのか、緑色には割とすんなりなれました。
緑色になってから
ようやく本題。緑になる前後くらいから、少し焦りはじめていました。Dまでは(つっかえることもあるけど)スラスラ解けるようになっているのに、ABCのEがなかなか解けない。
レートは上がっているのですが、自分の成長が止まってしまったように感じられました。実際のところは元々の能力にレートが追いついてきたって感じなのでしょうが。
この頃はABC-CやAGC-Aを埋めていってました。自分にとっては難しすぎず簡単すぎずくらいの難易度でした。特にABC-Cの昔の方は典型問題が多く、足りない知識が埋まっていく感覚がありました。
この精進をする中で前節の「足りない知識」の基礎部分は身についたと思っています。
具体的には、
・DFS, BFS
・優先度付きキュー
・collections.Counterやoperator.itemgetterなど便利なモジュール
・UnionFind
・しゃくとり法
・二部探索
・ナップサック、LISなどの典型DP
・いもす法
・座標圧縮
・最短経路問題、最小全域木問題のやつ
・ビット演算
・Python高速化テク
などなど。
停滞期
それ以降もゆるゆるとレートは上がってきてたのですが、1100を超えたあたりで伸びがかなり小さくなり、その後一ヶ月ほどの停滞期に入ってしまいました。
精進のおかげか、ABCのDまで解くスピードは上がりました。逆に、Eを通せないのが不自然な感じになってきました。80分かけて通せないのは雑魚すぎる...
ずっと400まで通すだけの期間が長く、どうやら「500点はまだ自分は無理」という意識が根付いてしまったようです。コンテスト中も解けないと諦めムードが漂う、よくない姿勢になっていました。
一応、Dまでの早解きでも水パフォは出ます。でもこれを繰り返すだけだとたとえ水色になってもそこ止まりだな、と悟りました。
水色になるまで
精進方法を変えました。それまで敬遠していた500点問題に腰をすえて挑むようになりました。もちろん難しいので、全然見当もつかなかったら解説をみてしまいますが。
精進に当たって、AtCoder Problems様のDifficulty機能がかなり有用でした。Difficulty1100~1300くらいでも500点問題が結構あります。これらを解くことで本番でも500以上に怖じ気つかないようになってきたと思います。
簡単な問題でも方針がたったらすぐに実装はせず、落ち着いて証明を考えるよう心がけるようになりました。これによって間違った方針で実装してしまうことは減ったような気がします。
そして実装したあと、うまく行かなかったときもすぐには諦めない。時間は気にせず、頑張って原因を探ります。この段階で解説をみてしまうのが一番もったいない気がしています。1時間くらいは向き合います。
粘ってもダメそうなら解説をみます。まず方針と実装どっちがダメだったのか見直す。方針があっていそうだったら、もう一度コードを見直す。
方針が間違っていると萎えますが、それでも解説を理解するように心がけます。アルゴリズム自体知らなかったらググる。
まあとにかく粘るようにしたわけです。これは結構時間のかかる方法ですが、これで本番も粘ることができるようになった気がします。いいやり方なのかはわかりません。
その他工夫してみたこと
・Twitterを始めた
→強い人たくさんいて結構刺激になります。
・こどふぉをやる
→問題たくさんあります。読解がツラいけど。
・解説ACしたものを記録しておく。
→あとでもう一回やるため。
・C++の勉強
→読めるようになるだけでも学習効率がだいぶ違う。
・Streakをつなぐ
→問題解くのを習慣化できました。
・社会性を捨てる
→飲み会とかは断る
水色になってみて
水色になった昨日は興奮してなかなか寝付けなかったくらいでした。嬉しい。
でも目が覚めて冷静になると、AtCoder始めたときに「無理せずなれる適正ライン」くらいに思っていたのが水色だったなーと思い出しました。まだチュートリアル終了しただけじゃんみたいな気分です。
実際Twitterには水色コーダーくらいならゴロゴロ転がっているし特にすごくもないかなー...と謙虚になっています。むしろ緑落ちしないようにしないと(フラグ)
課題とこれから
次は青色...と言いたいところですが自分の人生もあるので、これからは無理なくゆるゆるやっていきたいと思っています。でもパソコン開くと無意識のうちに問題解いてるんだよなあ...
現時点で青色に向けてやらなければならないと思っていることは、
・蟻本ちゃんと読む(結局3章まで流し読みしただけ)
・500を安定させる
・こどふぉの問題もたくさん解いていく。
・C++に乗り換え。でもライブラリとかめんどそう...
大雑把にこんな感じ。ゆるゆる頑張ります。
読んでくださった方(いるのか？)、駄文に長々とお付き合いいただきありがとうございました。
AtCoder反省会~4-500点編~
前の記事がかなり長くなってしまったので新しく作る。
結構難しくなってきたから解説AC多くなってきた...
・ABC082-D
初見の方針
よくよく挙動を辿ればx方向とy方向で動きを分けることができるのがわかる。ただその後がO(2^N)の全列挙しか思いつかない...
解説を見て
自然にdpらしい。こういうのが見えないのだめだね...
・ABC074-D
初見の方針
一見すると最小全域木問題に見える。実際にはできるのは木ではないが、似たような考え方を使えるんじゃないかと思った。
クラスカル法のように辺の長さの小さい方から追加するかどうか決める。ここで、「今までみた中での最短距離」を逐次更新していく。...だがWA
どうやら最短距離を求めるところが不完全だったようだ。本来なら
D[n][m] = min(D[n][m], D[n][a]+D[m][b])
というのを各n,mでやらないといけない。だが当然これはO(N^4)なので間に合わない。
解説をみて
最初にワーシャルフロイド法で全頂点対の最短経路を求めておいて、これが元のと一致するならokである。あとは考えていたことは同じである。
・ARC086-D
初見の方針
右側に正の区間、左側に負の区間と分けて考える。正区間は右方向に、負区間は左方向に累積和を取っていけば実現できる。
ただ0を含む場合や[1, -9, 3]のようになってるケースが怪しい。これらには対応してみたが他にもダメなケースがあるっぽかった。
解説を見て
まず「全て<=0 or 全て>=0」という単純なパターンなら上の方法でN-1回で実現できることに気づく。
そして数列のmaxとminに着目すればそのような特殊な数列をN回で作ることができる。
困難は分割、基本だね。もうちょい考えれば思いついたかもしれない。
・ABC049-D
初見の方針
UnionFindでそれぞれ結合すれば良いというのはすぐ分かる。が、その後共通部分をとるのがどうしてもO(N^2)しか思いつかない。
解説を見て
辞書を使って整理すればよかった。こういう辞書で整理する問題、前にもあったな。。
割と典型なのかもしれない。
Python定数倍高速化
AGC033-Aの高速化に非常に苦労したため、Python定数倍高速化の技術をまとめとく。
この辺の記事が参考になる。
・PyPyを使う
大事。
・sys.stdin.readlineを使う
入力が大きくなると大事。
・main関数にする
if __name__=='__main__':
main()
にする。
・tupleを１次元にする
(a, b)をa*(1E8)+bとする。取り出すのは商とあまりでよい。
AtCoder反省会
AtCoderでうまく実装できず、解説を見たものを列挙していく。反省を成長に繋げたい。
・ABC123-D
初見の方針
全列挙してソートすると計算量が多くなってしまう。なのでいかに不要なデータを削るかの話になってくる。
一つのリストAを見ていって、その値がB, Cでどこに入ってくるかを二部探索で探す。そうやって探したインデックスia,ib,icの積がKを超えてしまったら、それ以降は必要ないのでループを切る。
あとは念の為それぞれia,ib,icより一個分多いところまでのリストを作り、全探索してソートで終わり。
でもなぜかWA...
解説を見て
データを削るというのは良い。が、わざわざリストを作らなくても全探索中のループでインデックスの積がKを超えるならbreakしてしまえば良い。
「また、一般の 𝐾 に対して、𝑎 × 𝑏 × 𝑐 ≤ 𝐾 であるケーキの選び方は高々 𝑂(𝐾 log2 𝐾) 通りです。」
らしい。ab<=Kで考えると、aは1からKまでのK通り試して、それに対してb<=K/aが決まるとするとK/aをa=0~Kで積分すればよく、O(KlogK)になるってわけか。
他にも色々方針があるが一番近いのはこれ。
・ABC118-D
初見の方針
桁をなるべく増やしたい。なのでとりあえず1とか7とか必要数の少ない数をダーッと並べる。ここから合計をちょうどNに合わせる。
この合わせ方をかなり苦労して実装。ダーッと取ってきたやつを一つずつ減らして、残りを他ので分け合うようにする。「他の」は複数ありえるので再帰関数で組む。
なんとか実装はできたもののTLEが残ったので退散。
解説を見て
DPだった。dp[i]=「ちょうどi本使うときの最大桁数」として先に桁を求めておいて、あとで数字を上の桁から埋めていくらしい。
「ちょうど」といえばDPか。DP使う可能性を頭から外さないようにしないと。
・ABC022-C
初見の方針
最短経路問題やん！よっしゃこないだ蟻本でやったダイクストラ法が火を吹くでーww
1に繋がってる各頂点に対して、1とその頂点を除いたグラフに対してダイクストラ法で最短経路を求める。
TLEだった。
解説を見て
この方法はモロでダメなやつらしい(凹んだ)。隣接頂点ペアの選び方がO(N^2)、そこからダイクストラで探索するとさらにO(N^2)かかってしまう。ダイクストラは始点が決まってると有利だけど全探索っぽいのには向いていない...
そこでワーシャルフロイドくんの登場である。全頂点対の最短距離をO(N^3)で求めてくれる。蟻本読んでた時はダイクストラでよくね？と思っていたが全探索した方がいいならこっちを使うようにしよう。
書き方が簡単ではあるがループの取り方を間違えてたくさんWAを出してしまった。経由頂点を一番外に持ってくるんだね〜
・ABC017-C
初見の方針
その前の問題でいもす法を使ったので今回も使うかなと思って実装。しかしその後どう答えにむすびつけたら良いかわからず、部分点解法に切り替えた。
解説を見て
いもす法で良い。各座標のうちもっとも合計の小さいものを選べば、これを満たすものを選択しないことでもっとも損失の少ない得点を得ることができる。
・ABC018-C
初見の方針
よくわからなかった。愚直に全探索したらO(RCK^2)で明らかに間に合わないことがわかっていたのでどうしたもんかなあと。
解説を見て
最初にたて一列で見て距離を計算しておく。そうすれば全マス見るときにたて方向は呼び出すだけでいいのでO(RCK)となってまあ間に合うくらい。なんかこうやって「たて(横)一方向で事前に処理しておく」というのは前やった気がするけどなんだったかな。
・ABC104-D
初見の方針
この感じはDPだとはわかった。i文字目を読んだとき「それまでにあったAの数」と「それまでにあったA→Bの数」を記録していくようにした。しかし '?'の処理の仕方がよくわからなかった。
解説を見て
dpではあるが、「残りのあり得る可能性の数」を記録する。それを完成させた方から遷移させていくとうまくいく。目から鱗。
・ABC096-D
初見の方針
とりあえず素数をだすコードは書いたが、それ以降が全然わからない。
解説を見て
「足して合成数」を「足して5の倍数」に限定してしまうとグッっと簡単になってしまう。こういう「適当な例を引っ張ってくる」って数オリとかに近い発想があるなあ...
・ABC044-C
初見の方針
いわゆる部分点解法。O(2^N)で全列挙。どうしたらいいんか....
解説を見て
DPだった(またか)。解法はほぼナップサック問題。とるかとらないかを要素ごとに選べる。合計は小さいので、合計で整理していけば良い。この発想はまだ慣れないなあ。
・ABC076-D
初見の方針
列車の走行区間ごとに見ていって、前の区間と後ろの区間によって形を決める。早く実装できたーとか思ってたけど、これは誤り。上限がめっちゃ大きい区間が連続すると前後の区間を見るだけでは足りない。
解説を見て
時間で区切って離散的に見ていってしまう。各時間ごとに全部の区間の寄与を考えて積分していけばできる。Nとtが小さいことに気づけば自然な発想である...
・ABC061-D
初見の方針
この前のABCでやったのに似ている。スコアにマイナスをかけて最短経路問題としてしまう。負符号なのでベルマンフォード法を使う。
ただ、負閉路ループがあるときは注意が必要で、更新され続けてしまう。よって必要以上に更新されたら打ち切るというのが元のアルゴリズムである。
ただ、終状態までにない経路でループがあった場合もinfとなってしまう。なんとかこの場合を取り除く必要がある。
解説を見て
一旦更新をやめてから、もう一回更新ループをやって見てどの点が更新されるかリストで見ておく。これで最後の点がループ状態にあるかどうかわかる。
・ABC063-D
初見の方針
愚直シミュレーションでは無理。そこでHの最小値を基準に最初に引いちゃえ！と思ってとりあえず引いたがこの方針ではこれをO(N)繰り返さないといけない。実質愚直と同じ。
解説を見て
「条件を満たす最小回数」を二部探索していく。ある回数Tを固定したとき、これが条件を満たすかどうかを判定することができる。うーん、こういうのはよくある発想なのか...?
・ARC093-D
初見の方針
頑張って互い違いに組もうとしたらバグが永遠に取れなかった。
解説をみて
制約を見ればある程度の余裕があることはわかってしまう。最初に「ベース色」を2分割してそこに違いにプロットしていけば良い。
・ARC073-D
初見の方針
ナップザックって言ってるし完全にDPだと思うじゃん？？「重さ」「いくつまでとったか」「実際にとった個数」の３次元配列を組んで遷移させようとしたけど意味わからなくなって挫折...
解説をみて
全然DPじゃないやんけ。重さで場合分けすれば全探索できるんかーい！
・全国統一プログラミング王決定戦本戦-C
初見の方針
方針立たず放置。
解説をみて
縦横独立に考える。そしてそれぞれの中央値を持ってくるだけ。よく考えればそりゃそうだ...
・ABC020-C
初見の方針
「黒マスを通る回数」を固定すれば白マスを通る回数をなるべく少なくするような経路を取れば良い。が、実際にこの経路を探すのが思ったよりしんどく(最悪O(N!))、諦めた。
解説を見て
「x秒で黒マス移動」のxを固定してしまう。単調性があるので二部探索が使えて、O(HWlogT)で間に合う。
・DISCO2016予選-C
初見の方針
Kを素因数分解して因数ごとにループ組んで〜ってやろうとした。でもループが意外に重くなりそうだったし「残りペア」の探し方もよくわからなくて断念。
解説をみて
素因数ではなく、約数全列挙で良い。約数の個数で見れば大した量ではないので。
・ARC090-D
初見の方針
重みつきUnionFindでなんとかならないかなーと思ったけどこっちの実装が辛そうで断念。実際に割り当てするのが現実的だとは思ったが、一回調べたものをもう一回みる必要がある&非連結部分の判定がよくわからなかった。
解説をみて
重みつき有向グラフにする。片方からの距離が D、もう片方からの距離が-Dとなるように設定しておく。連結性は先にUnionFindで根を取ってくることで行う。
仮想環境のactivate
仮想環境を立ち上げるのをすぐ忘れてしまう。
何の環境があるかは
$ conda info -e
コマンドで確認できる。
activateするには、
source activate (venv)
と打てば良い。
DFS, BFSの実装
AtCoderのTypical Contestで深さ優先探索の実装を練習した。
A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder
大まかな流れとして、
・グラフを表すリストを用意(inを使わないために要素をインデックスにしてTrue Falseを収納するようにする)。
・checkしたかどうかのリストを用意(同上)。
・stackを用意
・stackが存在する間、(while)
stackの最後を入手(a)
aをcheckしたことにする
aから繋がってるやつら(bs)を入手
bsのうちcheckしてなくて条件を満たすものをappnd→break
もし何もappendされなかったらaを取り除く
という流れ。
BFSにするなら...?
