AtCoder Beginner Contest (ABC) 227 Pythonで参戦しました。 C問題まで解説あり。
前回の参戦記録
こんばんは。めりーです。
最近雨がひどいです。
特に、自分が出かける日に限っていつも雨が降ります。
ままならないものですね。
というわけで、AtCoder Beginner Contest (abc) 227 参戦したので、参戦レポート的なの書いていきます。
言語はPython、提出はPyPyです。
目次
A問題 Last Card
Last Card
問題文
K枚のカードをN人に順番に配ります。
ただし、最初にカードを配るのは、A番目の人からです。
さて、最後のカードは何番目の人に配られるでしょうか。
という問題。
ちょっと沼った。
数学的に解ける問題かなーと思って、KをNで割ってAを足してみたりしたのですが、入力例が通らず・・・。
このまま考えたところで時間の無駄だと思ったので、愚直に問題文に書いてある通りに実装することに。
疑似的にカードを配ってみました。
というわけで、方針は、
1. 入力する。
2. k-1回ループを回す。
3. ループの中でAを+1していく。(Aがそのカード配られた人)
4. AがNを超えたらA-Nする。(AをNの範囲に収めるため。)
5. 最後にAを出力。
というわけで、コードは
n,k,a = map(int, input().split())
for i in range(k-1):
a += 1
if a > n:
a -= n
else:
print(a)
ループが1回回ると、カードを1枚配ったことになるようなコードです。
aが、カードを配られた人を表しています。
範囲がk-1なのは、1枚目のカードを配ったのがA番目の人なので、1枚は配り終わってることになってるからです。
そして、AがNよりも大きくなったばあい、AからNを引くことで、Aを1~Nの範囲に収めています。
そして最後にAを出力して終了です。
B問題 KEYENCE building
KEYENCE building
問題文
N人に敷地面積Sを予測させました。
敷地面積は4ab+3a+3bと表されます。
確実に間違っている予測をしている人は何人いますか？
ただし、a,bは正の整数しか取りません。
という問題。
これもそれなりに沼った。
全探索してNからSとしてあり得る分だけ-1するとか、Sとしてあり得る物をlistに入れてその長さとNを比較するとか試したんですが、うまくいかず。
原因は、予測値Siに重複が許されていることなのですが・・・。
というわけで、フラグを用意する方法でやりました。
配列を用意し、N個の1を格納します。
これがフラグです。
フラグが1であるときは、Sとしてあり得ないことを表しています。(最初はわからないので全部1)
そして、a,bの取り得る値を全探索し、それぞれにおいて、Siが4ab+3a+3bと一致した場合に、フラグを0にします。
そして、最後にフラグが1だった数を数えれば、Sとして確実に間違っている予測をしている人の数を割り出せる、という戦法です。
というわけで、これをまとめた方針です。
1. 入力する。
2. フラグを用意する。
3. 取り得るa,bを全探索する。
4. さらに、Siを全探索する。
5. Siが4ab+3a+3bと一致した場合に、フラグを0にする。
6. フラグが1の個数を数える。
というわけで、コードです。
n = int(input())
s = list(map(int,input().split()))
ans = [1]*n
for a in range(1,335):
for b in range(1,335):
for i in range(n):
if 4*a*b + 3*a + 3*b == s[i]:
ans[i] = 0
print(sum(ans))
解説です。
a,bの範囲が335なのは、Sの上限が1000だからです。
計算したところ、aが1、bが334を超えると、Sが1000を超えるっぽいです。
そして、Siが4ab+3a+3bと一致した場合、フラグを0にします。
最後に
フラグが1の数を数える = フラグを全て足す
なので(フラグの取り得る範囲が0,1のみのため)、ansを足して出力して終了です。
C問題 ABC conjecture
ABC conjecture
問題文
整数Nが与えられます。
A <= B <= Cかつ、ABC <= NとなるA、B、Cの総数を求めよ。
という問題。
滅茶苦茶いいとこまで行ったのですが、解けず。
ダメだったコードです。
n = int(input())
ans = 0
for a in range(1,int(n**(1/3)+1)):
for b in range(a,int(n**(1/2))+1):
for c in range(b,n+1):
if a*b*c <= n:
ans += 1
else:
break
print(ans)
3重ループです。
この、普通にやったコードはTLEになります。
まぁ、明らかに計算量間に合わないですよね。
次。
n = int(input())
ans = 0
for a in range(1,int(n**(1/3)+1)):
for b in range(a,int(n**(1/2))+1):
if n / (a*b) >= b:
ans += int((n / (a*b)) - b + 1)
else:
break
print(ans)
2重ループで、計算量を抑えるコード。
20個中、4個がWAになりました。なんでじゃ。
こういうバグの時は、端っこの場合(コーナーケース、全部1とか)が予期しない動作を引き起こしている場合が多いらしいので、チェックしたんですが、解決せず。
解決しないうちにコンテストが終了しました。
というわけでコンテストが終わり、解説を見ました。
解説
Editorial - KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227)
あれ、やってること、同じじゃね・・・？
計算量もあってね・・・？
なんでWA出るん・・・？？
と、思い、WAの出たコードの範囲を+1したコードを提出してみました。
n = int(input())
ans = 0
for a in range(1,int(n**(1/3)+2)):
for b in range(a,int(n**(1/2))+2):
if n / (a*b) >= b:
ans += int((n / (a*b)) - b + 1)
else:
break
print(ans)
ACしました。なんでだよ。
なんか、最大値の方のコーナーケースがバグってたっぽいですね。
これできるならコンテスト中がんばればACできてたじゃんか・・・。
というわけで方針を。
1. 入力する。
2. 2重ループで全探索する。
3. ansを足していく。
4. ansを出力する。
正解したコードを解説していきます。
n = int(input())
ans = 0
for a in range(1,int(n**(1/3)+2)):
for b in range(a,int(n**(1/2))+2):
if n / (a*b) >= b:
ans += int((n / (a*b)) - b + 1)
else:
break
print(ans)
Aが最大値を取るとき、B、Cを制約の中で可能な限り低くすることになります。
すると、Aが最大値を取るときは、A=B=Cとなります。
この時、制約はABC = A3 <= N となります。
なので、A = N1/3が範囲の最大値となります。
同様に、Bが最大値を取るとき、A、Cを制約の中で可能な限り低くすることになります。
すると、A = 1、C = Bが制約の中での最低値です。
すると、制約は、ABC = B2 <= Nとなります。
なので、B = N1/2がBの上限です。
というわけで、計算量を抑えることができます。
特に、今回の制約だと、N = 1011なので、計算量がO(N)だと、TLEになります。
※AtCoderでは、ループが108くらいまで回せる。
素数判定のアルゴリズムの応用的な方法ですね。
※素数判定では、O(√N)で計算可能
次に、ansに足す(n / (a*b)) - b + 1です。
A,Bがそれぞれ確定した時、Cの取り得る最大値は、制約から、C = N / (A×B) となります。
また、Cの最小値はB = Cです。
なので、A、Bが確定している状況下での、Cの取り得る個数は、最大値 - 最小値 + 1なので、
(n / (a*b)) - b + 1となります。
最後にansを出力して終了です。
C問題が頑張ればコンテスト中にACできただけに悔しい！！！
それでは！
