htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Beginner Contest 119

A - Still TBD

AC: Submission #4367141 - AtCoder Beginner Contest 119

4月30日は4月最終日なので、月以外見る必要なし。月の部分だけ整数に取って条件分けしましょう。と思ったら文字列のままで"2019/04/30"と辞書順比較すればよかった(意外と頻出テク)

B - Digital Gifts

AC: Submission #4368133 - AtCoder Beginner Contest 119

誤差の制約がゆるゆるなので何も考えず小数で計算してやりましょう。

C - Synthetic Kadomatsu

AC: Submission #4373507 - AtCoder Beginner Contest 119

いやなんだこれ。C問題とは思えなくて頭真っ白になった。制約より無理やりにでも全探索しろと言っているのは明らかなんだけど、与えられた竹を3つの材料に分類する方法が思い浮かばなくて、結局今作ろうとしている竹の材料をビット全探索して、使用済みを渡しつつ次の竹へと再帰するみたいな超重量級の実装になってしまった。自分は全探索というとどうしてもビット使ってやる(つまり選ぶ集合を一度に決める)発想ばかりが浮かんでしまうが、2つに分ける場合はそれが最適だけど今回は選ばないものも含めれば4つに分けなければならないなので明らかに適さない(愚直にやれば28を3つ回してビットの被りがないケースのみ採用することになり、ロスがかなりでかい)。全探索はアルゴリズムの基礎なので、適した方法を選べるようにしよう。

書き直したのはほぼ解説のコードそのままになっちゃったけど
Submission #4387234 - AtCoder Beginner Contest 119

D - Lazy Faith

AC: Submission #4374551 - AtCoder Beginner Contest 119

Cとは打って変わって二分探索するだけ、現在地が寺・神社のどの部分に入るかを二分探索で出して、左右の寺と神社の組み合わせで一番近いものを選んでいく。左右に-infinfを置いておくと場合分けが不要でスムーズ。とはいえちょっと実装をバグらせて少しもたついたりしたのは反省。

あとこの問題、PythonでTLEした/しそうという情報を耳にしたけど、↑のコードは入力が多いからinput()を避けた以外はあまり速度を気にしてない(一番回るところでmin()max()何回も使ってる)けど547msでかなり余裕あるので、やっぱり入力が105の桁行ったらsys.stdin叩きましょう。今回は3*105だからね。

min()max()避けてちょっと書き直したけど大して速くならなかった。105回のループ程度だと関数呼び出しコストはほぼ気にする必要なしかなあ。
Submission #4388003 - AtCoder Beginner Contest 119

追記

実際試してみたけど

sys.stdinで入力取るだけ 135 ms
Submission #4388791 - AtCoder Beginner Contest 119
input() 485 ms
Submission #4388824 - AtCoder Beginner Contest 119

差はでかいけどTLEするほどでもないような…?

Pythonの文字列検索が速い件について(雑)

と情報提供を受けておきながらC読めねーし…と放っておいて本当に一世紀経過しそうな最低マンですが、C勉強してPythonのソースがスラスラ読めるようになる前にぼくの寿命が尽きてしまう可能性が高いので、とりあえず該当ソースを示すだけしてお茶を濁したいと思います(ごめんなさい)。

Pythonの文字列検索

cpython/fastsearch.h at master · python/cpython · GitHub

Pythonの文字列検索ではたぶん↑164行目のFASTSEARCHが呼ばれている?で178行目で検索文字列が1文字以下の場合分けがあって、0文字ならreturn -1、1文字なら42行目のSTRINGLIBが呼び出される。STRINGLIBではほぼmemchr()して結果をreturnしているだけのようなので(1文字の場合のみ)、Pythonで1文字の検索や__contains__などはC言語memchr()するのと同等と言える?

