pythonで競技プログラミング 覚え書き

pythonで競技プログラミングはじめました。atcoderでレーティング灰色です。まずは目指せ茶色です。PASTは初級でした。単純にコーディングして問題を解くことが達成感があって楽しいのでやっています。

このページは私の個人的な備忘録です。素人なので色々間違ってるかも。間違いに気づいた親切な方は教えていただけると助かります。

競技プログラミングとは

与えられた問題を制限時間内になるべく早く多く解くことを競う競技です。私はAtCoder社の運営する、AtCoderで競プロをやっています。問題に対する回答はオンラインで提出し、リアルタイムで正解、不正解が判定されます。

競技プログラミングと、業務としてのプログラミングの違いは、「F1ドライバー」と「トラック、タクシー、路線バスの運転手、または営業職の人が車を運転する場合」の2者の対比のようなものかな、と思っています。(私は業務としてのプログラミングの経験はありませんが。)

あるいはウェイトリフティングと総合格闘技と捉えている人もいる。これは秀逸な例えかも。

ガイダンス

ガイダンスはこの2記事が秀逸と思う。

AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~

https://qiita.com/drken/items/fd4e5e3630d0f5859067

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編:競プロを始めよう】

https://qiita.com/e869120/items/f1c6f98364d1443148b3

精進

過去問を解くなりして競技プログラミングのスキルアップを図ることをこの界隈では「精進する」と表現するようだ。精進するには「atcoder problems」のtraining機能が役にたつ。

https://kenkoooo.com/atcoder/#/training

使うにはGitHubのアカウントが必要。ない人は一緒に作ってしまおう。

標準入力

まずはこれを適切に使えるようにならないと話にならない。

文字1行

一番基本的なやつ。入力を文字列として受け取る。

S=input()

pythonの文字列はリストとして各要素にアクセスできるので便利。整数データでもあえて文字列として受け取って処理するのも時に有効。10進数の格桁に簡単にアクセスしたい時など。

整数1行

整数として受け取る場合は下記。

N=int(input())

上で出てきた「input()」で受け取ったものをint(整数型)に変換して変数にぶちこんでいるだけ。

1行に複数の整数

よくあるパターン。あまりにも頻出するので覚える気がなくてもすぐに覚えてしまう。

N,M=map(int,input().split())

1行に複数の文字列

あまり登場しない?

S,T=map(str,input().split())

出力

出力も入力の次に大事。print()で出力すればよい。

A=10
print(A)
#出力は 「10」

複数個ならべるならカンマで区切って書く。

A=10
B=5
C=1
print(A,B,C)
#出力は 「10 5 1」

文字でも一緒。

リストを出力する時、[’a’,’b’,’c’]じゃなくて「abc」のようにまとめて(結合して)出力したい時はjoin。たまにしか使わないので忘れがち。

A=['a','b','c']
print(A)
#出力は ['a','b','c']
print(''.join(A))
#出力は abc

10進数の格桁の求め方

10で割った余りが一番したの桁。10で割った商をさらに割って余りをどんどん求めていく。

Dict型の操作

それぞれの要素が何個ずつあるのか数え上げる時は、dict型を使うと良い。

ABC091 B Two Colors Card Game で使ったときの例。

https://atcoder.jp/contests/abc091/tasks/abc091_b

T=dict()
for i in range(M):
	tmp = input()
	if tmp in T:
		T[tmp]+=1
	else:
		T[tmp]=1

要素を一つ一つ読み込むときに、その要素が辞書の中にあれば、そのキーの値を+1、もしまだなければ、要素を作って値に1を入れる。ここらへんの基礎的な操作ができないと、何もできないケース多し。

辞書には順番の概念は無い。しかし「sorted」を使ってkeyもしくはvalueでソートできる。返ってくるのはdict型ではなくlist型が返ってくるので注意。

ABC081 Not so diverseなど。

https://atcoder.jp/contests/abc081/tasks/arc086_a

keyでソートする例(昇順)。

t=sorted(t.items())

keyでソート(降順)

t=sorted(t.items(),reverse=True)

valueでソート

t=sorted(t.items(),key=lambda x:x[1])

valueでソート(降順)

t=sorted(t.items(),key=lambda x:x[1],reverse=True)

値のスワップ

そのうち書く。

min,max

そのうち書く。

リストのcopy

ちゃんとcopyメソッドでコピーしないと、中身が連動してしまう。

https://techblog.recochoku.jp/5158

import copyしてから、copy.copy、copy.deepcopyなど。

アルゴリズム

最大公約数の求め方(ユークリッドの互除法)

最大公約数:ユークリッドの互除法 整数A,B間の最大公約数(Greatest Common Divisor : GCD)は「ユークリ...

素数の求め方(エラトステネスの篩(ふるい))

エラトステネスの篩 ある正の整数N以下の素数を高速で求めるアルゴリズムです。計算量はO(NloglogN)となります。 pyt...
スポンサーリンク
スポンサーリンク




スポンサーリンク




シェアする

  • このエントリーをはてなブックマークに追加

フォローする

スポンサーリンク
スポンサーリンク