ABC 189 振り返り

完全に趣味で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++で解くようにする。
- 問題を間違えたら、自作の問題を数パターン作成して、確認するようにする。簡単であれば、全探索のプログラムを作った方が確実。