htkb-proconの日記

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

AtCoder Regular Contest 078 参戦記

oo-- 1337 -> 1358 (+21)

C - Splitting Pile

結果:AC
Submission #1422177 - AtCoder Regular Contest 078 | AtCoder

すぬけくんが先頭から連続した数列を取り、アライさんが残りを取ることになるので、snuke = 0,arai = sum(a)から始めて、数列から数字を1つずつ取ってすぬけくんに足してアライさんから引いて、そのつどabs(snuke - arai)を取ればいい。両者とも最低1枚は必要なことに注意。でもそれを忘れてループを最後まで回すと2つ目のサンプルケースで答えが合わず気付かせてくれるあたり、AtCoderは優しい。

D - Fennec VS. Snuke

結果:AC(3WA)
Submission #1427667 - AtCoder Regular Contest 078 | AtCoder

最初はただ単にそれぞれの初期位置から相手の初期位置をまたがずに取れるマスを数えてWA、進み方によって相手の取れるマスを減らせることにやっと気付いたあとに凡ミスでWA、最後に数が同じだった場合先行の勝ちにしててWAの3WA。

相手の方向に一直線に進んでいくと相手の進行可能なマスを減らせるので、最適な動きはお互いの初期位置への最短経路をお互いがたどることになる。んで自分はその経路を取るためにダイクストラをかまし、v[0]からv[N-1]への経路を復元して先頭から半分(切り上げ)をフェネックのもの、それ以降をすぬけくんのものと割り振り、相手のマスには進行不可能との条件を付けて幅優先探索を2回行ってお互いが取れるマスを数えた。

あんまりにもあんまりな解法だったので、解説にあるとおり初期位置からの距離を取って比較するやり方で書きなおしてみた。

Submission #1433142 - AtCoder Regular Contest 078 | AtCoder

時間的にはあんま変わんないけど。こっちは相手の初期位置で探索を止める処理を入れてないので。

おまけ

pythonで大量に入力を受け付けるとき、input()よりsys.stdin.readline()のがかなり速い。

readline = sys.stdin.readline

とキャッシュして(pythonはオブジェクトの属性探すのが遅いので)readline()で入力を受けると、入力回数5*105回の問題でinput()と比べて0.7〜0.8秒くらい速くなった。念のためinputの方も

_input = input

とローカルにキャッシュして試したが変わらなかった(それはそう)。仮に106回入力を取るような問題があるとinputでは全然ダメそうなのでreadlineを使っていきたい。

AtCoder Grand Contest 016 参戦記

o---- 1293 -> 1300 (+7)

A - Shrinking

結果:AC
Submission #1360112 - AtCoder Grand Contest 016 | AtCoder

うだうだ考えないでシミュレーションしましょう。高々100文字しかないのだしどう見ても計算量的に間に合うのに無い頭で考えようとするから早解きできないんだよ!!うえーん

B - Colorful Hats

結果:わかんなかった

諦めた時点のコード
f:id:htkb:20170621225028j:plain
割とあと一歩じゃん!!と思ったけどコンテスト中はこんな場合分けするのはきっと想定解と違う……などとスットコドッコイなこと考えてたし最後のelse節の部分を思いつくのは無理だっただろう。というか解説見てもよくわからんのです。

  • max(a)min(a)の差が1より大きい場合はNo。これは自明。
  • max(a) == min(a)の場合は以下のどちらかに当てはまるならYes
    • 全ての猫が違う色ケース。必ずみんなN-1と言う。
    • aloneな猫が1匹もいないケース。1色につき少なくとも2匹の猫が存在するため N//2 >= 色数

で問題は max(a) == min(a)+1のケース。解説に載ってる式とちょっと違うけど、↓の理解で通った。

f:id:htkb:20170621225303j:plain

ACコード:Submission #1369417 - AtCoder Grand Contest 016 | AtCoder

C - +/- Rectangle

あとでやる

ABC054-D DP

D - Mixing Experiment

DPやるだけの400点問題なんだけど今更こんなのでハマってしまったので忘れないように記す。

2種類の物質がa:bで混じっているc円の薬がN個あるので、これを好きなように混ぜてなるべく安く指定の比率を実現したいという問題で、制約もゆるいのでaの物質とbの物質の量でDPするんだけど、dp[i番目まで見た][aの物質の量][bの物質の量]と3次元DPテーブルを立てるところを、dp[aの物質の量][bの物質の量]と2次元DPにしてしまった。

WA: Submission #1353922 - AtCoder Beginner Contest 054 | AtCoder

変なWA出た時点で解説見たんだけど、i番目までってのを覚えとかなくてもカウント漏れはしないよなぁ……?としばらく何が悪いのか気付けなかった。カウント漏れは確かにしないはずだけど、

N=3
1:2の薬 1円
2:1の薬 2円
3:3の薬 1円

というテストケースがあった場合、2次元DPだと

