AtCoder-ABC179 C - A x B + C【Python解答例】
AtCoderの練習としてAtCoder Beginner Contest179の問題C A x B + Cに取り組みました。
atcoder.jp
AtCoder Beginner Contest179 C - A x B + C
問題文
正整数Nが与えられます。
A×B+C=Nを満たす正整数の組 (A,B,C) はいくつありますか？
制約
2≤N≤10^6
入力はすべて整数
解答例
# coding:utf-8 n = int(input()) count = 0 for i in range(n): if i == 0: count += n - 1 elif i == n: count += 0 elif n % (i + 1) != 0: count += n // (i + 1) else: count += n // (i + 1) - 1 print(count)
解説
問題文からA×BがNより小さい値なら必ずCは存在するといえます。
なので、Nより小さいAとBの組み合わせが何個あるかを求めればいいと思います。
AとBの組み合わせの数は、AとBの2重ループで簡単に求まりそうですが、
時間切れになると思ったので試していません。
（詳しい説明ができないです…勉強不足）
例えばN＝10、A＝3のときに条件にあてはまるBは1～3となります。
(A,B,C)=(3,1,7),(3,2,4),(3,3,1)
つまりNをAで割ったときの商の数が求める条件を満たすので、
その商を足し合わせていって答えを求めました。
4種類 条件分けとして、
①A=1の場合：(A,B)=(N,1)のときCが存在しないので、Nから1を引いた数を足しました。
②A＝Nの場合：①と同じ理由から、条件にあう組み合わせがありません。
③AでNが割り切れない場合：NをAで割ったときの商を足しています。
④AでNが割り切れる場合：例えばN=10、A＝2の場合、(A,B)=(2,5)ではCが存在しないので、NをAで割った商から1を引いています。
もっとシンプルに求めることもできるかもしれませんので、
ほかの方の解法など勉強したいと思います。
1からNまでの和
1からNまでの整数の和を求める方法は、
for文によるループ処理で求められます。
n = 10 # 1から10までの和を求める sum = 0 # 1からnまでの和の答え for i in range(n): sum += i + 1 # sum = 55
その他の方法として次の公式からも求められます。
n = 10 # 1から10までの和を求める sum = int(n * (n + 1) / 2) # 1からnまでの和の答え # sum = 55
どちらも同じ答えが求まりますが、for文では1からNまでの値を足し合わせるためN回計算を行うことになります。
競プロではプログラムの実行時間に制限があるため、計算量を減らす工夫が必要なる場合があります。
また、僕のようにプログラミング自体が遅い人はfor文を使うとさらに時間がかかってしまいますので、公式を使って解くように心掛けるようになりました。
競プロをされてる方々にはセオリーなのだと後から気づきましたが、僕はそんなことも知らずにコンテストに出てTLEが表示されてめちゃくちゃ焦りました。
そんな無謀なことを繰り返していますが、少しずつでも学んでいきたいと思います。
プライバシーポリシー
プライバシーポリシー
広告の配信について
当サイトは第三者配信の広告サービス「Googleアドセンス」を利用しています。
広告配信事業者は、ユーザーの興味に応じた広告を表示するために「Cookie（クッキー）」を使用することがあります。
Cookieを無効にする設定およびGoogleアドセンスに関して、詳しくはをこちらクリックしてください。
第三者がコンテンツおよび宣伝を提供し、訪問者から直接情報を収集し、訪問者のブラウザにCookie（クッキー）を設定したりこれを認識したりする場合があります。
ebisuke競プロ初心者脱出黙示録は、Amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイトプログラムである、Amazonアソシエイト・プログラムの参加者です。
アクセス解析ツールについて
当サイトでは、Googleによるアクセス解析ツール「Googleアナリティクス」を利用しています。
このGoogleアナリティクスはトラフィックデータの収集のためにCookieを使用しています。
このトラフィックデータは匿名で収集されており、個人を特定するものではありません。
この機能はCookieを無効にすることで収集を拒否することが出来ますので、お使いのブラウザの設定をご確認ください。
この規約に関して、詳しくはこちらをクリックしてください。
当サイトへのコメントについて
当サイトでは、スパム・荒らしへの対応として、コメントの際に使用されたIPアドレスを記録しています。
これはブログの標準機能としてサポートされている機能で、スパム・荒らしへの対応以外にこのIPアドレスを使用することはありません。
当サイトでは、次に掲げる内容を含むコメントは管理人の裁量によって承認せず、削除する事があります。
・特定の人または法人を誹謗し、中傷するもの。
・極度にわいせつな内容を含むもの。
・禁制品の取引に関するものや、他者を害する行為の依頼など、法律によって禁止されている物品、行為の依頼や斡旋などに関するもの。
・その他、公序良俗に反し、または管理人によって承認すべきでないと認められるもの。
免責事項
当サイトで掲載している画像の著作権・肖像権等は各権利所有者に帰属致します。権利を侵害する目的ではございません。
記事の内容や掲載画像等に問題がございましたら、各権利所有者様本人が直接メールでご連絡下さい。確認後、対応させて頂きます。
当サイトからリンクやバナーなどによって他のサイトに移動された場合、移動先サイトで提供される情報、サービス等について一切の責任を負いません。
当サイトのコンテンツ・情報につきまして、可能な限り正確な情報を掲載するよう努めておりますが、誤情報が入り込んだり、情報が古くなっていることもございます。
当サイトに掲載された内容によって生じた損害等の一切の責任を負いかねますのでご了承ください。
運営者：ebisuke33
初出掲載：2020年11月22日
