- 投稿日：2019-02-26T23:57:34+09:00
経験2年目の私が「まぁ、最初だからね」と言われるまでに潰して置いてよかったこと集
はじめに
前回の投稿、https://qiita.com/mamoru09230937/items/d5ed006ab0b9e5fae5ca
の逆バージョン。ポジティブにやっておいてよかったなと思えることをいくつか紹介します。社内政治編
・案件にアサインする担当営業と仲良くする。
一見、技術には何も関係ないように思えますが、これをしておくことにより、
現場でもめ事があったとき助けてくれる確率が上がります。
ほかにも、仲良くなる過程でSEに必須（と私は思っている）
コミュニケーションスキルとビジネスマナーが学べます。
・面談時に稼働や燃えっぷりを聞いておく。
こちらは一番大切なことかもしれません。聞いておくことで
「こちらも案件を選べますよ」という姿勢を見せることができ、黒い現場を避けやすくなります。
（時々を見てですが）技術編
・得意言語の資格を1つ取得しておく
資格は不要派、必要派で意見が分かれますが個人的には対外的にアピールできる手段として
有効な場合が多かったです。
私の持っている資格はJavaSE8 Silverのみですが、
それでも「Silverもってんだ」とか話のタネになりました。・SQLの基本文法
4大命令（SELECT,UPDATE,DELETE,INSERT）とサブクエリ、内部結合と外部結合がわかっていれば
最初のうちは（アサインされた案件にもよりますが）楽勝でしょう。個人的にはJavaやPHP等の
メインの実装に使用する言語よりも使う事が多かったです。・見積時間を盛る技術
多くの場合、作業開始前に「どれくらいでできそう？」と聞かれることがあると思います。
サーバが起動しない、競合が発生してしまった等を考えて、想定よりも
2時間くらい多く報告しておきましょう。おわりに
今回書いたのは一例であり、必ずしもすべての人に当てはまるわけではありませんが、何かの参考になればと思います。
コメント等あればお待ちしております。
- 投稿日：2019-02-26T23:54:55+09:00
もうそれtrueなんだから比較しないでくれ頼むから
if文って？
世の中には様々な言語がありますが、どの言語にも大抵備わっている構文、「if文」。
「if」と記載した後ろに条件を書くことで、その条件を満たした時のみ実行させる処理を記載できる、プログラミングといったらコレだよコレって感じのアレです。if文が成立する条件とは
上で「どの言語にも大抵備わっている」と書きましたが、それが成立する条件は言語ごとに異なります。
ざっくり分けても以下のパターンがあり得ます。
- 条件がtrueになった時
- 条件がその言語でtrueと等価であるとされる値になった時
- 条件が特定の値以外となった時
- 条件がnullやnilといった空ではない時
世の中の「ほげほげ入門」や「サルでもわかるふがふが」みたいな本やページにはtrue/falseのパターンしか載っていないことも多々ありますが、ちゃんとした仕様は言語によって異なるのでお気をつけて。
(といってもtrue/falseを覚えてれば書けますが)「true == trueやめてもらえます？」問題
初めて聞いたって？そら今作ったからね。
なんの話をしたいかというと、プロジェクトのコードをチェックアウトしてザーッと眺めた時に他の人が書いたであろう「それ比較前にtrueですからぁ〜！残念ッ！」
なコードで見てぐんにゃりしてしまい、まだ午後一だというのに元よりクソみたいなプロジェクトのせいでほんの5g程度しかない仕事のやる気が雲散霧消する事態を避けるべく、ついでに言ってしまえばさも言語に詳しい風を装ってチームに情報共有し自身の成功体験とチームからの信頼を勝ち取ろうという極めて前向きなディスりをしていこうという話です。(ここまで一呼吸で)
先に述べた通り、言語によって異なるのでここから先はお使いの言語で調べてみてください。
今回はmatlabというググラビリティ皆無の言語でやっていきます。if文の 仕 様 を確認 し よ う (たのめーる的ギャグ)
どこで確認するか、公式リファレンスだよ。それ以外信じちゃダメ、ゼッタイ。
説明のところを読んでみると、
if expression, statements, end は、式を評価し、式が真 (true) であるときに一連のステートメントを実行します。
ふむふむ、「true」で実行するのは他の言語と変わりませんね。
ただ、その後ろに気になることが書いてありますね。結果が空でなく、非ゼロの要素 (論理値または実数値) のみが含まれる場合に、式は true になります。それ以外の場合は、false です。
これを知っているか否かでif文の組み方が変わってしまいます。
例えば、文字列中に特定の文字列が含まれている場合を想定してください。(ていうかその状況でこの記事思いついたんだけど)
以下では「hogehoge」という文字配列から「eho」を探し、見つかったら開始インデックスを、見つからなかったら空配列を返してくることを想定しています。if strfind('hogehoge', 'eho') ~= 0 % ステキなサムシング………………………………………………カモン！ endnot equalで比較してるので正しそうですが、if文の仕様に照らし合わせると、以下で十分な訳です。
if strfind('hogehoge', 'eho') % 話は変わるけど、サトームセンもうないんだよね end言語仕様がわかってるとコード量が少なくて済むので、知ってる構文も調べてみてはいかがでしょうか。
(そして暇な時間を潰しましょう)文体がぶっ飛んでるけど今日どしたの？
にほんしゅはおいしい。
- 投稿日：2019-02-26T18:22:38+09:00
AtCoderの問題を分類しました
はじめに
2019年1月から AtCoder を始めました。問題の復習と自分の技術力を分析するために、問題を解いて得られた知見をメモとして残しています。周りの方から「知見を共有して欲しい」「公開することでコードレビューされて、技術力がより高まるよ」などのアドバイスを頂いたため、本記事を執筆する運びとなりました。
これまでの取り組みは下記ブログに記載しています。参考のためにリンクを記載しますが、本記事とは論点が異なるため、読み飛ばして頂いて構いません。
本記事について
記事の構成
本記事では分類観点を定義し、分類観点ごとに問題を分類します。各分類観点では、サンプルコードと解答例を記載しています。サンプルコードと解答例の定義は下記の通りです。
- サンプルコード：問題から得られた知見と検証によって得られた知見を整理したコード
- 解答例：提出したACのコード（一部、TLEのコードがあります。その場合は、「解答例(TLE)」と記載しています。）
実行環境
サンプルコードは下記環境で動作することを確認しています。
$ python --version Python 3.6.4解答例はAtCoderの下記言語でACになることを確認しています。
Python3 (3.4.3)分類観点の定義
分類観点の定義は下記の通りです。1つの問題から複数の観点で分類できる問題は、複数の観点に分類します。
- 実装観点：実装方式を知っていれば解ける問題
- 処理観点：処理方式を知っていれば解ける問題
- 数学観点：数学的知見を知っていれば解ける問題
- アルゴリズム観点：アルゴリズムを知っていれば解ける問題
- 計算量観点：計算量を工夫すれば解ける問題
分類する問題の範囲
分類する問題の範囲は下記の通りです。ABC-C問題とARC-A問題は一部問題が同じです。同じ問題の場合、ABC-C問題として扱います。
- ABC‐A問題（ABC001 - ABC119）
- ABC‐B問題（ABC001 - ABC119）
- ABC‐C問題（ABC001 - ABC119）
- ARC‐A問題（ARC001 - ABC103）
分類する対象の問題
本記事では、上記分類範囲で示したすべての問題が記載されているわけではありません。私が上記分類観点で知見が得られた問題のみを記載しています。そのため、参考として私がAtCoderを始めた頃の知識・能力を示します。
- コーディングができる
- 四則演算
- 簡易な if-else文 / for文 / while文
- コーディングができない
- 入出力処理
- 三項演算
- bit演算 / bool演算
- リスト処理 / タプル処理 / 辞書処理 / 集合処理
- 正規表現
- 各アルゴリズム
- 計算量を工夫したコード
- AtCoderの問題解答レベル
- ABC-A問題が5割解ける
- ABC-B問題が3割解ける
- ABC-C問題は全く解けない
本記事の対象者
下記のような方に向けた記事を想定しています。
- AtCoderを始めようとしている方（使用言語の候補としてPython3がある方）
- AtCoderをPython3以外でやっている方（使用言語をPython3にしたい方）
- Python3のコードバリデーションを参考にしたい方
- Python3の仕様に依らない問題分類を参考にしたい方（処理観点 / 数学観点 / アルゴリズム観点 / 計算量観点）
- 本記事の内容 / コードをレビューして頂ける方
コーディング規約
利用しているコーディング規約はありません。しかし、下記の方針でコーディングを行っています。※あくまで方針なので、厳密にコーディングしている訳ではありません。
- インデントは4とする
- 1行の長さは定義しない
- 空行はしない（可読性のために一部入れることもある）
- importは行を分けて定義する
- クオーテーションはダブルクオテーションで統一する
- 不要な半角スペースは入れない（可読性のために一部入れることもある）
- 1処理は1行で記載する
- 変数 / 型を1行で定義できる場合、1行で定義する
- if文 / for文 / while文の処理行数が1行の場合、文と処理を1行でコーディングする
- 命名規則はない
- 自分の直感に合うコーディングをする
記事の更新方針
分類範囲の問題で未分類 / 未解答の問題があります。また、今後はABC-D問題を解く予定です。そのため、本記事は今後、下記の更新する予定です。更新情報は編集履歴より確認をお願い致します。
- 未分類問題の追加
- 未解答問題の追加
- ABC-D問題の追加
- AGC-A問題の追加
知的財産
本記事に記載しているコードはすべて私が作成したコードです。また、AtCoderにおける知的財産権は下記の通りです。
知的財産権
1.本サービスに対して投稿されたプログラムの所有権と著作権は、そのプログラムを作成したユーザに帰属します
2.本サービスを構成する文章、画像、プログラムその他のデータ等についての一切の権利（所有権、知的財産権、肖像権、パブリシティー権等）は、ユーザ自身が作成したものを除き、弊社又は当該権利を有する第三者に帰属しています
3.ユーザ自身が作成した著作物を本サービスを通じて掲載した場合、弊社が宣伝告知等に利用することを許諾するものとします。また、かかる使用に際して、当該ユーザは著作者人格権を行使しないものとします本記事に記載しているコードを私的利用する場合、自由に活用して頂いて構いません。また、作成したコードは Github で公開しています。コードを転用する / 商業利用する場合は、本記事のコメント欄 / メール / Twitter で事前にご相談をお願い致します。
学習方法の特性上「他人のコードに酷似している」ことがあります。気分を害される方がいましたら、相談の上で引用元の記載 / 記事の更新 / 文章の削除等に対応しますので、ご連絡をお願い致します。※学習方法は ブログ に記載しています。
最後に
最後となりましたが、読者の方におかれましては初心者競プロerの成長過程と思い、温かく見守って頂けると幸いです。また、このような学習環境を提供して頂いている AtCoder社、SNS等で関わって頂いている競プロerの方に感謝を申し上げます。
以下から分類一覧となります。
実装観点
入力処理
1行 / C列
- 変数に格納する
サンプルコード# 入力 1 2 a,b=map(int,input().split()) print(a,b) # 1 2
- リストに格納する
サンプルコード# 入力 1 2 3 4 5 List=[int(i) for i in input().split()] print(List) # [1, 2, 3, 4, 5]
- 変数とリストに格納する
サンプルコード# 入力 abcdefg a,*List,b=input() # アンパック print(a) # a print(List) # ['b', 'c', 'd', 'e', 'f'] print(b) # g解答例a,b=map(int,input().split()) print(a+b if a+b<10 else "error")解答例print(sorted(map(int,"2 1 4 3".split()))) # [1, 2, 3, 4]解答例print(*input().split(','))解答例a,_,b=input() print("DH"[a==b])解答例a,b,c,d=input() print("Yes" if a==b==c or b==c==d else "No")ABC103 A - Task Scheduling Problem
解答例*a,=map(int,input().split()) print(max(a)-min(a))R行 / 1列
- 変数に格納する
サンプルコード# 入力 1 2 a=int(input()) b=int(input()) print(a,b) # 1 2サンプルコード# 入力 1 2 a,b=(int(input()) for i in range(2)) # a,b=[int(input()) for i in range(2)] print(a,b) # 1 2
- リストに格納する
サンプルコード# 入力 1 2 3 4 5 List=[int(input()) for i in range(5)] print(List) # [1, 2, 3, 4, 5]
- 入力行数が指定される
サンプルコード# 入力 5 # 入力行数指定(Row=5) 1 2 3 4 5 Row=int(input()) List=[int(input()) for i in range(Row)] print(List) # [1, 2, 3, 4, 5]
- 終了フラグ(-1)が指定される
サンプルコード# 入力 1 2 3 4 5 -1 # 終了フラグ List=[] while True: Row=int(input()) if Row==-1: break List.append(Row) print(List) # [1, 2, 3, 4, 5]ABC044 A - 高橋君とホテルイージー / Tak and Hotels (ABC Edit)
解答例n,k,x,y=(int(input()) for i in [0]*4) print(n*x-(x-y)*max(n-k,0))R行 / C列
- 2次元リストに格納する
サンプルコード# 入力 3 # 行数(Row)を指定する 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Row=int(input()) List=[[int(j) for j in input().split()] for i in range(Row)] print(List) # [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]]サンプルコード# 入力 3 # 行数(Row)を指定する 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Row=int(input()) List=[] for i in range(Row): List.append(list(map(int,input().split()))) print(List) # [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]]サンプルコード# 入力 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 List=[input().split() for i in range(3)] print(List) # [['1', '2', '3', '4', '5'], ['6', '7', '8', '9', '10'], ['11', '12', '13', '14', '15']]
- 1次元リストに格納する
サンプルコード# 入力 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 List=[] for i in range(3): List+=list(map(int,input().split())) print(List) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
- 変数に格納する
サンプルコード# 入力 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a=" ".join([input() for i in [0]*3]) print(a) # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 print(type(a)) # <class 'str'>解答例print(input()[0]+input()[1]+input()[2])不定形
サンプルコード# 入力 1 2 hoge (a,b),s=map(int,input().split()),input() print(a,b,s) # 1 2 hoge出力処理
int型
- 1次元リストを出力する
サンプルコードLists=[1,2,3,4,5] for List in Lists: print(List,end=' ') # 1 2 3 4 5サンプルコードList=[1,2,3,4,5] for i in range(len(List)): print(List[i],end=' ') # 1 2 3 4 5
- 2次元リストを出力する
サンプルコードLists=[[1,2,3],[4,5,6],[7,8,9]] for List in Lists: print(List,end=' ') # [1, 2, 3] [4, 5, 6] [7, 8, 9]サンプルコードList=[[1,2,3],[4,5,6],[7,8,9]] for i in List: for j in i: print(j,end=' ') # 1 2 3 4 5 6 7 8 9サンプルコードList=[[1,2,3],[4,5,6],[7,8,9]] for i in range(len(List)): for j in range(len(List[i])): print(List[i][j],end=' ') # 1 2 3 4 5 6 7 8 9解答例from itertools import chain List=[[1,2,3],[4,5,6],[7,8,9]] print(*chain(*List)) # 1 2 3 4 5 6 7 8 9str型
- 1次元リストを出力する
サンプルコードLists=["ab","cd","ef"] for List in Lists: print(List,end=' ') # ab cd efサンプルコードList=["ab","cd","ef"] for i in List: for j in i: print(j,end=' ') # a b c d e fサンプルコードList=["ab","cd","ef"] for i in range(len(List)): print(List[i],end=' ') # ab cd efサンプルコードList=["ab","cd","ef"] for i in range(len(List)): for j in range(len(List[i])): print(List[i][j],end=' ') # a b c d e f
- 2次元リストを出力する
サンプルコードList=[["ab","cd","ef"],["gh","ij","kl"]] for i in List: for j in i: print(j,end=' ') # ab cd ef gh ij klサンプルコードList=[["ab","cd","ef"],["gh","ij","kl"]] for i in List: for j in i: for k in j: print(k,end=' ') # a b c d e f g h i j k lサンプルコードList=[["ab","cd","ef"],["gh","ij","kl"]] for i in range(len(List)): for j in range(len(List[i])): print(List[i][j],end=' ') # ab cd ef gh ij klサンプルコードList=[["ab","cd","ef"],["gh","ij","kl"]] for i in range(len(List)): for j in range(len(List[i])): for k in range(len(List[i][j])): print(List[i][j][k],end=' ') # a b c d e f g h i j k l解答例print(*input().split()[::-1])ABC048 A - AtCoder *** Contest
解答例print("A%sC"%input()[8])区切り文字指定
- 空白（デフォルト）
サンプルコードa=1 b=2 c=3 print(a,b,c) # 1 2 3
- 改行を指定する
サンプルコードa=1 b=2 c=3 print(a,b,c,sep='\n') # 1 # 2 # 3
- カンマを指定する
サンプルコードa=1 b=2 c=3 print(a,b,c,sep=',') # 1,2,3
- 区切り文字なしを指定する
サンプルコードa=1 b=2 c=3 print(a,b,c,sep='') # 123数値リテラル
指数
サンプルコードprint(10**9+7) # 1000000007 print(9**.5) # 3.0解答例print(10**int(input())+7)浮動点小数
サンプルコードprint(5e10) # 50000000000.0 print(1.1e-3) # 0.0011解答例H,B=map(float,input().split()) print(H**2*B/1e4)解答例print((int(input())+1)*5e3)進数変換
サンプルコード# 2進数⇒10進数 print(int("1101",2)) # 13 # 8進数⇒10進数 print(int("700",8)) # 448 # 16進数⇒10進数 print(int("FE",16)) # 254 # 10進数⇒2進数 print(bin(23)) # 0b10111 # 10進数⇒8進数 print(oct(23)) # 0o27 # 10進数⇒16進数 print(hex(23)) # 0x17 # 2進数表示 print(0b10111) # 23 # 8進数表示 print(0o27) # 23 # 16進数表示 print(0x17) # 23解答例n=int(input()) x="" while n!=0: x=str(n%2)+x n=-(n//2) print(0 if x=="" else x)解答例print(2**(len(bin(int(input())))-3))解答例n=int(input()) l=[1,2,4,8,16,32,64] m=0 for i in l: if i <= n: m=max(m,i) print(m)複素数
サンプルコードprint(3+4j) # (3+4j)四則演算
小数点切り捨て
- 床関数（切り捨て）：floor
サンプルコードprint(5//3) # 1 import math print(math.floor(5/3)) # 1解答例x,y=map(int,input().split()) print(y//x)解答例print(int(input())**2//4)解答例k=int(input()) print((k//2)*((k+1)//2))小数点切り上げ
- 天井関数（切り上げ）：ceil
サンプルコードprint(-(-5//3)) # 2 print(math.ceil(5/3)) # 2 print(-~(4+5)//2) # 5 print(-~(5+5)//2) # 5解答例print(-(-int(input())//2))解答例print(5//3+(5%3>0))解答例a,b=map(int,input().split()) print(-(-b//a))解答例print(-~sum(map(int,input().split()))//2)四捨五入
- 四捨五入：rounding
サンプルコードprint(round(5/3)) # 2べき乗
- べき乗：power
サンプルコードprint(2**3) # 8 import math print(math.pow(2,3)) # 8.0平方根
- 平方根：square root
サンプルコードprint(4**(1/2)) # 2.0 print(4**.5) # 2.0 import math print(math.sqrt(4)) # 2.0解答例print(int(int(input())**.5)**2)解答例print("No" if int(input().replace(" ",""))**.5%1 else "Yes")解答例c=int(input().replace(" ","")) print("Yes" if c==int(c**.5)**2 else "No")階乗
- 階乗：factorial
サンプルコードimport math print(math.factorial(5)) # 120=5×4×3×2×1解答例import math print(math.factorial(int(input()))%(10**9+7))乗算
- 乗算：Multiplication
解答例print((["Bad"]*6+["Good"]*3+["Great"]+["Perfect"])[int(input())//10])ABC115 A - Christmas Eve Eve Eve
解答例print("Christmas"+" Eve"*(25-int(input())))剰余演算
- 剰余演算：modulo
解答例print(int(input())%12+1)解答例a,b=map(int,input().split()) print("Draw" if a==b else "Bob" if (a+13)%15<(b+13)%15 else "Alice")解答例print(sum(map(int,input().split()))%24)解答例print(int(input())%9)ABC102 A - Multiple of 2 and N
解答例n=int(input()) print(n+n%2*n)解答例print((eval(input().replace(" ","%"))>0)+0)繰り返し文
インクリメント/デクリメント
サンプルコードfor i in range(2,5,1): print(i, end=' ') # 2 3 4 for i in range(5,2,-1): print(i, end=' ') # 5 4 3インクリメント数/デクリメント数の指定
サンプルコードfor i in range(2,10,2): print(i, end=' ') # 2 4 6 8 for i in range(10,2,-2): print(i, end=' ') # 10 8 6 4条件文
if文
解答例a,b=map(int,input().split()) print("Draw" if a==b else "Bob" if (a+13)%15<(b+13)%15 else "Alice")if/break/else文
解答例N,M,A,B=map(int,input().split()) for i in range(M): if N<=A:N+=B N-=int(input()) if N<0: print(i+1) break else:print("complete")if/in文
サンプルコードif "abc" in input(): print("Include") else: print("Not incluede")解答例print("YES" if input() in "369" else "NO")解答例print("Yes" if "9" in input() else "No")解答例print("No" if "2" in input() else "Yes")ABC111 A - AtCoder Beginner Contest 999
解答例print("".join(["9" if x=="1" else "1" for x in input()]))解答例print("YES" if input() in "753" else "NO")複数条件式
サンプルコードprint("True" if a<=x<=a+b else "False")ABC061 A - Between Two Integers
解答例a,b,c=map(int,input().split()) print("Yes" if a<=c<=b else "No")解答例a,b,c,d=input() print("Yes" if a==b==c or b==c==d else "No")解答例a,b,x=map(int,input().split()) print("YES" if a<=x<=a+b else "NO")bit演算
反転
サンプルコードprint(~(5-3)) # -3 print(~-3) # 2 print(~-4) # 3解答例print(~eval(input().replace(" ","-"))+2)解答例a,b=map(int,input().split()) print(~-a*~-b)解答例a,b=map(int,input().split()) print(~-a*~-b)シフト
解答例print(["ABC","ARC","AGC"][int(input())//50+8>>5])解答例print(int(input())**2>>2)bool演算
bit変換
サンプルコードprint(True+0) # 1 print(False+0) # 0 print(-(3>2)) # -1 print(-(3<2)) # 0解答例n,s,t=map(int,input().split()) w=c=0 for i in range(n): w+=int(input()) c+=s<=w<=t print(c)解答例a,b,c,k=map(int,input().split()) s,t=map(int,input().split()) print(a*s+b*t-(s+t)*c*(s+t>=k))解答例a,b=map(int,input().split()) print(a-(a>b))解答例print((eval(input().replace(" ","%"))>0)+0)リスト処理
- リスト
[ ]はミュータブルで要素の挿入と削除を行うことができ、インデックス（番号）で要素にアクセスします。リストの長さ
- len
ABC046 A - AtCoDeerくんとペンキ / AtCoDeer and Paint Cans
解答例print(len(set(input().split())))解答例print("Yes" if len(set(input()))==3 else "No")要素の合計値
- sum
解答例print(sum(eval(input().replace(' ','*')) for i in range(3))//10)要素の追加
- append/extend/insert
サンプルコードList=['a','b','c'] List.append('d') print(List) # ['a', 'b', 'c', 'd'] List.extend(['e','f']) print(List) # ['a', 'b', 'c', 'd', 'e', 'f'] List.insert(1,'z') print(List) # ['a', 'z', 'b', 'c', 'd', 'e', 'f'] List.append(['g','h']) print(List) # ['a', 'z', 'b', 'c', 'd', 'e', 'f', ['g', 'h']] List.insert(1,['x','y']) print(List) # ['a', ['x', 'y'], 'z', 'b', 'c', 'd', 'e', 'f', ['g', 'h']]解答例S=list(input()) A,B,C,D=map(int,input().split()) S.insert(D,"\"") S.insert(C,"\"") S.insert(B,"\"") S.insert(A,"\"") print(*S,sep="")要素の探索
- index
サンプルコードList=['a','b','c','d','e','f'] print(List.index('c',0,5)) # 2 List=['a','b','c','d','c','c'] print(List.index('c', 0, 5)) # 2解答例print((1/int(input()))*sum("FDCBA".index(r) for r in input()))解答例N=int(input()) print(sum(map(int,input().translate(str.maketrans("FDCBA","01234"))))/N)解答例print(["Saturday","Friday","Thursday","Wednesday","Tuesday","Monday","Sunday"].index(input())%6)要素の削除
- pop/remove/del
サンプルコードList=['a','b','c','d','e','f'] print(List.pop(1)) # b print(List) # ['a', 'c', 'd', 'e', 'f'] List.pop() print(List) # ['a', 'c', 'd', 'e'] List.remove('d') print(List) # ['a', 'c', 'e'] del List[1] print(List) # ['a', 'e']要素の出現回数
- count
サンプルコードList=['a','b','b','c','c','c'] print(List.count('c')) # 3 print(List.count('d')) # 0解答例input() C=input() print(*sorted(C.count(c) for c in "1234")[::-3])解答例input() C=input() l=[C.count(c) for c in "1234"] print(max(l),min(l))解答例input() C=input() a=C.count("1") b=C.count("2") c=C.count("3") d=C.count("4") print(max(a,b,c,d),min(a,b,c,d))解答例a,b=map(int,input().split()) s=input() print("Yes" if s[a]=="-" and s.count("-")==1 else "No")要素の連結
- join
サンプルコードList=["ab","cd","ef"] print(List) # ['ab', 'cd', 'ef'] s=''.join(List) print(s) # abcdef解答例S=list(input().split()) a=[] for s in S: if s=="Left":a.append("<") elif s=="Right":a.append(">") else:a.append("A") print(" ".join(a))要素のユニーク化
- set
サンプルコード# 1次元リスト List=[2,3,1,2] print(list(set(List))) # [1, 2, 3] # 多次元リスト List=[[1,0],[0,0],[1,1],[1,0],[0,1],[0,0]] print(list(map(list,set(map(tuple,List))))) # [[0, 1], [1, 0], [0, 0], [1, 1]]ABC046 A - AtCoDeerくんとペンキ / AtCoDeer and Paint Cans
解答例print(len(set(input().split())))スライス
サンプルコードList=["a","b","c","d","e"] print(List[1:3]) # ['b', 'c'] print(List[1:4:2]) # ['b', 'd'] print(List[:3]) # ['a', 'b', 'c'] print(List[3:]) # ['d', 'e'] print(List[::-1]) # ['e', 'd', 'c', 'b', 'a'] print(List[::-2]) # ['e', 'c', 'a']解答例input() print(input()[:-1].lower().split().count("takahashikun"))解答例S=input() A,B,C,D=map(int,input().split()) print(S[:A]+'"'+S[A:B]+'"'+S[B:C]+'"'+S[C:D]+'"'+S[D:])解答例print(input()[::2])解答例print("NO" if int(input()[::2])%4 else "YES")解答例print(sum(sorted(map(int,input().split()))[:2]))解答例print("YES" if input()==input()[::-1] else "NO")解答例print("2018"+input()[4:])リスト内包表記
サンプルコード# 非ネスト List=[1*i for i in range(5)] print(List) # [0, 1, 2, 3, 4] # ネスト List=[1*i + 10*j + 100*k for k in range(2) for j in range(3) for i in range(4)] print(List) #[0, 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23, 100, 101, 102, 103, 110, 111, 112, 113, 120, 121, 122, 123]in演算子
サンプルコードList=["a","b","c"] print("a" in List) # True print("a" not in List) # False print("d" in List) # False print("d" not in List) # True print("a" in "auieo") # True解答例S=map(str,input().split("+")) ans=0 for s in S: if "0" not in s:ans+=1 print(ans)解答例A=[2,4,6,8,10] A=[a/2 for a in A] print(A) # [1.0, 2.0, 3.0, 4.0, 5.0]解答例input() l=map(str,input().split()) print("Three" if len(set(l))==3 else "Four")解答例input() print("Four" if "Y" in input() else "Three")ABC049 A - 居合を終え、青い絵を覆う / UOIAUAI
解答例print("vowel" if input() in "aiueo" else "consonant")タプル処理
- タプル
( )はイミュータブルで要素の書き換えができません。リストと同様、インデックス（番号）で要素にアクセスします。要素の探索
解答例import itertools N,M=map(int,input().split()) edges={tuple(sorted(map(int,input().split()))) for i in range(M)} ans=0 for i in itertools.permutations(range(2,N+1),N-1): l=[1]+list(i) ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1 print(ans)辞書処理
- 辞書
{ }はミュータブルでリストに似ていますが、要素へのアクセスは値に一意なキーで行います。要素の探索
解答例print({'Mo':5,'Tu':4,'We':3,'Th':2,'Fr':1,'Sa':0,'Su':0}[input()[:2]])解答例d=({"Saturday":0,"Sunday":0,"Monday":5,"Tuesday":4,"Wednesday":3,"Thursday":2,"Friday":1}) print(d[input()])解答例N=int(input()) A=[int(input()) for i in range(N)] B={a:i for (i,a) in enumerate(sorted(set(A)))} for a in A: print(B[a])解答例import bisect N=int(input()) A=[int(input()) for i in range(N)] B=sorted(list(set(A))) for a in A: print(bisect.bisect_left(B,a))解答例XU=[input().split() for i in range(int(input()))] print(sum([float(x)*{"JPY":1,"BTC":380000}[u] for x,u in XU]))集合処理
- 集合
{ }は辞書と同様、要素へのアクセスは値に一意なキーで行いますが同じ要素を一つしか持てないため辞書のように値はありません。和
A \cup Bサンプルコードprint({"a","b","c"}|{"c","d","e"}) # {'a', 'b', 'd', 'e', 'c'}差
A － Bサンプルコードprint({"a","b","c"}-{"c","d","e"}) # {'a', 'b'}積
A \cap Bサンプルコードprint({"a","b","c"}&{"c","d","e"}) # {'c'}ABC079 C - Cat Snuke and a Voyage
解答例N,M=map(int,input().split()) sa=set() sb=set() for i in range(M): a,b=map(int,input().split()) if a==1:sb.add(b) if b==N:sa.add(a) print("IMPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")ABC118 B - Foods Loved by Everyone
解答例n,m=map(int,input().split()) S=set(range(1,m+1)) for i in range(n): K,*A=map(int,input().split()) S&=set(A) print(len(S))対称差
A ⊕ Bサンプルコードprint({"a","b","c"}^{"c","d","e"}) # {'a', 'b', 'e', 'd'}解答例N=int(input()) s=set() for i in range(N):s^={input()} print(len(s))解答例print(eval(input().replace(' ','^')))解答例print(eval(input().replace(" ","^")))部分集合
A \subseteq Bサンプルコード# 左辺の要素すべてが右辺の集合に含まれている場合 print({"a","b"}<={"a","b","c"}) # True # 左辺の要素すべてが右辺の集合に含まれていない場合 print({"a","d"}<={"a","b","c"}) # False解答例x,y=input().split() a={"1","3","5","7","8","10","12"} b={"4","6","9","11"} print("Yes" if {x,y}<=a or {x,y}<=b else "No")文字の集合
サンプルコードimport string letters=string.ascii_lowercase print(letters) # abcdefghijklmnopqrstuvwxyzサンプルコードprint(sorted(map(chr,range(97,123)))) # ['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(sorted(map(chr,range(65,91)))) # ['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(min(set(map(chr,range(97,123)))-set(input())or["None"]))ABC093 B - Small and Large Integers
解答例a,b,k=map(int,input().split()) r=range(a,b+1) for i in sorted(set(r[:3])|set(r[-3:])): print(i)文字列処理
文字列の長さ
解答例print(max(input(),input(),key=len))文字列の参照
サンプルコードs="abc" print(s[-1]) # c s="abc" print(s[len(s)-1]) # c解答例a,b,c=input().split() print("YES" if a[-1]==b[0] and b[-1]==c[0] else "NO")文字列の逆順
サンプルコードs="abc" print(s[::-1]) # cba解答例print(*input().split()[::-1])文字列のコピー
解答例s=input() for i in range(int(input())): l,r=map(int,input().split()) s=s[:l-1]+s[l-1:r][::-1]+s[r:] print(s)文字列の判定
サンプルコードs="dog" [print(chr(i), end=" ") for i in range(ord('a'), ord('z')+1) if chr(i) in s] # d g o s="dog" [print(chr(i), end=" ") for i in range(ord('a'), ord('z')+1) if chr(i) not in s] # a b c e f h i j k l m n p q r s t u v w x y z解答例print(min(set(map(chr,range(97,123)))-set(input())or["None"]))文字列からリスト型に変換
サンプルコードs="abcde" print(s) # abcde l=list(s) print(l) # ['a', 'b', 'c', 'd', 'e']大文字小文字変換
- upper：すべての文字列を大文字に変換する
サンプルコードs="this is a pen." print(s.upper()) # THIS IS A PEN.ABC059 A - Three-letter acronym
解答例for a in input().upper().split():print(a[0],end="")解答例a,b,c=input().split() print((a[0]+b[0]+c[0]).upper())
- lower：すべての文字列を小文字に変換する
サンプルコードs="THIS IS A PEN." print(s.lower()) # this is a pen.
- capitalize：文字列の先頭文字を大文字に変換する
サンプルコードs="this is a pen." print(s.capitalize()) # This is a pen.解答例print("abcd".capitalize()) # Abcd
- title：各単語の先頭文字を大文字に変換する
サンプルコードs="this is a pen." print(s.title()) # This Is A Pen.三項演算
サンプルコードprint("1" if a == 1 else "other") # if a == 1: # print("1") # else: # print("other") print("1" if a == 1 else "2" if a == 2 else "3" if a == 3 else "other") # if a == 1: # print("1") # elif a == 2: # print("2") # elif a == 3: # print("3") # else: # print("other")Lambda式
解答例x=lambda:int(input()) print((x()+x())*x()//2)解答例a,b=map(lambda x:(int(x)+13)%15,input().split()) print("Alice" if a>b else "Bob" if a<b else "Draw")解答例i=lambda:int(input()) print((i()-i())%i())解答例f=lambda:min(int(input()),int(input())) print(f()+f())正規表現
- 正規表現：Regular Expression
findall
- findall：マッチする部分すべてをリストで返す
解答例import re print(*re.findall("[0-9]+",input()))match
- match：文字列の先頭がパターンにマッチするかを調べる
解答例import re print("YES" if re.match("^(dream|dreamer|erase|eraser)+$",input()) else "NO")解答例import re s=input().replace("?",".") t=input() for i in range(len(s)-len(t),-1,-1): if re.match(s[i:i+len(t)],t): s=s.replace(".","a") print(s[:i]+t+s[i+len(t):]) exit() print("UNRESTORABLE")解答例import re s=input().replace("?",".") t=input() for i in range(len(s)-len(t)+1): if re.match(s[i:i+len(t)],t): s=s.replace(".","a") print(s[:i]+t+s[i+len(t):]) exit() print("UNRESTORABLE")解答例import re S = input() print("AC" if(re.match("^A[a-z]+C[a-z]+$",S)) else "WA")search
- search：先頭に限らずパターンにマッチするかを調べる
解答例import re print("YES" if re.search("i.*c.*t",input().lower()) else "NO")解答例import re print("YES" if re.search("[i|I].*[c|C].*[t|T]",input()) else "NO")sub
- sub：マッチした部分を置換する
解答例import re print(re.sub("\D","",input()))解答例import re print(re.sub("[aiueo]","",input()))解答例import re print("NO" if re.sub(r"ch|o|k|u","",input()) else "YES")解答例import re print(re.sub("[aiueo]","",input()))import
bisect
サンプルコードimport bisect List=[ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19] print(bisect.bisect_left(List,5)) #2 """ List=[ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 1 2 3 4 5 6 7 8 9 10 ^ """ print(bisect.bisect_right(List,5)) #3 """ List=[ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 1 2 3 4 5 6 7 8 9 10 ^ """ print(bisect.bisect_left(List,15)) #7 """ List=[ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 1 2 3 4 5 6 7 8 9 10 ^ """ print(bisect.bisect_right(List,15)) #8 """ List=[ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 1 2 3 4 5 6 7 8 9 10 ^ """ List=[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3] print(bisect.bisect_left(List,2)) #4 """ List=[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3] 1 2 3 4 5 6 7 8 9 10 11 12 ^ """ print(bisect.bisect_right(List,2)) #8 """ List=[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3] 1 2 3 4 5 6 7 8 9 10 11 12 ^ """ print(bisect.bisect_right(List,2)) #8 """ List=[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3] 1 2 3 4 5 6 7 8 9 10 11 12 ^ """ print(bisect.bisect_right(List,3)) #12 """ List=[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3] 1 2 3 4 5 6 7 8 9 10 11 12 ^ """解答例import bisect A,B,Q=map(int,input().split()) INF=10**18 S=[-INF]+[int(input()) for i in range(A)]+[INF] T=[-INF]+[int(input()) for i in range(B)]+[INF] for q in range(Q): x=int(input()) i=bisect.bisect_right(S,x) j=bisect.bisect_right(T,x) d=INF for s in [S[i-1],S[i]]: for t in [T[j-1],T[j]]: d1=abs(s-x)+abs(s-t) d2=abs(t-x)+abs(s-t) d=min(d,d1,d2) print(d)解答例import bisect N=int(input()) A=sorted(list(map(int,input().split()))) B=sorted(list(map(int,input().split()))) C=sorted(list(map(int,input().split()))) print(sum(bisect.bisect_left(A,b)*(N-bisect.bisect_right(C,b)) for b in B))解答例from collections import Counter N=int(input()) A=Counter(input().split()) B=Counter(input().split()) C=Counter(input().split()) ans=0 for a_key,a_count in A.most_common(): for b_key,b_count in B.most_common(): for c_key,c_count in C.most_common(): a_key,b_key,c_key=int(a_key),int(b_key),int(c_key) if a_key<b_key and b_key<c_key: ans+=a_count*b_count*c_count print(ans)collections
- Counter
サンプルコードList=['a','a','a','a','b','c','c'] c=collections.Counter(l) print(c) # Counter({'a': 4, 'c': 2, 'b': 1}) print(type(c)) # <class 'collections.Counter'> print(issubclass(type(c), dict)) # True print(c.keys()) # dict_keys(['a', 'b', 'c']) print(c.values()) # dict_values([4, 1, 2]) print(c.items()) # dict_items([('a', 4), ('b', 1), ('c', 2)]) print(c.most_common()) # [('a', 4), ('c', 2), ('b', 1)] print(c.most_common()[0]) # ('a', 4) print(c.most_common()[-1]) # ('b', 1) print(c.most_common()[0][0]) # a print(c.most_common()[0][1]) # 4 print(c.most_common()[::-1]) # [('b', 1), ('c', 2), ('a', 4)] print(c.most_common(2)) # [('a', 4), ('c', 2)] values,counts=zip(*c.most_common()) print(values) # ('a', 'c', 'b') print(counts) # (4, 2, 1) print(c['a']) # 4 print(c['b']) # 1 print(c['c']) # 2 print(c['d']) # 0解答例from collections import Counter input() L=Counter(input().split()) R=Counter(input().split()) print(sum([min(value,L[key]) for key,value in R.items()]))解答例from collections import Counter N=int(input()) A=Counter(list(map(int,input().split()))) x=[0,0] for a in A: if A[a]>1:x.append(a) if A[a]>3:x.append(a) x.sort() print(x[-1]*x[-2])ABC071 C - 怪文書 / Dubious Document
解答例from collections import Counter n=int(input()) s=Counter(input()) for i in range(n-1): s&=Counter(input()) print("".join(sorted(s.elements())))解答例from collections import Counter N=int(input()) A=Counter([int(input()) for i in range(N)]) print(sum(1 if count%2 else 0 for count in A.values()))解答例from collections import Counter n,k=map(int,input().split()) a=Counter(input().split()) print(sum(sorted(a.values(),reverse=True)[k:]))解答例from collections import Counter n,k=map(int,input().split()) a=Counter(input().split()) ans=0 keys,counts=zip(*a.most_common()) for num,(key,count) in enumerate(zip(keys,counts)): if int(num)>k-1:ans+=count print(ans)解答例from collections import Counter n=int(input()) a=Counter(input().split()) ans=0 for i,j in a.items(): i=int(i) if i>j: ans+=j elif i<j: ans+=j-i print(ans)解答例from collections import Counter n=int(input()) v=list(map(int,input().split())) a=Counter(v[0::2]).most_common() b=Counter(v[1::2]).most_common() a.append([0,0]) b.append([0,0]) if a[0][0]!=b[0][0]: print(n-(a[0][1]+b[0][1])) else: print(min(n-(a[1][1]+b[0][1]),n-(a[0][1]+b[1][1])))ABC110 C - String Transformation
解答例from collections import Counter s=Counter(list(input())) t=Counter(list(input())) s,t=list(s.values()),list(t.values()) print("Yes" if sorted(s)==sorted(t) else "No")解答例from collections import Counter a=Counter([input() for i in range(int(input()))]) print(a) # Counter({'taro': 2, 'jiro': 1, 'saburo': 1}) print(a.most_common()[0][0]) # tarofractions
fraction：分数
gcd
ABC118 C - Monsters Battle Royale
解答例import functools,fractions n=input() a=list(map(int,input().split())) print(functools.reduce(fractions.gcd,a))functools
functools：高次関数
reduce
サンプルfrom functools import reduce from operator import add from operator import sub from operator import mul List=[20,1,2,3,4,5] print(reduce(add,List)) # 35 # add：20+1+2+3+4+5=35 print(reduce(sub,List)) # 5 # sub：20-1-2-3-4-5=5 print(reduce(mul,List)) # 2400 # mul：20*1*2*3*4*5=2400 # Lambda式に変換が可能 print(reduce(lambda a,b:a+b,List)) # 35 print(reduce(lambda a,b:a-b,List)) # 5 print(reduce(lambda a,b:a*b,List)) # 2400解答例from functools import reduce from fractions import gcd N,X=map(int,input().split()) x=[abs(X-int(i)) for i in input().split()] print(reduce(gcd,x))heapq
解答例import heapq N=int(input()) s=set() q=[0,0] for a in map(int,input().split()): if a>q[0]: try: s.remove(a) heapq.heapreplace(q,a) except: s.add(a) print(q[0]*q[1])itertools
- permutations
4! = 4 × 3 × 2 × 1 = 24通りサンプルコードfrom itertools import permutations List=["a","b","c","d","e"] print(list(permutations(List))) # [('a', 'b', 'c', 'd'), ('a', 'b', 'd', 'c'), ('a', 'c', 'b', 'd'), ('a', 'c', 'd', 'b'), ('a', 'd', 'b', 'c'), ('a', 'd', 'c', 'b'), ('b', 'a', 'c', 'd'), ('b', 'a', 'd', 'c'), ('b', 'c', 'a', 'd'), ('b', 'c', 'd', 'a'), ('b', 'd', 'a', 'c'), ('b', 'd', 'c', 'a'), ('c', 'a', 'b', 'd'), ('c', 'a', 'd', 'b'), ('c', 'b', 'a', 'd'), ('c', 'b', 'd', 'a'), ('c', 'd', 'a', 'b'), ('c', 'd', 'b', 'a'), ('d', 'a', 'b', 'c'), ('d', 'a', 'c', 'b'), ('d', 'b', 'a', 'c'), ('d', 'b', 'c', 'a'), ('d', 'c', 'a', 'b'), ('d', 'c', 'b', 'a')] print(len(list(permutations(List)))) # 24_4 P _2 = 4 \times 3 = 12通りサンプルコードfrom itertools import permutations List=["a","b","c"] print(list(permutations(List,2))) # [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'a'), ('b', 'c'), ('b', 'd'), ('c', 'a'), ('c', 'b'), ('c', 'd'), ('d', 'a'), ('d', 'b'), ('d', 'c')] print(len(list(permutations(List,2)))) # 12解答例from itertools import permutations n,m,l=map(int,input().split()) P=list(map(int,input().split())) v=0 for p,q,r in permutations(P): v=max(v,(n//p)*(m//q)*(l//r)) print(v)
- product
解答例from itertools import product [print("".join(i)) for i in product("abc",repeat=int(input()))]解答例import itertools N=int(input()) ans=0 S=[] for i in range(10): S+=list(itertools.product("357",repeat=i)) for s in S: if len(set(s))>2 and int("".join(s))<=N: ans+=1 print(ans)
- groupby
ABC063 C - 一次元リバーシ / 1D Reversi
解答例from itertools import groupby S=input() G=groupby(S) print(len(list(G))-1)解答例import itertools print("".join([i+str(len(list(j))) for i,j in itertools.groupby(list(input()))]))解答例import itertools s="" for i,j in itertools.groupby(list(input())): s+=i+str(len(list(j))) print(s)
- combinations
_4 C _2 = \frac{_4 P _2}{2!} = 6通りサンプルfrom itertools import combinations List=["a","b","c","d"] print(list(combinations(List,2))) # [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')] print(len(list(combinations(List,2)))) # 6解答例from itertools import combinations S=map(int,input().split()) print(sorted(map(sum,combinations(S,3)))[-3])サンプルコードfrom itertools import combinations for a,b,c in combinations("MARCH",3): print(a,b,c) # M A R # M A C # M A H # M R C # M R H # M C H # A R C # A R H # A C H # R C H解答例from itertools import combinations from collections import Counter N=int(input()) S=Counter() for i in range(N): S[input()[0]]+=1 print(sum([S[a]*S[b]*S[c] for a,b,c in combinations("MARCH",3)]))math
ABC067 C - Factors of Factorial
解答例import math N=math.factorial(int(input())) i=2 ans=1 M=10**9+7 while i*i<=N: cnt=1 while N%i==0: cnt+=1 N//=i ans*=cnt i+=1 if N!=1:ans*=2 print(int(ans%M))解答例import math print(math.factorial(int(input()))%(10**9+7))組み込み関数
abs
サンプルコードprint(abs(-1)) # 1all/any
- all
サンプルコードprint(all([True,True])) # True print(all([True,False])) # False print(all([False,False])) # False解答例n=int(input()) a=[int(i) for i in input().split()] c=0 while(True): for i in range(len(a)): if a[i]==0: print(c) exit() elif a[i]%2==0: a[i]=a[i]/2 else: print(c) exit() c+=1解答例input() A=list(map(int,input().split())) c=0 while all(a%2==0 for a in A): A=[a/2 for a in A] c+=1 print(c)
- any
サンプルコードprint(any([True,True])) # True print(any([True,False])) # True print(any([False,False])) # Falseenumerate
サンプルコードa,b=divmod(5,2) print(a) # 2 print(b) # 1enumerate
サンプルコードList=['Alice', 'Bob', 'Charlie'] for num,name in enumerate(List): print(num,name) # 0 Alice # 1 Bob # 2 Charlie解答例N=int(input()) A=[(int(a), i) for i,a in enumerate(input().split(),1)] for a in sorted(A,reverse=True): print(a[1])ABC102 C - Linear Approximation
解答例N=int(input()) A=sorted(a-i-1 for i,a in enumerate(map(int,input().split()))) print(sum(abs(a-A[N//2]) for a in A))eval
サンプルコードprint(eval("1+2")) # 3解答例print(eval(input().replace(" ","**2*"))/1e4)解答例print("4:3" if eval(input().replace(" ","*"))%144 else "16:9")解答例print(sum(eval(input().replace(' ','*')) for i in range(3))//10)ABC050 A - Addition and Subtraction Easy
解答例print(eval(input()))map
ABC110 C - String Transformation
解答例s=input() t=input() S=sorted(map(s.count,set(s))) T=sorted(map(t.count,set(t))) print("Yes" if S==T else "No")max/min
- max
サンプルコード# 2値 print(max(1,2)) # 2 # 多値 print(max(2,1,3)) # 3 # リスト print(max([2,1,3])) # 3 # 文字リスト print(max(['b','a','c','d'])) # d # 文字列リスト print(max(['ab','aa','ca','bd'])) # ca # 文字列長さ print(max(['a','bcde','fg','hij'],key=len)) # bcde解答例print(max(input(),input(),key=len))解答例a,b,c=map(int,input().split()) print(max(c//a,c//b))
- min
サンプルコード# 2値 print(min(1,2)) # 1 # 多値 print(min(2,1,3)) # 1 # リスト print(min([2,1,3])) # 1 # 文字リスト print(min(['b','a','c','d'])) # a # 文字列リスト print(min(['ab','aa','ca','bd'])) # aa # 文字列長さ print(min(['a','bcde','fg','hij'],key=len)) # a解答例a,b,c=map(int,input().split()) print(c//min(a,b))解答例n,x=map(int,input().split()) print(min(x-1,n-x))ord/chr
- ord
サンプルコードprint([chr(i) for i in range(ord('a'),ord('z')+1)]) # ['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(ord(input())-64)解答例print(["A","B","C","D","E"].index(input())+1)
- chr
サンプルコードprint([chr(i) for i in range(97, 97+26)]) # ['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']range
サンプルコードr=range(2,10) print(r) # range(2, 10) print(r[:3]) # range(2, 5) print(set(r[:3])) # {2, 3, 4} print(r[3:]) # range(5, 10) print(set(r[3:])) # {5, 6, 7, 8, 9} print(r[-3:]) # range(7, 10) print(set(r[-3:])) # {8, 9, 7} print(r[:-3]) # range(2, 7) print(set(r[:-3])) # {2, 3, 4, 5, 6}zip
サンプルコードMatrix=[ [1,2,3], [4,5,6], [7,8,9] ] print(list(map(list,zip(*Matrix)))) # [[1, 4, 7], [2, 5, 8], [3, 6, 9]]解答例print(sum(map(max,zip(*[list(map(int,input().split())) for i in range(2)]))))解答例D=map(int,input().split()) J=map(int,input().split()) print(sum(max(d,j) for d,j in zip(D,J)))解答例o=list(input()) e=list(input())+[""] for x,y in zip(o,e):print(x+y,end="")メソッド
find/rfind
解答例S=input()[0:12] key="WBWBWWBWBWBW"*2 ans=["Do","","Re","","Mi","Fa","","So","","La","","Si"] print(ans[(key.find(S))])解答例s=input() print(s.rfind("Z")-s.find("A")+1)isdecimal/isdigit/isnumeric/isalpha/isalnum
- isdecimal：全ての文字が十進数字なら真、そうでなければ偽（半角・全角のアラビア数字が真）
サンプルコードs="1234567890" print(s.isdecimal()) # True解答例a,b=map(int,input().split()) s=input() if 1<=a<=5 and 1<=b<=5: if s[a]=="-": if s[0:a].isdecimal() and s[a+1:a+b+1].isdecimal(): print("Yes") exit() print("No")
- isdigit：全ての文字が数字なら真、そうでなければ偽（半角・全角のアラビア数字、特殊数字が真）
サンプルコードs="\u00B2" # 2乗 print(s.isdigit()) # True解答例print("".join(i for i in input() if i.isdigit()))
- isnumeric：全ての文字が数を表す文字なら真、そうでなければ偽（半角・全角のアラビア数字、特殊数字、漢数字が真）
サンプルコードs="一二三四五六七八九〇壱億参阡萬" print(s.isnumeric()) # True
- isalpha：全ての文字が英字なら真、そうでなければ偽（便宜上「英字」と書いているが、平仮名やカタカナ、漢字なども真）
サンプルコードs="abcあいうアイウ漢字" print(s.isalpha()) # True
- isalnum:：全ての文字が英数字なら真、そうでなければ偽（各文字が上のメソッドで真となれば真）
サンプルコードs="abc100" print(s.isalnum()) # Truereplace
サンプルコードList=["aabbaa","bbaabb","ababab"] List=",".join(List) print(List) # aabbaa,bbaabb,ababab List=List.replace('a','c') print(List) # ccbbcc,bbccbb,cbcbcb List=List.split(',') print(List) # ['ccbbcc', 'bbccbb', 'cbcbcb']サンプルコードList=["aabbaa", "bbaabb", "ababab"] List=",".join(List).replace('a', 'c').split(',') print(List) # ['ccbbcc', 'bbccbb', 'cbcbcb']解答例S=input() for b,a in zip("ODIZSB","001258"): S=S.replace(b,a) print(S)解答例S=input() b="ODIZSB" a="001258" for i in range(6): S=S.replace(b[i],a[i]) print(S)解答例print(input().replace("O","0").replace("D","0").replace("I","1").replace("Z","2").replace("S","5").replace("B","8"))解答例print(input().replace("Left","<").replace("Right",">").replace("AtCoder","A"))解答例print(sum(eval(input().replace(' ','*')) for i in range(3))//10)解答例print(eval(input().replace(' ','^')))解答例print(eval(input().replace(" ","-"))+1)解答例print("No" if eval(input().replace(" ","*"))%2==0 else "Yes")ABC111 A - AtCoder Beginner Contest 999
解答例print(input().replace("1","x").replace("9","1").replace("x","9"))sort/reverse
- sort
サンプルコード# 昇順 List=[2,1,3] List.sort() print(List) # [1, 2, 3] # 降順 List=[2,1,3] List.sort(reverse=True) print(List) # [3, 2, 1] # 多次元昇順 List=[[0,1],[1,1],[1,0],[0,0]] List.sort(key=lambda List:(List[0],List[1])) print(List) # [[0, 0], [0, 1], [1, 0], [1, 1]] # 多次元昇順 from operator import itemgetter List=[[0,1],[1,1],[1,0],[0,0]] Listsort(key=itemgetter(0,1)) print(List) # [[0, 0], [0, 1], [1, 0], [1, 1]] # 多次元降順 List=[[0,1],[1,1],[1,0],[0,0]] List.sort(key=lambda List:(List[0],List[1]),reverse=True) print(List) # [[1, 1], [1, 0], [0, 1], [0, 0]] # 多次元降順 from operator import itemgetter List=[[0,1],[1,1],[1,0],[0,0]] List.sort(key=itemgetter(0,1),reverse=True) print(List) # [[1, 1], [1, 0], [0, 1], [0, 0]]
- reverse
サンプルコード# 1次元 List=[2,1,3] List.reverse() print(List) # [3, 1, 2] # 多次元 List=[[0,1],[1,1],[1,0],[0,0]] List.reverse() print(List) # [[0, 0], [1, 0], [1, 1], [0, 1]]translate/maketrans
解答例print(input().translate(str.maketrans("ODIZSB","001258")))処理観点
行列処理
行集計
\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ 1 \\ \end{pmatrix} = \begin{pmatrix} 6 \\ 15 \\ 24 \\ \end{pmatrix}サンプルコードMatrix=[[1,2,3],[4,5,6],[7,8,9]] print([sum(x) for x in Matrix]) # [6, 15, 24]列集計
\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix}^T \begin{pmatrix} 1 \\ 1 \\ 1 \\ \end{pmatrix} = \begin{pmatrix} 12 \\ 15 \\ 18 \\ \end{pmatrix}サンプルコードMatrix=[[1,2,3],[4,5,6],[7,8,9]] print([sum(x) for x in zip(*Matrix)]) # [12, 15, 18]転置行列
A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \\ \end{pmatrix}A^T = \begin{pmatrix} 1 & 3 & 5 \\ 2 & 4 & 6 \\ \end{pmatrix}解答例h,w=map(int,input().split()) a=[[j for j in input()] for i in range(h)] b=[x for x in a if "#" in x] c=zip(*[y for y in zip(*b) if "#" in y]) for d in c:print("".join(d))回転行列
A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix}A^{回転} = \begin{pmatrix} 3 & 6 & 9 \\ 2 & 5 & 8 \\ 1 & 4 & 7 \\ \end{pmatrix}解答例print("\n".join(input() for _ in range(4))[::-1])解答例for i in reversed([input() for i in range(4)]): print(i[::-1])解答例s=[input() for i in range(int(input()))] for x in zip(*s):print("".join(x)[::-1])解答例s=reversed([input() for i in range(int(input()))]) for x in zip(*s):print("".join(x))順位行列
解答例import collections import bisect n,m=map(int,input().split()) p=[[int(j) for j in input().split()] for i in range(m)] a=collections.defaultdict(list) for x,y in sorted(p): a[x]+=[y] for x,y in p: z=bisect.bisect(a[x],y) print("%06d%06d"%(x,z))うるう年判定
- うるう年：Leap year
解答例import calendar print("YES" if calendar.isleap(int(input())) else "NO")解答例Y=int(input()) print("YES" if Y%4==0 and Y%100!=0 or Y%400==0 else "NO")奇数/偶数判定
- 入力数1
f(x) = \left\{ \begin{array}{ll} Even & (x\;\;mod\;\;2\;\;=\;\;0) \\ Odd & (x\;\;mod\;\;2\;\;=\;\;1) \end{array} \right.サンプルコードx=int(input()) print(["Even","Odd"][x%2])
x 1 2 x%2 1 0 ["Even","Odd"][x%2] Odd Even
- 入力数2
f(x,y) = \left\{ \begin{array}{ll} Even & (x y\;\;mod\;\;2\;\;=\;\;0) \\ Odd & (x y\;\;mod\;\;2\;\;=\;\;1) \end{array} \right.サンプルコードx,y=map(int,input().split()) print(["Even","Odd"][x*y%2]) # Even
x*y 1 2 x*y%2 1 0 ["Even","Odd"][x*y%2] Odd Even
- 入力数3以上
f(x) = \left\{ \begin{array}{ll} Even & (if\;\;x_{all}\;\;mod\;\;2\;\;=\;\;0) \\ Odd & (otherwise) \end{array} \right.サンプルコードx=[2,4,6,8] print("Even" if all([i%2==0 for i in x]) else "Odd") # Even x=[2,4,6,9] print("Even" if all([i%2==0 for i in x]) else "Odd") # OddARC014 A - 君が望むなら世界中全てのたこ焼きを赤と青に染め上げよう
解答例print("Blue" if int(input())%2==0 else "Red")N値判定
- 2値判定(Zero/NotZero判定)
f(x) = \left\{ \begin{array}{ll} Zero & (x=0) \\ Not Zero & (x\neq0) \end{array} \right.サンプルコードx=int(input()) print(["Not Zero","Zero"][x==0])
x 0 1 x==0 True False ["Not Zero","Zero"][x==0] Zero Not Zero 解答例print("HD"[len(set(input()))%2])解答例print(['ABC','ABD'][len(input())>3])ABC102 A - Multiple of 2 and N
解答例n=int(input()) print([N,N*2][N%2])
- 3値判定(正の数/0/負の数判定)
f(x) = \left\{ \begin{array}{ll} Positive & (x > 0) \\ 0 & (x = 0) \\ Negative& (x < 0) \end{array} \right.サンプルコードx=int(input()) print(["0","Positive","Negative"][x>0 or -(x<0)])
x -1 0 1 x>0 False False True x<0 True False Flase -(x<0) -1 0 0 x>0 or -(x<0) -1 0 True ["0","Positive","Negative"][x>0 or -(x<0)] Negative 0 Positive 解答例x,y=input().split() print("=><"[x>y or -(x<y)])解答例a,b,c,d=map(int,input().split()) print(['Balanced','Left','Right'][(a+b>c+d)-(a+b<c+d)])解答例print(["ABC","ARC","AGC"][(int(input())+400)//1600])桁数の和
f(x) = \sum_{1}^{length(x)} x_i （x_i：xのi桁目の数）サンプルコードx=1234 print(sum(map(int,x))) # 10(=1+2+3+4)解答例n,a,b=map(int,input().split()) print(sum(i for i in range(n+1) if(a<=sum(map(int,str(i)))<=b)))解答例n,a,b=map(int,input().split()) s=0 for i in range(n+1): if a<=sum(map(int,str(i)))<=b: s+=i print(s)解答例n,a,b=map(int,input().split()) s=0 for i in range(n+1): if a<=sum(int(j) for j in str(i))<=b: s+=i print(s)解答例n,a,b=map(int,input().split()) s=0 for i in range(n+1): c=0 d=str(i) for j in range(len(d)): c+=int(d[j]) if a<=c<=b: s+=i print(s)解答例N=input() print("Yes" if int(N)%sum(map(int,list(N)))==0 else "No")解答例N=input() print("Yes" if int(N)%sum(int(_) for _ in N)==0 else "No")解答例N=input() s=0 for n in N: s+=int(n) print("Yes" if int(N)%s==0 else "No")解答例print(sum(map(int,input())))桁の数
ABC057 C - Digits in Multiplication
解答例N=int(input()) i=int(N**(1/2)) while N%i!=0: i-=1 print(len(str(N//i)))解答例def ketasu(N): count=1 while N>=10: N//=10 count+=1 return count N=int(input()) keta=10**10 for i in range(1,int(N**.5)+1): if N%i==0: keta=min(keta,max(ketasu(i),ketasu(N//i))) print(keta)解答例N=int(input())-1 print(str(N%9+1)*(N//9+1))解答例N=int(input()) num=1 while N>0: if len(set(str(num)))==1:N-=1 num+=1 print(num-1)日時
解答例import datetime y=int(input()) m=int(input()) d=int(input()) print((datetime.date(2014,5,17)-datetime.date(y,m,d)).days)解答例Y=int(input()) M=int(input()) D=int(input()) if M==1 or M==2: Y-=1 M+=12 print(735369-(365*Y+Y//4-Y//100+Y//400+306*(M+1)//10+D-429))解答例n=int(input()) print("%02d:%02d:%02d"%(n//3600,(n%3600)//60,n%60))解答例print("Heisei" if input()<="2019/04/30" else "TBD")時計
解答例n,m=map(int,input().split()) a=abs(n%12*30-5.5*m) print(min(a,360-a))コイン
解答例x,y=map(int,input().split()) k=int(input()) print(x+y-abs(k-y))カード
ABC090 C - Flip,Flip, and Flip......
解答例N,M=map(int,input().split()) print(1 if N==1 and M==1 else max(N,M)-2 if N==1 or M==1 else N*M-2*N-2*M+4)グラフ
解答例N=int(input()) K=int(input()) print("YES" if K<=N//2 else "NO")解答例V,E=map(int,input().split()) edges=[set() for i in range(V)] for i in range(E): a,b=map(int,input().split()) edges[a-1].add(b-1) edges[b-1].add(a-1) for i in range(V): print(len({n for v in edges[i] for n in edges[v] if not n in edges[i] and n!=i}))解答例import itertools N,M=map(int,input().split()) edges={tuple(sorted(map(int,input().split()))) for i in range(M)} ans=0 for i in itertools.permutations(range(2,N+1),N-1): l=[1]+list(i) ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1 print(ans)解答例N,M=map(int,input().split()) edges=[list(map(int,input().split())) for i in range(M)] ans=0 for x in edges: l=list(range(N)) for y in edges: if y!=x:l=[l[y[0]-1] if l[i]==l[y[1]-1] else l[i] for i in range(N)] if len(set(l))!=1:ans+=1 print(ans)
- 未分類
ABC012 D - バスと避けられない運命
ABC014 D - 閉路
ABC019 D - 高橋くんと木の直径
ABC035 D - トレジャーハント
ABC051 D - Candidates of No Shortest Paths
ABC061 D - Score Attack
ABC070 D - Transit Tree Path
ABC073 D - joisino's travel
ABC074 D - Restoring Road Networkソート
解答例N,M=map(int,input().split()) A=[int(input()) for i in range(M)][::-1] ans=[] s=set() for a in A: if a not in s:ans.append(a) s.add(a) for i in range(1,N+1): if i not in s:ans.append(i) print(*ans,sep="\n")順位/ランキング
解答例X=[int(input()) for i in range(3)] for x in X:print(3-sorted(X).index(x))解答例l=[int(input()) for _ in range(3)] s=sorted(l)[::-1] for i in l: print(s.index(i)+1)宝くじ
解答例E=set(input().split()) b=input() L=set(input().split()) l=len(E&L) ans=0 if l==5 and b in L:ans=2 elif l==6:ans=1 elif l>2:ans=8-l else:ans=0 print(ans)解答例a = [int(i) for i in input().split()] b = int(input()) c = [int(i) for i in input().split()] k = 6 - len(set(a) - set(c)) if k == 5 and b in c: print(2) else: print({6:1,5:3,4:4,3:5}.get(k,0))グリッド
解答例H,W=map(int,input().split()) S=["."+input()+"." for i in range(H)] S=["."*(W+2)]+S+["."*(W+2)] flag=0 for i in range(H): for j in range(W): if S[i][j]=="#": if S[i-1][j]=="." and S[i+1][j]=="." and S[i][j-1]=="." and S[i][j+1]==".": flag=1 print("Yes" if flag==0 else "No")解答例h,w=map(int,input().split()) a=[[j for j in input()] for i in range(h)] b=[x for x in a if "#" in x] c=zip(*[y for y in zip(*b) if "#" in y]) for d in c:print("".join(d))解答例h,w=map(int,input().split()) s=[input() for _ in range(h)] for i in range(h): l="" for j in range(w): if s[i][j]=="#": l+="#" else: l+=str(sum([t[max(0,j-1):min(w,j+2)].count("#") for t in s[max(0,i-1):min(h,i+2)]])) print(l)解答例n,m=map(int,input().split()) a=[input() for _ in range(n)] b=[input() for _ in range(m)] r=any([r[j:j+m] for r in a[i:i+m]]==b for i in range(n-m+1) for j in range(n-m+1)) print('Yes' if r else 'No')回文
ABC090 B - Palindromic Numbers
解答例a,b=map(int,input().split()) print(sum(i==i[::-1] for i in map(str,range(a,b+1))))解答例a,b=map(int,input().split()) print(len([i for i in map(str,range(a,b+1)) if i==i[::-1]]))数列
解答例import math N=int(input()) A=list(map(int,input().split())) flag=True if N%2==0: if 0 in A or len(set(A))!=N//2:flag=False else: if len([0 for a in A if a==0])!=1 or len(set(A))!=N//2+1:flag=False if flag:print(2**(N//2)%(10**9+7)) else:print(0)解答例n=input() a=[int(i) for i in input().split()] def chk(a,t): ans=0 x=0 for i in a: x+=i if t==True and x<1: ans+=1-x x=1 elif t==False and x>-1: ans+=x+1 x=-1 t=not t return ans print(min(chk(a,True),chk(a,False)))解答例n=int(input()) a=list(map(int,input().split())) b=list(map(int,input().split())) print(max(sum(a[:i+1])+sum(b[i:]) for i in range(n)))解答例n=int(input()) a=list(map(int,input().split())) b=list(map(int,input().split())) ans=0 for i in range(n): ans=max(ans,sum(a[:i+1])+sum(b[i:])) print(ans)解答例N=int(input()) A=[0]+list(map(int,input().split()))+[0] cost=sum(abs(A[i+1]-A[i]) for i in range(N+1)) for i in range(1,N+1): print(cost-abs(A[i+1]-A[i])-abs(A[i]-A[i-1])+abs(A[i+1]-A[i-1]))解答例N=int(input()) A=list(map(int,input().split()))+[0] A.insert(0,0) cost=0 for i in range(N+1): cost+=abs(A[i+1]-A[i]) for i in range(1,N+1): print(cost-abs(A[i+1]-A[i])-abs(A[i]-A[i-1])+abs(A[i+1]-A[i-1]))解答例l=sorted(map(int,input().split())) a=2*l[2]-l[1]-l[0] print((a+3)//2 if a%2 else a//2)解答例n=int(input()) a=list(map(int,input().split())) c=0 for i in a: while i%2==0:i,c=i/2,c+1 print(c)範囲
解答例N,T=map(int,input().split()) t=list(map(int,input().split())) ans=0 for i in range(N-1): ans+=min(t[i+1]-t[i],T) print(ans+T)解答例a,b,c,d=map(int,input().split()) print(max(0,min(b,d)-max(a,c)))解答例a,b,c,d=map(int,input().split()) t=len(set(map(int,range(a,b+1)))&set(map(int,range(c,d+1))))-1 print("0" if t==-1 else t)文字列の回転
解答例print("Yes" if input() in input()*2 else "No")文字列の辞書順
解答例s=input() n=int(input())-1 print(s[n//5]+s[n%5])剰余算
解答例N=int(input()) ans=N for i in range(N+1): cnt=0 while i>0: cnt+=i%6 i//=6 j=N-i while j>0: cnt+=j%9 j//=9 ans=min(ans,cnt) print(ans)ABC111 B - AtCoder Beginner Contest 111
解答例N=int(input()) print((((N-1)//111)+1)*111)解答例N=int(input()) print(N//10*100+min(100,N%10*15)解答例print(-int(input())%int(input()))解答例a=int(input()) b=int(input()) print((((a//b)+1)*b-a) if a%b else "0")再帰
解答例N,X=map(int,input().split()) a,p=[1],[1] for i in range(N): a.append(a[i]*2+3) p.append(p[i]*2+1) def f(n,x): if n==0:return 0 if x<=0 else 1 elif x<=1+a[n-1]:return f(n-1,x-1) else:return p[n-1]+1+f(n-1,x-2-a[n-1]) print(f(N,X))数学観点
和差算
解答例a,b,c=sorted(map(int, input().split())) print(a+b+c*2**int(input()))解答例l=[int(_) for _ in input().split()] k=int(input()) print(sum(l)-max(l)+max(l)*2**k)ABC110 A - Maximize the Formula
解答例l=list(map(int,input().split())) print(sum(l)+max(l)*9)解答例print(eval('+'.join(sorted(input()))+'*10'))ABC111 A - AtCoder Beginner Contest 999
解答例print(1110-int(input()))数直線
解答例import bisect A,B,Q=map(int,input().split()) INF=10**18 S=[-INF]+[int(input()) for i in range(A)]+[INF] T=[-INF]+[int(input()) for i in range(B)]+[INF] for q in range(Q): x=int(input()) i=bisect.bisect_right(S,x) j=bisect.bisect_right(T,x) d=INF for s in [S[i-1],S[i]]: for t in [T[j-1],T[j]]: d1=abs(s-x)+abs(s-t) d2=abs(t-x)+abs(s-t) d=min(d,d1,d2) print(d)解答例N,M=map(int,input().split()) X=sorted(set(list(map(int,input().split())))) s=[] for i in range(M-1): s.append(X[i+1]-X[i]) s=sorted(s)[::-1] print(sum(s[N-1:]))ABC110 B - 1 Dimensional World's Tale
解答例N,M,X,Y=map(int,input().split()) xi=list(map(int,input().split())) yi=list(map(int,input().split())) xi.append(X) yi.append(Y) print("No War" if max(xi)<min(yi) else "War")円と長方形
解答例x,y,r=map(int,input().split()) a,b,c,d=map(int,input().split()) if a<=x-r and x+r<=c and b<=y-r and y+r<=d:print("NO") else:print("YES") if max((a-x)**2,(c-x)**2)+max((b-y)**2,(d-y)**2)<=r**2:print("NO") else:print("YES")座標
解答例sx,sy,tx,ty=map(int,input().split()) ans=[] for i in range(ty-sy): ans.append("U") for i in range(tx-sx): ans.append("R") for i in range(abs(sy-ty)): ans.append("D") for i in range(abs(sx-tx)): ans.append("L") ans.append("L") for i in range(ty-sy+1): ans.append("U") for i in range(tx-sx+1): ans.append("R") ans.append("D") ans.append("R") for i in range(abs(sy-ty)+1): ans.append("D") for i in range(abs(sx-tx)+1): ans.append("L") ans.append("U") print("".join(ans))解答例s=input() d=abs(s.count("L")-s.count("R"))+abs(s.count("U")-s.count("D")) q=s.count("?") if int(input())==1:print(d+q) else:print(max(len(s)%2,d-q))解答例x1,y1,x2,y2=map(int,input().split()) x=x2-x1 y=y2-y1 print(x2-y,y2+x,x1-y,y1+x)面積
解答例h,w=map(int,input().split()) pattern=[h//2+w//3+1,h//3+w//2+1,h,w] if h%3==0 or w%3==0: pattern+=[0] if h%2==0: pattern+=[h//2] if w%2==0: pattern+=[w//2] print(min(pattern))ABC047 B - すぬけ君の塗り絵 2 イージー / Snuke's Coloring 2 (ABC Edit)
解答例w,h,n=map(int,input().split()) b=c=0 for _ in range(n): x,y,a=map(int,input().split()) if a==1:b=max(b,x) if a==2:w=min(w,x) if a==3:c=max(c,y) if a==4:h=min(h,y) print(max(0,(w-b))*max(0,(h-c)))解答例w,h,n=map(int,input().split()) l=[[int(j) for j in input().split()] for i in range(n)] b=c=0 for i in range(n): x,y,a=l[i][0],l[i][1],l[i][2] if a==1:b=max(b,x) if a==2:w=min(w,x) if a==3:c=max(c,y) if a==4:h=min(h,y) print([(w-b)*(h-c),0][(w<b)|(h<c)])解答例a,b,c=map(int,input().split()) print(a*b//2)解答例a,b,c=map(int,input().split()) print(2*(a*b+b*c+c*a))倍数
ABC100 B - Ringo's Favorite Numbers
解答例D,N=map(int,input().split()) l=[int(pow(100,D)*i) for i in range(1,N+1)] print(l[N-1])約数
- 約数：Divisor
サンプルコードN=int(input()) divisor=[] for i in range(1,N+1): if N%i==0:divisor.append(i) print(divisor)解答例N=int(input()) count=0 for i in range(105,N+1,2): divisor=0 for j in range(1,i+1): if(i%j==0):divisor+=1 if(divisor==8):count+=1 print(count)素数
- 素数：Prime number
サンプルコードN=int(input()) print("Prime" if all([N%i for i in range(2,int(N**.5)+1)]) else "Not prime")解答例N=int(input()) print("YES" if all([N%n for n in range(2,int(N**.5)+1)]) else "NO")解答例N=int(input()) print("YES" if all([N%n for n in range(2,N)]) else "NO")解答例N=int(input()) print("NO" if any([N%n==0 for n in range(2,N)]) else "YES")解答例N=int(input()) S=sum(n for n in range(N+1)) flag=0 for s in range(2,S): if S%s==0: flag=1 print("WANWAN" if flag==0 and N!=1 else "BOWWOW")解答例N=int(input()) flag=1 if N==1:flag=0 elif N==2 or N==3 or N==5:flag=1 elif N%2==0 or N%3==0 or N%5==0:flag=0 else:flag=1 print("Prime" if flag==1 else "Not Prime")素因数分解
- 素因数分解：Factoring
サンプルコードfor num in range(2,10): i=num Factoring=[] flag=True while flag: for j in range(2,num+1): if i%j==0: i=i/j if i==1:flag=False Factoring.append(j) break if len(Factoring)==1:print(num,"is a prime") else:print(num,Factoring)約数の個数
ある整数 $ x $ が素因数分解によって $ x= p^n × q^m × ... (p,q,...は素数) $ と表される時、 $ x $ の約数の個数は $ (n+1) × (m+1) × ... $ となる。
解答例N=int(input()) e=[0]*(N+1) for i in range(2,N+1): cur=i for j in range(2,i+1): while cur%j==0: e[j]+=1 cur//=j def num(m):return len(list(filter(lambda x:x>=m-1,e))) print(num(75)+num(25)*(num(3)-1)+num(15)*(num(5)-1)+num(5)*(num(5)-1)*(num(3)-2)//2)ABC067 C - Factors of Factorial
解答例import math N=math.factorial(int(input())) i=2 ans=1 M=10**9+7 while i*i<=N: cnt=1 while N%i==0: cnt+=1 N//=i ans*=cnt i+=1 if N!=1:ans*=2 print(int(ans%M))順列
- 順列：permutation
_4 P _2 = 4 \times 3 = 12通りサンプルコードfrom itertools import permutations List=["a","b","c","d"] print(list(permutations(List,2))) # [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'a'), ('b', 'c'), ('b', 'd'), ('c', 'a'), ('c', 'b'), ('c', 'd'), ('d', 'a'), ('d', 'b'), ('d', 'c')] print(len(list(permutations(List,2)))) # 12サンプルコードfrom itertools import permutations List=["a","b","c","d"] print(list(permutations(List,2))) # [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'a'), ('b', 'c'), ('b', 'd'), ('c', 'a'), ('c', 'b'), ('c', 'd'), ('d', 'a'), ('d', 'b'), ('d', 'c')] print(len(list(permutations(List,2)))) # 12解答例from itertools import permutations n,m,l=map(int,input().split()) P=list(map(int,input().split())) v=0 for p,q,r in permutations(P): v=max(v,(n//p)*(m//q)*(l//r)) print(v)組み合わせ
- 組み合わせ：combination
_4 C _2 = \frac{_4 P _2}{2!} = 6通りサンプルfrom itertools import combinations List=["a","b","c","d"] print(list(combinations(List,2))) # [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')] print(len(list(combinations(List,2)))) # 6解答例from itertools import combinations S=map(int,input().split()) print(sorted(map(sum,combinations(S,3)))[-3])解答例from itertools import combinations from collections import Counter N=int(input()) S=Counter() for i in range(N): S[input()[0]]+=1 print(sum([S[a]*S[b]*S[c] for a,b,c in combinations("MARCH",3)]))解答例K=int(input()) print((K//2)*((K+1)//2))経路
\frac{(width+height -2)!}{(width-1)!(height -1)!}解答例from math import factorial W,H=map(int,input().split()) m=10**9+7 print(factorial(W+H-2)*pow(factorial(H-1)*factorial(W-1)%m,m-2,m)%m)色塗り
ABC046 B - AtCoDeerくんとボール色塗り / Painting Balls with AtCoDeer
解答例n,k=map(int,input().split()) print(k*(k-1)**(n-1))重複組み合わせ
サンプルコードfrom itertools import combinations_with_replacement List=["a","b","c","d"] print(list(combinations_with_replacement(List,3))) # [('a', 'a', 'a'), ('a', 'a', 'b'), ('a', 'a', 'c'), ('a', 'a', 'd'), ('a', 'b', 'b'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'c'), ('a', 'c', 'd'), ('a', 'd', 'd'), ('b', 'b', 'b'), ('b', 'b', 'c'), ('b', 'b', 'd'), ('b', 'c', 'c'), ('b', 'c', 'd'), ('b', 'd', 'd'), ('c', 'c', 'c'), ('c', 'c', 'd'), ('c', 'd', 'd'), ('d', 'd', 'd')] print(len(list(combinations_with_replacement(List,3)))) # 20ABC011 D - 大ジャンプ
ABC021 D - 多重ループ直積
サンプルコードfrom itertools import product A=["a","b","c"] X=["x","y","z"] for p in product(A,X): print(p) # ('a', 'x') # ('a', 'y') # ('a', 'z') # ('b', 'x') # ('b', 'y') # ('b', 'z') # ('c', 'x') # ('c', 'y') # ('c', 'z')サンプルコードfrom itertools import product A=["a","b","c"] X=["x","y","z"] for a,x in product(A,X): print(a,x) # a x # a y # a z # b x # b y # b z # c x # c y # c zサンプルコードfrom itertools import product for p in product("357",repeat=3): print("".join(p)) # 333 # 335 # 337 # 353 # 355 # 357 # 373 # 375 # 377 # 533 # 535 # 537 # 553 # 555 # 557 # 573 # 575 # 577 # 733 # 735 # 737 # 753 # 755 # 757 # 773 # 775 # 777確率
- 未分類
ABC024 D - 動的計画法
ABC028 D - 乱数生成期待値
解答例n,m=map(int,input().split()) print((1900*m+100*(n-m))*2**m)解答例print((int(input())+1)*5e3)数列の和
f(x) = \sum_{1}^n x = \frac{n(n + 1)}{2}サンプルコードn=int(input()) print(n*(n+1)//2)サンプルコードn=int(input()) print(n*-~n//2)サンプルコードprint(sum(range(int(input())+1)))解答例a, b = map(int, input().split()) n = b - a print(n*(n+1)//2-b)ABC043 A - キャンディーとN人の子供イージー / Children and Candies (ABC Edit)
解答例n=int(input()) print(n*(n+1)//2)連立方程式の解
2x+3y+4z=10 （0≦x<20, 0≦y<30, 0≦z<40）サンプルコードList=[(x,y,z) for z in range(40) for y in range(30) for x in range(20) if 2*x+3*y+4*z==10] print(List) # [(5, 0, 0), (2, 2, 0), (3, 0, 1), (0, 2, 1), (1, 0, 2)] List=list(map(list,set(List))) print(List) # [[2, 2, 0], [3, 0, 1], [0, 2, 1], [5, 0, 0], [1, 0, 2]] print(len(List)) # 5
- 解に条件がある場合
2x+3y+4z=10 （0≦x<20, 0≦y<30, 0≦z<40, x+y+z=4）サンプルコードList=[(x,y,z) for z in range(40) for y in range(30) for x in range(20) if 2*x+3*y+4*z==10 and x+y+z==4] print(List) # [(2, 2, 0), (3, 0, 1)] List=list(map(list,set(List))) print(List) # [[3, 0, 1], [2, 2, 0]] print(len(List)) # 2連立方程式の解の個数
2x+3y+4z=10 （0≦x<20, 0≦y<30, 0≦z<40）サンプルコードprint([2*x + 3*y + 4*z for z in range(40) for y in range(30) for x in range(20)].count(10)) # 5サンプルコード# 1はdummy変数 print(len([1 for x in range(20) for y in range(30) for z in range(40) if 2*x+3*y+4*z==10])) # 5x+y+z=S （0≦x, y, z<k≦2500）（0≦S<3K）サンプルコードs=7000 k=2500 # 1はdummy変数 print(len([1 for y in range(k) for x in range(k) if 0<=s-x-y<=k])) # 124750サンプルコードs=7000 k=2500 # 1はdummy変数 print([1 for y in range(k) for x in range(k) if 0<=s-x-y<=k].count(1)) # 124750ABC051 B - Sum of Three Integers
平方根の整数部と小数部の算出
y = x^{1/2} （a：整数部, b：小数部）サンプルコードa,b=divmod(5,2) print(a) # 2 print(b) # 1サンプルコードx=2 y=x**.5 # 平方値 print(y) # 1.4142135623730951 # 整数部 a=int(y) print(a) # 1 # 小数部 b=y-a print(b) # 0.41421356237309515解答例print(int(int(input())**.5)**2)相加相乗平均
\frac{a+b}{2} ≧ \sqrt{ab}解答例print(int(input())**2//4)解答例n=int(input()) print((n//2)*(-(-n//2)))ユークリッド距離
distance(\boldsymbol{x},\boldsymbol{y}) = \sqrt{\sum_{i=1}^n(x_i - y_i)^2}\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}ARC004 A - 2点間距離の最大値 ( The longest distance )
解答例p=[list(map(int,input().split())) for i in range(int(input()))] print(max(((a[0]-b[0])**2+(a[1]-b[1])**2)**.5 for b in p for a in p))解答例import math p=[list(map(int,input().split())) for i in range(int(input()))] print(max(math.hypot(a[0]-b[0],a[1]-b[1]) for b in p for a in p))解答例N=int(input()) p=[] for i in range(N): x,y=map(int,input().split()) p.append([x,y]) d=0 for i in range(N): for j in range(N): if i!=j:d=max(d,((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**.5) print(d)マンハッタン距離
distance(\boldsymbol{x},\boldsymbol{y}) = \sum_{i=1}^n|x_i - y_i||x_1 - x_2| + |y_1 - y_2|解答例n,m=map(int,input().split()) ab=[[int(j) for j in input().split()] for i in range(n)] cd=[[int(j) for j in input().split()] for i in range(m)] for a,b in ab: l=[abs(a-c)+abs(b-d) for c,d in cd] print(l.index(min(l))+1)解答例n,m=map(int,input().split()) a=[[int(j) for j in input().split()] for i in range(n)] c=[[int(j) for j in input().split()] for i in range(m)] for i in range(n): d=10e8 b=0 for j in range(m): if abs(a[i][0]-c[j][0])+abs(a[i][1]-c[j][1])<d: d=abs(a[i][0]-c[j][0])+abs(a[i][1]-c[j][1]) b=j+1 print(b)ヘロンの公式
S = \sqrt{s(s-a)(s-b)(s-c)} \\ s = \frac{a+b+c}{2}ヘロンの公式 - Wikipedia
ABC002 C - 直訴解答例x1,y1,x2,y2,x3,y3=map(int,input().split()) a=((x1-x2)**2+(y1-y2)**2)**.5 b=((x2-x3)**2+(y2-y3)**2)**.5 c=((x3-x1)**2+(y3-y1)**2)**.5 s=(a+b+c)/2 print((s*(s-a)*(s-b)*(s-c))**.5)コラッツ予想
f(n) = \left\{ \begin{array}{ll} n / 2 & (if\;\;n=0) \\ 3n + 1 & (if\;\;n=1) \end{array} \right.コラッツの問題 - Wikipedia
ABC116 B - Collatz Problem解答例S=int(input()) l=[] while (S not in l): l.append(S) if S%2==0:S//=2 else:S=3*S+1 print(len(l)+1)必要十分条件
P \rightarrow Q解答例x,y,r=map(int,input().split()) a,b,c,d=map(int,input().split()) if a<=x-r and x+r<=c and b<=y-r and y+r<=d:print("NO") else:print("YES") if max((a-x)**2,(c-x)**2)+max((b-y)**2,(d-y)**2)<=r**2:print("NO") else:print("YES")アルゴリズム観点
ユークリッドの互除法
- 2つの自然数の最大公約数を求める手法
サンプルコードwhile y!=0: x,y=y,x%y解答例a,b,n=(int(input()) for _ in range(3)) while n%a!=0 or n%b!=0:n+=1 print(n)最大公約数
- GCD：Greatest Common Divisor
サンプルコードfrom functools import reduce from fractions import gcd x=[15,25,30] print(reduce(gcd,x)) # 5解答例from functools import reduce from fractions import gcd N,X=map(int,input().split()) x=[abs(X-int(i)) for i in input().split()] print(reduce(gcd,x))ABC118 C - Monsters Battle Royale
解答例import functools,fractions n=input() a=list(map(int,input().split())) print(functools.reduce(fractions.gcd,a))最小公倍数
- LCM：Least Common Multiple
解答例from fractions import gcd def lcm(a,b): return a*b//gcd(a,b) N=int(input()) ans=1 for i in range(N): t=int(input()) ans=lcm(ans,t) print(ans)ABC118 C - Monsters Battle Royale
解答例import functools,fractions n=input() a=list(map(int,input().split())) print(functools.reduce(fractions.gcd,a))解答例a,b,n=(int(input()) for _ in range(3)) while n%a!=0 or n%b!=0:n+=1 print(n)DP
- DP：Dynamic Programming（動的計画法）
解答例N,M=map(int,input().split()) A=list(map(int,input().split())) d=[0]*N*9+[-1]*N*9 for i in range(1,N+1):d[i]=max(d[i-int("0255456376"[a])]*10+a for a in A) print(d[N])解答例N,M=map(int,input().split()) A=list(map(int,input().split())) weight=[0,2,5,5,4,5,6,3,7,6] dp=[-1]*(N+1) dp[0]=0 for i in range(N+1): for a in A: if i+weight[a]<N+1: dp[i+weight[a]]=max(dp[i+weight[a]],dp[i]*10+a) print(dp[N])解答例N=int(input()) A=list(map(int,input().split()))+[0] dp=[0]*N dp[1]=abs(A[1]-A[0]) for i in range(1,N-1): dp[i+1]=min(dp[i]+abs(A[i+1]-A[i]),dp[i-1]+abs(A[i+1]-A[i-1])) print(dp[N-1])解答例N=int(input()) NG=[int(input()) for i in range(3)] dp=[float("INF")]*301 dp[N]=0 for i in range(N,0,-1): if i in NG:continue for j in range(1,4): dp[i-j]=min(dp[i]+1,dp[i-j]) print("YES" if dp[0]<=100 else "NO")
- 未解答
DFS
- DFS：Depth First Search（深さ優先探索）
- 未解答
BFS
- BFS：Breadth First Search（幅優先探索）
解答例h,w=map(int,input().split()) sy,sx=map(int,input().split()) gy,gx=map(int,input().split()) grid=[list(input()) for x in range(h)] grid[sy-1][sx-1]=0 loc=[[sy-1,sx-1]] for k in range(1,h*w): next_loc=[] for y,x in loc: for i,j in ([1,0],[-1,0],[0,1],[0,-1]): if grid[y+i][x+j]=='.': grid[y+i][x+j]=k next_loc.append([y+i,x+j]) loc=next_loc if [gy-1,gx-1] in loc: break print(k)UnionFind
解答例N = int(input()) def dfs(s): if int(s)>N: return 0; ret = 1 if all(s.count(c) > 0 for c in "753") else 0 for c in "753": ret += dfs(s+c) return ret print(dfs("0"))
- 未解答
ABC040 D - 道路の老朽化対策について
ABC075 C - Bridge
ABC054 C - One-stroke Path
ABC015 C - 高橋くんのバグ探ししゃくとり法
解答例N,K=map(int,input().split()) S=[int(input()) for i in range(N)] length=left=0 mul=1 if 0 in S: length=N else: for right in range(N): mul*=S[right] if mul<=K: length=max(length,right-left+1) else: mul//=S[left] left+=1 print(length)解答例(TLE)N,K=map(int,input().split()) S=[int(input()) for i in range(N)] length=0 if 0 in S: length=N else: for i in range(N): for j in range(i+1,N): mul=1 for k in range(i,j+1): mul*=S[k] if mul<=K: length=max(length,j-i+1) print(length)解答例N=int(input()) A=list(map(int,input().split())) diff=0 ans=N for i in range(N-1): if A[i]<A[i+1]: diff+=1 ans+=diff else: diff=0 print(ans)全探索
ABC045 C - たくさんの数式 / Many Formulas
解答例S=input() ans=0 for i in range(len(S)): for j in range(i+1): ans+=int(S[-(i+1)])*(10**j)*(2**(len(S)-1))//(2**min(i,j+1)) print(ans)解答例S=input() ans=0 for i in range(2**(len(S)-1)): tmp=S[0] for j in range(len(S)-1): if i&(1<<j):tmp+="+" tmp+=S[j+1] ans+=eval(tmp) print(ans)解答例N=int(input()) F=[int(input().replace(' ',''),2) for i in range(N)] P=[list(map(int,input().split())) for i in range(N)] print(max(sum([p[bin(f&i).count('1')] for f,p in zip(F,P)]) for i in range(1,2**10)))解答例n,k=map(int,input().split()) x=sorted(list(map(int,input().split()))) print(min((min(abs(x[i])+abs(x[i+k-1]-x[i]),abs(x[i+k-1])+abs(x[i]-x[i+k-1]))) for i in range(n-k+1)))解答例n,k=map(int,input().split()) x=sorted(list(map(int,input().split()))) a=[] for i in range(n-k+1): l=x[i] r=x[i+k-1] a.append(min(abs(l)+abs(r-l),abs(r)+abs(l-r))) print(min(a))解答例N=int(input()) T=sorted(int(input()) for i in range(N))[::-1] x=y=0 for t in T: if x<y:x+=t else:y+=t print(max(x,y))解答例x,y=map(int,input().split()) k=int(input()) print(x+y-abs(k-y))
- 未分類
ABC002 D - 派閥
ABC018 D - バレンタインデー
ABC031 D - 語呂合わせ
ABC039 D - 画像処理高橋君
ABC075 D - Axis-Parallel Rectangle貪欲法
解答例N=int(input()) NG=[int(input()) for i in range(3)] if N in NG: print("NO") exit() for i in range(100): N-=3 if N in NG: N+=1 if N in NG: N+=1 if N in NG: print("NO") exit() print("YES" if N<=0 else "NO")解答例A=list(map(int,input().split()))+[0] ans=0 for i in range(N): eated=max(0,A[i]+A[i-1]-x) ans+=eated A[i]-=eated print(ans)最大フロー
- 未分類
エラトステネスのふるい
- 未解答
ワーシャル–フロイド法
- 未解答
クラスカル法/プリム法
- 未解答
計算量観点
ソート
解答例N=int(input())%30 X=[1,2,3,4,5,6] for i in range(N): tmp=X[i%5+1] X[i%5+1]=X[i%5] X[i%5]=tmp print(*X,sep="")解答例(TLE)N=int(input()) X=[1,2,3,4,5,6] for i in range(N): tmp=X[i%5+1] X[i%5+1]=X[i%5] X[i%5]=tmp print(*X,sep="")つるかめ算
解答例N,M=map(int,input().split()) if 2*N<=M<=4*N: y=M%2 z=((M-3*y)-2*(N-y))//2 x=N-y-z print(x,y,z) else: print("-1 -1 -1")解答例(TLE)N,M=map(int,input().split()) for x in range(N+1): for y in range(N+1): z=N-x-y if 2*x+3*y+4*z==M and z>=0: print(x,y,z) exit() print("-1 -1 -1")いもす法
解答例n,m=map(int,input().split()) imos=[0]*(m+1) t=0 for i in range(n): l,r,s=map(int,input().split()) imos[l-1]+=s imos[r]-=s t+=s for i in range(m): imos[i+1]+=imos[i] print(t-min(imos[:-1]))解答例N,Q=map(int,input().split()) O=[0]*(N+1) for i in range(Q): l,r=map(int,input().split()) O[l-1]+=1 O[r]-=1 for i in range(N): if i>0:O[i]+=O[i-1] print(O[i]%2,end="") print()解答例(TLE)N,Q=map(int,input().split()) O=[0]*N for i in range(Q): l,r=map(int,input().split()) for j in range(l,r+1): O[j-1]+=1 for i in range(N): if O[i]%2==0: O[i]=0 else: O[i]=1 print(*O,sep="")解答例N=int(input()) n=10**6+1 x=[0]*(n+1) for i in range(N): a,b=map(int,input().split()) x[a]+=1 x[b+1]-=1 for i in range(n): x[i+1]+=x[i] print(max(x))
- 未分類
累積和
解答例N=int(input()) A=list(map(int,input().split())) S=sum(A) T=[0]*N for i in range(N-1): T[i+1]=T[i]+A[i] print(min(abs(S-2*T[i]) for i in range(1,N)))解答例(TLE)N=int(input()) A=list(map(int,input().split())) print(min(abs(sum(A[:i])-sum(A[i:])) for i in range(1,N)))解答例N=int(input()) S=input() cnt=S.count("E") m=cnt for i in S: if i=="E": cnt-=1 else: cnt+=1 m=min(m,cnt) print(m)
- 未分類
二分探索
解答例import bisect A,B,Q=map(int,input().split()) INF=10**18 S=[-INF]+[int(input()) for i in range(A)]+[INF] T=[-INF]+[int(input()) for i in range(B)]+[INF] for q in range(Q): x=int(input()) i=bisect.bisect_right(S,x) j=bisect.bisect_right(T,x) d=INF for s in [S[i-1],S[i]]: for t in [T[j-1],T[j]]: d1=abs(s-x)+abs(s-t) d2=abs(t-x)+abs(s-t) d=min(d,d1,d2) print(d)解答例import bisect N,M=map(int,input().split()) X,Y=map(int,input().split()) A=list(map(int,input().split())) B=list(map(int,input().split())) ans=0 time=0 while time<=A[-1]: time=A[bisect.bisect_left(A,time)]+X if time<=B[-1]: time=B[bisect.bisect_left(B,time)]+Y ans+=1 else:break print(ans)解答例import bisect N=int(input()) A=sorted(list(map(int,input().split()))) B=sorted(list(map(int,input().split()))) C=sorted(list(map(int,input().split()))) print(sum(bisect.bisect_left(A,b)*(N-bisect.bisect_right(C,b)) for b in B))解答例(TLE)from collections import Counter N=int(input()) A=Counter(input().split()) B=Counter(input().split()) C=Counter(input().split()) ans=0 for a_key,a_count in A.most_common(): for b_key,b_count in B.most_common(): for c_key,c_count in C.most_common(): a_key,b_key,c_key=int(a_key),int(b_key),int(c_key) if a_key<b_key and b_key<c_key: ans+=a_count*b_count*c_count print(ans)
- 未分類
ABC023 D - 射撃王
ABC026 D - 高橋君ボール1号
ABC034 D - 食塩水中央値の算出
解答例N=int(input()) X=list(map(int,input().split())) S=sorted(X) b=S[N//2] a=S[(N//2)-1] for i in X: print(b if i<b else a)解答例N=int(input()) X=list(map(int,input().split())) s=[] for i in range(N): s=sorted(X[:i]+X[i+1:]) print(s[N//2-1])条件式によるループ回数削減
解答例x=int(input()) c=1 for b in range(1,x): for p in range(2,x): if b**p<=x:c=max(c,b**p) else:break # b**pがx以上は計算を省く print(c)解答例(TLE)x=int(input()) c=1 for b in range(1,x): for p in range(2,x): if b**p<=x:c=max(c,b**p) print(c)集計から除算に変換
ABC048 B - Between a and b ...
解答例a,b,x=map(int,input().split()) print(b//x-(a-1)//x)解答例(TLE)a,b,x=map(int,input().split()) print(sum(1 for i in range(a,b+1) if i%x==0))処理中の剰余算(10*n+7)
解答例from math import factorial W,H=map(int,input().split()) m=10**9+7 print(factorial(W+H-2)*pow(factorial(H-1)*factorial(W-1)%m,m-2,m)%m)解答例import math N,M=map(int,input().split()) print(max(2-abs(N-M),0)*math.factorial(N)*math.factorial(M)%(10**9+7))解答例a,b,c=0,0,1 for i in range(int(input())-1): a,b,c=b,c,(a+b+c)%10007 print(a)解答例(TLE)a,b,c=0,0,1 for i in range(int(input())-1): a,b,c=b,c,a+b+c print(a%10007)方程式
解答例N,Y=map(int,input().split()) for x in range(N+1): for y in range(N-x+1): z=N-x-y if 0<=z<=2000 and 10000*x+5000*y+1000*z==Y: print(x,y,z) exit() print(-1,-1,-1)キュー
- キュー：Queue
解答例N=int(input()) A=list(map(int,input().split())) print(*A[::-2],*A[N%2::2])解答例(TLE)N=int(input()) A=list(map(int,input().split())) B=[] for i in range(N): B.append(A[i]) B=B[::-1] print(*B)部分数列の総和
解答例N,K=map(int,input().split()) A=list(map(int,input().split())) print(sum(A[i]*min(i+1,K,N-i,N-K+1) for i in range(N)))解答例(TLE)N,K=map(int,input().split()) A=list(map(int,input().split())) print(sum(sum(A[i:i+K]) for i in range(N-K+1)))用語
AtCoder用語集
ハーシャッド数
- 各位の数字和が元の数の約数にある自然数
解答例n=input() print("No" if int(n)%sum(map(int,n)) else "Yes")リュカ数
- 初項（最初のリュカ数）を 2、次の項を 1 と定義し、それ以降の項は前の2つの項の和になっている数列
L_0 = 2, L_1 = 1L_{n+2} = L_n + L_{n+1}解答例a,b=2,1 for i in range(int(input())): a,b=b,a+b print(a)解答例n=int(input()) l=[2,1] for i in range(2,n+3): l.append(l[i-2]+l[i-1]) print(l[n])トリボナッチ数列
L_0 = 0, L_1 = 0, L_2 = 1L_{n} = L_{n-1} + L_{n-2} + L_{n-3}解答例a,b,c=0,0,1 for i in range(int(input())): a,b,c=b,c,a+b+c print(a)参考記事/サイト
実装観点
- 2進数・8進数・10進数・16進数の相互変換についてまとめてみた
- Pythonビギナーズガイド（変数・配列編）
- pythonで三項演算子のネスト
- 【Python入門】いまさらだけどパイソニスタとして必要な文法を網羅してみた
- 【Python入門】for文でのin演算子の使い方とは?
- Python ビット演算 超入門
- Pythonの集合演算
- Python リストのメソッド
- pythonの内包表記を少し詳しく
- 【Python】ソート
- Pythonで2次元配列の重複行を一発で削除する
- Python標準で転置行列
- Pythonのリスト、タプル、辞書
- [Python]リスト、タプル、辞書、集合の違い
- 正規表現操作
- Pythonでの正規表現の使い方
- Pythonの正規表現モジュールreの関数match、search、sub
- itertoolsによる順列、組み合わせ、直積のお勉強
- 組み込み関数
- [python] いろいろな文字種のリストを作成
- Pythonで文字列が数字か英字か英数字か判定・確認
- 高階関数の使い方！Pythonでreduceを使う方法【初心者向け】
- Pythonで大文字・小文字を操作する文字列メソッド一覧
- Pythonでタプルやリストをアンパック（複数の変数に展開して代入）
計算量観点
関連サイト
AtCoder情報
- AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問
- AtCoder コンテストについての tips
- AtCoder に登録したら解くべき精選過去問 10 問 をPythonで解いてみた
- AtCoderでの勉強の仕方（コンテスト編）
競技プログラミング情報
レート情報
緑色
水色
- あの水色ってきれいだよね。(競プロ!! AdC)
- AtCoderで水色になるまでにやったこと
- AtCoderで水色になるまでにしたこと
- AtCoderで水色になるまでにやった事とかをまとめる
- AtCoderのレートが水色になるまでにやったこと
- AtCoderで水色になりました
- AtCoder で水色になるまでを振り返る
- AtCoder水色になるまでにやったこと
青色
- PythonでAtCoder青になるまで -Pythonで競プロやるときに気をつけること-
- AtCoder 青になったのでブログをはじめました
- AtCoderで青色になるまでにやった事とかをまとめる
- AtCoderで青色になるまでにやったこと
- AtCoderで青色になった話
黄色
コーディング規約
PEP 8 -- Style Guide for Python Code
[Pythonコーディング規約]PEP8を読み解くマークダウン記法
変更管理
1.0版：2019年02月26日（火）
- 初版公開
1.1版：2019年03月03日（日）
- 本記事に「変更管理」項目（本項目）を追加（変更管理をするため）
- divmod追加（平方根の整数部と小数部の算出、組み込み関数）
- string.ascii_lowercase追加（文字の集合）
- 問題追加（ABC-D問題114, 115, 118, 119）
- 記載修正（ABC063 B - Varied⇒ABC063 A - Restricted）
- スペル修正（入力処理、Raw⇒Row）
- スペル修正（利用規約、AtCode⇒AtCoder）
- スペル修正（約数、Prime⇒Divisor）
- 「記事の更新方針」項目に「AGC-A問題の追加」を追加（AGCコンテスト対策として）
- 投稿日：2019-02-26T15:05:35+09:00
コピペで始める Spring Boot
Spring Bootをいちから始めるヒト向けに、とりあえずコピペしたらなんか動く、ってのを目標に記事にしてみます。基本 Building a RESTful Web Service を参考にしています。
環境
$ sw_vers ProductName: Mac OS X ProductVersion: 10.14.3 BuildVersion: 18D109$ mvn --version Apache Maven 3.6.0 (97c98ec64a1fdfee7767ce5ffb20918da4f719f3; 2018-10-25T03:41:47+09:00) Maven home: /usr/local/Cellar/maven/3.6.0/libexec Java version: 1.8.0_25, vendor: Oracle Corporation, runtime: /Library/Java/JavaVirtualMachines/jdk1.8.0_25.jdk/Contents/Home/jre Default locale: ja_JP, platform encoding: UTF-8 OS name: "mac os x", version: "10.14.3", arch: "x86_64", family: "mac" $いわゆるふつうのMacですが、Mavenさえあれば Windowsでもほぼ同じ手順で動かせると思います。
あと疎通をcurlでおこないます。
$ curl --version curl 7.54.0 (x86_64-apple-darwin18.0) ... $やってみる
まず pom.xmlを下記からコピペで作成しましょう。
$ mkdir myproject && cd $_ $ cat pom.xmlpom.xml<?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> <modelVersion>4.0.0</modelVersion> <groupId>com.example</groupId> <artifactId>myproject</artifactId> <version>0.0.1-SNAPSHOT</version> <parent> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-parent</artifactId> <version>2.1.3.RELEASE</version> </parent> <!-- Additional lines to be added here... --> <dependencies> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-web</artifactId> </dependency> </dependencies> <!-- (you don't need this if you are using a .RELEASE version) --> <repositories> <repository> <id>spring-snapshots</id> <url>https://repo.spring.io/snapshot</url> <snapshots><enabled>true</enabled></snapshots> </repository> <repository> <id>spring-milestones</id> <url>https://repo.spring.io/milestone</url> </repository> </repositories> <pluginRepositories> <pluginRepository> <id>spring-snapshots</id> <url>https://repo.spring.io/snapshot</url> </pluginRepository> <pluginRepository> <id>spring-milestones</id> <url>https://repo.spring.io/milestone</url> </pluginRepository> </pluginRepositories> <properties> <java.version>1.8</java.version> </properties> <build> <plugins> <plugin> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-maven-plugin</artifactId> </plugin> </plugins> </build> </project>sourceとpropertiesファイルを配置するディレクトリを作成します。
$ mkdir -p src/main/java $ mkdir -p src/main/resourcesSpring Bootを起動するおまじないが書いたファイルを作成します。
$ cat src/main/java/nu/mine/kino/springboot/SampleTomcatApplication.javaSampleTomcatApplication.javapackage nu.mine.kino.springboot; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; @SpringBootApplication public class SampleTomcatApplication { public static void main(String[] args) { SpringApplication.run(SampleTomcatApplication.class, args); } }WEB機能を記述した、下記のControllerを作成します。
$ cat src/main/java/nu/mine/kino/springboot/GreetingController.javaGreetingController.javapackage nu.mine.kino.springboot; import java.util.concurrent.atomic.AtomicLong; import org.springframework.web.bind.annotation.RequestMapping; import org.springframework.web.bind.annotation.RequestParam; import org.springframework.web.bind.annotation.RestController; @RestController public class GreetingController { private static final String template = "Hello, %s!"; private final AtomicLong counter = new AtomicLong(); @RequestMapping("/greeting") public Greeting greeting( @RequestParam(value = "name", defaultValue = "World") String name) { return new Greeting(counter.incrementAndGet(), String.format(template, name)); } } class Greeting { private final long id; private final String content; public Greeting(long id, String content) { this.id = id; this.content = content; } public long getId() { return id; } public String getContent() { return content; } }環境設定を記述する、propertiesファイルを作成します。
$ cat src/main/resources/application.propertiesapplication.propertiesserver.compression.enabled: true server.compression.min-response-size: 1 server.connection-timeout=5000 server.port=8080 server.address=0.0.0.0server.portは起動するポート番号。デフォルトの8080でよければ実際は記述不要です。
server.addressは他のマシンからも繋がるようにするためのおまじないです。起動
さあ、起動しましょう。
$ pwd /xxxxx/xxx/myproject $ mvn spring-boot:run ばばーーっていろいろ表示されて、、 ... 2019-02-26 14:03:46.797 INFO 40644 --- [ main] n.m.k.s.SampleTomcatApplication : Started SampleTomcatApplication in 4.749 seconds (JVM running for 11.845) ってでてればOK！起動したら別のプロンプトから疎通してみます。
$ curl http://localhost:8080/greeting {"id":1,"content":"Hello, World!"} $めでたく動きましたね！
起動したSpring BootのWEBサーバ(Tomcatですが)は Ctrl-Cなどで止めてあげましょう。
おつかれさまでした。おまけ
jar化する
$ mvn clean packageで、Tomcat込みの実行可能なjarファイルができます。
$ java -jar target/myproject-0.0.1-SNAPSHOT.jarとすることで、先の
mvn spring-boot:runと同じようにTomcatが起動します。。Eclipseで読み込む
$ mvn eclipse:clean eclipse:eclipseで .project/.classpath ファイルが出来るのでEclipseにインポートできるようになります。
戻り値のJSONを整形して返すようにする
application.properties に以下の設定を追加します。
$ cat src/main/resources/application.propertiesapplication.properties... spring.jackson.serialization.indent-output=trueCtrl-Cして
mvn spring-boot:runで再起動してからcurlで繋いでみると、、、$ curl http://localhost:8080/greeting { "id" : 1, "content" : "Hello, World!" }JSONが整形されました。。
関連リンク
- Spring Boot 公式
- Building a RESTful Web Service
- Developing Your First Spring Boot Application
- Appendix A. Common application properties application.properties の設定可能な項目一覧。