dp[0][0] = 0
dp[0][0] = 0, dp[1][2] = 1
dp[0][0] = 0, dp[2][1] = 2, dp[1][2] = 1, dp[3][3] = 3

と動いたあと、最後の薬を考慮するときに

dp[0+3][0+3] = min(dp[0][0]+1, dp[3][3]) = 1
dp[3+3][3+3] = min(dp[3][3]+1, dp[6][6]) = 2
                   ^^^^^^^^
            3だったのに1に書き換わってる!!

というふうに、他のケースの遷移で値が上書きされるようなことが起こりうるはず。これが3次元DPならば薬を足す前の値はdp[i-1]から取るし、薬を足した後の値はdp[i]に入れるのでぶつからないわけ。考え方が誤っている証明が浮かばなかったので無駄に悩んでしまったけど、DPでは何番目までを考慮したかをちゃんと状態として持ちましょうという自明オブ自明な話でした。

AC: Submission #1354004 - AtCoder Beginner Contest 054 | AtCoder


追記

量を増やした時に衝突する可能性があるのだから多い方から見てけば衝突を避けられるのは自明でした。結局どう回ってるのかしっかり把握せずにコード書いてるのでバグったりするわけですはい。

Submission #1355632 - AtCoder Beginner Contest 054 | AtCoder

少し早くなってメモリ使用量が1/8くらいになった!アドバイスありがとうございます🙇

AtCoder Beginner Contest 064 参戦記

oooo unrated

A - RGB Cards

結果:AC
http://abc064.contest.atcoder.jp/submissions/1339289

(100*r+10*b+g) % 4 == 0で判定。

B - Traveling AtCoDeer Problem

結果:AC
http://abc064.contest.atcoder.jp/submissions/1339821

max(a) - min(a)を出力。

C - Colorful Leaderboard

結果:AC(1WA)
http://abc064.contest.atcoder.jp/submissions/1342283

これ罠すぎるんですけど!!!レートによって色が決定されるけど、レート3200以上の人は自由に色を決められるよ。そんとき最小・最大何色になるの?って問題だけど、レート3200以上はそれ以下の8色の中から選べるのではなくて本当に無限の色の中から好きな色を選べるので、min(colors+pro, 8)とかやっちゃダメ(やりました)。入出力例の説明の中に

4 人目が「赤色」を選び、5 人目が「青色」を選んだ時、色の種類数は 3 であり、これは最小値を取る一つの例である。
4 人目が「紫色」を選び、5 人目が「黒色」を選んだ時、色の種類数は 5 であり、これは最大値を取る一つの例である。

と8色の中にない色を選んでいる例が挙げられているので、ここで気付かなければならない模様。

実装としてはnumpy.array

colors += ((a >= スコア下限) & (a <= スコア上限)).sum() > 0

などとして色数を取ってみたよ。numpyマスターしたい……!

D - Insertion

結果:AC
http://abc064.contest.atcoder.jp/submissions/1343809

与えられた文字列を一文字ずつ見ていって、

  • (が来たら深さ+1
  • )が来たら深さ-1
  • 深さ0なのに)が来たら先頭に(を追加
  • 読み終わったのに深さが1以上なら深さ分の)をお尻に追加

とやった。正当性がよくわかんないままぶん投げたら通ったけどあってんのこれ……?(このやり方だと頭とお尻以外一切触らないんだよなあ……)正当性の証明ができないままぼんぼん投げてCodeforcesなどでボコボコhackされたりシステスで落とされたりしてるのでなんとかしたい。

ABC041-D bitDP

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder

この問題、解説見てもACコード見てもプロい人のブログとか見ても、お願いだから日本語書いて?って感じで困っていたのだけど、このブログの

感覚的には空集合の場合の数から全集合の場合の数へ、集合の数を増やす感じに計算していく。 http://mmxsrup.hatenablog.com/entry/2016/07/03/142548

この文から取っ掛かりが得られたので、海より深く感謝しながら実際に解いてる最中に考えたことを書き残しておきます。


dpの回し方としてはdp[0] = 1空集合)から始め、立ったビットのdpテーブルにビットが立つ前のdpテーブルの値を加算していく流れになるのかな?dp[01] += dp[0], dp[10] += dp[0], dp[11] += dp[01] + dp[10], …こんな感じに。

まず問題をシンプルにするために、bitDPで全ての順列の数をdpテーブルに書き込んでみる。

N = int(input())
bit_max = 1<<N
dp = [0]*(bit_max)
dp[0] = 1

for bitset in range(bit_max):
    for usa_num in range(N):
        usa_bit = 1 << usa_num
        if bitset & usa_bit:
            dp[bitset] += dp[bitset-usa_bit]
print(dp)

このコードに3を与えてみると

[1, 1, 1, 2, 1, 2, 2, 6]

が出力される。3匹の中から3匹を選ぶ順列の数3P3 = 3!/(3-3)! = 6なので合っている。このコードを実行すると、dpテーブルは以下のような遷移をしているはず:

f:id:htkb:20170605211438j:plain

