問題文 E - Sequence Growing Hard ほげほげ(ポエム) 最近割と解説みて「はあ？」ってなるなること減ってきた気がする。 いや、これ普通にできなかったけれどね。【言われてみれば】妥当な進め方だよなあとか思う感じ。 まあでも、操作を整理してから木を数…
問題文 F - Sweet Alchemy にゃー 解法を知ってからだいぶ時間がたっていた。 日々詰み問題は増える一方です。 個数制限ナップサックの中身を知らなかったので後回しにしていたけれど、いい加減やりなさいということでやりました。 この問題の最初のステップ…
問題文 E - Decrease (Judge ver.) ポエム 制約大事ですよね。 突然なんじゃってなるけれど、nが50と言われると結構回すんだなってなる。 つまり、(これはいい癖なのか悪い癖なのかわからないけれど)始めについつい考えてしまう下手な貪欲をあきらめるいい材…
問題文 F - Monochrome Cat ポエム 個人的にすごいいいなって思った。 黒の葉を除く。 辺を高々2回までしか通らないと決める すべて二回通ると仮定してから、二回通らないパスを探す。 というのが主な流れになるけれど。 無駄な情報を省く。 行動を制限する…
問題文 E - Sorted and Sorted ポエム コンテスト中に通せませんでしたね…ほげほげ。 コンテスト中はひたすら貪欲を探していました、盲目状態、非常によろしくない。 解説を見て通したわけですが。 これは最適な並べ方について、明確に「こうじゃ！」みたい…
本日の勉強会で使ったスライドを置いておきます。 内容はARC096_C,Dと 幅優先探索です。Seicaちゃん講座20180423
サークルで使ったスライドです。 気が向いたら読んでみてくださいな。 内容はARC095の復習とDP入門です。Seicaちゃん講座20180416
問題文 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に…
問題概要 Alien's Counting | Aizu Online Judge N本の指を持つエイリアンがM個の屈曲の規則を持っている。 そのエイリアンが指で数えられる数は？ みたいな感じ。 小指曲げたら薬指も曲がるねみたいな。なんやかんややった結果、できませんでした。(´・ω・…
朝 7:30に起床AC。8:00ちょいに出発～。あれ、交通費とかどうするんだろう、何？領収書？？んじゃあ切符じゃなきゃあかんな。->WA(在来線は領収書必要ない)帰りの分も買っとくか～。->WA(帰りの切符を新橋やテレコムセンターでなく最寄り駅で買ったため帰り…
やっぱり何かものを書いていた方がいいみたいで。 考えをまとめるためや、メモが程度のものが中心になりそう。 続きますように、、、。
