猫チャンの気持ちになることが何よりも大事です。 問題 The Castle | Aizu Online Judge 感想 制約が小さいのでDPいろいろできそうですよね。何かを調べるとき、最初に探索できるかを考えるのも大事だなあと思ったり。それができなければ貪欲だとか、グラフ…

こうゆうのをパッと書けるのはいいですね。 問題 Prime Caves | Aizu Online Judge 感想 やります、以上。なんつって。素数洞穴と素数判定表を作ったのちDPすればよさそうただ、どう再現すればいいのかというところにだいぶ苦労する感じです 素数洞穴は大き…

いっぱい☆ついていたけれど。 問題 Hakone | Aizu Online Judge 感想 DPですね。今回は少しわかり辛いのですが。まず考えることなのですが、前の中継所でのその順位にはいる候補は。 現在その順位より上にいて’U'である。 現在その順位より下にいて'D'である…

題名よくわかりませんが... 問題 How can I satisfy thee? Let me count the ways... | Aizu Online Judge 感想 構文解析入門みたいな感じ。PQR全通り試していけばいいです。解析の仕方的には構文が必ず 「-」+「論理式」 「(」+「論理式」+「op」+「論理式…

働き方改革！！！ 問題 Mr. Rito Post Office | Aizu Online Judge 感想 全探索したい、そう思えたら勝ち。船をどう使えばいいのかというのは全部見ていかないと行けなさそうですよね。まあ、全探索をまともにできるわけがないので、DPになりますが。dp[i][j…

確かに、確かに大事なんですがね？ ★つくのか～これ。 問題 インビジブル | Aizu Online Judge 感想 問題文を４回くらい読みましょう。分かりつらい。サンプル2を見てみるとすっごい悩みますが、おそらくこれは最初っからどちらもパスして終わる or どちらも…

実装力。大事。 問題 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 にゃん すこーしだけ丁寧に書きたい(願望)ので丁寧に私の思考をなぞっていきましょう。(未定) 問題を見て、最初に操作についてみてみ…

いやー。盛大にバグらせた。 辛いね。 問題文 Sinking islands | Aizu Online Judge 考察 無駄な橋はかけたくないです。 なので、最初っからこれ以上かける必要のないような橋のかけ方をします。説明が何とも難しいところですが...ある島を沈ませたとき、残…

問題文 F - Sweet Alchemy にゃー 解法を知ってからだいぶ時間がたっていた。 日々詰み問題は増える一方です。 個数制限ナップサックの中身を知らなかったので後回しにしていたけれど、いい加減やりなさいということでやりました。 この問題の最初のステップ…

問題文 F - Monochrome Cat ポエム 個人的にすごいいいなって思った。 黒の葉を除く。 辺を高々2回までしか通らないと決める すべて二回通ると仮定してから、二回通らないパスを探す。 というのが主な流れになるけれど。 無駄な情報を省く。 行動を制限する…

問題文 E - Sorted and Sorted ポエム コンテスト中に通せませんでしたね…ほげほげ。 コンテスト中はひたすら貪欲を探していました、盲目状態、非常によろしくない。 解説を見て通したわけですが。 これは最適な並べ方について、明確に「こうじゃ！」みたい…

問題文 D - ディスクの節約 考察 端的に言うとtayama_killerデス。 嘘解法を1ケースだけ落とすという♰悪魔的行為♰をしている。さて、見た感じからdpをしたくなる感じ。 局所的にディスク容量が大きくなるところを考えると、あるタスクを行うときにそのタスク…

問題 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の扱いが難しい。状態数が増えます。 今回の問題だと文字数が同じであれば文字列を作る組み合わせは等…

土曜日(一日目) つくば駅に向かう。 二回目のアジア大会ですね。もう一年もたったのですか(もうちょい長いけれど)。 前回は本当にマスコットだった(当時素人でいわゆる数合わせ)から今回はちゃんと働きたいなあという気持ちになりながらTXに揺られた、ゆうほ…

問題 Never Wait for Weights | Aizu Online Judge 考察 n m なのでn log mとか m log nにしたい気分。 連結判定はUnion Find使えばいい。 わりかしすぐに求められる情報が欲しい、どの情報があると便利か。 Union Find使うので、親との距離がわかっていれば…

問題 Minimal Backgammon | Aizu Online Judge 考察 典型的なDP dp[i][j] :=iターン目にjにいる確率 LだったりBだったり折り返しだったりの判定に順序だけちょっと気を遣う。 #include<iostream> #include<cstdio> #include<vector> #include<string> #include<cstring> #include<functional> #include<stack> #include<queue> #inc</queue></stack></functional></cstring></string></vector></cstdio></iostream>…

問題 Shifting a Matrix | Aizu Online Judge 考察 行列処理の扱い方について考える。 処理の回数が多いのでどうにか省く必要がある。 何回か回せば一周して来そうとか思ったけれど、場所によって周期が違うので却下。 処理を何かしらの関数や行列で表せると…

問題文 Rabbit Party | Aizu Online JudgeI hate English. 考察 探索したい問題。 辺の数が少ない。 ある組み合わせに新しくウサギ(a)を招待するとき、そのウサギとの重みが０のウサギ(b)が一匹でもいるとスコアは上がらない。 その後他のウサギを招待してス…

問題文 D: すぬけそだて――トレーニング―― - COLOCON -Colopl programming contest 2018- | AtCoder 考察 M 最終的なスコアには上限がありそう(x+T_(n-1)-t_1くらい) スタミナの上限があるので、回復しきったら早めに消費した方がよい。 また、スタミナがXに…