先週に引き続きここ最近仕事が忙しい時期だったのと、JSの学習に重きを置いていたため、競プロの精進出来なかった1週間でしたが、ABC179に参戦してきました！
この記事は灰色コーダーの私がABCのC問題までを深く理解するために振り替える記事です。もしかしたら、同じくらいのレート帯(300前後)の方の参考になるかもしれないし、ならないかもしれないチラ裏記事です。
A – Plural Form
文字列の取り扱いと条件分岐の問題。
文字列の最終文字が”s”か否かを判定して、文字列に追加する文字を分岐させればOK。最終文字が”s”の場合は、”es”を追加して出力。”s以外”であれば”s”を追加して出力。
# AtCoder Beginner Contest 179
# A - Plural Form
S=input()
if S[-1]=='s':
print(S+'es')
else:
print(S+'s')B – Go to Jail
可変行の標準入力の受取と繰り返し処理の問題。
このタイプの標準入力の受取は競プロ始めたころの私はものすごく苦手でした。
今の私は標準入力自体をfor文で記述しています。
毎回サイコロの目がゾロ目であるかを判定して、ゾロ目であればカウンターを１つ増やして、ゾロ目ではなかった場合はカウンターをリセット。カウンターが3になったらそのセットでの出力は”Yes”になります。
私は、途中でカウンターが3以上になったら”Yes”を出力してプログラムを終了させるように記述しました。
# AtCoder Beginner Contest 179
# B - Go to Jail
N=int(input())
count=0
for i in range (N):
a,b=map(int,input().split())
if a==b:
count+=1
else:
count=0
if count>=3:
print('Yes')
exit()
print('No')C – A x B + C
数学的な考察と全探索の問題。
今回も！解けませんでした！
掛け算の組み合わせ個数は、素因数分解して、各素数の指数に+1した数を掛けた値が組合わせの個数ということがこのサイトを参考にして分かったので、素因数分解の関数をちょっと変形させて、A×B=N-CのN-Cが”1″(C=N-1)から”N-1″(C=1)となるAとBの組み合わせの個数を足し合わせていくプログラムです。
サンプルはすべて合うことは確認したのですが、実行時間が遅いようなので実行時間が早いと噂のpypyで提出して見事TLE！
計算量はCの全探索でO(N)、for文の中の関数でO(√N)なので、N=100000の場合、10**(6+3)で処理が自体が早ければギリギリ行けるか!?と思ってしまったのですね。
実際にコードテストでやれば試せば通らないことが確認できたのですが、お祈りで投げたら無事TLEしました。
計算量は10**9ということでC++とかなら通りそうだよな。と思って、PythonでC言語の速さを享受できるみたいなことを見聞きしたCythonを調べていたら時間切れでした。
(ちなみにC++だとこのような解法でも通ったみたいです。)
Cを全探索するやり方で考えていましたが、Aを全探索することで求まることが解説を見て理解しました。
この問題は、A×BがN未満(またはN-1以下)となる組み合わせは何個ありますか。と問われている問題としてみることができます。
この場合、Cはどこ行ったんだろう？と思っていたのですが、前述の「N未満」にCが隠れていることになります。C=1の場合A×B＝N-1となるAとBの組となり、C=Nの時にはA×Bが0になってしまうので、問題の性質上、C=N-1までのAとBの組み合わせ確認すれば良いことがわかります。
N-1以下になるAとBの組み合わせは、Aを固定すると、Bが取りえる値は、(N-1)//A(商の部分)となるので、Aを1からN-1まで全探索してすべて足せばOKです。
# AtCoder Beginner Contest 179
# C - A x B + C
N=int(input())
ans=0
for i in range (1,N):
ans+=(N-1)//i
print(ans)答え自体はあっていそうだったので、埋め込みで対応しようとしましたが、埋め込み用の答えを計算するのに、試しに20,000から30,000の答えを用意しようとしたら20分以上かかって無理でしたｗ
コメント