2文字以上の処理は198行以降で(FAST_RSEARCHフラグは逆から検索かな?)、206行のコメントにboyer-mooreの差分テーブルを作るよっとあるように、boyer-moore法+αで検索している。実装の詳細は↓に説明があり、Python 2.5から追加されたらしい。

The stringlib Library

boyer-moyer法について理解しようかと思ったけど自前で実装すること無さそうだし(Python上で再実装しても100億倍遅くなるだけだし)やめた。

そもそもC言語の世界で全部やってるから速いのでは

もともと冒頭のツイートは1文字検索で試したときに思ったもので、1文字ならそもそもboyer-moore法使ってないので魔法のアルゴリズム云々の話ではなかったわけ。で cpython の stringlib はどれもC実装であり、検索やらsplitやらなんやら文字列操作している最中はPythonの世界と行き来することなく、多分処理の全てをC言語の世界の中で完結していると思う。結局それができないリストとかの検索と比べてそれのアドバンテージがめちゃくちゃデカいだけのような気がします。リスト内の検索は要素ごとにPythonのオブジェクトをCの世界に変換して持ってく手間がかかるはずだし(ソース読んでないので適当です)。そもそも型ごちゃまぜにできる時点でアレだし。

実例

例えばこの問題

No.599 回文かい - yukicoder

は具体的な説明は省くけど文字列をN2区間比較する必要があって、文字列比較を直接やると文字列比較自体にO(|s|)かかるから結局全体でO(N3)になっちゃうよ、それを何かしら工夫してO(N2)でやってねという問題。

でこれをTLE上等で愚直にO(N3)の文字列比較でやってみる:
#317456 No.599 回文かい - yukicoder

まあさすがに104の3乗は無理だよねっと今度はローリングハッシュでO(N2)風味にしてみる。ロリハほとんど書いたことないのでちょっとおかしくてもいじめないで

#317459 No.599 回文かい - yukicoder

変わらずTLEどころかちょっと遅くなってる??これ最も遅そうなテストケース2_7.txtを試してみると、手元環境では上のO(N3)解が5.08sで、下のO(N2)解は6.71sなんですよ。定数倍の差は結構あるけど、それにしてもオーダーの指数が1違うのをひっくり返すほどの速度差やばくないですか。まあTLE同士比べて速いの遅いの言うのもほんとしょうもないですけど…

ちなみにpypyだとロリハでAC。上のは通りません(pypyは文字列操作遅いとかなんとか)
#317460 No.599 回文かい - yukicoder

結局

Pythonの文字列同士の比較(一致判定や辞書順比較)、strにぶら下がってるメソッドなどでかなり計算量重めの処理をさせる場合、想定よりかなり短い時間で済むことが期待できる。細々とした文字列処理のメソッドを何百万回も呼ぶみたいなのはPython←→C世界の行き来とかそもそも関数呼び出しコストなどがボトルネックになって速くないので注意。

4. 組み込み型 — Python 3.6.5 ドキュメント
ちょっと試した限りでは、複雑な置換ができそうなstr.translateなどもとても高速にやってくれるので、色々覚えておくと使い道があるかもしれない。

AtCoder Beginner Contest 118

A - B +/- A

AC: Submission #4278888 - AtCoder Beginner Contest 118

b%aを取って場合分けする。

B - Foods Loved by Everyone

AC: Submission #4281111 - AtCoder Beginner Contest 118

本番ではBにしては微妙に実装が重いと思いながら書いたが、見直したらなんでこんなめんどくさいことしてるんだ…配列用意して出現したの足してけばいいだけ。なんかついついCounterを無駄に使いがち

C - Monsters Battle Royale

AC: Submission #4282239 - AtCoder Beginner Contest 118

gcdっぽい(完)。似たようなgcdの単純な問題で自分が最初に思い浮かぶのは

4面サイコロがあって、サイコロの目はa, -a, b, -bである。
スタート地点はマス0で、ゴールはマス1である。a,bが与えられたときにゴールできるかを判定せよ。

