成長観察日記

競プロとかPythonとかに関しての成長記録

ABC278振り返り

2度目の3完!
Dも時間内にTLEでは通せたし、ほんの3行の違いだった
過去最高につよかった!!



A問題

atcoder.jp

問題概要

n個の数字に対して「最初のやつ消して、最後に0を追加する」をk回やってほしい

考察

  • 頭に0を追加してn個にしたものを反転しようとして「あ、違う」と気付いた。
  • まず、n(数字の数)よりk(操作の回数)が大きい場合は全部0になる。
  • そうでなくとも、最初のものは必ずk個消される、つまりk番目以降は必ずある。
  • そして、nまでの足りない分は0を追加すればよし。

コード

# 受け取り
n,k = map(int,input().split())
a = list(map(int,input().split()))

# nよりkがでかかった時
if n <= k:
  # 0をn個、半角スペース空けて出力したい
  # そうだ配列をアンパックして出力しよう!
  print(*[0]*n)
# nよりkがちっちゃかった時
else:
  # 「数列aのa[k]から先のものと、0をk個」を合体して出力
  print(*a[k:]+[0]*k)

感想

問題文が読めなかった(?!)久しぶりにAに5分以上かかり無念だ!!



B問題

atcoder.jp

問題概要

デジタル時計の「20:23」って表示、もし時と分の表示がタテに並んでたら「22:03」って見間違えちゃうよね。その時刻がありえないやつ…例えば「19:11」を見間違えて「11:91」だったら、びっくりしちゃうよね!もしそうだったら、次に迎える、見間違えてもびっくりしない時刻(20:00と20:00)を教えてー!

考察

  • まず、見間違えてもびっくりしない時刻の域を考える

    • 時間の2桁目 : 0〜2

    • 時間の1桁目 : 0〜5

    • 分の2桁目 : 0〜5

    • 分の1桁目 : なんでもおk(0〜9)

  • つまり、見間違えてびっくりするやつ

    • 6時〜9時、16時〜19時

    • 20時〜23時のそれぞれ40分以降

は、次の大丈夫な時刻を表示してあげればヨシ
見間違えてもびっくりしない時刻なら、そのまま出力してあげる

コード

# 受け取り
h,m = map(int,input().split())

# 6時〜9時
if 6 <= h <= 9:
  # 次のびっくりしない時間は10時00分
  print("10 0")
# 16時〜19時
elif 16 <= h <= 19:
  # 次のびっくりしない時間は20時00分
  print("20 0")
# 23時
elif 23 == h:
  # 40分以降は
  if 40 <= m:
    # 0時0分
    print("0 0")
  # 39分までは
  else:
    # そのままでもびっくりしない
    print(h,m)
# 20時〜22時の
elif 20 <= h:
  # 40分以降は
  if 40 <= m:
    # 時に+1の0分
    print(h+1,0)
  # 39分までは
  else:
    # びっくりしない
    print(h,m)
# 他は全部びっくりしない
else:
  print(h,m)

感想

むずくね???シミュレーションの方法が思いつかなかったから、丁寧に場合分けした。
そもそも問題を理解するまでに30分かかった!めっちゃお絵描きした!
Bに40分かかるなんてまだまだひよこだな(にわとり目線)
直前else忘れに気付けて本当によかった…!!



C問題

atcoder.jp

問題概要

SNSの闇データ…n人の人間たちのフォローとリムの記録をあげるよ。記録の最中、たまに「こいつら今、相互フォローしてる?」って聞くから、YesかNoかで答えてね。

考察

そうだフラグ管理をしよう!

例えば3人の記録

[

[0,0,0], // 1人目

[0,0,0], // 2人目

[0,0,0] // 3人目

]

1人目が2人目をフォローしたら

[

[0,1,0], // 1人目 が 2人目(2番目)をフォローした!

[0,0,0], // 2人目

[0,0,0] // 3人目

]

って感じにして、リムったら1を0にしよう

