AtCoder Beginner Contest 267 メモ(A-D)
今回の結果
2AC
調子悪いのが続いてる。
Ratingも右肩下がり。
A - Saturday
Difficulty: 13
問題文
ある日、学校へ行くのに疲れてしまった高橋くんは、土曜日まであと何日あるかを知りたくなりました。
その日は平日で、曜日を英語で表すと
なお、月曜日、火曜日、水曜日、木曜日、金曜日はそれぞれ英語で Monday
, Tuesday
, Wednesday
, Thursday
, Friday
です。
制約
-
はS Monday
,Tuesday
,Wednesday
,Thursday
,Friday
のいずれかである
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを整数として出力せよ。
入出力例
入力例 1
Wednesday
出力例 1
3
入力例 2
Monday
出力例 2
5
参加中に考えたこと
if文を5つ並べて曜日ごとに対応する数値を選ぶようにするだけ。
B - Split?
Difficulty: 171
問題文
ボウリングのピンは
この図の二つの点線に挟まれた部分を列と呼ぶことにします。
例えば、ピン
いくつかのピンが倒れた状態のうち、特殊なものはスプリットと呼ばれます。
ピンの配置がスプリットであるとは、以下の条件が全て成り立つことを言います。
- ピン
が倒れている。1
ある二つの異なる列であって、次の条件を満たすものが存在する。 - それぞれの列には、立っているピンが
本以上存在する。1 - それらの列の間に、ピンが全て倒れている列が存在する。
具体例は入出力例を参考にしてください。
さて、あるピンの配置が長さ
0
であり、ピン 1
です。
制約
-
はS 0
と1
からなる長さ の文字列10
入力
入力は以下の形式で標準入力から与えられる。
出力
Yes
を、そうでないなら No
を出力せよ。
入出力例
入力例 1
0101110101
出力例 1
Yes
入力例 2
0100101001
出力例 2
Yes
入力例 3
0000100110
出力例 3
No
入力例 4
1101110101
出力例 4
No
参加中に考えたこと
問題文のスプリットの条件を順に判定していく。
まず、ピン No
を出力して終了。
次の2つの列ごとの条件については、まず図を見てそれぞれのピンがどの列に入っているか、そしてその列に立っているピンの有無の情報を持たせておいて、左側、右側、2つの列の間の3重ループでチェックする。
2重ループだと間の2列以上にピンがない場合の判定ができない。
C - Index × A(Continuous ver.)
Difficulty: 524
問題文
長さ
長さ
注記
数列の 連続部分列 とは、数列の先頭から
例えば
制約
1 \le M \le N \le 2 \times 10^5 - 2 \times 10^5 \le A_i \le 2 \times 10^5 - 入力は全て整数。
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
入出力例
入力例 1
4 2
5 4 -1 8
出力例 1
15
入力例 2
10 4
-3 1 -4 1 -5 9 -2 6 -5 3
出力例 2
31
参加中に考えたこと
それ以下の方法を考える必要がある。
問題は単純な部分和ではなくて
方向性がこれであってるのか分からず、30分ほど悩んでやっとこの方針で答えが出せそうな道筋が見えてきた。
入力例2において計算してみると、以下のようになる。
この性質に加えて、両端の考慮を入れて左端を1つ消して右端を1つ足してやれば
数式をで表すと、
となる。
ただし、
で求まるので
と、方針が決まってコードを書いたがほとんどのケースでWAになってしまい、時間が残っておらず終了。
考察・感想
原因はどこだろうとコードを見直してると、
累積和の配列をint型で持ってるとオーバーフローするのでは。。
入力の
long long 型に変えたらACした。。
マクロの作成や他の人のコードを見てて、全部long longで扱ってる人や、#define int long long
と書いて強制的にlong long を使うようにしている人を見たけど、ここで詰まってACできないのは勿体ないし、害になることはなさそうならその書き方を採用しようかな?
あとは上で考えていた数式のところは、
ともう少し綺麗にできた。
公式の解説を見ると、
全ての提出をいくつか見てるとどっちのやり方もあるけど公式と同じ考え方のほうが多いかな。
D - Index × A(Not Continuous ver.)
Difficulty: 864
問題文
長さ
長さ
注記
数列の 部分列 とは、数列から
例えば、
制約
1 \le M \le N \le 2000 - 2 \times 10^5 \le A_i \le 2 \times 10^5 - 入力は全て整数。
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
入出力例
入力例 1
4 2
5 4 -1 8
出力例 1
21
入力例 2
10 4
-3 1 -4 1 -5 9 -2 6 -5 3
出力例 2
54
参加中に考えたこと
C問題と似ているが異なるのは以下の2点。
- 連続部分列 → 部分列
-
の上限がM,N →2 \times 10^5 2000
全探索すると確実にTLEするのでこういう時はDPかなと思ったが、漸化式が思いつかなかった。
考察・感想
解き方が分からないので解説を読んで方針だけ見て、後はコードは悩まずに解けた。
漸化式が分かれば全然解ける問題だったな。
入力例2の場合のDPは以下のような感じになる。
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
-INF | -3 | 1 | 1 | 1 | 1 | 9 | 9 | 9 | 9 | 9 |
-INF | -INF | -1 | -1 | 3 | 3 | 19 | 19 | 21 | 21 | 21 |
-INF | -INF | -INF | -13 | 2 | 2 | 30 | 30 | 37 | 37 | 37 |
-INF | -INF | -INF | -INF | -9 | -9 | 38 | 38 | 54 | 54 | 54 |
C問題よりD問題のほうが簡単だという声がいくつがあったみたいだが、DPの中ではそんなに難しいものではないのでDPに慣れている人はそう感じたのかもしれない。
Discussion