みたいな問題で多分atcoderだったと思うんだけど探しても見つからなかった……(この問題はgcd(a, b)が1かどうか判定するだけ)。こう、大きい方から小さい方を引いてくとどんな数が作れるの?的な感じの問題はやってることがユークリッドの互除法まんまだしgcdっぽいのでgcdを投げます。今回のABCの解説動画でちゃんと図付きで説明してたのでピンとこない人は見るべし。

D - Match Matching

えーん解けなかった。のでいろいろ反省書こうと思ったんだけど、解説見てACしたらこれ普通のDPすぎて書くことないな?何で解けなかったの?って感じになった。

最初はNから始まって数字を追加しつつ0を目指す、残りマッチ棒をキーとしたDPを立てたんだけど、桁数を管理するためにdp[今の桁数][残りマッチ棒]と二次元にしてしまった上、中身に最大で5000桁になりうる生の数を入れてしまったため、手元で最大ケースを試したときに10秒以上かかったのでDPを諦めた。

→ 1次元にして中身を文字列にしたら余裕だった。これマジで遷移も素直なふつーの文字列DPなのでこれ書けないと本当にダメ
Submission #4296895 - AtCoder Beginner Contest 118

DPを諦めた後は迷走アンド迷走で、桁数が大きい方が必ず最善だからと桁数をN / (与えられた数字の中で最小のコスト)決め打ちで変な貪欲をしようとしたのでWAWAWAで時間切れ。N / 最小コスト桁が必ず実現できるとは限らないので(残り本数をピッタリ0にできない場合がある)、先に桁数を決めたい場合もNからコストで遷移させるDPをする必要がある。

桁数DPしてから貪欲で数字を復元
Submission #4295223 - AtCoder Beginner Contest 118

この桁数DP→復元という手法は知見だけど、この問題に関してはまどろっこしすぎて、上のDP書けば終わりなので。DP練習しましょう。

AGC021 B - Holes

B - Holes

ACしてる人たちの解説が簡潔すぎてきょうぷろらーには天才しかいねーのかという感じになったのでメモ。

まずこの問題は制約より円が無限に近く大きいので、穴の集合の中で外側にあるやつは外側の無限に広い範囲に落ちたすぬけくんをモリモリ拾えるけど、内側にある点は有限範囲に落ちたすぬけ君しか拾えない。

f:id:htkb:20190212215416j:plain

このため、内側の点は0とみなしてしまってよく、外側の点のみを見ていきたい。この外側の点の集合は凸包になるので、なんかグラハムスキャンみたいなのを使って凸包を得る(蟻本p233)。んで各頂点が拾える外側の範囲は、凸包の順序で前の点を繋ぐ辺の垂直二等分線と、次の点を繋ぐ辺の垂直二等分線の間くらいかなーというおきもちになる。

f:id:htkb:20190212215430j:plain
(図が不正確……)

そうなると、これ結局垂直二等分線のなす角の比を求めればいいんじゃんということになるんですが、凸包の点・垂直二等分線との交点*2・外心がなす四角形のうち、垂直二等分線との交点の部分は当然90°なので、360° - 90 - 90 - 内角で出ます。おわり。

AC: Submission #4245067 - AtCoder Grand Contest 021

↑のグラハムスキャンは微妙にバグっぽいので(偏角が同じ点が複数あるときに危うい)流用は非推奨。蟻本のを写経しましょう。

みんなのプロコン 2019

ooo--- 1648 -> 1660

A - Anti-Adjacency

AC: Submission #4204105 - Yahoo Programming Contest 2019

一つ飛ばしで取っていくと半分の数を取れるんだけどNが奇数のときは両端を取れるので半分+1個取れる。つまりN/2の切り上げとKを比較。

B - Path

AC: Submission #4205935 - Yahoo Programming Contest 2019

