A問題
四捨五入の仕方がわからず、ググってround関数なるものを使ったらWA。便利なものは理解して使わなければ不便みたいです。結局、少数第一位部分が５以上か否かの判定を自分で書いてACしました。
B問題
B問題にしては難しい気がして涙目。setに随時数列を入れて、最後にsetの長さを出力しました。setの中にlistを入れることはできないことを今更知りました。
C問題
思考の整理をしないまま、各技を習得するのに必要な時間を前から計算していったらWA。A問題と合わせて2つ目のWAにより、押し寄せる絶望感。息をついて冷静になると後ろから見ていくべきであることに気づきました。まず技N習得に必要な時間を加算。技N習得前に習得しておかなければならない技の時間を加算。さらにそれより前に習得しておかなければならない技の時間を加算、、、という風に後ろから見ることでACできました。
D問題
使用する移動は、できるだけ小さいほうが、数多くの場所間の移動に使えそうです。例えば、(4,2)移動するならば(2,1)移動して(2,1)移動したほうが良さそうです。なぜなら(6,3)移動したい時に(4,2)移動のみでは辿り着けませんが、細かくしておくことで(2,1)を３回することでたどり着けるからです。この考察を元に、各ij間の移動をできるだけ細かくしてから、setにぶち込みその長さを出力しました。今回のABCではsetが大活躍です。i→j間の移動とj→i間の移動は対象なので最後に２倍しました。忘れなかった自分に拍手です。
E問題
「閉路がないと条件を満たすことはできない」「閉路が1つあれば2**1=2通り、閉路が2つあれば2**2=4通り、閉路が3つあれば2**3=8通りできる」という考察のもと、dfsで閉路が検出できたらans*=2するようなプログラムを実装してみましたが、サンプルコードが通らず。考察が間違っているのか、実装が間違っているのかわからないままタイムアップしてしまいました。
結局、考察が間違っていました。まず、連結成分ごとに考えるという思考が欠如していました。そして、頂点の数と辺の数が等しくなければ条件は満たし得ないということに気づくことができていませんでした。普段解説ACばかりで、紙とペンでの実験が甘いことを痛感しました。
全然惜しくはありませんでしたが、個人的に今までで1番解ける気がしたE問題でした。力不足をしっかりと受け止めて前向きに頑張ります。
総括
とにかく水色で年を越したいです。
