htkb-proconの日記

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

AtCoder Beginner Contest 100

B - Ringo's Favorite Numbers

Submission #2676172 - AtCoder Beginner Contest 100

N=100のケースだけ注意。200点のくせに問題文斜め読みしてたら足引っ掛けそうな罠が。

C - *3 or /2

Submission #2677755 - AtCoder Beginner Contest 100

ある数を3倍するか2で割るかというのは、素因数分解したときに3の指数を1増やすか(あれば)2の指数を1減らすかということなので、3倍しても2で割れる回数に影響しない。で回数を最大化するためには当然1ターンあたり一つの数のみ2で割るようにすればいいので、結局全部の数に対して何回2で割れるか試せばいい。

何回2で割れるかはどうせ高々log n回のループなので工夫する必要はないんだけど、bin(n)で二進数表記を取って最初に1が現れるまでに何個0が出たかとか数えたりする手もある?逆に遅くなるか。

D - Patisserie ABC

コンテスト中にアホなことして延々とWA叩いてた……。
WA→Submission #2683278 - AtCoder Beginner Contest 100
それぞれ符号をプラスとマイナスにして8通り試せばいいってとこまではたどり着いたんだけど、ただソートして上からM個取ればいいだけなのをわざわざdp組んでしまい、さらにdpの初期値を全部0にしてdp全体のmaxを結果としたために、M個取らない合計値が採用されてWAが出てたっぽい。M個選ばなきゃならないので、dp[0]以外は-infかなんかで初期化しなきゃならないしreturnするのもdp[-1]だけだしif subtotal < 0: continueもしちゃだめ。

dpでAC→Submission #2691785 - AtCoder Beginner Contest 100
そもそもソートして上位M個取るだけでいい→Submission #2691763 - AtCoder Beginner Contest 100

うーん始めて1年以上なるのに未だに400点が解けたり解けなかったりで成長しないなあ……。結局精進が足りないのだろうけど。追い越していく人をへこたれない程度に見習いつつ地道にやっていきます。

AtCoder Beginner Contest 099

B - Stone Monument

https://beta.atcoder.jp/contests/abc099/submissions/2645570

問題文が!よくわからない!!塔の上には積もらず、上の方を覆い隠すようにだけ積もったってこと??よくわからないのでサンプルから雰囲気で和の公式でアレした。わたしにほんごちょっとわからない。

C - Strange Bank

https://beta.atcoder.jp/contests/abc099/submissions/2646783

Nを超えない範囲の1, 6の累乗, 9の累乗のリストを作って、Nからそれらの数を引いた答えを全てsetで持って、0が出たらそこまでかかったターン数を出力というよくわからん解き方をした。答えはあまり大きな数にならんだろうと、いかにもsetの要素数が増えてループ数が爆発しそうなことに目を瞑ってぶん投げたら1.4秒かかってやっぱりアレだった。

丁寧にDPで書き直したらクソ遅くなった件 https://beta.atcoder.jp/contests/abc099/submissions/2652056

D - Good Grid

https://beta.atcoder.jp/contests/abc099/submissions/2648980

500*500の全てのグリッドを毎回走査しなくても、最初から(i+j)%3ごとに色情報をまとめておけば、色を変える時の総コスト計算は高々150回の計算で済む(C=50, (i+j)%3=0〜2)。そのように下準備をして、色1〜Cから3色を選ぶ順列をitertools.permutationsで作って、総コストを計算し最小を更新する。

最悪計算量は50*49*48*150=17640000で107の桁になるので、pythonでは絶対に通らないし最初っからpypyで提出しようかと思ったけど普通にpython3で734msで通ってしまった。何故通ったのかわからない。

AOJ 0585 Nearest Two Points 最近点対問題

距離が最小の2点 | Aizu Online Judge

この問題、適当に証明もせずなんとなく思いつきでコードを書いて提出したら通ってしまって、CPU時間のランキングを見てみるとC++Javaのコードに囲まれていておっかしいなーと思ってたんだけど、ちょっと考えてみたら自明に嘘解法だった。ていうかなんでこんなのが通るの?

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2914496

上のコードはx軸でソートしてx軸で隣り合う点同士の距離を取っていき、次にy軸でソートしてy軸で隣り合う点同士の距離を取っていき、最小値を出力するだけ。当然ながらx軸でもy軸でも隣り合わない点対が最近だった場合は正しい答えが出ず、

4
1 3
2 100
3 1
100 2

のテストケースだと9410を出力してしまう。最近点対問題は典型問題のようなのでちゃんと知っとかないとまずいなっと思い色々調べたところ、基礎的な考え方について一番わかりやすかったのはなんと蟻本(p324〜)だった。上級編のとこだったから100年早いと思って読んでなかったよ……。

