くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU

AtCoder Beginner Contest 179 参加ログ・感想

約数の数をカウントする方法素因数分解以外思いつかずC解けずOrz


内容

  • Python3でやっている。
  • 参加ログ。
  • 所感。
  • コンテスト中に何を考えたか。
  • コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
  • 問題の詳細で細かく書こうと思うものは別記事とする。
  • E以上はとりあえず現状自力では無理なのでDまで。解けるようになってきたら更新するかも

結果

AB完。Cは約数列挙はだめだから素因数分解だろと思ったけど計算量{\displaystyle O(N\sqrt{N})}になっちゃうのでダメ。全パターンの約数出すなら定数倍的に考えればよかった。


どう考えたか + α

A - Plural Form

問題タイプ:条件分岐 ・文字列操作

文字列の最後を取得するにはs[-1]とすればいいので、それで条件分岐。

s = input()
if s[-1] == 's':
    ans = s + 'es'
elif s[-1] != 's':
    ans = s + 's'
print(ans)

B - Go to Jail

問題タイプ:条件記述 ヒントで条件が書いてある。実装は、リストの3つめから考えて、2つ前、1つ前、今が全てゾロ目かを満たしていれば、Yesとする。

n = int(input())
D = [list(map(int, input().split())) for i in range(n)]
for i in range(2, n):
    if D[i-2][0] == D[i-2][1] and \
        D[i-1][0] == D[i-1][1] and \
            D[i][0] == D[i][1]:
                print('Yes')
                exit()
print('No')

A x B + C

問題タイプ:約数の個数のカウント

ある数の約数を数える場合は素因数分解を使えばいいが、今回は制約が大きいので、素因数分解して、全てのパターンを計算すると間に合わない。{\displaystyle N=i~N}なら定数倍的に考える方がいい。別記事にする。


D - Leaping Tak

問題タイプ:DP

動的計画法で解くが単純にやると、計算量が{\displaystyle O(N^2)}なので、移動方法が少ない区間の和を利用する必要がある。別記事にする。


おわりに

ABはできたが、Cも図表をかけば規則に気づけたと思うが、瞬間的に理解できないとまだまだだと思う。まだまだ問題を解く量が少ない。別の仕事も多くなかなか精進できないが、やれるだけやろう。