htkb-proconの日記

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

AtCoder Regular Contest 083 参戦記

o--- 1422 -> 1408

C - Sugar Water

結果:AC(2WA)
Submission #1598690 - AtCoder Regular Contest 083

コンテストではDPで解いたのだけど、DPを思いついてコードを書き始めるまでにすごい時間がかかってしまったのでダメ。最大F+1までのサイズのdp配列を用意して、

  • 水をA*100g追加する
  • 水をB*100g追加する
  • 砂糖をCg足しても溶け切るならばCg追加する
  • 砂糖をDg足しても溶け切るならばDg追加する

をFを超えない範囲で繰り返した。「現時点では砂糖が溶け切らないが後で水を足せば程よい濃度になる」という状態への遷移は、先に水を足して後から砂糖を足す遷移でもたどり着けるので切る。また、水も砂糖も0gはWA。これで2WAした。

実際はAもBも100g単位でFも高々3,000であるため、取りうる水の量を全列挙しその都度限界まで砂糖を足していけば良いだけであった。Pythonではitertools.productとか使えるとモテ系って感じね。

D - Restoring Road Network

結果:-

問題読んでワーシャルフロイドだなと気づいて300^3pythonでは明らかに無理だと諦めつつ別解を探しながら眺めてたのだけど、解説読んでも理解に時間がかかったのでNが少なくてもコンテスト中にACにたどり着けたかあやしい。

解くべきは2点:

  1. 与えられた表が本当に最短距離になっているか
  2. 表に書かれた最短距離を満たす範囲で最小の道の長さの総和

1はワシャフロすればいいんだけど、2はダイクストラでもかますのかしらとスットコドッコイなことを考えてた(通るわけない)。 f:id:htkb:20170917223144j:plain
こういう、迂回しても同じ距離でたどり着けますよという頂点間には辺を貼る必要がない(総和の最小を求めているため)ので、迂回路に最短距離が見つからない場合のみ辺を貼る(答えに距離を加算していく)。例では経由点が1箇所だけだけど、仮に1-2-4-3が最短距離だったとしても1-2-3ないし1-4-3で同じ距離が得られるはずなので、N回だけ回してA[i][k] + A[k][j]をチェックすればいい。ついでに、このチェックのときにA[i][j] > A[i][k]+A[k][j]なケースが見つかったならばそれはそもそもの最短距離表が間違っていることがわかる。つまり1のワシャフロは省略可能。

で、ワシャフロを省略してもi0~N-1ji+1~Nk0~Nの三重ループとなるため、(N-1)*(N-2)/2*Nで最悪1.3*10^7くらいでやっぱり絶望的なのだけれど、定数倍改善ゲームをがんばったら通った。

Submission #1604109 - AtCoder Regular Contest 083

2次元配列より1次元配列、配列より値で受けて触るほうがかなり速くなる(それはそう)。enumerateは基本だけど有効なところでピシッと使えると間違いなくモテる。

AtCoder Grand Contest 019 参戦記

oo---- 1428 -> 1425 (-3)

A - Ice Tea Store

結果:AC
Submission #1539280 - AtCoder Grand Contest 019 | AtCoder

アイスティーは1/4リットル・1/2リットル・1リットル・2リットルの4種類の値段が付いているが、購入するアイスティーはN(整数)リットルであるため、最も安く買うためには1/4リットル・1/2リットル・1リットルの中から複数種類を買う必要はない。よって1リットルの最安はmin(Q*4, H*2, S)であり、2リットルの単価のほうが安いケース、さらにNが奇数であるケースを考慮してアレする(適当)。

B - Reverse and Compare

結果:AC(5WA)
Submission #1544332 - AtCoder Grand Contest 019 | AtCoder

文字数をNとするとすべての文字がユニークならばN*(N-1)//2+1通りで、この中からダブりを引いていくのだが、どうすればいいか思いつかなかったのでシミュレートする関数を立てて色々文字列を食わせてみた。

def hoge(s):
    _set = set()
    add = _set.add
    add(s)
    l = len(s)
    for i in range(l, 0, -1):
        for j in range(l-i+1):
            s1 = s[:j]
            s2 = s[j:i+j][::-1]
            s3 = s[i+j:]
            add(s1+s2+s3)
    return len(_set)

print(hoge(s))

abcdefg
abcdeff
abcdeee
abcdddd

