ABC143:水色競プロerのムーブ備忘録
本当に久々のコンテスト中のムーブ備忘録です。
Djangoのwebアプリ作りも楽しいですが、競プロはもっと楽しいですね。
レートが上がればですけれど。
今回はABC143のムーブ記録です。
〇配点 A:100 B:200 C:300 D:400 E:500 F:600
〇制限時間 100分
配点も時間もいつものABCですね。
〇コンテスト開始時のsyunsukeのレート 1246
〇今回の方針
基本前から解く。
ただし、はまったら順位表を確認して、次の問題を通す人が多ければ、次の問題を先に解く。
コンテスト開始！
A:問題文表示しろ！問題文表示しろ！問題文表示しろ！
01:49 AC
B:for ループ。ただし、重複しないように
d=map(list(int,input())
ans=0
for i in range(N-1):
for j in range(i+1,N):
ans+=d[i]*d[j]
print(ans)
04:18 AC
C:前のスライムと種類がかわる箇所の数を数える。
N=int(input())
S=list(input())
Color=""
ans=0
for i in range(N):
if N[i]!=Color:
ans+=1
Color=N[i]
print(ans)
08:10 AC ここまで順調
D:小さい順にソートする。
作る三角形の辺を小さいほうからA,B,Cとする。
A,Bをforループで回す。
bisectで、B<CかつA+B>Cを満たすCを探す。
書けば単純なんですが、実装に苦戦。
38:00 AC
この時点で順位は1200位を超えて、レートは1200割れ。
Eを解けなければレートダウン確定・・
E:とりあえずCがL以下なら、距離1としてワーシャルフロイド①。
テストケースを試したら・・
ダメです。
町1⇒町2⇒町3 を町2で給油せずに行けるケースがありますね。
前処理として今度は辺の距離をCとしてワーシャルフロイド②。
②で距離がL以下となった辺は1として、①のワーシャルフロイドを実行
pypyで提出・・TLE この時点で 66:55
ここで3択
１．pypyの高速化
何故か300^3を2回は無理と判断。
(せめてTLEの内訳を見ていれば・・)
２．C++で勝負
ワーシャルフロイドくらいなら書けるか？
３．scipyのライブラリを使用
scipyのワーシャルフロイドはC++で書いてあったはず。
ただ、使ったことないですけど。
私は３を選択しました。
ワーシャルフロイドがscipyに入っているのは知っていますが、使い方は知りません。ググってググって実装してRE出しながらもギリギリセーフ
97:06 AC 3ペナ
F:残り3分を切っていたので、開くことなくギブアップ
結局A,B,C,D,E 5完 97:03 +3ペナ
463位で パフォ1649 レートは+47 で1293
レートが上がってよろこんでいたのですが、あとでわかりました。
EのTLEしたpypyで、入力を高速化するための、
import sys
input=sys.stdin.readline
をしていませんでした。
TLEの内訳は、50のケース中2つがTLE
これを確認いれば、高速化の工夫に目が行き、入力の高速化忘れに気づけたでしょう。
これを怠ったために、30分+2ペナ分のロスが生じました。
もっと稼げていたレートを無駄にしてしまいました。
今回の反省点：
TLEしても、あと少しでACできそうなのか、全くダメなのかは確認する！