入次数が奇数の頂点がちょうど2つか、あるいは全て偶数の頂点場合のみ一筆書き可能(前者は片方の奇数の頂点からスタートしてもう片方の奇数の頂点で終わる。後者は任意の点から始まって自分の元へ戻ってくる)。ただこの問題はそもそも辺が3本で固定なので、一筆書きできないのはある頂点から辺が3つ生えている場合のみ。

C - When I hit my pocket...

AC: Submission #4209281 - Yahoo Programming Contest 2019

すぐ場合分けするおきもちになれないと詰まるかも。ビスケットの転売ヤーになって儲かるなら明らかに可能な限りそれをし続けるのが最善なので、逆に儲からないケースを先に場合分けする。

  • B-A(転売利益)が2以下(効率がポケット叩き続けるのと同等以下)
  • KがA以下(K回の操作ではビスケットをA個用意して転売して回収するところまで完了しない)

この場合は制限いっぱいまで狂ったようにポケットを叩き続けるのが最善なのでprint(1+K)

そうでない場合、今回の条件ではお金を残すことに意味はないのでビスケットA個を1円で売るのと1円でB個買うのはセットで考える。するとビスケットをA個用意した段階での残りの操作回数を2で割って切り捨てた回数だけB-A個ビスケットが増える。操作回数が1回余ったら前述の通りお金に変える意味はないのでポケットを1回叩く。

D - Ears

C解けたのが17分でずーーーーっと考えていたんだけど、必要条件をもれなく考察することができなかった。この問題は気づかなければならないポイントがいくつもあって、全部気づかないと多分DPに至るおきもちになれないと思われるので難しい。

まず考察すべき点を自明な順に列挙してみる。

  • 散歩する範囲は連続した区間である(はい)
  • 散歩区間外の石は全て操作回数を使って補充しなければならない(はい)
  • 散歩区間内ではいくら必要数が大きい地点があっても反復横飛びをして数を増やせる(図に書いてれば気付く)
  • 上より、最終的にあるポイントに左から入って右から出る(あるいは逆)場合は奇数個取れる、そうでなければ偶数個、など、偶奇のみが問題になる(ただし0は分ける)(図に書いてれば…)
  • 結局、散歩区間は[偶数回取るゾーン]→[奇数回取るゾーン]→[偶数回取るゾーン]に分けられる(無理)

よって、散歩区間外も合わせるとこんな感じになる:
f:id:htkb:20190210131524j:plain

区間が5つに分けられて(ただし長さが0の区間もあり得る)、上から下へと移行する流れになる。ここまで考察できて初めて各AiについてDPをするという考えが出てくる。ここで各区間の性質と遷移についてもう少し詰めよう。

  • 最初のスルー区間: Aiを取れないのであとでりんごさんが入れることになる(コスト+Ai)
    • →スルーを継続
    • →最初の偶数区間に遷移: 次の状態は散歩の折り返す範囲内である(散歩の始点はさらに先)
    • →飛ばして奇数区間に遷移: 次の状態が散歩の始点である(折り返す範囲は無い)
  • 前の偶数区間: 必ず2個以上の偶数個取るので、Aiが偶数ならちょうど同じ数取れる、奇数なら1個足りないか余る(コスト+1)、0ならば最低でも2個取るのでコスト+2
    • →偶数区間を継続
    • →奇数区間に遷移:今の状態と次の状態の間に散歩の始点が存在する
    • →飛ばして後の偶数区間に遷移: この遷移、実は必要ないんだよね
  • 奇数区間: 必ず奇数個取るので、Aiが奇数ならちょうど取れる、0・偶数の場合はコスト+1
    • →奇数区間を継続
    • →偶数区間に遷移:今の状態と次の状態の間に散歩の終点が存在する
    • →飛ばして最後のスルー区間に遷移:折り返さないまま散歩を終了
  • 後の偶数区間: 前の偶数区間に同じ
    • →偶数区間を継続
    • →最後のスルー区間に遷移:散歩の範囲が終了
  • 最後のスルー区間: 最初のスルー区間に同じ
    • →スルーを継続するのみ(散歩区間が後ろにあるので他の状態への遷移はない)

