PSM

プログラミング 初心者の メモ書き です

初めてAtCoder Beginner Contestで全完した話

競技プログラミングというものを初めて1ヶ月経ちました.
情報系の専攻とかでは全くなく,最初は「プログラミング?よくわかんないけど頭めちゃくちゃ良くないとできなさそう……」とひたすらビビりまくっていましたが
,徐々にその面白さにハマりつつあります.

さて,そんな私ですが,今回は競プロサイトの1つであるAtCoderでほぼ毎週行われているAtCoder Beginner Contest (ABC)で初めて全完することができました.しかも全問1発AC!

正直に言ってめちゃくちゃ嬉しかったので,浮かれて攻略日記みたいなのを書くことにしました.
(たぶん今回はたまたま簡単な問題が多かったのだとは思いますが,それでも嬉しいものは嬉しいです.)
自分が実際に考えた内容なので模範回答ではないかもしれませんが,悪しからず.

A問題

東西n本,南北m本の街路に囲まれた街区の数を求める問題.

それぞれから1引いて掛けたのを出力するだけ.

# K-City
n,m = list(map(int, input().split()))

print((n-1)*(m-1))

B問題

与えられる1単語を所定のルールによって略す問題.

pythonのstr型はリストとして扱えることを知っていれば簡単.
リストの最後尾の要素はlist[-1]で呼び出せる.

# i18n
s = input()

print(s[0]+ str(len(s)-2) +s[-1] )

C問題

ある数列が与えられたとき,それを並び替えることでどの連続する二数の積も4の倍数となるような数列を作れるか判定する問題.

まず,4の倍数を●とそれ以外の数を○で表してみたとき,
○●○●・・・●○●○
のように交互に並べられるならば,その数列は条件を満たす.
さらに○のうち「2の倍数であって4の倍数でない数」を▲で表し,「2の倍数でも4の倍数でもない数」を△と表す.
(注意:全ての数字は●,△,▲に重複なく分類できる)

▲×△は2の倍数でしかないが,▲×▲は4の倍数になる.もちろん▲×●は4の倍数である.
▲が偶数個あるならちょうど2つずつ隣同士ペアを作ることができるので,残りの△と●が交互に並べられるかを考えれば良いし,▲が奇数個あるなら△が一つ増えたと考えて交互に並べられるか考えれば良い.

● : 4で割ったあまりが 0
△ : 4で割ったあまりが 1 or 3
▲ : 4で割ったあまりが 2
なので,与えられた数列を4で割ったあまりの数列に変換して考える.

# 4-adjacent
N = int(input())
a = list(map(int, input().split())) 

b = [a[i]%4 for i in range(N)] #4で割ったあまり
if ( b.count(2)%2 + b.count(1) + b.count(3) > 1 + b.count(0) ):
    print("No")
else:
    print("Yes")

D問題

長方形のマス目を塗り分ける問題.

問題をよく読んで,ぐねぐねと折り返しながら蛇のようにマス目を塗っていけば良い,ということに気がつけば簡単.
かかった時間の大半はpythonでどう実装するかググるのに費やした.
(調べた内容:リストを高速にflattenする方法,リストを逆順にする方法,リストの出力時に半角スペースを挟む方法)

# Grid Coloring
H,W = list(map(int, input().split()))
N = int(input())
a = list(map(int, input().split()))
 
from itertools import chain
b = list(chain.from_iterable([[i+1]*a[i] for i in range(N)]))  #指定された数だけ色iを並べたリストをつくる
c = [b[i*W:(i+1)*W] if i%2==0 else b[i*W:(i+1)*W][::-1] for i in range(H)]  #リストをHずつで切る.奇数列の時はlist[::-1]の表記を使ってリストを逆順にする
 
for i in range(H):
    print(' '.join(map(str, c[i])))  #半角スペースを間に挟みながら出力する

結果

A問題 01:51 (01:51)
B問題 03:51 (02:00)
C問題 13:06 (09:15)
D問題 36:13 (23:07)