Go to Qiita Advent Calendar 2024 Top
LoginSignup
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@takeu-com

ABC190振り返り

Posted at

ABC189 より、Atcoderコンテストの振り返りを実施することにしました。
色々な方からアドバイスをいただけるということのありがたさを実感。継続していきたいと思います！

前回の振り返り：
https://qiita.com/takeu-com/items/fa4fe0c481aca48cae5d

状況

ABC189前で、ギリギリ茶コーダーです。
今回のコンテストで、緑コーダーに上がるはず。。。！

image.png

↓自分のアカウントです。
https://atcoder.jp/users/takeucom

結果

結果は、A,B,C,Dを解き終わりました。
E問題を解く力がまだない。。。

ただ、開始から異様にPCが遅く、まさかの開始15分くらいでPCの電源が切れるという。。。orz
何やら、macだと、電源のワット数が足りない場合、充電されないことがあるらしく、本日osアップデートしたことによる弊害かもしれない。。。
※別のPCを使って、続けることはできましたが。。。

image.png

※この記事を書いているときに、緑色に上がったことがわかりました！
image.png

前回の改善ポイント

  • Pythonではなく、PyPyを使用する。
    • 振り返り記事をあげた際にアドバイスいただいて、実践してみました！おかげさまで、TLEに悩まされることがめっちゃ減りました！！(@c-yanさん、@ether2420さんありがとうございます！）
  • 割り算をする際には気をつける。（できる限り、割り算は使用しないようにする。）

各問題の解法と振り返り

A: Very Very Primitive Game

これは、さっとやり方を考えました。
A == B の時だけ、順番が関係あるな。と言うことで、以下のロジックにしました。

A, B, C = list(map(int, input().split()))
 
winA = A > B or (A == B and C == 1)
 
print('Takahashi' if winA else 'Aoki')

B: Magic 3

最初は、トータルのダメージ数だと思ってしまって、少し間違えましたが、確認中に気づいたので、すぐに修正してOKでした。
ダメージを与えることのできる条件を考えれば、OKですね。

N, S, D = list(map(int, input().split()))
 
can_atack = False
for _ in range(N):
  x, y = list(map(int, input().split()))
  if x < S and y > D:
    can_atack = True
    break
 
print('Yes' if can_atack else 'No')

C:Bowls and Dishes

この問題は、 K が最大でも 16であることに気付いたことが大きかったです。
Kが16くらいであれば、 $2^{16} = 65536 $ くらいであることを考えれば、bit全探索でいけるはず。
と言うことで、試してみたらいけました！pythonのままだったら、この辺りでTLE食らっていた気がする。。。

N, M = list(map(int, input().split()))
 
condition = []
for _ in range(M):
  a, b = list(map(int,input().split()))
  condition.append((a,b))
 
K = int(input())
ks = []
 
for _ in range(K):
  c, d = list(map(int,input().split()))
  ks.append((c,d))
 
max_count = 0
for i in range(2 ** K):
  s = [False] * N
  for j in range(K):
    if ((i >> j) & 1):
      s[ks[j][0] - 1] = True
    else :
      s[ks[j][1] - 1] = True
  count = 0
  for m in range(M):
    if s[condition[m][0] - 1] and s[condition[m][1] - 1]:
      count +=1
  if max_count < count:
    max_count = count
print(max_count)

D:Staircase Sequences

今回は、数学的な問題でしたね。大学受験の整数問題を彷彿とさせました。
数学は好きだったので、これは、もう少し早く解きたかった。。。

ざっくり考え方として、等差が1の等差数列の和が、初項 a, 項数 n とすると、公式から和の数式を導くことはできるので、その答えがNになると言うことを考えると、以下の式を満たす整数 a, n が存在すれば良い。

\frac{n}{2} (2a +(n-1)) = N

nは2次となることを考えて、aに係る式をたててみると何かわかりそうなので、数式を変換。

2a = \frac{2N}{n} - n + 1

となると、2aが整数となれば良いから、 以下の2つの条件を満たせば、整数aであることが成り立つ！

  • nは、2Nの約数
  • $2N/n - n + 1$ が偶数

と言うことで、まずは、何も考えずにプログラミングをしてみましたが、サンプル問題でTLEが起きる。今回は、Nの範囲が$10^{12}$だったので、ギリギリいけないかな。。。と思っていたけど、考えが甘かった。

N = int(input())

count = 0
for n in range(1, 2 * N + 1):
  if ((2 * N) % 2 == 0) and ((2 * N) // n - n + 1) % 2 == 0:
    count += 1
 
print(count)

n が 2N の約数 と言う条件を考慮すれば、もう少し処理するパターンを減らすことができそう。
と言うことで、約数検索方法は調べればありそうなので、調べてみたら、あったので、それを利用。

以下のサイトを参考にしたところ、TLE回避！（というか、最初はそのまま使ってしまいました。。。）

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
 
N = int(input())
 
divisors = make_divisors(2 * N)
count = 0
for n in divisors:
  if ((2 * N) // n - n + 1) % 2 == 0:
    count += 1
 
print(count)

これで投稿してしまいましたが、他人のコードそのまま使って、終わらしても勉強にならないな。と言うことで、ソースコードを確認してみたら、約数全探索するのであれば、 $\sqrt{2N}$ 分を調べれば、約数は全部調査できることに気づく。。。
素因数分解プログラムとか思い出せば、当たり前ですよね。。。

と言うことで、プログラムを修正して、再提出。ちゃんと通りました。

import math
 
N = int(input())
 
count = 0
check_max = math.floor(math.sqrt(2 * N))
for n in range(1, check_max + 1):
  if (2 * N % n == 0) and ((2 * N) // n - n + 1) % 2 == 0:
    count += 1
    tn = 2 * N // n
    if ((2 * N) // tn - tn + 1) % 2 == 0:
      count += 1
 
  
if check_max * check_max == 2 * N:
  if ((2 * N) // check_max - check_max + 1) % 2 == 0:
    count -= 1
 
print(count)

総括

まず、PCトラブルは絶対に避ける！ちゃんと、充電しておく！！と言うことは大前提として。。。

一旦、暫定の目標としていた緑コーダーにはなれた。次に目指すは、もちろん水色！
今の自分の状況を振り返ると、水色に上がるのはそれなりにハードルが高く。。。

  • A,B,C,D は安定的に解けているが、決して早いわけではない。
  • Eはチャレンジする前提の知識がなく、チャレンジすらできていない。

以下の記事を参考にすると、このままで行くと、実力的に緑色コーダーで留まることになりそう。。。
https://qiita.com/e869120/items/eb50fdaece12be418faa#2-1-%E6%B0%B4%E8%89%B2%E3%82%B3%E3%83%BC%E3%83%80%E3%83%BC%E3%81%A7%E8%A6%81%E6%B1%82%E3%81%95%E3%82%8C%E3%82%8B-4-%E3%81%A4%E3%81%AE%E3%81%93%E3%81%A8

【↑の記事で記載されている水色コーダーになるための条件】

  • AtCoder Beginner Contest で確率 8 割以上で 4 問正解できる
    • これは最近は大体できている。
  • AtCoder Beginner Contest で確率 3-4 割で 5 問正解できる
    • これが全くできていない。
  • AtCoder Beginner Contest の問題をある程度早く解くことができる
    • ここはちょっと課題。。。

以下のような対策を考えていきたいと思う。

アルゴリズムを全体的に理解し、使えるようにする。

割と感覚となんとなくの知識で進めてしまっているので、これは最重要課題だと思う。
↑のサイトにあるアルゴリズムについても、なんとなく知っている。。。程度。

この辺りの知識を使いつつ、問題Eにチャレンジする力をつけていく。

解くスピードを早くする。

スピードを早くすると言っても難しいが、そもそもpythonに触れる機会が少ない。
最近の仕事では、 TypeScript、今まで触れてきた一番の言語はJavaとそもそもそこまでなれていないことも原因の1つか。。。

また、問題の解き方も、AtCoderのコードテストのページを使っている。
デバッグ等も対応しづらいこともあるので、開発環境も整えたい。

まとめると、

次のAtCoderまでに対応したいこと

  • 開発環境を整える。
  • E問題を最低でも週に2問はとく。（その時は、どのアルゴリズムを使っていたかをしっかりと認識する。）
  • A-C問題を週に3-4問解く。（できれば、毎日。。。）

ここから上がるのは、小手先の技術だけだと難しそう。
せっかく楽しくなってきたし、勉強も頑張るようにしようー！

3
0
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?