コード

# 都合のよく高速な(?!)辞書を使えるようにするライブラリを読み込む
from collections import defaultdict

# 受け取り
n,q = map(int,input().split())
# フォロー記録リストの二次元辞書をつくる
# n = 3なら [0,0,0],[0,0,0],[0,0,0]ってリストが作られるイメージ
# 辞書なので、重複処理は排除される
w = defaultdict(lambda :defaultdict(list))

# クエリ処理
for i in range(q):
  t,a,b = map(int,input().split())
  # インデックス管理楽にするために-1
  a -= 1
  b -= 1
  # クエリその1 aがbをフォローする
  if t == 1:
    w[a][b] = 1 # a人目のデータの中、b人目のフォロー状況チェックを1に
  # クエリその2 aがbをリムる
  elif t == 2:
    w[a][b] = 0 # a人目のデータの中、b人目のフォロー状況チェックを0に
  # クエリその3 相互フォローチェック
  elif t == 3:
    # a人目データの中 b人目のフォロー状況と、b人目データの中 a人目のフォロー状況が共に「1」だったら
    # (データを覗いた時「1」ならTrueだから、True and Trueで全体Trueになる)
    if w[a][b] and w[b][a]:
      print('Yes')  # ハッピーだね!Yes!
    else:
      print('No') # 片思い、または両方思ってないなら悲しいね、No

感想

やっぱりまだ計算量の計算が苦手で、n個の二次配列の中でn個の0をループして作って爆死。
TLE原因がわからないまま、連結リストチックなことappendでやって爆死
「そういえばなんかいい感じの辞書あった気がする…」と思い出し、自分のコードを引っ張り上げてAC!
でも実際まだdefaultdictのことよくわかってない。
TLEを阻止する要感まんまんだから、たまにはちゃんとpythonのお勉強をするーー!!
あと計算量も…アルゴ式…!!(依存)



D問題

atcoder.jp

問題概要

値がn個の数列に対して、以下処理を行なってくれよな

  • 処理1:全部yにする
  • 処理2:i番目にyを足す
  • 処理3:i番目を出力する

考察

言われたままやるしかねえっっ

コード

# いつもありがとう辞書
from collections import defaultdict

# 受け取り
n = int(input())
a = list(map(int,input().split()))
q = int(input())

for i in range(q):
  # クエリ番号をxとして入力
  # 残りは、1桁の時y[0] 2桁ならy[0]とy[1]として処理するためあんパック入力
  x,*y = map(int,input().split())
  # 処理その1
  if x == 1:
    ad = y[0] #置き換える数字を指定
    a = defaultdict(lambda:ad) #指定した数字をキーにして、数列を作り替える
  # 処理その2 指定されたindexに加算
  elif x == 2:
    a[y[0]-1] += y[1]
  # 処理その3 指定されたindexを出力
  elif x == 3:
    print(a[y[0]-1])

感想

まさかD問題があと一歩で解けるところまで来るとは…
コンテスト中のTLEコードとコンテスト後に他の人の提出見てACしたコードの比較、見てほしい

from collections import defaultdict #これを追加

n = int(input())
a = list(map(int,input().split()))
q = int(input())

for i in range(q):
  x,*y = map(int,input().split())
  if x == 1:
    # a = [y[0]]*n コンテスト中の敗因を
    ad = y[0] #これに書き換え
    a = defaultdict(lambda:ad) #これに書き換え
  elif x == 2:
    a[y[0]-1] += y[1]
  elif x == 3:
    print(a[y[0]-1])


計算量ダメだろうな〜ってわかってるのにダメ元で出してしまう、ってのが次に越えるべく壁だなあ
茶diffが解けるようになったの本当に嬉しい!成果〜〜!!

来週のburiodenは

これの昼公演行ったあと

stars-dreamlive.com

このライブに行き

はい、その後に
前回神の家で参加するも0完をした、因縁のトヨタコンに…出ます……(白目)