とか試したら各アルファベットにおけるダブリ文字数をniとするとni*(ni-1)//2分減ってたのがわかったのでそのように実装しました(思考停止)。

問題は1文字だけひっくり返す(=元の文字列そのままにする)ことができないと勘違いしていたため、2文字以上ひっくり返さないといけない=文字列によっては元の文字列が結果に入るケース(どっかでs[i] == s[i+1] or s[i] == s[i+2]が成り立つ場合かな?)と入らないケースがあると考え、不必要な場合分けを入れてWA生やしまくった。問題文を読み違えて大爆死したの久しぶりで反省しきり。

AtCoder Regular Contest 079 参戦記

o-o- 1355 -> 1395 (+40)

C - Cat Snuke and a Voyage

結果:AC
Submission #1463078 - AtCoder Regular Contest 079 | AtCoder

用意してあったダイクストラをそのままベタッと貼りました。完。

pythonheapqは二分ヒープのようなのでこれを使ったダイクストラ(E+V)*log2Vで大体6.6*10^6くらいで、こんなもんでもpythonだと時間が結構やばめなので怖い。

D - Decrease (Contestant ver.)

結果:わかんなかった

1 0 0 ← k = 0
2 0 0 ← k = 0
3 0 0 ← k = 1
6 0 0 ← k = 2
9 0 0 ← k = 5 ???

みたいに基本は数字を1個だけ動かしてなんとかしようとしたのでめちゃくちゃこんがらがった。逆順でシミュレートするなら足す数以外は全部引けばいいという発想が全く出てこなかった。

N=50決め打ちで、数列の初期状態を[0, 1, 2, ... 49]にして、K // 50(切り捨て)の数だけ数列の全ての数に加算して、K % 50回だけ「数列の最小値に50を足し他の数字を-1する」をシミュレートすればいい。←このシミュレートを50回繰り返すと結果的に数列の全ての数が1加算された状態になる。

Submission #1471485 - AtCoder Regular Contest 079 | AtCoder

E - Decrease (Judge ver.)

結果:AC
Submission #1466238 - AtCoder Regular Contest 079 | AtCoder

「数列の数aiNを超えていたらai // Nを他の数に加算しai = ai % Nにする」という二重ループをmax(a) < Nになるまで繰り返すシミュレーションで通ってしまった。計算量がよくわからなかったのでダメ元だったんだけど(そして解説読んでもよくわからん)。N=50で数列が全て10^16の場合、whileブロックは838回しかループしないみたい。Youtubeの解説では二分探索やってたけどそっちは絶対思いつかない……。

AtCoder Grand Contest 018 参戦記

o---- 1358 -> 1355 (-3)

A - Getting Difference

結果:AC(1WA)
Submission #1446363 - AtCoder Grand Contest 018 | AtCoder

問題文一通り読んでどういう問題なのか全く把握できなかったので辛かった。

入力例 2
3 5
6 9 3
出力例 2
IMPOSSIBLE
どれだけ操作を行っても、5 の書かれたボールを箱の中に入れることはできません。 よってこの例の答えは、IMPOSSIBLE になります。

この例がなければ全く解けなかったかも。要するにxの倍数のボールしかない場合は何回abs(n*x - m*x)してもxの倍数しか作れないので、K-max(A)xの倍数でなければIMPOSSIBLEだというわけ。ただしmin(A)xの倍数であるケースに注意(A = [6, 9, 12]の場合xは3)。要するに最大公約数を取れという問題。

B - Sports Festival

結果:ダメ

貪欲じゃないよなーと思ったら貪欲だった。計算量的にも余裕だった。700点だから何かしら知らないと解けない問題だよなーと思ったんだよ……!言い訳ですけど。

全てのスポーツが開催される前提で第一希望を見比べて、その中からスポーツを廃止して第二希望以降をリストから取ってくる……という考え方自体はあったんだけど、何を血迷ったのかどこかのリストが空になった場合にその時点での答えは最適なのか??みたいなことを考えてしまった。全員は全てのスポーツについて第M希望まで持つので、どこかのリストだけが空になることはなく全ての希望リストが同時に空になる(あたりまえ)。よって単に全員の第一希望から一番多く被っているスポーツを消してって次の希望リストから補充する、をちょうどM回繰り返せばいい。補充するときにすでに消したスポーツは捨てて補充し直すことだけ注意する。

Submission #1450906 - AtCoder Grand Contest 018 | AtCoder

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くらいになった!アドバイスありがとうございます🙇