冒頭の問題に戻ると、上の遷移がゴールの早いうさぎ順に順番を決めているとするならば、集合を増やしていく過程で自分よりも先にゴールしたうさぎを全て含まない状態への遷移はありえない。例えば

3 2
2 1
3 1

のテストケース、うさぎが3匹で1のうさぎより2,3のうさぎのほうが早かった場合、1が初めて出てくる集合は{1, 2, 3}しかない。{}から{1}への遷移は、うさぎ1が1等だった場合の順列を数えようとしており、このような条件に合わない遷移を除外する。 f:id:htkb:20170605213734j:plain

んでそれをどう判定すんのか。自分より早いうさぎをあらかじめビット列で取っておき、

(自分より早いうさビット列) & (今のビット列から自分自身を引いたもの) == (自分より早いうさビット列)

というやり方をこのACコードからパクりました考えた。自分より早いうさぎの集合⊆現在の集合になっているかを見ているわけね。

最終的なACコードはこれ:Submission #1333411 - AtCoder Beginner Contest 041 | AtCoder

AtCoder Regular Contest 075 参戦記

o— 1281 -> 1293

C: Bugged - AtCoder Regular Contest 075 | AtCoder

結果:AC
Submission #1323396 - AtCoder Regular Contest 075 | AtCoder

数列をソートして合計を取り10の倍数だったら数列の中の10の倍数ではない最小の数字を捨てて合計をチェック……を繰り返した。←これ今思えば繰り返す必要なかった(10の倍数から非10の倍数引けば非10の倍数になることは自明なので)

D: Widespread - AtCoder Regular Contest 075 | AtCoder

結果:わかんなかった

ソートした数列を取り出したり泥臭いやり方をしようとしてた時点で負けだった。てかにぶたんなんて全く思いつかなかったよ……!

Tターンで全滅させられる、とは、各モンスターに対してT*B+(A-B)*nn(切り上げ)の合計を求め、それがT以下であるということ。(A-B)*nとは何度そのモンスターを中心にして攻撃したかということなので。

A = 3, B = 1
h = [3, 3, 9] 

T = 3 とすると、
h1: 3 = 3*1+(3-1)*n
    3 = 3 + 2n
    n = 0 # 3ターン全て中心に選ばなくても倒せる
h2: 同上
h3: 9 = 3*1+(3-1)*n
    9 = 3 + 2n
    n = 3 # 3ターン中心に選べば倒せる

T >= nの合計 より、3ターン以内で倒せた

以上の考え方で、Tの値を二分探索する。
ACコード:Submission #1329512 - AtCoder Regular Contest 075 | AtCoder
pythonだと1787msもかかってるんだけどやり方悪いのかな……?

Codeforces Round #416 (Div. 2) B 平方分割

B. Vladik and Complicated Book

適当訳:数列と3つの数字からなるクエリl, r, xが与えられるので、元の数列とそれのl番目からr番目までを昇順にソートした数列を比べて、x番目の数字が変わってないか調べてNE!

数列 5 4 3 2 1
クエリ 1 3 1 → 変換済み数列 3 4 5 2 1 → 1番目は元の数列と違うので No
クエリ 2 4 3 → 変換済み数列 5 2 3 4 1 → 3番目は元の数列と同じなので Yes

f:id:htkb:20170530205829j:plain

_人人人人人人人人人人人人人人人人人人_
> あ!これ蟻本でやったところだ!! <
 ̄Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y ̄

でも覚えてなかった!!平方分割してそれぞれのバケットごとにソートするのは覚えてたんだけど、そこからわからなくてWAとTLEを食らった。跨いでる各バケットについて二分探索するんだった。

元の数列 1 7 4  3 9 2  6 5 8
√n個のバケットに分割してソート
バケット[1 7 4][3 9 2][6 5 8]
↓
ソート  [1 4 7][2 3 9][5 6 8]

クエリ 3 8 5 の場合:元の数列の5番目の数は 9
3〜8番目の中でまるまる含まれているバケット(この例では2番めのバケット)について
二分探索などで9が各バケット内の何番目こに入るか高速に調べる。
           ↓ここ!
    [ 2  3  9 ]

バケットの一部しか含まれない左右の部分は、元の数列から引っ張ってきて
くっつけてソートし、同じように何番目に入るか調べる。
左の切れ端 右の切れ端
    [ 4 / 6 5 ]
         ↓
    [ 4  5  6 ]
             ↑9が入るのはここ!

つまりソート部において9の左に5個数字がある=ソート部の6番目に入る
=ソート開始地点より左の2つも合わせて、変換済み数列の8番目に9がくる
元の数列では5番目だったので答えは No

pythonならばbisectモジュールのbisect_left()を使うことで簡単にある数字がリストのどこに入るのか二分探索で調べてくれる。
提出コード(汚い):http://codeforces.com/contest/811/submission/27383788

蟻本に載ってるPOJの問題はこちら 2104 – K-th Number