Category: AtCoder

概要 本記事は、2020/5/31に開催されたABC169のB,C問題を整理した内容を記載します。D問題までの回答を目指しているにもかかわらず、まさかのB,C問題でつまづいてしまいました。非常に不甲斐ない結果ですが、しっかりできなかったポイントを整理していきたいと思います。ただ、TwitterやYoutubeのコメントを見ていると同じようにB,Cで苦戦している人が多かったようなので、少しだけほっとしていました。 B – Multiplication2 問題 https://atcoder.jp/contests/abc169/tasks/abc169_b 解説 PDF https://img.atcoder.jp/abc169/editorial.pdf Youtube 理解 N個の整数Ajを全て掛け合わせして解を求めるという非常にシンプルな問題です。ポイントは2つあって、まず1つはAjは0になることがあるということ。もう1つはAjは最大で10の9乗であり、そのまま全てをかけるとオーバーフローを起こしてしまうということです。python3.0の場合は、int型が多倍長整数であるので基本的にメモリがある分は桁数を使用することができます。なので、単純に毎回掛けて10の18乗を超えていないかをチェックする処理で動作します。 実装 参考 – 任意精度演算 https://ja.m.wikipedia.org/wiki/%E4%BB%BB%E6%84%8F%E7%B2%BE%E5%BA%A6%E6%BC%94%E7%AE%97 C –

概要 本記事は、AtCoderのABC165に参加した際に回答することができなかったの問題を解説を読んで理解した内容を記載します。C問題で回答できなかったのは久しぶりだったので、しっかりと復習したいと思います。 問題 C – Many Requirementshttps://atcoder.jp/contests/abc165/tasks/abc165_c 解説 pdf https://img.atcoder.jp/abc165/editorial.pdf 動画(Youtube) 理解 まず計算量を考える部分ですが、数の組み合わせですが等しい数も選択することができるので、玉を並べてそれらに仕切りを置くようなイメージで算出します。具体的にはN個の仕切りとM-1個の玉からN個を選択するときの組み合わせが総数となります。なので、N+M-1 Choose N となり、今回の最大数は19 Choose 9なので92378通りで全探索でも問題ない処理量と考えられます。次に全探索のdfs関数についてですが、全探索を考えるときのポイントは以下の2つです。 一回のステップでどんな処理をすることで次につなげられるか 終了条件をどうするか

概要 コンテストの日から少し時間が空いてしまいましたが、2週間前？くらいに参加したABC163(2020/4/19)で相変わらずD問題がクリアすることができなかったので、復習のために解説を確認しながら、概念を理解してACするプログラムを実装しました。 問題 https://atcoder.jp/contests/abc163/tasks/abc163_d 解説 PDF https://img.atcoder.jp/abc163/editorial.pdf 動画(Youtube) 理解 まずM個の数である10^100の部分は非常に大きい数であるため、選択する数が変わると合計の値は他の数の組み合わせとは重複しないので、各選択した数の組み合わせによる合計値を求めれば算出可能となります。本問題でキーとなる部分は、M個からK個選ぶ場合の最大値は大きい方からK個選ぶ場合であり、最小値は小さい方からK個選ぶ場合となり、これらの最大値と最小値の間の値は全てを組み合わせで生成できるという点となります。したがって、作成できる数の総和は最大値-最小値で算出できます。次に、2つの連続するrからlまでの数の合計は、(l+r)*(r-l+1)/2で求めることができます。というポイントを抑えて実装すると下記のようになりました。 実装

まえおき 最初に記事の本題に入る前に前置きを書きたいと思います。去年くらいから新しくプログラミング言語を勉強していても実務で使用する機会がない言語でアウトプットする場がないと身につかないなと思い始めました。そこで色々考えていたのですが、ある時TwitterのTLでAtCoder(https://atcoder.jp/)という日本発の競技プログラミングが流行りはじめているのをみて興味を持ったのがきっかけでした。試しに参加してみたら割と簡単に参加できて、大体週一回開催というペースがあっているなと感じ少しづつ始めるようになりました。言語は最近勉強し始めていたPythonを使って参加しておりますが、数回参加して感じたのはプログラミング言語の問題や課題ではなく自分のアルゴリズム能力の無さでした。この課題は将来のためにも改善した方が良いと思い、より本腰を入れて毎週末の夜にABCのコンテストに参加するようになりました。ところが、参加するだけではなかなか能力の向上はないので、問題に臨んだけど解くことができなかった問題は回答や他の方の実装を参照して、自分なりの実装を作成するというのを始めることにしました。そして、その内容はなるべくブログで簡単にでもアウトプットしようと思っています。それの初回が本記事となります。また、時間があれば、アルゴリズムについてチーター本、蟻本、螺旋本あたりを読んでブログで整理できればと考えています。ということで、前置きが長くなりましたが、早速先週末(4/12)の夜に開催されたABC162のD問題が解けなかったので、その回答と自分なりの実装を本記事では記載します。 問題 ABC162 D問題 RGB Triplets https://atcoder.jp/contests/abc162/tasks/abc162_d 解説 https://img.atcoder.jp/abc162/editorial.pdf 理解 何も考えないで実装すると、i, j, kについて全探索で処理を行ってしまい計算量はO(N^3)となり、nは最大で4000なのでTLEしてしまいそうです。なので、方針として最初に”R”,”G”,”B”の3つが異なる組み合わせとなる総数を算出してから2つの条件にマッチしないものを引いていくことにします。その理由は、マッチしないパターンであれば問題文の2個目の条件でi, j, kの関係でi, jを固定するとkが算出できるので、その分を総数から引いてあげることができます。その場合の計算量はO(N^2)とすることができそうです。 実装例 自分が作成した実装は下記の通りとなります。