【AtCoder】AtCoder Beginner Contest 215 (A~D) 参戦記

AtCoder Beginner Contest 215に出場した

先週のABC214に出場したあと,くじかつに毎日参加して実戦力を鍛えた

そのおかげで今回もレートを上げることができた

結果

順位:8537人中2542位

得点:1000点(5)

ペナルティ付き最終解答時間:69:18

パフォーマンス:972

※()内の数字はWAの回数

各問題の結果
得点 WA回数 解答時点での経過時間
A 100点 0 1:08
B 200点 0 2:59
C 300点 0 8:00
D 400点 5 44:18
E 500点 - -
F 600点 - -

レート変化

917→923 (+6)

f:id:monhime:20210821230705j:plain

f:id:monhime:20210821230708j:plain

解答

A-Your First Judge

A - Your First Judge

問題要約

文字列$ S $ が与えられるので,この文字列が"Hello,World!"と完全に一致するなら"AC",そうでないなら"WA"と出力せよ。

解答

やるだけ

コードを見る(クリックして下さい)

ABC215_A

 

Submission #25192580 - AtCoder Beginner Contest 215

B-log2(N)

B - log2(N)

問題要約

正の整数$ N $が与えられるので,$ 2^k \leq N $となる最大の整数$ k $ を求めて下さい。

制約

$ 1 \leq N \leq 10^{18} $

$N $は整数

解法

問題のタイトルがもう「対数使って求めろ」っていているが,math.ceil(math.log(N, 2))を使うと浮動小数点誤差でミスりそう。

なので$ k = 0 $ から愚直にループした。

浮動小数点数での計算は出力の説明に「絶対誤差または相対誤差が〇〇であれば許容する」みたいなことが書いてある場合だけにしたい。

解答

コードを見る(クリックして下さい)

ABC215_B

 

Submission #25197854 - AtCoder Beginner Contest 215

C-One More aab aba baa

C - One More aab aba baa

問題要約

文字列$ S$ の各文字を並び替えて作ることができる可能な文字列を辞書順に全て列挙した時,前から$ K $番目にくる文字列を求めよ。

制約

$ 1 \leq |S| \leq 8$

$ S $ は英小文字のみからなる

$ S $ の各文字を並び替えてできる文字列は$ K$ 種類以上存在する。

解法

文字の順列リスト→各要素を文字列に変換して辞書順にソート→k種類目を出力

pythonのitertoolsのpermutationsやcombinations,combinations_with_replacement,productはけっこう便利なので使えるようにしよう

解答

コードを見る(クリックして下さい)

ABC215_C

 

Submission #25205791 - AtCoder Beginner Contest 215

D-Coprime 2

D - Coprime 2

問題要約

長さ$ N $の正の整数列$ A = (A_1,\,A_2,\,....,\,A_N) $が耐えられるので,以下の条件を満たす$ 1$以上$ M $以下の整数$ k $ を全て求めよ。

条件

全ての$1\leq i \leq N $を満たす整数$ i $について,$gcd(A_i,\,k)=1$である。

制約

$ 1 \leq N,\,M \leq 10^5$

$ 1 \leq A_i \leq 10^5$

入力は全て整数

解法

$ A $の全ての要素を素因数分解し,出現した素因数を全て記録する。

$1 $~$m$までの各数字について,記録した素因数のうち$m$以下のもので割り切れなければ条件を満たす。

↑2文目の工程の計算量についてだけど,意外と間に合った

解答

エラトステネスの篩のコードは下の記事のものを一部改変して,素因数リストを全てのAの要素で共有できるようにした。

素因数分解とかエラトステネスの篩(ふるい)とかのメモ - 唯物是真 @Scaled_Wurm

コードを見る(クリックして下さい)

ABC215_D.py

 

Submission #25225827 - AtCoder Beginner Contest 215

感想

2回連続でレートがあがっていい調子

緑パフォのままで停滞してもいいので,継続的に楽しめるようにしたい