ABC173の参戦記です。
今回”も”AB2完でした。
C問題は解法の目途がたったにもかかわらず、実装でミスってコンテスト中に解けませんでした。
解説やいろいろな方のブログ、Quiitaも参考にさせてもらいつつ、解法の本質的な部分については間違っていないことが分かったので、翌日にコードを一から書いたらACしました。
本記事では、Python3での、ABC173 A-C問題のコードと、
C問題の二重のfor文の中でbit全探索がどう処理されているかについて、私が理解できるように可視化したコードがあります。
A – Payment
割り算の余りを利用しておつりを計算する問題。
ただし、お買い物の金額が1,000円の倍数の場合が例外ケースになるので、それを考慮する必要があります。
N=int(input())
n=N%1000
if n==0:
print(0)
else:
print(1000-n)私は、入力例2がなかったらWA出してたと思います。
B – Judge Status Summary
受け取った情報を集計する問題。
私は、dict型を利用しましたが、もっと簡単な、短い記述がいろいろあるようです。
Python3なら、collections のCounterや、とりあえずlistに入れておいて出力時にcountするとか。
いろいろと勉強になるな。
ちなみにx(英小文字のエックス)が、×(かける)になっていてWAになっている人がいたみたい。
私は出力例をコピペしたから大丈夫だったけど、もしかしたら危なかったかも・・・
今回私が提出したコードはこれです。
もっときれいな書き方ができるようになりたい・・・
N=int(input())
dic={}
dic['AC']=0
dic['WA']=0
dic['TLE']=0
dic['RE']=0
for i in range (N):
_=input()
dic[_]+=1
print('AC x {0}'.format(dic['AC']))
print('WA x {0}'.format(dic['WA']))
print('TLE x {0}'.format(dic['TLE']))
print('RE x {0}'.format(dic['RE']))それにしても、問題文でもTLEという文言が出てくるので、最近TLE恐怖症の私にはなかなかつらい問題でしたｗ
ELTも字面が似ているためにちょっとドキッとします。
C – H and V
bit全探索で条件に合うパターンの数を数える問題。
問題文は赤く塗りつぶすと書いていますが、黒じゃなければ何色でもよくて、黒の数を数える対象から外す。というところが分かったので、私は、行や列を削除する方針にしました。
削除するパターンがわかれば、そのパターンについてそれぞれ残っている黒い箇所を数えればOKですね。
削除するパターンについては、行と列でそれぞれ何通りあるかを、bit全探索を利用して試せば良さそうです。
bit全探索は私が競プロを始めてから初めて本格的にアルゴリズムの手法を学んだものなので少し思い入れがあります。(今回の問題解けなかったけど・・・)
ものすごく簡単に書くと、以下のようなコードです。
より、詳しい説明は、こちらのブログ(けんちょんの競プロ精進記録 – bit 全探索)などを参考にしてください。私はこの記事たぶん10回以上読みました。
それでもまだわからない部分がたくさんあります。
N=3
for i in range(2**N):
P=[]
for _ in range(N):
if i>>_ & 1 ==1:
P.append(1)
else:
P.append(0)
print(P)
# >>
'''
[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[1, 1, 0]
[0, 0, 1]
[1, 0, 1]
[0, 1, 1]
[1, 1, 1]
'''コンテスト当日の日中に精進している時、numpyを使って解いていたこと、ndarrayの表現が今回の問題のような場合に、見やそうと思ったこと、最終的な黒いマスの数え上げにnumpy.sum()が有効そうだなと思ったことなどにより、何を思ったかnumpyを利用しています。
白いマスは0に、黒いマスは1に変換して、二次元配列として扱っていきます。
まずは削除する行のパターンをbit全探索で求めて、削除する行のインデックスを取得して、最初に与えられた状態から削除します。
上記のfor文の中で、さらにbit全探索して、削除する列のインデックスを取得して、行が削除されている状態から、それぞれのパターンで列を削除していき、残った黒(1)の数を数えて、Kと一致していたら正しい組合わせとして認識する。
コンテスト当日は高さと幅を合わせて組合わせのパターンをとってしまって、削除する対象のコントロールがうまくできなかったのですが、翌日落ち着いて、高さを削除するパターンを求めて、その中で幅を削除するパターンを計算していったら無事ACできました。
import numpy as np
H,W,K=map(int,input().split())
b=[]
for i in range(H):
_=input()
temp=_.replace('#','1').replace('.','0')
b.append(list(map(int,temp)))
area=np.array(b)
ans=0
for h in range (2**H):
select_H=[] #削除する行の組合わせを取得
for i in range (H):
if (h>>i) & 1==1:
select_H.append(1)
else:
select_H.append(0)
sHarr=np.array(select_H)
delsHarr=np.where(sHarr==1) #削除する行のindexを取得
area_afterDelsH=np.delete(area,delsHarr,axis=0) #エリアから行を削除する。
# 以下、行が削除された各パターンについて、列を削除していく。
for w in range (2**W):
select_W=[] #削除する列の組合わせを取得
for j in range (W):
if (w>>j) &1 ==1:
select_W.append(1)
else:
select_W.append(0)
sWarr=np.array(select_W)
delsWarr=np.where(sWarr==1) #削除する列のindexを取得
area_afterDelsHsW=np.delete(area_afterDelsH,delsWarr,axis=1)
if np.sum(area_afterDelsHsW)==K:
ans+=1
print(ans)Appendix ～おまけ～
私が、二重のfor文(高さ幅)の中で、削除する対象を確認しながら理解できたコードです。
もしかすると、どこで何が実施されているかが見える役に立つかもしれません。立たないかもしれません。
import numpy as np
H,W,K=map(int,input().split())
b=[]
for i in range(H):
_=input()
temp=_.replace('#','1').replace('.','0')
b.append(list(map(int,temp)))
area=np.array(b)
# print(Arr)
ans=0
print('Start >'+'>>'*42)
for h in range (2**H):
select_H=[] #削除する行の組合わせを取得
print("")
print("# "*5 + 'pattern{0}'.format(h+1) + " # "*25)
print('↓ 基の状態')
print(area)
for i in range (H):
if (h>>i) & 1==1:
select_H.append(1)
else:
select_H.append(0)
sHarr=np.array(select_H)
delsHarr=np.where(sHarr==1) #削除する行のindexを取得
area_afterDelsH=np.delete(area,delsHarr,axis=0) #エリアから行を削除する。
# 以下、行が削除された各パターンについて、列を削除していく。
print(' {0} ← 今回削除する 行index'.format(delsHarr))
for w in range (2**W):
select_W=[] #削除する列の組合わせを取得
for j in range (W):
if (w>>j) &1 ==1:
select_W.append(1)
else:
select_W.append(0)
sWarr=np.array(select_W)
delsWarr=np.where(sWarr==1) #削除する列のindexを取得
area_afterDelsHsW=np.delete(area_afterDelsH,delsWarr,axis=1)
print('- '*10 + 'pattern{0}-{1}'.format(h+1,w+1)+ ' - '*21)
print('↓ 行削除後')
print('{0}'.format(area_afterDelsH))
# print(' '+". "*2 + 'pattern{0}-{1}'.format(h+1,w+1) + ". "*10)
# print(' ↓_今回削除する 列index')
print(' {0} ← 今回削除する 列index'.format(delsWarr))
# print('削除行：{0}、削除列{1}'.format(delsHarr,delsWarr))
print('↓ 列も削除後')
print('{0}'.format(area_afterDelsHsW))
print('1"がある個数は、{0}個。 よって、ans + = {1}'.format(np.sum(area_afterDelsHsW),np.sum(area_afterDelsHsW)==K))
print("")
if np.sum(area_afterDelsHsW)==K:
ans+=1
print('')
print('...')
print("最終的な答えは、{0}".format(ans))
print('<<'*43 + ' enD')
# print(ans)今回の入力例1で実施した結果はこちら。
# >>
'''
Start >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
# # # # # pattern1 # # # # # # # # # # # # # # # # # # # # # # # # #
↓_基の状態
[[0 0 1]
[1 1 1]]
(array([], dtype=int64),) ← 今回削除する 行index
- - - - - - - - - - pattern1-1 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]
[1 1 1]]
(array([], dtype=int64),) ← 今回削除する 列index
↓_列も削除後
[[0 0 1]
[1 1 1]]
1"がある個数は、4個。 よって、ans + = False
- - - - - - - - - - pattern1-2 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]
[1 1 1]]
(array([0]),) ← 今回削除する 列index
↓_列も削除後
[[0 1]
[1 1]]
1"がある個数は、3個。 よって、ans + = False
- - - - - - - - - - pattern1-3 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]
[1 1 1]]
(array([1]),) ← 今回削除する 列index
↓_列も削除後
[[0 1]
[1 1]]
1"がある個数は、3個。 よって、ans + = False
- - - - - - - - - - pattern1-4 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]
[1 1 1]]
(array([0, 1]),) ← 今回削除する 列index
↓_列も削除後
[[1]
[1]]
1"がある個数は、2個。 よって、ans + = True
- - - - - - - - - - pattern1-5 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]
[1 1 1]]
(array([2]),) ← 今回削除する 列index
↓_列も削除後
[[0 0]
[1 1]]
1"がある個数は、2個。 よって、ans + = True
- - - - - - - - - - pattern1-6 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]
[1 1 1]]
(array([0, 2]),) ← 今回削除する 列index
↓_列も削除後
[[0]
[1]]
1"がある個数は、1個。 よって、ans + = False
- - - - - - - - - - pattern1-7 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]
[1 1 1]]
(array([1, 2]),) ← 今回削除する 列index
↓_列も削除後
[[0]
[1]]
1"がある個数は、1個。 よって、ans + = False
- - - - - - - - - - pattern1-8 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]
[1 1 1]]
(array([0, 1, 2]),) ← 今回削除する 列index
↓_列も削除後
[]
1"がある個数は、0個。 よって、ans + = False
# # # # # pattern2 # # # # # # # # # # # # # # # # # # # # # # # # #
↓_基の状態
[[0 0 1]
[1 1 1]]
(array([0]),) ← 今回削除する 行index
- - - - - - - - - - pattern2-1 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[1 1 1]]
(array([], dtype=int64),) ← 今回削除する 列index
↓_列も削除後
[[1 1 1]]
1"がある個数は、3個。 よって、ans + = False
- - - - - - - - - - pattern2-2 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[1 1 1]]
(array([0]),) ← 今回削除する 列index
↓_列も削除後
[[1 1]]
1"がある個数は、2個。 よって、ans + = True
- - - - - - - - - - pattern2-3 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[1 1 1]]
(array([1]),) ← 今回削除する 列index
↓_列も削除後
[[1 1]]
1"がある個数は、2個。 よって、ans + = True
- - - - - - - - - - pattern2-4 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[1 1 1]]
(array([0, 1]),) ← 今回削除する 列index
↓_列も削除後
[[1]]
1"がある個数は、1個。 よって、ans + = False
- - - - - - - - - - pattern2-5 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[1 1 1]]
(array([2]),) ← 今回削除する 列index
↓_列も削除後
[[1 1]]
1"がある個数は、2個。 よって、ans + = True
- - - - - - - - - - pattern2-6 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[1 1 1]]
(array([0, 2]),) ← 今回削除する 列index
↓_列も削除後
[[1]]
1"がある個数は、1個。 よって、ans + = False
- - - - - - - - - - pattern2-7 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[1 1 1]]
(array([1, 2]),) ← 今回削除する 列index
↓_列も削除後
[[1]]
1"がある個数は、1個。 よって、ans + = False
- - - - - - - - - - pattern2-8 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[1 1 1]]
(array([0, 1, 2]),) ← 今回削除する 列index
↓_列も削除後
[]
1"がある個数は、0個。 よって、ans + = False
# # # # # pattern3 # # # # # # # # # # # # # # # # # # # # # # # # #
↓_基の状態
[[0 0 1]
[1 1 1]]
(array([1]),) ← 今回削除する 行index
- - - - - - - - - - pattern3-1 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]]
(array([], dtype=int64),) ← 今回削除する 列index
↓_列も削除後
[[0 0 1]]
1"がある個数は、1個。 よって、ans + = False
- - - - - - - - - - pattern3-2 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]]
(array([0]),) ← 今回削除する 列index
↓_列も削除後
[[0 1]]
1"がある個数は、1個。 よって、ans + = False
- - - - - - - - - - pattern3-3 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]]
(array([1]),) ← 今回削除する 列index
↓_列も削除後
[[0 1]]
1"がある個数は、1個。 よって、ans + = False
- - - - - - - - - - pattern3-4 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]]
(array([0, 1]),) ← 今回削除する 列index
↓_列も削除後
[[1]]
1"がある個数は、1個。 よって、ans + = False
- - - - - - - - - - pattern3-5 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]]
(array([2]),) ← 今回削除する 列index
↓_列も削除後
[[0 0]]
1"がある個数は、0個。 よって、ans + = False
- - - - - - - - - - pattern3-6 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]]
(array([0, 2]),) ← 今回削除する 列index
↓_列も削除後
[[0]]
1"がある個数は、0個。 よって、ans + = False
- - - - - - - - - - pattern3-7 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]]
(array([1, 2]),) ← 今回削除する 列index
↓_列も削除後
[[0]]
1"がある個数は、0個。 よって、ans + = False
- - - - - - - - - - pattern3-8 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[[0 0 1]]
(array([0, 1, 2]),) ← 今回削除する 列index
↓_列も削除後
[]
1"がある個数は、0個。 よって、ans + = False
# # # # # pattern4 # # # # # # # # # # # # # # # # # # # # # # # # #
↓_基の状態
[[0 0 1]
[1 1 1]]
(array([0, 1]),) ← 今回削除する 行index
- - - - - - - - - - pattern4-1 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[]
(array([], dtype=int64),) ← 今回削除する 列index
↓_列も削除後
[]
1"がある個数は、0個。 よって、ans + = False
- - - - - - - - - - pattern4-2 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[]
(array([0]),) ← 今回削除する 列index
↓_列も削除後
[]
1"がある個数は、0個。 よって、ans + = False
- - - - - - - - - - pattern4-3 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[]
(array([1]),) ← 今回削除する 列index
↓_列も削除後
[]
1"がある個数は、0個。 よって、ans + = False
- - - - - - - - - - pattern4-4 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[]
(array([0, 1]),) ← 今回削除する 列index
↓_列も削除後
[]
1"がある個数は、0個。 よって、ans + = False
- - - - - - - - - - pattern4-5 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[]
(array([2]),) ← 今回削除する 列index
↓_列も削除後
[]
1"がある個数は、0個。 よって、ans + = False
- - - - - - - - - - pattern4-6 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[]
(array([0, 2]),) ← 今回削除する 列index
↓_列も削除後
[]
1"がある個数は、0個。 よって、ans + = False
- - - - - - - - - - pattern4-7 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[]
(array([1, 2]),) ← 今回削除する 列index
↓_列も削除後
[]
1"がある個数は、0個。 よって、ans + = False
- - - - - - - - - - pattern4-8 - - - - - - - - - - - - - - - - - - - - -
↓_行削除後
[]
(array([0, 1, 2]),) ← 今回削除する 列index
↓_列も削除後
[]
1"がある個数は、0個。 よって、ans + = False
...
最終的な答えは、5
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< enD
'''
コメント