2018-01-01から1年間の記事一覧
ICPCっぽさを感じるね。 問題 C - Lexicographic constraints 考察 二部探索をする、「K種類の文字で実現可能か」について考える。愚直にやろうとすると10＾9桁考えなくてはいけなくなるのでRun Lengthといわれる(であろう)実装をする。 aaabbbabbccbbbbを a…
問題 https://onlinejudge.u-aizu.ac.jp/resources/icpcooc2018/J.pdf木が与えられる(頂点数100000まで)、各点には色が塗られている。 次の２つのクエリを最大100000回行う ある頂点の色を塗り替える。 ある色に塗られている頂点が全て含まれるような最小の…
今年で3回目ですね。今年はmamumamuとEuldernaと参加しました。会場は横浜産貿ホールです、もう少し地方でもいいんですよ？観光したいね。 １日目 チームの皆さんはぬくぬくしてるそうです pic.twitter.com/X4M2PRhcfL— seica (@seica_at_se) December 8, 20…
JAGの夏合宿に参加しました。参加記かくぞー だいぶ忘れているのでこれは参加記ではなく創作ということにしておきます。 JAG夏合宿に参加したSeicaの物語書くぞー写真撮影5級 pic.twitter.com/78dE6b5Y16— seica (@seica_at_se) September 15, 2018 DAY1 オ…
問題 Dinner | Aizu Online Judge 感想 これねー。適当な基準を付けてソートするやーつ、ド典型ですが、むつかしいです。 自炊をするかどうかで自炊パワーが変動するので、ある日に自炊をしたら？しなかったら？みたいなのを考えてみたりします。また、簡単…
漂うインフレ感...？(適当いってます) 問題 E - Or Plus Max 感想 高速ゼータ変換初めて使いましたが。ある集合Aに対して、A⊆Bを満たすBすべてに対する処理(逆も可)を各集合に対してうまく行うものという感覚でいいのかな？詳しくはこの方の記事を参照くださ…
ARCももう三桁回数開いてるんですね。 問題 D - Equal Cut 感想 本番中全く頭が働いていませんでしたが、、、。数列を四つに分ける(= 数列に仕切りを三つ入れる)というのですが、普通にやると間に合わないので一つ固定したときにどうなるかを見てみます。状…
問題 Patisserie ACMACM洋菓子店 | Aizu Online Judge 感想 面白いですねこれ。(ほんとに感想) 一見して何もわからないけれど。すっごく簡単に言うと。 折るということについて考える(必要条件・共通項を見つける)と凹みのところが大事な点(2*2の範囲のうち3…
去年はちんぷんかんぷんでしたが。 解けるようになるもんですね。 問題文 Boolean Expression Compressor | Aizu Online Judge 感想 えー、ごり押しです。文字列の長さが16までなので全部見てみます。すべての文字列に対してabcdがそれぞれ0,1の場合、つまり…
これはなかなか難しいね 問題 野球観戦 | Aizu Online Judge 感想 どれも10^6なので、二重ループは回せなさそうです。したがって、何かしら共通の基準を用意したいのですが。例えばCのみ(同点の試合)考えるのであればただの組み合わせですよね、N個のものをM…
猫チャンの気持ちになることが何よりも大事です。 問題 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問題で動転しすぎていてちゃんと考察できずに終わってしまった問題。第一印象で左右に振り回せばよさそうなのはわかりますが、それをどうすればいいのか詰めるのがむつかしそうだなとか考えていま…
組み合わせで独立は典型！(ﾌﾞｵﾝｯ!) 組み合わせで独立は典型！(ﾌﾞｵﾝｯ!) 組み合わせで独立は典型！(ﾌﾞｵﾝｯ!) 組み合わせで独立は典型！(ﾌﾞｵﾝｯ!) 問題 B - RGB Coloring 感想 Ax + By = K を満たすx,yそれぞれについて計算をしたくなるのですが(ﾌﾞｵﾝｯ!) それがな…
期待値の気持ちになるですよー 問題 C - Pushing Balls 感想 Rabbit Exerciseをやった後だとだいぶお気持ちがわかるようになるね。名状しがたいとか思ってる時点でまだまだなんですが。期待値に関しては試行する回数と和が同じなら結果が変わらないとか考え…
この類、すｇｇｇｇｇｇｇっごい苦手だぴょん。 問題 C - Rabbit Exercise ぴょん ダブリングを始めて書いた気がするうさー。問題の解説を読んでると思うさが、「〇〇という操作をするして△△というアルゴリズムを使うと解けます。」と言われると解けない気が…
なんかDPについて少しだけお気持ちがわかった気になったよ。 問題 F - Donation にゃっほい これは日本語のeducationalがわかりやすかったです(seica視点)。思いっきり解説を見たので実際に解くときにどうゆう流れで行くべきかを考えていくわけですが。基本…
いやー、これは反省ですねえ。 つらいつらい。 問題 E: Range Minimum Queries - AtCoder Regular Contest 098 | AtCoder にゃん すこーしだけ丁寧に書きたい(願望)ので丁寧に私の思考をなぞっていきましょう。(未定) 問題を見て、最初に操作についてみてみ…
題名の破壊力半端ないよね。 問題文 D - Xor Sum 2 ほげ 最初に式について吟味してあげましょうって感じ問題。 n = 2*10^5なので、O(n^2)無理なんだよね。なので、式とにらめっこ。そうすると条件を満たしているとき、各ビットについて、そのビットがたって…
いやー。盛大にバグらせた。 辛いね。 問題文 Sinking islands | Aizu Online Judge 考察 無駄な橋はかけたくないです。 なので、最初っからこれ以上かける必要のないような橋のかけ方をします。説明が何とも難しいところですが...ある島を沈ませたとき、残…
問題文 E - Sequence Growing Hard ほげほげ(ポエム) 最近割と解説みて「はあ？」ってなるなること減ってきた気がする。 いや、これ普通にできなかったけれどね。【言われてみれば】妥当な進め方だよなあとか思う感じ。 まあでも、操作を整理してから木を数…
問題文 F - Sweet Alchemy にゃー 解法を知ってからだいぶ時間がたっていた。 日々詰み問題は増える一方です。 個数制限ナップサックの中身を知らなかったので後回しにしていたけれど、いい加減やりなさいということでやりました。 この問題の最初のステップ…
問題文 E - Decrease (Judge ver.) ポエム 制約大事ですよね。 突然なんじゃってなるけれど、nが50と言われると結構回すんだなってなる。 つまり、(これはいい癖なのか悪い癖なのかわからないけれど)始めについつい考えてしまう下手な貪欲をあきらめるいい材…
問題文 F - Monochrome Cat ポエム 個人的にすごいいいなって思った。 黒の葉を除く。 辺を高々2回までしか通らないと決める すべて二回通ると仮定してから、二回通らないパスを探す。 というのが主な流れになるけれど。 無駄な情報を省く。 行動を制限する…
問題文 E - Sorted and Sorted ポエム コンテスト中に通せませんでしたね…ほげほげ。 コンテスト中はひたすら貪欲を探していました、盲目状態、非常によろしくない。 解説を見て通したわけですが。 これは最適な並べ方について、明確に「こうじゃ！」みたい…
