Atcoder灰色の為のアルゴリズムノート【3/3】

前回に引き続きAtcoder灰色から茶色になるために必要な知識をまとめたノートを公開します。今回は最終回です。

目次

  • はじめに
  • 標準入力の関数化
  • 少数の計算の誤差
  • 文字の扱い方
  • おわりに

はじめに

コンテストでは早く解くこともパフォーマンスに直球します。今回はA、B問題を早く解くために必要な知識について紹介したいと思います。

#1 -> TODO
#2 -> TODO
#3 -> 本記事

標準入力の関数化

標準入力から値を取得するとき、標準入力をするコードを記述しますが、毎回イチから書くのは手間なので関数にしましょう。私は以下のコードをコピペしています。20文字ぐらいタイプしていた標準入力が4文字ぐらいで書くことが出来るのでかなり快適になり便利です。

・ソースコード

#標準入力---------------------------------------------------------------------
import sys
sys.setrecursionlimit(10 ** 5 + 10000)
input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LIS(): return list(map(int, SI()))
def LA(f): return list(map(f, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return input().strip('\n')
def MS(): return input().split()
def LS(): return list(input().strip('\n'))
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def LMS(rows_number): return [MS() for _ in range(rows_number)]

・説明

  • int1(x) xから1を引く
  • II() 単体のint型を取得
  • MI() 複数のint型を取得
  • MI1() 複数のint型を取得し、それぞれ1を引く
  • LI()複数のint型を取得し、リストに格納する
  • LI()複数のint型を取得し、それぞれ1を引いてからリストに格納する
  • LLI(rows_number) rows_number行のそれぞれの行からint型の要素のリスト(空白区切り)を作成し、それをリストに格納する
  • SI()単体のstr型を取得
  • MS()複数のstr型を取得する
  • LS()単体のstr型を一文字づつ区切り、リストに格納する
  • LLS(rows_number)rows_number行のそれぞれの行からstr型の要素のリスト(一文字ずつ)を作成し、それをリストに格納する
  • LMS(rows_number)rows_number行のそれぞれの行からstr型の要素のリスト(空白区切り)を作成し、それをリストに格納する

・補足

事前に用意するコードのことをテンプレートといいます。エディタのスぺニック登録で標準入力を呼び出す人もいますが、こういうのを作成している人もいます。自分の使いやすいようにカスタマイズしてみてください。

標準入力以外のテンプレートでは以下のようなものが多くみられます。

INF = 10**18
MOD = 10**9+7
mod = 998244353
def YesNo(b): print("Yes") if b else print("No")
def YESNO(b): print("YES") if b else print("NO")

少数の計算の誤差

この問題でWAを出してコンテスト中でペナルティを食らってしまう人が多いです。初学者にとっては一番の罠といえるようなものなので非常に気を付けなければなりません。

・説明

コンピュータでは数字を2進数で扱っていますが、少数のなかには2進数で表せないものがあるので、少数同士の計算では誤差が生じてしまいます。

例えば 0.1 → 0.000110011…(2) のように、無限に続いてしまうものがあります。

誤差を生まない計算をするためには以下の手段があります。

  • 整数として計算し、その計算結果の適当な位置に小数点をつける。
    • 掛け算a×b=cをa*10^n×b*10^m = c ×10^(n+m)として計算をします。ただ、このままだとcを求める工程にて誤差が生まれてしまうので、文字列として扱います。
  • ライブラリを使う(比較的精密に計算するものであり、誤差がないことを保証するものではないことに注意してください)

まずは普通に計算したものです。これだと、計算誤差が生まれてしまっているのが分かると思います。

# 普通に計算をしたパターン
a = 0.1
b = 0.2
print(a+b)
# 0.30000000000000004
print(a*b)
# 0.020000000000000004

次に整数として計算したパターンです。今回は以下の問題を考えます。

A×B の小数点以下を切り捨て、結果を整数として出力してください。

C – Multiplication 3 (ABC169) (diff597)

・ソースコード

a,b = map(str,input().split())
a = a.replace(".","")
b = b.replace(".","")

ans = (int(a) * int(b)) // 100
print(ans)

・入力

198 1.10

・出力

217

・問題

B –  Alcoholic (ABC274) (diff274)

・補足

少数を扱う問題で厳密性を問う問題はあまり多くないですが、いざという時に対処できるように知識としてもっておいて損はないと思います。また、コンテスト中は順位表からペナルティ率を見ることによって多少の対策を行うことが出来ます。

文字の扱い方

A、B問題では文字を扱う問題も出題されます。数字と違い、少しめんどくさいので早くコーディングするためのコツを紹介します。

・説明

  • 0埋め : str(n).zfill(x)
  • 全部大文字に変換:str.upper()
  • 全部小文字に変換:str.lower()
  • 先頭のみ大文字に変換:str.capitalize()
  • 各単語の先頭のみ大文字に変換(タイトルケース):str.title()
  • 大文字と小文字を入れ替える:str.swapcase()
  • 文字 → ASCIIコード ord(s)
  • ASCIIコード → 文字 chr(x)
  • ASCII表
    • 65:A ~ 90:Z
    • 97:a ~ 122:z

文字を扱う問題は少ないので、自然と頭の中に入るようなことが少ないので、以上のような基礎的な知識は覚えた方がいいです。いちいちググるという手もありますが、それだと少し時間がかかってしまいます。

ときどき、A問題では「文字cが英小文字であるか」のような問題で英文字のリストが必要になるときがあります。その時はstringメソッドを使いましょう。

import string

print(list(string.ascii_lowercase))
# ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
print(list(string.ascii_uppercase))
# ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

おわりに

これで、全3回のAtcoder灰色の為のアルゴリズムノートを終えます。ここまで読んでいただきありがとうございました。茶色版の記事を書くかどうかは未定ですが、好評なら書こうと思います。
よきアルゴリズムライフを。