x軸で再帰的に左右に分割していき、分割したそれぞれの領域内の最近点対距離で最小dを得て、x軸の中央値から±dの範囲内について分割境界をまたぐ点対が最短にならないかチェックする、というのが図で示してあって分かりやすかった。ただし、与えられた全ての点のx座標が同じ、などのようないじわるなテストケースについてのフォローがなく、そのようなケースだと境界をまたぐ点対チェックでO(N2)になっちゃう?のかな?中央値±dの範囲に全ての点が含まれてしまうので、渡された点のx座標を重複なしのsetで取り数を数え、半分以上被ってたら基準軸をy軸に切り替えるなどの工夫をする必要があった。

ACコードはこれ http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2917868

axis1を基準にleftrightに分割し再帰していき、境界をまたいで最近点対になる可能性のある点をmid_aに取って各点+dまでの範囲について点対距離をチェックしていく。itertools.takewhileが便利だった。

ただこの問題は5つしかテストケースがなく全部同じx座標/y座標のようなコーナーケースも含まれず、逆にNは大きくLLでは定数倍改善ゲームになりがちなので、まずは下の問題を通すのから始めたほうがいいかも。

最近点対 | 計算幾何学 | Aizu Online Judge

ACコード http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2917884

こっちはいじわるなケース完備なので、ちゃんと軸を変えていかないとめっちゃTLEする。

yukicoder No.407 鴨等素数間隔列の数え上げ

No.407 鴨等素数間隔列の数え上げ

素数の列挙を行う必要のある問題。素数列挙といえばエラトステネスのふるいで、これを普通に組んでTLEになった問題に今まで当たったことはなかったけどこの問題ではだめだった。

定数倍に気を遣ったエラトステネスのふるいでの素数列挙
https://yukicoder.me/submissions/260831

上のコードで気を遣ったポイントは

  • 最初から偶数を省いて素数候補を作る
  • ふるいで素数の倍数を落とす際に、素数の偶数倍は偶数で↑により既に候補に含まれないため、i*3からi*2飛ばしでrangeを作る(今見ているのが3ならば9, 15, 21, 27...みたいな数列を作ってふるい落とす)
  • set.difference_updateは差集合を得る、つまり+=と同じだがset以外のiterableも受け付けるのでsetインスタンスを作り捨てずに済む
  • もちろん属性アクセスはループ前にキャッシュ

でそこそこ速いつもりだったんだけど普通に通らなかったので高速な素数列挙を調べてみたところ、とりあえずエラトステネスの前処理でお手軽にできるWheel factorizationとやらが見つかったので試してみた。とても分かりやすかったサイト↓

理屈は上のサイト見れば全部わかるのであとは実装どうすっかだけど、pythonでforループでちまちま要素追加してくと余計遅くなりそうなので、とりあえずサイクル長=6で素数候補は{2, 3, 5から6飛ばしの数、7から6飛ばしの数}と決め打ちでsetを作る。ふるい落としのターンでは5から6飛ばしの数と7から6飛ばしの数のみチェックすればいいので、for i in range(5, N+1, 6)みたいにして回して、ii+2に対してチェックしていけばいい。上のサイトの長方形の数列を見て理屈を理解すればライブラリ化してなくてもその場で問題なく素で書ける。

でACしたコード https://yukicoder.me/submissions/260853

微妙な改善って感じだけど……。サイクル長を30にしたら実装が煩雑になって手元では余計に遅くなった。そもそもset素数候補全部持つのが重いんだろうか。もっと根本的に軽い実装あるかなぁ

AtCoder Beginner Contest 097

B - Exponential

Submission #2496124 - AtCoder Beginner Contest 097

どうやって求めるかぱっと出てこなかったのでめっちゃループを回した。

for i in Xから1まで
  for j in ルートiから1まで
    for k in 1から9まで
      i == jのk乗だったら答えはi

みたいな。kが1~9なのは制約X <= 10002^9 < 1000 < 2^10のため。

C - K-th Substring

Submission #2498311 - AtCoder Beginner Contest 097

|s| <= 5000なので全列挙は無理。1 <= K <= 5なので若いアルファベットの周辺だけちょこちょこ探索して済みそう。辞書順問題の基本として、先頭に近いアルファベットが若ければ必ず辞書順も小さくなるので、文字列の中に"a"が含まれるなら必ずそれを先頭に使った部分文字列が辞書順の先頭の方に来る。なので文字列sにアルファベットaが含まれるインデックス番号を列挙し、そこから後ろ5文字くらいまで範囲を伸ばして(k <= 5なので)aが頭文字となる部分文字列を列挙して、重複を排除し、部分文字列の個数がk個以上だったら辞書順k番目の文字列が答え、k個未満ならその個数分kを減らして次のアルファベットを同じように探索……を繰り返した。

