完全に趣味でAtCoderを始めました。そこまでガチガチに頑張っているわけではないですが、できる限り、ABCには参加するようにしています。
より上位を目指していくために、受験したABCを毎回しっかり、振り返っていきます。。
自己紹介
ABC189直前の状態で、ギリギリ茶色コーダーです。ただ、コンテスト参加回数は11回なので、もう少しコンテスト受ければ、緑コーダーに上がれるか。。。とワクテカしていました。
ちなみに、ABCでは、A,B,Cは30分以内には解き終わって、残りの時間でD問題を目指す。と言うのが、最近の状況です。
E,Fを解けるようになる程勉強はしておらず、今年のどこかでチャレンジできるようにしていきたいです。
ちなみに、言語は python でやっています。
pythonの勉強がてら、競技プログラミングをやってみるか。と言うのが、最初のモチベーションです。
※ python の勉強はちゃんとしたことはないし、仕事で使ったこともない。なので、pythonの変数ルールとか、あまり守れていない。。。
↓自分のアカウントです。
https://atcoder.jp/users/takeucom
結果
A,B,D は解き終わりました。
ただ、今回は間違いが多かった。。。反省しまくりです。
その辺りを振り返りがてら、整理します。
各問題の解法と振り返り
A: Slot
1問目は特に問題なく完了。
s = input()
print('Won' if s[0] == s[1] == s[2] else 'Lost')
B: Alcoholic
2問目も特に問題なく完了。と思ったら、まさかの間違い。。。
NGプログラム
N, X = list(map(int, input().split()))
total = 0
ans = -1
for i in range(N):
v, p = list(map(int, input().split()))
total += v * p / 100
if total > X:
ans = i + 1
break
print(ans)
他の問題をある程度進めてから、振り返ってみると、割り算でもしかしたら、おかしいことになっているのでは？と気付き、割り算を使用しない方針に変更したところ、正解。
過去にpythonで割り算をしたところ、精度の問題で間違えたことがあったのに、ハマってしまった。 / 100 と言うキリが良い数で問題が起きるとは、盲点であった。。。
OKプログラム
N, X = list(map(int, input().split()))
total = 0
ans = -1
for i in range(N):
v, p = list(map(int, input().split()))
total += v * p # 割り算を使用しないようにする。
if total > X * 100: # 割り算をしない分、100を掛けるように変更
ans = i + 1
break
print(ans)
C:Mandarin Orange
問題を見たところ、全探索ならなんとなくかけそう。。。と思いましたが、
N=10^4 となっており、何も考えずに書くと、10^8くらいの計算量になりそうで、全探索がギリギリ難しいかもな。。。と言う問題。
一旦、D問題を解いた後に戻ってきました。
結論から言うと、 C++ だったら、解けていたっぽい。。。
一旦、ちょっと工夫した全探索で問題を書いてみるもののTLEになってしまった。。。
と言うところで、時間が来てしまったので、今回は解けず。。。
解説を見ると、ほぼほぼ同じ方法で解いている。。。
C++に変換してみると、普通に成功した。。。
Python:
N = int(input())
a = list(map(int, input().split()))
max_count = 0
for l in range(N):
x = a[l]
t_mac_count = x
for r in range(l, N):
if a[r] < x:
x = a[r]
c = x * (r - l + 1)
if c > t_max_count:
t_max_count = c
if t_max_count > max_count:
max_count = t_max_count
print(max_count)
C++:
#include<bits/stdc++.h>
using namespace std;
int a[10010];
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++)cin >> a[i];
int ans=0;
for(int l=0;l<n;l++){
int x=a[l];
for(int r=l;r<n;r++){
if(a[r] < x) {
x = a[r];
}
int c=x*(r-l+1);
ans=max(ans,c);
}
}
cout << ans;
}
D:Logical Expression
この問題は、紆余曲折があって、ようやく解けたので、その経緯を書いていきます。
bit全探索で解いてみる。
まずは、bit全探索で解いてみるが、当たり前の如くTLE...
N = int(input())
s = []
for _ in range(N):
s.append(input())
count = 0
for i in range(2 ** (N + 1)):
ans = i >> 0 & 1
for j in range(N):
x = i >> (j + 1) & 1
if s[j] == 'AND':
ans = ans and x
else:
ans = ans or x
if ans:
count += 1
print(count)
論理的に問題がある状態で解いてしまう。
次に、 OR で区切ることを考える。 ORで区切れば、区切ったブロックごとにその演算がTRUEになれば、全パターン網羅できたことになるのじゃないかな？と。
要は、
{...AND...AND...AND} OR {AND...AND...AND} ... と言う感じでブロックで区切ることを考えると、
1つのブロックが全てFALSEになるパターン数は求められるので、
全パターンから FALSE OR FALSE OR FALSE と全てFALSEになるケースを引けば、答えが出るんじゃないの！？と言うことで、プログラムを書いてみる。
例題では、正解が出たのですが、実際には間違い。。。
N = int(input())
false_pattern = 1
and_count = 1
for _ in range(N):
if input() == 'OR':
false_pattern *= 2 ** (and_count) - 1
and_count = 1
else:
and_count += 1
false_pattern *= 2 ** and_count - 1
print(2 ** (N + 1) - false_pattern)
bit全探索の結果と自作の問題を掛け合わせることによって、考え変えたの間違いに気づく。
何が違うんだ！と言うことで、自作の問題を作って、いくつか試してみるが、自分の考えとロジックは間違ってなさそう。
考え方が違うのかな？と言うことで、bit全探索で答えを出してみると、明らかに答えが違った。
ここで、考え方の間違いに気づく。
論理演算は前から演算していくから、そもそもブロックの考え方が間違っているじゃないか！
と言うことで、1から考えることに。。。
答えを導く。
順番に演算していく必要がある、と言うことを基にもう一度解き方を考えてみる。
- ANDが来たら、ANDの直前の結果がTrueで直後がTrueだったら、Trueになる。
- ORが来たら、ORの直前の結果がTrueで直後がTrue / False か、直前の結果がFalseで直後がTrueだった、Trueになる。
と言うことを思いつき、True / False のパターンの数をちゃんと数えていけば、計算量も少なく、結果が導けるのでは！？ と考え、早速書いてみたところ、うまくいく！！
N = int(input())
t = 1 # Trueとなるパターン数
f = 1 # Falseとなるパターン数
for _ in range(N):
if input() == 'OR':
t = t + f + t
f = f
else:
t = t
f = t + f + f
print(t)
総括
今回は、反省が残る結果に。。。とは言え、次への教訓はシンプルで、
- python だと計算量とか精度の問題で、不利である。
- 結果の確認は重要。簡単なパターンを自作で問題を考えて、ちゃんとチェックした方が良い。
と言うことで、次のABCでは、以下を実践しようと思う。
- 簡単な問題はpython。複雑そうな問題は、C++で解くようにする。
- 問題を間違えたら、自作の問題を数パターン作成して、確認するようにする。簡単であれば、全探索のプログラムを作った方が確実。