こんな感じで、A1からANまで上の状態から下へ+0〜2の範囲で遷移させるDPをやっていく。これをナイーブにやるとpythonではTLEしてしまうので、上の区間を1〜5番と呼ぶとすれば、次の1番へ遷移するのは前の1番+コスト、次の2番へ遷移するのはmin(前の1番, 前の2番)+コスト, 次の3番へ遷移するのはmin(前の1番, 前の2番, 前の3番)+コスト、…みたいにまとめてやると十分に通る。

AC:Submission #4219971 - Yahoo Programming Contest 2019

ついでに深夜の変なテンションでコードを縮めるのを頑張ってみた。
Submission #4220372 - Yahoo Programming Contest 2019

D解けなかったのは完全に力負け(今の実力では考察しきれない)という感じ。知らないアルゴリズムが必要なわけでも何でもない純粋な力勝負のDP問題という感じなのでこういうのを取れるようにならないと。

AtCoder Beginner Contest 117

(しかもDは嘘解法だったので実質3完)

A - Entrance Examination

AC(1WA): Submission #4153281 - AtCoder Beginner Contest 117

初めて直書きREを経験した。

B - Polygon

AC: Submission #4154435 - AtCoder Beginner Contest 117

ソートして与えられた定理をそのまま使いましょう。

C - Streamline

AC(2WA): Submission #4159353 - AtCoder Beginner Contest 117

問題をちゃんと読まないうちにコード書き始めるのは辞めなさいって言ってるでしょ!最初何考えてたんだか二分探索しようとするしほんと最悪だった。イメージ的には隣接した頂点2つを選ぶと間の辺を通過する必要がなくなりそこのコストを消せるので、結局置いた頂点-1個の辺を重い方から消せばいいだけの問題。

D - XXOR

AC(2WA, 嘘解法): Submission #4160592 - AtCoder Beginner Contest 117

嘘貪欲を書きました。反省。しかしなんでこんなのが通るのって感じですが…。反省のため色々自己分析します。

なぜ貪欲をしたか

一般的に桁ごとに数を決めていく最小数/最大数や辞書順最小/最大問題は貪欲が最良と相場が決まっていて、上位桁/文字がより良い状態をそれ以降の桁/文字で挽回することはできない。例えば

N個の数字があって、K桁の数を作りたい。N個の数字には全てコストが設定してあり、
コストCを超えて数字を選ぶことはできない。条件を満たす最小の数を出力せよ。

例1:
N=8, K=4, C=10
1=コスト7,  2=コスト3, 3=コスト3, 4=コスト2,
5=コスト2,  9=コスト1, 9=コスト1, 9=コスト1

この例の場合、最上位桁に1を選んでしまうと残りコスト的に下3桁は9で埋めて1999にしなければならない。しかし最上位桁に2を選んだあらゆる組み合わせよりも(仮に2000が作れたとしても)自明に小さくなるためそれが最良である。このようにこういう問題ではその後の桁でいくら頑張っても上位桁の結果を挽回することができない=貪欲が最良ということがよく知られている。

ただしそれは一つの数/文字列を決める場合ならば

今回は数列の総和を最大化するため、上位桁の最良が全体の最良になるとは限らない。ツイッターで流れてた例としては

5 2
2 2 0 0 0

の答えは6ではなく9である。2bit目をひっくり返すと2*2 -> 2*3になって+2となるが、ここをあえてひっくり返さずに1bit目をひっくり返すと1*0 -> 1*5となって+5になり、このほうが差し引き+3得になる。一般化して考えると、最上位桁をひっくり返す場合の最小の利得は2^bit(Nが奇数の場合)で、その次の桁以降をひっくり返す場合の最大の利得は(2^bit-1)*Nであり、当然ながら後者のほうが大きくなりうるので貪欲は最良ではない。はい論破。おまえのカーチャンの子供でーべそ。

