結果
ユーザ名 tokumini コンテスト名 AtCoder Beginner Contest 135 順位 327th / 4583 パフォーマンス 1795 レーティング 1925 → 1913 (-12)
難しかった。
A問題
見た目が難しくてびびった。
B問題
脳みそを使わない力のこもった三重ループを投げつけた。
C問題
証明とかよくわからないけど貪欲にやっていけばできるっしょ! というノリ。最大流で考えるのかぁ。
D問題
桁DPっぽい雰囲気も感じたけどその方針にはあまり深入りせず考えていたらDPっぽい遷移が見えたので実装し始める。しかしいつも通りちゃんと詰めてはいないので書いてからサンプル合わないし遷移の式がよくわからんという感じになって二度手間になるやつ。
意識はしていなかったけどDP配列を2つ分しか用意しない省メモリの実装になっていた。普通に「dp[i][j] := 先頭 i 文字として考えられるもののうち,13 で割ったあまりが j であるものの数」とした方が混乱せずに済むのでそうしていれば良かったのに。初期化のところも汚くてひどい実装になってしまった。
E問題
なにこれ難しすぎる。が小さくて回り道しなければいけないサンプル1と、貪欲に近づいてから最後調整するだけでは最適にならないサンプル3のコンビネーションが強くてなにもわからなかった。マンハッタン距離なので45度回転みたいなご利益もわかっていない念仏を唱えてみたりもしたけど別になにも起こらず。
解説PDFを見てもはぁそうですかという感じで実装に数時間かかった。個人的には行き方のパターンA, Bで分類するよりもかどうかで分類したほうがわかりやすかった。
とするように変換し忘れていたり負の数の剰余を取っていたりとバグらせまくってひどい有様に。自分の提出ページが2ページまでいってしまった。きつかった。
F問題
コンテスト中は開きもしなかった。順位表も見ていないのでどのくらい解かれているのかも知らないけど、もしF問題が簡単めでみんなそっち解いているとかだったらパフォーマンスがひどいことになっていただろうな。別に簡単ではなかったようで良かった。
30分くらい考えてみたけど全然わからなくて解説を見てAC。Zアルゴリズムで検索できるというのも知らなかったしグラフに落としてからもなんだか芋臭い実装しかできなくてしっくりこない感じがある。難しい。