AtCoder Beginner Contest 187をPythonで解く

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 187を, Pythonで解いてみた結果を書き連ねていこうと思います.

AtCoder Beginner Contest 187 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - Large Digits

数字をint型に変換せず文字列で取得します. 文字列はリストのように○番目の文字を取り出すことができるので, それを利用して各桁の数字の合計を計算します. その後, 大小判定を行います.

B - Gentle Pairs

2つの点の組み合わせの全パターンを出し, それぞれに関して傾きが$-1$以上$1$以下であるかを計算します. 傾きの計算の際には$x$座標の差の絶対値と$y$座標の差の絶対値を比べるようにすれば, 整数の範囲内での計算で済みます.

C - 1-SAT

不満な文字列であるための必要条件として, その文字列は$S_1, S_2, \ldots , S_N$のどれかであるということが挙げられます. よって, $S_1, S_2, \ldots , S_N$に対して, それらの先頭に!を付けたものが$S_1, S_2, \ldots , S_N$に存在するかを確認します.

$S_1, S_2, \ldots , S_N$にある文字列が存在するのを確認する「item in seq」の演算にかかる時間計算量は, list型が$O(N)$でset型が$O(1)$です. したがって, set型で扱った方が実行時間が短くて済みます. 実際, list型で行うとTLEです.

D - Choose Me

$X$として$X = (\text{高橋氏の得票数} - \text{青木氏の得票数})$を考え, これが正になるかどうかを判定にします.

「高橋氏がある町で演説を行わなかった場合, その町の青木派は全員青木氏に投票し, 高橋派は投票に行きません」ので, $X$の初期値は$-1 \times (\text{全青木派有権者数})$です. そして, 「高橋氏がある町で演説を行った場合, その町の高橋派も青木派も全員高橋氏に投票します」ので, $i$番目の町で演説をした場合, $X$は$2A_i + B_i$だけ増加します.

したがって, $2A_i + B_i$の大きい順にソートして, 順番に加えていけばよいです. ソートに時間計算量が$O(N \log N)$だけかかります.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

• 「解説 - AtCoder Beginner Contest 187」
  Editorial - AtCoder Beginner Contest 187

  AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

• nkmk様による「Pythonで階乗, 順列・組み合わせを計算, 生成」
  Pythonで階乗, 順列・組み合わせを計算, 生成 | note.nkmk.me

  Pythonの数学関数の標準モジュールmathを使うと階乗を計算できる. これを利用して順列・組み合わせの総数を算出できる. SciPyの関数にも順列・組み合わせの総数を算出するものがある. また, itertoolsモジュールを使うとリスト（配列）などから順列・組み合わせを生成して列挙することができる. ここでは, 階乗: math.facto...

• nkmk様による「Python, set型で集合演算（和集合, 積集合や部分集合の判定など）」
  Python, set型で集合演算（和集合, 積集合や部分集合の判定など） | note.nkmk.me

  Pythonには標準のデータ型として集合を扱うset型が用意されている. set型は重複しない要素（同じ値ではない要素, ユニークな要素）のコレクションで, 和集合, 積集合, 差集合などの集合演算を行うことができる. 4. 組み込み型 set（集合）型 — Python 3.6.4 ドキュメント ここでは, 基本操作の, setオブジェクトの生成: {}...

• kitadakyou様による「Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由」
  Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由 - Qiita

  リストの中に特定の要素があるか探す処理 とある競技プログラミングで, 「大量の要素群の中に特定の要素が入っているかチェックする」といった処理を実装する必要がありました. 私は何も考えずに List 型で実装しました. 概ね同じ...

• nkmk様による「Pythonでリストをソートするsortとsortedの違い」
  Pythonでリストをソートするsortとsortedの違い | note.nkmk.me

  Pythonでリストを昇順または降順にソートするにはsort()とsorted()の2つの方法がある. 文字列やタプルをソートしたい場合はsorted()を使う. ここでは以下の内容について説明する. リスト型のメソッドsort(): 元のリストをソート 組み込み関数sorted(): ソートした新たなリストを生成 文字列, タプルをソートする方法 昇順・...