🐈

私のA問題奮闘記(ABC228)

2021/11/20に公開約1,800字1件のコメント

まずいです。

A問題が通りません!

解法が浮かびません!
えー、どうしましょう、、、

とりあいずBへ

B問題へ行ってから考えることとします。A問題はクソムズな可能性もあるので、点数デカい確実に解けるところから狙おうという魂胆です。

普通にBはBFSしました。(?)
BFSしか思いつかなかったけど、いい方法ありそうですよね。もしご存知でしたらコメントで教えていただけると幸いです。

Aへもどる

Aに戻りました。
まじでわからんかったので、この時点で綺麗に解くことは諦めています。
全探索してみたり、良くも知らない標準ライブラリを使ったり

s, t, x = map(int, input().split())
 
import datetime
 
s = datetime.datetime(1, 1, 1, hour = s)
t = datetime.datetime(1, 1, 2, hour = t)
x = datetime.datetime(1, 1, 1, hour = x, minute = 30)
 
if s < x < t:
    print("Yes")
else:
    print("No")

しましたが、なかなかACを得られません。

かなしい。

なかなか厳しそう

前回もA問題をなかなか通せなかったので、「またか・・・」と鬱にながらコーディングしています。鬱コードがこちら。

import datetime
 
s, t, x = map(int, input().split())
 
date1s = datetime.datetime(1, 1, 1, hour=s)
date1t = datetime.datetime(1, 1, 1, hour=t)
date1x = datetime.datetime(1, 1, 1, hour=x, minute=30)
date2s = datetime.datetime(1, 1, 2, hour=s)
date2t = datetime.datetime(1, 1, 2, hour=t)
date2x = datetime.datetime(1, 1, 2, hour=x, minute=30)
 
if date1s < date1x < date1t or date1s < date1x < date2t:
    print("Yes")
else:
    print("No")

はい。わからんですわね。

何を書いているのか自分でもわからんです。

競技プログラミングとは何だったのかって感じのコードに仕上がってしまいました。

結局、全探索が一番強い

全探索のコードを改良して通しました。
こちら

まとめ

ABCの3完でした。
書くの忘れてましたがCは途中で通してました。(
早く解放思いついたので、はやくA解けてれば3完内順位結構上がっててワンちゃんあったまるまでありました完全にA問題のせいです本当にありがとうございました
とはいえ、解けなかったのは完全に自分の実装力のたりなさ(というか発想力のたりなさ)のせいなので、これからも精進していきたいですね

急いで書いたので散文的になってしまいましたが、ここまでご覧頂きありがとうございました。


Discussion

B問題は同様に最初BFSで解きました.
ただ,別の解法もあるなぁと思っていろいろと考えていました(灰Diffなので簡単なのがあると思って)
(ここでは,1-indexedで表すことにします)
1.knowというリストを作成します.
定義:know[i] = i番目(1≦i≦N)の人が高橋君の秘密を知っていれば1,知っていなければ0
2. know[X] = 1とし,now = A[X]とします. (nowは次に調べる人を指します)
3. know[now] = 1 となるまで,以下のwhile文を繰り返します.
もし,know[now] = 0ならば, know[now] を1として, now = A[now] とする.
最後にknowの総和を出力する,という感じです.

実際の提出コードはURLからご確認下さい
ちなみにA問題は条件分岐でも解けるので時間があれば条件分岐で解いてみて下さい.

https://atcoder.jp/contests/abc228/submissions/27416773
ログインするとコメントできます