ついったーでは桁DPをみんな頑張ってたみたいだけど面倒くさいイメージしかないので、前処理して再帰してみた。コメントに書いたけどbit反転できるのに反転しない場合はそれ以降の桁で好きなように選べるので再帰するまでもなくその場で結果が確定し、再帰回数はlog(max(K, Ai))で済む。はず。実装が超軽く済んだ。

AC: Submission #4184930 - AtCoder Beginner Contest 117

反省の弁

早解きでfastest目指せるレベルじゃないんだから適当に無証明をぽんぽん投げるの止めましょう。ていうかunratedだからこそ順位を気にしすぎず丁寧に証明しながら解いて血肉にすべきなのに。

全国統一プログラミング王決定戦予選

oooo-- 1611 -> 1648

A - Subscribers

AC: Submission #4097865 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

数弱なので100点問題から紙に書くことに……。X・Yともに購読している最小人数は、両端から埋めていった場合の重なる部分

XXXXX--YYY # 答えは0
XXXX***YYY # 答えは3

であることはすぐに考察できるので、ぱっと式が思いつかなかったらいっそサイズNの配列作ってシミュレーションしたほうが早かったんじゃないのと思わなくもない(N <= 100なので)。いやでもこれノータイムで式立たないのはアレっすね……。

B - Touitsu

AC: Submission #4098952 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

こっちのほうが簡単。違う文字があればその場で変更しなければならないので、それぞれ頭から1文字ずつ取っていって何種類の文字があるか見るだけ。

C - Different Strokes

AC: Submission #4100640 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

悲喜こもごものC問題。強い人も結構落としてたりして、色々複合的な要因がありそう。400点という配点からソートして終わりというのは真っ先に思いつきにくくて、区間DPかなんか?再帰すんのかな?などと考えたけど、どうも貪欲っぽい→評価関数は?自分が美味しいものを取るのと相手に美味しいものを取らせないのは等価じゃないの?→A+Bでソートすればいいね→ACという感じ。

考察できればこんなもんだし実装は一発だけど、400点という配点が読みをずらしてきたり微妙というか絶妙というか、そんな問題。

D - Restore the Tree

AC: Submission #4105566 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

トポロジカルソートを使うであろうことはまともに考察する前に思い当たって、ライブラリに持ってなかったし問題も解いたことなかったので半分諦めよっかムードだったんだけど、とりあえずググって出たの貼っ付けて色々やったら何とかなった。あんまり考察詰めないまま通したので考察しなおし。

元の木から追加された辺は自分の子孫への辺に限られるので、木ではなくなっているけどDAGではあって、制約から多重辺もないので追加された辺は必ず元の木よりも繋ぐ頂点間の距離を縮める辺である。なのでトポロジカルソートとか使わなくても全探索を工夫して到達が一番遅くなるような辺(=元の木の辺)を探すことはできる。

トポロジカルソートをするとトポロジカル順序が得られるが、別にこれは木の親子対応を示すわけではないのでどうすんのって話だけど、トポロジカル順序を前からスタックに積んでいって、次の頂点番号がスタックの一番上の辺とつながっているなら親子関係確定、なければpop()するみたいな前から見ていく方針を取ったらRE。スタックが空になってるんだろうけどどういうケースでスタックが空になるのかわからないまま後ろから見る方針に変更。辺を取るときに逆辺も別に取っておいて、トポロジカル順序の後ろから見ていき、張られている逆辺の中でトポロジカル順序の出現が最も遅いものを親とする方針でAC。計算量が気になったが制約にN + M <= 10^5があるので全部辺を舐め直すようなやり方でも大丈夫だった。

DAG・トポロジカルソート関係の問題は要復習。