AtCoder Beginner Contest 107 A・B問題と典型90問（4問目）

AtCoder Python

前書き

AtCoder Beginner Contest 107 A・B問題と典型90問（4問目）を解きました。

A問題

  • 難易度：灰
  • 時間：1分
N,i=map(int,input().split())
print(N-i+1)

B問題

  • 難易度：茶
  • 時間：15分

atcoder.jp

1≤H,W≤100なので、二重配列でもACできます。

重要視したのは以下の三点です。

  1. 入力値を取得
  2. 横一行全て"."の場合は省略する
  3. 縦一列の要素のうち一つでも"#"が存在する列は出力対象とする
H,W=map(int,input().split())
lis,lis_w=[],[0]*W

for h in range(H):
  inp = list(input())
  if "#" in inp: 
    for j in range(W):
      if inp[j]=="#":
        lis_w[j]=1
    lis.append(inp)
    
for l in lis:
  print(''.join([l[w] for w in range(W) if lis_w[w]==1]))

典型90問（4問目）

  • 難易度：C問題クラス
  • 時間：30分
  • 実行：Pypy3

問題Twitterリンク

アルゴリズムの流れとしては以下の通りです。

  1. 配列の各列・各行の合計値を保存
  2. 該当列の合計+該当行の合計-該当該当要素の値を計算

以下のアルゴリズムはPythonだとTLEですが、Pypy3だとACになります。
一般的にはPypy3の方がACになる確率が高いようです。

H,W=map(int,input().split())
_sumh,_sumw=[0]*H,[0]*W
_lis=[]

for h in range(H):
  lisw = list(map(int,input().split()))
  _sumh[h]=sum(lisw)
  _lis.append(lisw)
  for w in range(W):
    _sumw[w]+=lisw[w]

for hh in range(H):
  for ww in range(W):
    _lis[hh][ww]+=(_sumh[hh]+_sumw[ww]-_lis[hh][ww]*2)
  print(' '.join(list(map(str, _lis[hh]))))