ABC 271のA,B,C,D,E問題を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。
この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。
また、問題の難易度を表す指標を Atcoder Problems から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。
質問やご指摘はこちらまで
Twitter : Waaa1471
作者プロフィール
Atcoder ：緑 855
20221216 現在
目次
はじめに
A.484558
B.Maintain Multiple Sequences
C.Manga
D.Flip and Adjust
はじめに
特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的考察が必要になり始めます。
しかし、公式解説ではこの部分の解説があっさりしすぎていて競技プログラミング(Atcoder)を始めたばかりの人にはわかりにくい、難しいと感じるのではないでしょうか。
またC++がわからないと、コードの書き方を勉強することが難しいです。一応、参加者全員のコードを見ること自体は可能ですが、提出コードは必ずしも教育的ではありません(ここで紹介する記事も本番で提出したものとは全く異なります)。そんなものから初学者が解説もなしになにか得ることはとても難しいと思います。実際適当に何人かのコードをみたものの、意味がわからずに終わった経験があるのではないでしょうか。
この記事がそんな方々の勉強の助けになればよいなと思っています。
A.484558
難易度 : 灰色 28
考察
知識問題です。知らなくても調べて正解しましょう。ここでは2通りの解答方法を掲載します。
➀ f-strings で2桁の大文字16進数を得る
pythonでは整数変数を与えて文字列化する場合、f-strings が便利です。
この問題で要求されている、16進数化、2桁表示 がどちらもオプション(書式指定)として存在するので、一撃で答えが求まります。
なお、"X"とすれば大文字の16進数が得られますが、"x"では小文字になるので気を付けましょう
➁ hex()[2:] で16進数の文字列を得る
hex() 関数に整数を与えると頭に 0x がついた16進数の文字列を得ることができます。
必要な部分だけスライスして取り出し、最後に upper() 関数で文字列を大文字化すれば答えが求まります。
コード
pypy3
➀ f-strings で2桁の大文字16進数をで得る
N=int(input())
# 02 は2桁になるまでゼロ埋め
# X は大文字16進数表示
print(f"{N:02X}")
➁ hex()[2:] で16進数の文字列を得る
N=int(input())
# 16進数の文字列を得る
# upper()で全ての文字列を大文字に変換
ans=hex(N)[2:].upper()
# 2桁に調整
if len(ans)<2:
ans="0"+ans
print(ans)
補足
-
f-strings
Pythonのf文字列（フォーマット済み文字列リテラル）の使い方
まずは、基本的な使い方をマスターすれば十分です。必要に応じて書式指定も覚えていきましょう。ゼロ埋め, 進数変換 を使いこなせればそれだけで正解できる A,B 問題もたくさんあります。 -
進数変換
Pythonで2進数、8進数、16進数の数値・文字列を相互に変換
16進数だけでなく、2進数、8進数も組み込み関数によって変換が可能です。 -
大文字 小文字操作
Pythonで大文字・小文字を操作する文字列メソッド一覧
大文字小文字変換、判定方法がまとめられています。
B.Maintain Multiple Sequences
難易度 : 灰色 97
考察
少し問題文が長いですが、「 入力、出力が適切に行えるか 」「 基本的なリストの操作ができるか」問われているだけです。
まず、数列を受け取りましょう。N個の数列を管理するためには、二次元リストが適切です。一つずつ入力から数列を受け取って、二次元リストへ append() 関数で格納していきましょう。
入力は、長さの後に数列が続いた形をしています。このような形式では、アスタリスク * を使ったアンパック を使うことで、数列を数列(リスト)としてそのまま受け取ることができます。
N,Q=[int(nq) for nq in input().split()]
# 二次元リスト Aで N個の数列を管理
A=[]
for _ in range(N):
l,*a = [int(la) for la in input().split()]
A.append(a)
なお、長さの情報はこの問題では必要ないので記憶しないことにします。
あとは、Q個のクエリに従って、目的のリストの目的の場所にある要素を Q行で出力するだけです。
python のリストが 0始まりのindex番号であるのに対して、問題の設定では数列の番号は 1始まりで、格納されている項も 1始まりです。このズレを調整しながら、クエリごとに出力していきましょう。
コード
pypy3
N,Q=[int(nq) for nq in input().split()]
# 二次元リスト Aで N個の数列を管理
A=[]
for _ in range(N):
l,*a = [int(la) for la in input().split()]
A.append(a)
for _ in range(Q):
s,t=[int(st) for st in input().split()]
print(A[s-1][t-1])
補足
-
出力形式
初心者向けAtcoder標準入力セット(Python)
様々な入力形式に対応しています。問題を解いていく中で、わからない形式に出会うたびに調べましょう。 -
出力形式
わかばめにっき
出力形式も入力型式と同じで、都度調べていくことで頻出なものは覚えていきます。 -
リストのアンパック
Pythonでタプルやリストをアンパック（複数の変数に展開して代入）
Pythonで関数の引数にリスト、タプル、辞書を展開して渡す
リストとして一度に受け取る場合に加えて、リストから関数へ一度に引数を与える場合にアンパックを利用します。
頻出なのは、空白区切り出力です。
C.Manga
難易度 : 緑色 842
考察
問題文の書き方によって、自然とシミレーションチックに、1巻ずつ読めるか判定していく処理を考えた(考えさせられた)方が多いのではないでしょうか。
まずはじめに、この考えでACするための考察を行います。
その後、別解をいくつか紹介します。
素直にシミレーション
サンプル 1を例にすると図のようになります
できるだけ多く読むためには、1巻から順に読み、読むことができないものを売るべきです。
図を例にすると、3巻を読むために末尾の 7巻、271巻の2冊を売るべきだということです。
そのため、持っている漫画の巻数を保存するためのテーブルは、前からも後ろからも操作できること が望ましいです。
リストは最も一般的なテーブルですが、前からの操作を行うことは得意ではありません。そこで deque で管理したいと思います。
これでテーブルの先頭を調べ、目的の巻数に一致すればそれを取り出し、一致しなければ末尾から 2要素取り出す操作ができます。つまり、目的の巻数を持っていれば売り、なければ不要な 2冊を売るシミレーションを行うことができるようになりました。
この操作をテーブルからデータが存在しなくなるまで繰り返せば、最大値を求めることができそうです。
シミレーションのイメージは図の通りです。
ただし、テーブルの先頭に読みたい目的の巻が、末尾に不要な巻がなければシミレーションは破綻してしまいます。
素直に考えると読むことができないものとは、巻数が他のものより高いものなので、巻数を昇順に並び替えてテーブルに格納すれば良さそうです。
しかしながら、このような実装ではACすることができません。
from collections import deque
N=int(input())
A=sorted([int(a) for a in input().split()])
AA=deque(A)
# 何巻まで読んだかを管理する変数
now=0
# テーブルの残数を管理するための変数
rem=N
while rem>0:
# 目的の巻を持っている場合
if AA[0]==now+1:
AA.popleft()
rem-=1
now+=1
continue
# 目的の巻を持っていない場合
else:
# まだ2冊以上あれば一番後ろの2冊を売って読む
if rem>=2:
AA.pop()
AA.pop()
rem-=2
now+=1
# 1冊しかなければ残数を0にしてループを終わらせる
else:
rem-=1
print(now)
適切な順番
図のような例で、この方法では明らかに最適化を行えていません。
将来読みたい巻を一時的に売って、それを買い戻す行為が発生してしまっていることが原因です。
つまり、巻数を昇順に並び替えただけではシミレーションを成立させるための適切な順番にできない ということです。
では、真の意味で順番通りににデータを格納することを目指します。
より高い巻数のものよりも、重複しているものの方が売る優先度が高いことがわかったので、昇順にデータを 重複なし で格納し、その後残っているデータを入れれば良いです。
ただし実装では図のように末尾に残った要素を入れる代わりに、適当な巨大数を入れることにします。どうせ売る(使わない)値なので真面目に入れなおす必要がないからです。
コード
pypy3
from collections import deque
N=int(input())
A=[int(a) for a in input().split()]
# 重複のない部分を得る
SA=set(A)
# 最大化できる順番でテーブルに格納
AA=deque(sorted(SA)+[10**10 for _ in range(N-len(SA))])
# 何巻まで読んだかを管理する変数
now=0
# テーブルの残数を管理するための変数
rem=N
while rem>0:
# 目的の巻を持っている場合
if AA[0]==now+1:
AA.popleft()
rem-=1
now+=1
continue
# 目的の巻を持っていない場合
else:
# まだ2冊以上あれば一番後ろの2冊を売って読む
if rem>=2:
AA.pop()
AA.pop()
rem-=2
now+=1
# 1冊しかなければ残数を0にしてループを終わらせる
else:
rem-=1
print(now)
別解
問題文の雰囲気に飲み込まれてシミレーションしてしまいましたが、実は残数変数を更新するだけで十分です。
なお、目的の巻を持っているか調べる処理を O(1) で行うために持っている漫画全体を集合で管理します。
コード
pypy3
N=int(input())
A=[int(a) for a in input().split()]
AA=set(A)
now=0
rem=N
while rem>0:
if now+1 in AA:
now+=1
rem-=1
else:
if rem>=2:
now+=1
rem-=2
else:
rem-=1
print(now)
別解2
W巻目まで最大で読めるとします。これは言い換えると、1～ W 巻 すべてを読むことができ、W+1巻以降は読むことができないということです。
この W巻を境界にした単調性 に注目すると、二分探索でこの問題をとくことができそうです。
図のように読める範囲と読めない範囲を境界に向かって狭めていくイメージで探索します。
中間地点である X巻目が読めるかどうかは、X巻目まで各巻ごとに1冊だけ残してそれ以外全部売った場合に、X巻目を読むことができるか で判定できます。
この判定を行うためには、X巻目までに何巻持っているか調べなくてはいけません。
素直に持っている漫画を前から探索する方法では、判定の度に$O(N)$ で調べることになるので、計算量は全体で $O(Nlog10^9)$ となってしまいます。
この問題は制約が緩いのでこれでも十分高速ですが、制約次第では間に合わない問題もあると思います。
そこで、ここでは 累積和 を用いて持っている巻数を管理することにします。これによって、X巻目までに何巻あるのか $O(1)$ で求められるようになります。つまり、判定処理が $O(1)$ となって二分探索全体の計算量が $ O(log10^9)$ にまで改善されることになります。
実装では、N+1巻以降の情報は累積和で管理しないようにしています。メモリの問題から、10^9 のサイズのリストを作成することができないためです。どうせ、N+1巻目以降は読めないので、全く問題ありません。
コード
pypy3
import itertools
N=int(input())
A=[int(a) for a in input().split()]
AA=set(A)
X=[0 for _ in range(N+2)]
for a in AA:
if a<=N:
X[a+1]+=1
# 累積和で、その巻の前に何巻あるか管理する
X=list(itertools.accumulate(X))
ok=0
ng=N+1
while ng-ok!=1:
mid=(ok+ng)//2
# mid巻目まで各巻ごとに1冊だけ残してそれ以外全部売っても、1～mid巻を読めなければ mid巻は読めない
if (N-X[mid+1])//2+X[mid+1]<mid:
ng=mid
else:
ok=mid
print(ok)
補足
-
deque
Pythonのdequeでキュー、スタック、デック（両端キュー）を扱う
deque の使い方を勉強できます。他の問題(尺取り法など)でも使う基本的なデータ構造なので絶対覚えましょう。 -
計算量 ～ リスト検索 vs 集合検索 ～
リストで管理するか、集合で管理するかで検索時の計算量が異なります。リストはO(要素数)で集合はO(1)です。
参考
Pythonistaなら知っておきたい計算量のはなし
Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由 -
二分探索
二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜
二分探索を勉強するのにとても参考になります
練習問題
アルゴ式に例題がいくつかあります
D.Flip and Adjust
難易度 : 緑色 886
考察
素直に N枚のカードの置き方を全部調べられれば うれしいですが、残念ながらこれはできません。
例えば $N=100$ の場合、$2^{100} \ ≒\ 10^{30} $ 通りの置き方があるからです。
よくわからないので、簡単な例でカードの置き方とその総和がどのよう遷移するか観察してみます。
すると例えば、$a_1 = 4, b_1 = 5, a_2 = 3, b_2 = 4$ の場合を考えると図のようになります。
この問題では条件を満たす置き方の一例だけ覚えておけば良いので、図のように 同じ枚数で総和が一致している置き方はどれか一つさえ管理できていれば十分である ことがわかりました。 (以降、どんな置き方をしても総和は全て等しいから)
このように管理すべき情報を取捨選択することで、計算量の問題を改善できたかもしれません。
ここまで得た情報を整理すると、
- 前から何枚目か
- 総和の値
- カードの置き方
これらの情報で状態を定義することで、状態の遷移に忠実に、必要な全ての状態を更新させることができそうです。
状態の遷移は 動的計画法 (DP) で行うことが頻出です。実験によってカードの枚数と総和で置き方を決められることがわかったので、1 ～ 2 の情報で 3 を管理すると考えると、2次元 dpテーブル (リスト) を作成することになりそうです。必要なすべての状態を管理するためには、テーブルのサイズは $N ×$ 総和の最大値 (max(a,b) × N) である必要があります。
ここで、各状態から次のカードを表で置くか、裏で置くかで2通りの遷移が生じることを考えると、計算量は最高でも $O(10^6)$ 程度なので十分高速です。
問題を解くことができる方針が定まったので、あとはどのように置き方を求めるか考えます。
まず、問題の出力要求に従って、置き方は文字列で管理することにします。
各操作でその文字列の末尾にカードの表裏を表す文字列を追加して状態を更新していけば、最終的に N枚目の総和 Sの位置に目的の置き方が格納されることになります。
ただし、初期値として与えた文字列が先頭に含まれているので、これを取り除いて出力する必要があります。
コード
pypy3
N,S=[int(ns) for ns in input().split()]
dp=[["" for _ in range(S+1)] for _ in range(N+1)]
# スタート位置を初期化
dp[0][0]="S"
for i in range(N):
a,b=[int(ab) for ab in input().split()]
for j in range(S+1):
if dp[i][j]:
#表
if j+a<=S:
dp[i+1][j+a]=dp[i][j]+"H"
# 裏
if j+b<=S:
dp[i+1][j+b]=dp[i][j]+"T"
if dp[-1][-1]:
print("Yes")
# 先頭をスライスで取り除く
print(dp[-1][-1][1:])
else:
print("No")
補足
- 動的計画法 (DP)
アルゴ式
動的計画法がわからないという方は、教科書で理解し、1～2章で練習しましょう。
終わり
また見てくれよな!