これは IQ1 Advent Calendar 2019 の 20 日目の記事です adventar.org はろはろー、ymduuさんです。 前回のIQ1 Advent Carendar から 約1年、今年も引き続きSplatoonをやっていたので懲りずに今年やったことを書いていきます。 今年は昨年のエリアXに続き、…

所見 700初自力AC atcoder.jp 問題概要 長さNの整数列Aについて以下の操作を繰り返し行う。 ある正整数Pを決め、Ai >= P なる最小のiについて、Ai -= P をする。 任意のiについてAiが0にならないように操作を行うとき、操作は最大何回できるか。 取った方針 …

https://atcoder.jp/contests/abc132/submissions/7044671 所感 拡張ダイクストラ、ノードを増やすんだけど、実際に実装するときは距離を格納する配列の次元を増やすみたいな実装になるんだなあ 問題概要 有向グラフの上で移動することを考える。頂点Sから頂…

https://atcoder.jp/contests/agc002/submissions/6740547 所感 AGC500も大した事ねえなガハハ(on 調子) 問題概要 N本のロープがあり、i番目のロープの長さはa_iである。 i番目のロープの右端とi+1番目のロープの左端が結ばれているとする。 長さL以上の繋が…

https://atcoder.jp/contests/abc136/submissions/6726558 所感 時間があればできた……？(怪しい) 問題概要 長さNの数列Aがある。以下の操作をK回以下行って得られるN個の数のGCDを最大化せよ。 i != j のA_i, A_j について、A_iに1を足し、A_jに-1を足す。 …

atcoder.jp 所感 700 初自力、ものすごい逆詐称だ problemsのれこめんどというのを使ってみたけど、500埋め終わったらこれをやったらいいかな 問題概要 '.'と'#' からなる盤面H*Wのが与えられる。1回の操作でイカができる時、最短何回で外周(0行目、0列目、H…

atcoder.jp 所感 基礎 * 大量だけど解けないね、悲しみ 問題概要 長さNの非負整数列a, b が与えられる。 a, bからそれぞれx, y を一つずつ取り出す方法はN2通りあるが、そのx + y のXORを計算せよ。 取った方針 XORなので各桁を独立に計算したくなるが、足し…

atcoder.jp 所感 500も結構自力ACできる 問題概要 0と1からなる文字列Sが与えられる。以下の操作を繰り返してSの要素をすべて0にできるような最大の整数Kを求めよ。 長さK以上の区間を選択し、0と1を反転させる。 取った方針 Sの長さ|S| をLとおく。 手元で…

所感 Cはカス 問題概要 木と数Kが与えられる。イカの条件で色を塗り分けるとき、塗り分け方の個数を求めよ。 二つの異なる頂点 x,y 間の距離が2以下ならば、頂点xの色と頂点yの色は異なる。 取った方針 あるノードに注目した時、距離が2以下である、とは、以…

所感 0b1000 < 0b0111、言われてみれば死ぬほど当たり前なんだけど上から桁DP + 二進数 で見えなくなっていたよね(言い訳) atcoder.jp 問題概要 正整数Lが二進数表記で与えられる。 a + b <= L a + b = a ^ b なる(a, b)の組み合わせの個数を109+7で割った余…

所感 やむと゛ぅ はちえんセク゛き をてにいれた！ やむと゛ぅ はさ゛あつ をてにいれた！ 問題概要 N個の道路工事とQ人の人間が与えられる。道路工事はS, T, Xの形で与えられ、それぞれS-0.5 からT-0.5 の時間座標Xを道路工事し通行止めにすることを表す。 …

所感 思ったより簡単だったし本番中解けてもよかったね 問題概要 N行M列の盤面にK個のコマを置くことを考える。 配置のコストをすべての盤面上のコマ同士のマンハッタン距離で定義するとき、すべての置き方のコストの総和を求めよ。 取った方針 コマを置く2…

言い訳 codevsたのしかったです 例の表 https://docs.google.com/spreadsheets/d/1nXQpWJ7fddnfDNqcdBumj2WzCbIy_H06upI6R-qkI/edit#gid=0 所見 一発で思いついたぞヤッホーと思っていたら既に解いた問題だった(は？) 問題概要 https://atcoder.jp/contests/…

abc008.contest.atcoder.jp 例の表 https://docs.google.com/spreadsheets/d/1nXQpWJ7fddnfDNqcdBumj2WzCbIy_H06upI6R-qkI/edit#gid=0 所感 最初から俺はさんすうだぞみたいな顏をしてくれれば解ける 問題概要 N枚の区別できるコインが与えられる。各コイン…

例の表 https://docs.google.com/spreadsheets/d/1nXQpWJ7fddnfDNqcdBumj2WzCbIy_H06upI6R-qkI/edit#gid=0 所感 さんすうだってわかっていれば行ける系 問題概要 N人の人間がいて、i番目の人はwiの白表とbiの青票を持っている。賛成の場合はwiの白票をすべて…

C 所感 にぶたんが見えた時まだあと20分あったのに通せなかったのは流石に†反省† 問題概要 問題をうまく要約できないので元のページを見て(は？) https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_c 取った方針 全てのゴーレムが呪文を唱え…

例の表 https://docs.google.com/spreadsheets/d/1nXQpWJ7fddnfDNqcdBumj2WzCbIy_H06upI6R-qkI/edit#gid=0 所感 DPだってわかっていれば行ける系 問題概要 N個の整数を持つスライムが与えられる。以下の操作を繰り返した時のコストの最小値をもとめよ。 隣り…

所感 最近残業が多くACできていなかったのでリハビリをね 問題概要 整数Nが与えられる。次の条件を満たす長さNの文字列の数を109+7で割った余りを求めよ。 * A, C, G, T 以外の文字を含まない。 * "AGC" を部分文字列として含まない。 * 隣接する2文字の入れ…

D 所感 有向辺を大小関係と見る + トポロジカルソートという単語 まで出てきて解けないのは怠慢すぎる、猛省 問題概要 N頂点の根つき木に、祖先->子孫であるようなM本の有向辺を追加したグラフが与えられます。元のグラフを復元してください。 取った方針 有…

atcoder.jp 所見 賢いO(1)解法があるっぽいけどいまの僕に必要なのは一般的なO(N2)解法なんだよな(自己分析) 問題概要 N枚からなる山札があり、上からi番目のカードにはaiが書かれている。 XさんとYさんが山札に対して順番にイカの操作を行うとき、山札がな…

atcoder.jp 所見 一度解説読んでこんなん(二回目の式変形)どうやって思いつくねん(絶望)となっていたが、思ったより地続きの考察で解ける 問題概要 x軸に平行な直線m本とy軸に平行な直線n本が与えられる。それらに囲まれる長方形すべての面積を1000000007で…

所見 方針は外していなかった気がするけど微妙に間違っていた、こういうのがこれ(下)なんだと思う、くやC ところで私はmdをプラグイン入れたVSCodeで書いてるんですが(プレビューを横で見たいので)、はてなブログに貼り付けた時に勝手にURL展開されてほしく…