競プロ弱者の解答

競プロ弱者の成長記録

ABC129:水色競プロerのムーブ備忘録

競プロ大好きなsyunsukeです。

今回はABC129のムーブ備忘録です。

配点 A:100 B:200 C:300 D:400 E:500 F:600

制限時間 100分

コンテスト開始時のsyunsukeのレート 1309

今回の方針 特になし

 

コンテスト開始

A:なかなか開かないけどいつもよりまし?

 min(P+Q,Q+R,R+P)

 一応テストケースで確認して

 2:00 AC

B:なぜか軽くパニクる

 自分で慌ててるのがはっきりわかる

 ・Wの合計を出しておいて

 ・CNTを用意しておいて

 ・Wを順にCNTに足す、Wの合計からCNTを引いて、CNTと比べる

 の方針で行けそうだがなぜかパニクる

 仕方がないので、

 ・sumW(Wの合計)とcnt(初期値0)とans(初期値sumW)を用意

 ・Wを1つ取り出してはsumWからWを引く、cntにWを足す

 ・ansとabs(smW-cnt)を比べて、ansより小さくなれば更新

 で実装

 ひやひやしながらテストケースで確認して

 7:57AC

C:これは似たような問題を解いたことあります。

 ごちそうさまです!

 ようやく落ち着きました。

 リストdp[0~Nまで]を用意して、-1で初期化

 dp[0]とdp[1]を1にして

 通れないところは0

 あとは1つ前と2つ前を足しながら更新するだけ

 一応テストケースで確認して提出

 ジャッジを確認する理由はないので次へ

D:HxWのリストを用意して、中身は[0,0,0,0] #[左、上、右、下]

  左上から順に、見ている点が"."なら、[左の値+1,上の値+1,0,0]で更新

  右下から順に同じことをして、

  最後に[左、上、右、下]を足して3を引く

  これは簡単ですがめんどくさい

  とりあえずCのACを先に確認しておきましょう。

!!!!!

C:RE!

  よくわかりませんがpypyで提出したのがいけなかたのでしょう。

  時間的に間に合うとわかっているならpypyは避けたほうがよいのでしょう。

  5分のペナルティは痛いけど、良い勉強になりました。

  提出したものをコピーしてpython3で提出

  RE!!

  ???

  pypyとかpythonとかそんな問題ではない?

  コーナーケースを探しましょう。

  M=0のケース OK

  スタート地点がNGなケース 制約上なし

  ゴールがNGなケース 制約上なしandそれでも問題なく通せます。

  ???

  質問も無し

  よくわからないので、書いたコードは捨ててゼロから書き直しましょう。

  ・・・

  ・・・

  ・・・

  ACになってる

  pypyもpythonもACになってる

  質問もなんか出てる

  C:12:57AC

D:もうわけがわかりませんが、面倒なDの実装をすすめましょう。

  ・・・

  ・・・

  面倒ですが単純です。

  テストケースで確認して制約が大きいのでpypyで提出

  TLE

  まじで?

  入力を高速化してませんでしたね。

  import sys

  input=sys.stdin.readline

  これでどう?

  ・・

  TLE

  左上から数えて、右下から数えて、最後に[左、上、右、下]を集計してたのを

  右下から数えた直後に集計すれば速くなる?

  ・・

  TLE

  仕方がないので、C++で書き直しましょう。

  間に合いません。

  最初の提出31:35からTLEを解消できず、タイムアップ

  これpythonで通せるんでしょうか?

  強いpython使いの方のコードを見て学びましょう。

 

結局A,B,C3完 12:57 0WA  1486でパフォ1067  レートは-23で1286

ratedなのは納得いきませんが、Cのジャッジが正常でも、Dが通せない私にとって、Cのトラブルは関係ないので、むしろ救われているのかもしれません。

さっさと強いpython使いのコードを見に行きましょう。

もし強い人でもTLEなら、そろそろC++に移る時期かもしれません。