ABC237(AtCoder Beginner Contest 237) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
A - Not Overflow
問題文の通りNが-2^31以上かつ2^31未満かを確認します。
条件を満たすなら「Yes」そうでないならば｢No」を出力します。
「aのx乗」はa**xと書きます。
「以上」は「<=」
未満は「<」
です。
「Yes」「No」は文字列なので出力の際、"Yes","No"とダブルクオーテーションをつけてください。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
#入力の受け取り
N=int(input())
# -2^31以上2^31未満ならば
if(-2)**31<=N<2**31:
# 「Yes」 を出力
print("Yes")
#そうでないならば
else:
# 「No を出力」
print("No")
B - Matrix Transposition
上から1行目、左からj列目の要素をA[i][j]と書きます。
この問題は要するに
B[i][j]=A[j][i]となるように行列を作って出力せよ
という問題です。
まず入力を受け取ります。二次元配列を使います。
二次元配列は空のリストを作り、そこにさらにリストを入れていくことで作れます。
まずAという空のリストを作り､1行ずつ受け取ってAへ入れる、ということを繰り返します。
#空のリストを作る
A=[]
# H回
for i in range (H):
# 一行ずつリストとして受け取り
A_tmp=list(map(int,input().split()))
# Aへ入れる
A.append(A_tmp)
こうすることでAの上からi行目、左からj列目をA[i][j]と確認できます。
ただし、0インデックスとなるため、行列の左上はA[1][1]ではなくA[0][0]となることに注意してください。
続いてBを確認していきます。
BはまずWH(W行H列)の二次元配列を作ってしまい。そこに値を埋めていくという方法を取ります。
WHの二次元配列を作るには以下のように書きます。
# W*Hの二次元配列を作成
B=[[0]*H for i in range(W)]
初期値はすべて「0」になっていますが、これはどうせ更新するのでなんでもいいです。
あとはB[i][j]=A[j][i]と順に埋めて、最後にBを一行ずつ出力すれば終わりです。
Bの出力の際
print(B[行番号])
とすると[]つきで出力されますが、
print(*B[行番号])
とすると[]なしで出力できるので楽です。
【提出】
# 入力の受け取り
H,W=map(int,input().split())
#空のリストを作る
A=[]
# H回
for i in range (H):
# 一行ずつリストとして受け取り
A_tmp=list(map(int,input().split()))
# Aへ入れる
A.append(A_tmp)
# W*Hの二次元配列を作成
B=[[0]*H for i in range(W)]
# i=0~(W-1)
for i in range (W):
#j=0*(H-1)
for j in range (H):
#Bの値を更新
B[i][j]=A[j][i]
# i=0~(W-1)
for i in range (W):
# 一行ずつ出力
print(*B[i])
C - kasaka
回文であるなら先頭と後ろの「a」の個数は一致している必要があります。
後ろの「a」の個数を数える場合はiを一つずつ減らしながらS[i]を確認します。
iを一つずつ減らしていくには以下のようにfor文を書きます。
for(開始,(終了-1),減る量):
i=(Sの文字数-1)~0まで一つずつ減らしていく場合なら以下のようになります。
# i=(Sの文字数-1)~0 -1ずつ
for i in range(len(S)-1,-1,-1):
先頭の「a」の個数が後ろの「a」の個数より多ければ回文にすることはできません。
例:aaabbaa
よって「後ろの「a」の個数」<「先頭の「a」の個数」なら「No」です。
そうでないケース、すなわち「先頭の「a」の個数」≤「後ろの「a」の個数」場合、先頭に足りない「a」をつけ足して回文かどうかの判定をします。
回文かの判定は単純に1文字ずつ見ていくだけです。
pythonでは0インデックスになるため、i=0~(N-1)についてS[i]=S[(N-1)-i]となっていることが回文であることの条件です。
【提出】
# 入力の受け取り
S=input()
# 先頭にある"a"の数
a_front=0
# i=0~(Sの文字数-1)
for i in range(len(S)):
# i文字目が"a" なら
if S[i]=="a":
#カウント
a_front+=1
# そうでないなら
else:
# for を抜ける
break
# 後ろにある"a"の数
a_back=0
# i=(Sの文字数-1)~0 -1ずつ
for i in range(len(S)-1,-1,-1):
# i文字目が"a" なら
if S[i]=="a":
#カウント
a_back+=1
# そうでないなら
else:
# for を抜ける
break
# 「後ろの「a」の個数」<「先頭の「a」の個数」
if a_back<a_front:
# 「No」を出力
print("No")
# 終了
exit()
# 先頭に足りない個数分「a」を追加
S="a"*(a_back-a_front)+S
# Sの長さ
N=len(S)
# i=0~(N-1)
for i in range(N):
# 回文か判定
# 1文字目と(N-i-1)文字目が違うなら
if S[i]!=S[N-i-1]:
# 「No」を出力
print("No")
# 終了
exit()
# ここまで来たら回文
# 「Yes」を出力
print("Yes")
D - LR insertion
pythonはdeque(両端キュー)と呼ばれる機能を使えます。
これは先頭と末端への要素追加が0(1)でできるリストだと思えばいいです。
(通常のリストだと要素数Nの場合、先頭への要素追加がO(N)となります)
dequeがわからない人は以下を参照してください。
dequeについて
dequeはリストのようなものですが、先頭から要素を取り出す操作をO(1)で行うことができます。
(リストだとO(N)かかります)
インポート：from collections import deque
作成：変数名=deque()
先頭(左端)に要素追加【O(1)】：変数名.appendleft(要素)
末尾(右端)に要素追加【O(1)】：変数名.append(要素)
先頭(左端)から要素を取り出して削除【O(1)】：変数名.popleft()
末尾(右端)から要素を取り出して削除【O(1)】：変数名.pop()
【使用例】
# インポート：from collections import deque
from collections import deque
# 作成：変数名=deque()
que=deque()
# 先頭(左端)に要素追加【O(1)】：変数名.appendleft(要素)
que.appendleft(1)
# 末尾(右端)に要素追加【O(1)】：変数名.append(要素)
que.append(3)
# 先頭(左端)から要素を取り出して削除【O(1)】：変数名.popleft()
x=que.popleft()
# 末尾(右端)から要素を取り出して削除【O(1)】：変数名.pop()
y=que.pop
詳しく知りたい人は以下のページを見てください。
dequeなら両端への要素追加はO(1)で出来ますが、問題文の通り「0」から始めると両端でなく真ん中に要素を追加するケースでTLEします。
こういった指示に従って操作を行う系の問題では「逆から操作する」というのがよく使うテクニックになります。
出力例1(1 2 4 5 3 0)を眺めてみると、「5」から逆順で追加すれば
先頭に「4」(4 5)
末端に「3」(4 5 3)
先頭に「2」(2 4 5 3)
と先頭か末尾への要素追加のみで解けることがわかります。
よってSを逆順に確認して
「R」→先頭に追加
「L」→末端に追加
としていけばOKです。
先頭(左端)への追加はappendleftを使います。
【提出】
# 入力の受け取り
N=int(input())
S=input()
# deque のインポート
from collections import deque
# キューを用意
que=deque()
# Nを追加
que.append(N)
# i=(N-1)~0 -1ずつ
for i in range(N-1,-1,-1):
# Sのi文字目が「R｣
if S[i]=="R":
# 先頭(左端)へ「i」を追加
que.appendleft(i)
# そうでない場合(Sのi文字目が「L」)
else:
# 末端(右端)へ「i」を追加
que.append(i)
# 答えの出力
# ([]がいらない場合は先頭に「*」をつける)
print(*que)
【広告】
『AtCoder 凡人が『緑』になるための精選50問詳細解説』
AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
1～24問目まではサンプルとして無料公開しています
『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説』
ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。
サンプルを5問分公開しています
Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。
値段：300円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
『Excelでリバーシを作ろう!! マクロ、VBAを1から学ぶ』
Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！ 丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)
サンプルとして「準備」～「三目並べ」を無料公開しています。
【kindle】
【booth(pdf】