D - Equals

Submission #2500414 - AtCoder Beginner Contest 097

多分プロの人らは一目見て即グラフ問題だと気づくんだろうなあ。スワップは何回でも可能なので、入力例2を見てもわかるとおり1 22 3が繋がってるなら1 2 3は自由に並べ替え可能。したがってスワップ可能なM個のペアを辺としてグラフを構築し、DFSなどで繋がっている頂点を調べる。繋がっている頂点の値は任意に並べ替え可能なので、繋がっている頂点番号の集合と頂点の値の集合の論理積を取るとかなんかそんな感じでp[i] == iにできる個数を数える。

{5, 3, 2, 4, 1} のうち1番目と3番目と5番目が繋がっている
↓
頂点番号:{1, 3, 5}
頂点の値:{5, 2, 1}

繋がっている頂点の値は任意に並べ替え可能なので、
頂点番号と頂点の値で被っているものがあればそれはp[i] == iにできる。

{1, 3, 5} & {5, 2, 1} = {1, 5} ←2個の頂点がp[i] = iにできる

最後に全く繋がっていない(スワップできない)頂点もチェックしなければならない。繋がっていない頂点は並べ替えできないので最初からp[i] == iになってないとダメ(1WA)。

AtCoder Beginner Contest 096

C - Grid Repainting 2

Submission #2461512 - AtCoder Beginner Contest 096

番兵で周りを囲む、ループ回しながら隣のマスを調べるなど二次元座標探索の基本をやる問題。制約がゆるいので定数倍を気にする必要は無かったが、pythonのindexingはかなり遅いため全座標に対して毎回二次元indexingしまくるとクソクソ遅い。こういうのはzipなどを駆使しできる限り座標の中身を値で受け取るようにしたい。

改善例→Submission #2472595 - AtCoder Beginner Contest 096

同じような定数倍改善で通らない問題が通せた例

よくpythonはforループが遅いと言われるけど、numpyが速いのでnumpyで完結できることをforでやると当然遅いってのと、indexingや属性アクセスなどの遅いことをループ内でやりがちってだけで、pythonの中でforループ自体が特別に遅いということは無いような気がするけどなぁ。append = a.appendのようにループ外で属性をキャッシュして使うとforと内包表記の速度差はかなり縮まるし。

D - Five, Five Everywhere

Submission #2464170 - AtCoder Beginner Contest 096

まずエラトステネスのふるいで55555以下の素数リストを作る。ふるいは過去に実行時間測定しながら効率良さげな書き方を調べたのを覚えてた。以下のような感じ:

import math
n = 55555
primes = set(range(2, n+1))
for i in range(2, math.sqrt(n)+1):
    primes.difference_update(range(i*2, n+1, i))

set.difference_updateは要するに-=演算子とほぼ同義なんだけど、-=の被演算子setしか取れないのに比べてdifference_updateの引数はiterableなら何でも取れる?のでrangeをそのまま渡すことができ、いちいちsetを作り捨てるよりかなり高速なのがミソだった気がする。

そこまではいいんだけど何をトチ狂ったか「2が入ってれば5つの和は必ず偶数になるんじゃね??」とか勘違いして1WA、しばらく思いつかなくて数が大きくなれば新たな素数はできにくくなるだろうと素数リストの大きい方から指定個数切り出してみて2WA(こういう横着を想定してないわけないよな……)。1の位が全部1なら5つの和は必ず5の倍数になるなとようやく気づいてAC。こういう発想問題は数論系の知識の引き出しが少ないと難しいな。

AtCoder Beginner Contest 094

B - Toll Gates

Submission #2352431 - AtCoder Beginner Contest 094

問題文読むのがなんか辛かった……。解いてる時は普通にループ回す泥臭い方法しか思いつかなかったけど、制約厳しくてもAを二分探索して終わりじゃないか。制約変えてCで出てたらハマりそうだった。

C - Many Medians

Submission #2353068 - AtCoder Beginner Contest 094

Nが偶数で、各Xiを除いた中央値を求めるということは、求めるべき中央値は元の数列の真ん中2つのどちらかになり、各XiにおいてXi >= 元の数列の真ん中上の数なら小さい方の数、違うなら大きい方。

D - Binomial Coefficients

Submission #2354005 - AtCoder Beginner Contest 094

0 <= ai <= 10**9

の制約より組み合わせの公式で計算することは不可能。n! / r!(n-r)!なのでnは最大の数字を選ぶのが最適なことは明らか。rはできるだけ真ん中っぽいほうがいいだろうなーというのはわかるけど、rn-rの差が最小であれば階乗の積も最小になるかな?証明わかんないけど投げちゃえって投げて通ったけどよく考えなくても当たり前だな……。差が大きくなれば大きい方の階乗に大きい因数が増えるので。