AtCoder ABC137 参戦記
今までは退職 -> 引っ越し -> 旅行 -> 転職で忙しかったので AtCoder はコンテスト参加だけしかできていませんでした。ようやく落ち着いたので。久々の参戦記になります。
AtCoder の ABC 137 に参戦しました。
結果は 65 分で ABCDE *1 の 5 問 (2 WA) となり、パフォーマンス 1900 で青復帰となりました。
感想
A 問題、 B 問題
やるだけ。
C 問題
- 文字の使用数が同じ文字列の個数を数える
- 文字列内をソートして使用文字を a から並べる
- 文字列間でソートして辞書順にする
- 上からなめて個数を数える
個が同じなら個数は
- 使用数が違う文字ごとに上記を加算する
std::string ってソートできるのを初めて知った。
D 問題
報酬期限の後ろの順にタスクを並べてゆけばよい。あとは priority_queue を用意して後ろの日から以下の操作を行う。
- その日期限のタスクをすべて追加する
- タスクの中で一番報酬の高いものがその日のタスク
E 問題
ワーシャルフロイドをやればよい。ただし閉路はスタートからゴールに到達できるパスの中にあるものだけがエラーになる。
ここまで考察して実装。閉路検出は step n から 2n までの間にゴールの価値が更新されれば NG。
で提出して AC をもらったが、上記は例えば直行するときの報酬が 10n でループの報酬が 1 のときに 10n と答えてしまうが正しい答えは当然 NGで嘘解法。
たぶん真面目に閉路の到達可能性をチェックする必要があるはず。
F 問題
この手の問題は苦手...
*1:ただし E は嘘解法
