AtCoder
実装力。大事。 問題 E - 祝日 感想 これは正直やるだけですよね。インプットの状態での祝日を数えた後、一つずつ曜日をずらしていって日数がどう変わるかを見ていきます。日にちの管理はsetで行い、抜き差しする際に祝日の計算をします。一年の開始の曜日が…
これ難しくないですか 問題 C - Interval Game 感想 本番中B問題で動転しすぎていてちゃんと考察できずに終わってしまった問題。第一印象で左右に振り回せばよさそうなのはわかりますが、それをどうすればいいのか詰めるのがむつかしそうだなとか考えていま…
期待値の気持ちになるですよー 問題 C - Pushing Balls 感想 Rabbit Exerciseをやった後だとだいぶお気持ちがわかるようになるね。名状しがたいとか思ってる時点でまだまだなんですが。期待値に関しては試行する回数と和が同じなら結果が変わらないとか考え…
なんかDPについて少しだけお気持ちがわかった気になったよ。 問題 F - Donation にゃっほい これは日本語のeducationalがわかりやすかったです(seica視点)。思いっきり解説を見たので実際に解くときにどうゆう流れで行くべきかを考えていくわけですが。基本…
いやー、これは反省ですねえ。 つらいつらい。 問題 E: Range Minimum Queries - AtCoder Regular Contest 098 | AtCoder にゃん すこーしだけ丁寧に書きたい(願望)ので丁寧に私の思考をなぞっていきましょう。(未定) 問題を見て、最初に操作についてみてみ…
問題文 F - Sweet Alchemy にゃー 解法を知ってからだいぶ時間がたっていた。 日々詰み問題は増える一方です。 個数制限ナップサックの中身を知らなかったので後回しにしていたけれど、いい加減やりなさいということでやりました。 この問題の最初のステップ…
問題文 F - Monochrome Cat ポエム 個人的にすごいいいなって思った。 黒の葉を除く。 辺を高々2回までしか通らないと決める すべて二回通ると仮定してから、二回通らないパスを探す。 というのが主な流れになるけれど。 無駄な情報を省く。 行動を制限する…
問題文 E - Sorted and Sorted ポエム コンテスト中に通せませんでしたね…ほげほげ。 コンテスト中はひたすら貪欲を探していました、盲目状態、非常によろしくない。 解説を見て通したわけですが。 これは最適な並べ方について、明確に「こうじゃ！」みたい…
問題 C - Fountain Walk 考察 サンプルを見てみる。 基本的には噴水を多く通った方がいことは明らかであるので、問題はいかに多く噴水を通れるかになりそう。 ただし、サンプルにもあるように、かえって遠回りになることもあるので注意、これはどんな時に起…
問題 B - Colorful Hats 考察 全体でｑ色あったとする。 そうするとaはｑかｑ－１のみ。 つまり、入力値の最大最小の差が２以上ならアウト すべてが同じ数字の場合。 自分を入れても入れなくても数字が変わらないので、各色については最低２匹以上いることに…
問題文 D: Menagerie - AtCoder Regular Contest 069 | AtCoder 考察 番目の動物が羊だった時、その左右はどうなるかを考えたいけれど条件分岐が多すぎる。 ということで、仮定を増やす。 番目と番目がそれぞれある動物だった時にどうなるかを考えると番目の…
問題文 D: Walk and Teleport - AtCoder Regular Contest 067 | AtCoder 考察 どこにワープしてもBだけかかるという話なので、複雑な順番を考える必要があると思いきや １から３にワープして２まで歩くのと １から２にワープして３まで歩くのは同じコストが…
問題 D: An Ordinary Game - AtCoder Regular Contest 064 | AtCoder 考察 三文字の場合 aba ならfirst abc ならsecond 四文字の場合 abca ならfirst abab ならsecond abac ならsecond abcd ならsecond 五文字の場合 abcde ならfirst acbcd ならfirst ababa …
問題文 D: 桁和 / Digit Sum - AtCoder Regular Contest 060 | AtCoder 考察 制約のがちょっと気になる。 最小の数字と言われているので、基本全部見たくなる。 数字に関してわちゃわちゃする問題なので、まず式に表すべきであろう。 という感じかな？ これ…
問題 F - Road of the King 考察 SCCしたくなるけれどしたところでどうするのって感じに。 組み合わせを考えるときは、グラフは合わない気がしてるが(使う問題あるのかな) なので全探索とかを考えるべき。(まあ、DP) 愚直にやると300^300 状態数もかなりの数…
問題文 F - バイナリハック / Unhappy Hacking 考察 指定された文字を作る組み合わせを求める。 愚直な全探索だと3^5000通り DPをしたくなりますが。0と1の扱いが難しい。状態数が増えます。 今回の問題だと文字数が同じであれば文字列を作る組み合わせは等…
問題文 D: すぬけそだて――トレーニング―― - COLOCON -Colopl programming contest 2018- | AtCoder 考察 M 最終的なスコアには上限がありそう(x+T_(n-1)-t_1くらい) スタミナの上限があるので、回復しきったら早めに消費した方がよい。 また、スタミナがXに…
