寺.py

フリーランスでソフトウェア開発してます。適当にプログラミングとかスタートアップとかについて書き垂らします

ABC 120 ただの感想

どうもーーーー


花粉。この一言で終えてしまってもなんら不足ない今日この頃。


殺してくれ〜〜〜!!!





さて、AtCoderのABCに参加しました。


今回は
A:音
B:割り切れる
C:箱
D:島と橋

というテーマでした。
(だから何)


ではここからただの感想


A:
高橋くんと出てきた時点でまず問題文に集中できない。

B円で聞ける最大回数と、C回を比べて小さいほうを出力しました。

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


A, B, C = LI()

result = B // A
print(min(result, C))



B:
約数が出てきた時点で吐き気を感じました。

とりあえず愚直に書きました。
両方を割り切れる数字を下から数えていってリストに格納。
ループしきったら大きい方からK番目を取るだけ。
最近はちゃんと制限を見て、これは全探索だとかなんとか一応考えながらやるようにしてます。
(この間のC問題の件もあるし)

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

A, B, K = LI()

nums = []
for i in range(1, 101):
    if A % i == 0 and B % i == 0:
        nums.append(i)

print(nums[-K])



C:
今回のC問題は箱ではありますが一切箱を意識しない問題でしたね。

最初、確認するのが面倒で、まあN<=10**5ぐらいならいいかーと思って提出したらTLEになったのでちゃんと考えました。

幸いすぐに0と1を数えて少ない方の数の2倍だと気づけたので通せました。

面倒ですが制限をみてちゃんと時間内にできるかも確認しながら最近はやるようには心がけています。
(コメントのような感じで)

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

S = S()
#  S = ''
#  for i in range(10**5):
#      if i % 2 == 0:
#          S += '011'
#      else:
#          S += '1'

# 0と1すくない方の数になる絶対
print(min(S.count('1'), S.count('0'))*2)


D:
端から解けるとは思っていませんが、毎度チャレンジします。
今回はデータ構造とかテクニカルなことはまだ準備できていないので、とりあえず愚直に書こうと思いました。

しかし実装でぐだり、愚直実装がようやく終了10分前とかにできて、そのあとこれは後ろから見れば良いのだと気づきました。

まあしかしその程度では到底間に合わんだろうということでジ・エンド


なんらかの木構造を使いたかったのですが、Union-Findその他データ構造は蟻本で眺めたことしかないので使えません。。



f:id:mktrdbg:20190303232739p:plain


もう8回も参加したのか。。。
今回はパフォ998の、レーティングプラス59でした。

そろそろ上がりづらくなってきたな〜。

来週再来週とAGCだし解けないし、一旦の目標である緑へはまだ2ヶ月ほどはかかりそうだ。

これからの方針として、C問題を重点的に対策することにしました。


というのも、A問題はまずプログラミング自体はできるのであまり勉強にならないので却下。

B問題も問題文のままの実装が多いため却下。

C問題は解けないときもままあるので、勉強になります。
アルゴリズムとかもいい感じででてくるし。


Dは難しすぎて今やる意味はあまりありません。

蟻本も難しすぎてあまり本気でやる効果は薄い状態です。


2ヶ月後には緑になりたいので精進します