AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

競プロ

天下一2013予選B B - 天下一後入れ先出しデータ構造

問題原文 atcoder.jp 解法 まともにデータを持っては間に合わないので、 (数字, 個数) というように持つ。 スタックの要素数は、↑の形式で持っても毎回舐めると間に合わないので、変数で管理するようにする。 ↓のちょっとめんどくさいバージョンという感じ。…

ARC007 C - 節約生活

問題原文 atcoder.jp 解法 sample2で貪欲の線はなくなる。 制約が小さいので「どこからテレビをつけ始めるか」のbit全探索ができる。 実装 過去にテレビを点けといたことにして、今から 分間ついてればOKみたいな感じにした。 modでやればよかったと後悔(ま…

DigitalArts 2012 B - Password

問題原文 atcoder.jp 解法 与えられたパスワードと同じものはダメ というのが少し面倒。 2種類正解候補を考えられればどちらかは必ず答えになりうる。 ということで、できるだけ z に近いものを使う場合のパスワード と できるだけ a に近いものを使う場合…

ABC019 D - 高橋くんと木の直径

問題原文 atcoder.jp 解法 で、質問は100回まで。 回の質問で葉を見つけ、 回の質問で木の直径を求めればよい。 普通に木の直径を求めるだけ。 実装 まぁ普通に。 N = int(input()) max_dist = 0 leaf = -1 for n in range(1, N + 1): print("? 1 {}".format…

ARC014 C - 魂の還る場所

問題原文 atcoder.jp 解法 とりあえず、消せる時は消してしまうのが最も得をしそうなのは明らか。 問題は消せない時。(例えば、 RG と詰めている時に、 B がきた時) これは、 R、 G のうち片方が次きても消せなくなるのと同じなので、 R、G のうち「より早…

Indeedなう(予選B) D - 高橋くんと数列

問題原文 atcoder.jp 解法 とりうる の組み合わせは 通り。 ( でも良いので) 各 について、条件を満たすものを数え上げようとすると、結局 のループを各 について回したくなるし、なにより面倒なので 条件を満たさないものを数えて引く ことを考える。 条…

CODE FESTIVAL 2014 予選B C - 錬金術士

問題原文 atcoder.jp 解法 から「最低何文字使う必要があるか」「最大何文字使う必要があるか」を計算し、 がその間にあれば YES。 各文字種について互いに影響し合わないので個別に考えて良い。 ある文字種 について、 から使える最大個数は、 内の の個数,…

Indeedなう(予選B) C - 木

問題原文 atcoder.jp 解法 「その時点で選べる頂点のうち、番号が最小のものを選ぶ」のが最適。 問題はそのような頂点を高速に取得することだけど、これは優先度付きキューを使うと簡単に実現できる。 実装 import heapq N = int(input()) T = [[] for _ in …

天下一コン2014 予選B B - エターナルスタティックファイナル

問題原文 atcoder.jp 解法 dp。 を構築する通り数 としてdpテーブルを順に埋めていく。 実装 なんだろう、拾う方が気持ちイメージが楽な気がします。 今 までを見ていて、最後に を使ってできるかな〜?というきもち N = int(input()) S = input() lenS = le…

ABC167 E - Colorful Blocks

問題原文 atcoder.jp 解法 ポイントはまとめて全パターン考えないようにすることだと思う。 まず、「隣り合う色が同じようなものがない」パターンを考えてみる。 これは、例えば一番左は 色使えて、次からは直前に使った色でない 色を使えるので、 通りとな…

ABC167 D - Teleporter

問題原文 atcoder.jp 解法 の制約がとても大きいため、実際に 回の移動を試すわけにはいかない。 全ての町について、必ずどこかに町に移動できるのでいずれどこかのループをぐるぐる回ることになる。 ループは 回以内に必ず現れるので、どこがループするかを…

ABC166 F - Three Variables Game

問題原文 atcoder.jp 解法 全部の数がある程度大きければ適当にやっていけばできそうなことがわかる。 ということでできるパターンのギリギリ、あるいは死ぬパターンを考える。 0 0 0 の場合 問答無用で死ぬ。 1 0 0 の場合 0 0 の部分を操作されると死ぬ。 …

ABC166 E - This Message Will Self-Destruct in 5s

問題原文 atcoder.jp 解法 条件を整理すると、 が探したいものだとわかる。 とりあえず として絶対値を消すと、 になった。 こういうのは と を別々に考えるとよくて、式変形をすると が得られる。 これで左辺と右辺が独立に前計算できるようになった。 あと…

ABC165 D - Floor Function

問題原文 atcoder.jp 解法 ならば右側が必ず0になるので、 には取りうる一番大きい数である を入れるのが最適。 そうでない時、 左側は をかけてる効果を最大に活かしたくて、右側は値が変わるギリギリに押さえ込みたい 気持ちになるので、 を入れるのが良…

ABC165 C - Many Requirements

問題原文 atcoder.jp 解法 と の制約が小さいことに注目する。 全パターン試すのが楽そうだけど、条件を満たすような数列はどれぐらいあるかを考える。 例えばバラバラの数字 個を適当に並べてそれが単調増加になっている確率は 。 この事実を考えると最大ケ…

第二回 PAST K - 括弧

問題原文 atcoder.jp 問題要旨 (, ) からなる を対応の取れた括弧列にすることを考える。 まず、以下の操作を0回以上行う。 文字目の ( と ) を反転させる。コストとして かかる。 次に、以下の操作を0回以上行う。 文字目を削除する。コストとして かかる。…

第二回 PAST J - 文字列解析

問題原文 atcoder.jp 問題要旨 英子文字と (, ) からなる「括弧の対応が取れているような」文字列 が与えられる。 また、 を 文字列 を反転した文字列とする。 以下の操作を可能中桐繰り返し行った時の、最終的な を求めよ。 (, ) を含まない の部分文字列 …

第二回PAST I - トーナメント

問題原文 atcoder.jp 問題要旨 人でトーナメントをおこなう。 番目の人の強さは で、これらは相異なる。 トーナメントでは隣の人と戦って、より強い方が勝ち残る。これを最後の1人になるまで行う。 各人について何回戦うかを求めよ。 解法 シミュレーション…

第二回 PAST H - 1-9 Grid

問題原文 atcoder.jp 問題要旨 S, G がひとつずつ、それと 1 ~ 9 で構成される のグリッドが与えられる。 上下左右への移動を繰り返して、S から G へ向かう時、 1 ~ 9 のマスを 1, 2 ... 9 の順番に踏んでいるようなものの最小の移動回数を求めよ。 そのよ…

第二回 PAST G - ストリング・クエリ

問題原文 atcoder.jp 問題要旨 文字列 に対して、 回のクエリを実行せよ。 最初 は空文字列である。 クエリには以下の2種類ある。 1. の末尾に英子文字 を つ追加する。 2. の先頭から 文字削除する。この操作で、 a, b, ... z がそれぞれ何文字削除された…

JOI難易度7 展覧会

問題原文 atcoder.jp 問題要旨 大きさ、価値がそれぞれ , であるような絵が 枚と、大きさが であるような額縁が 個ある。 各絵はそれよりも大きなサイズの額縁にしか入れることはできない。 また、絵を額縁に入れて飾る時、額縁の大きさについても絵の価値に…

JOI難易度7 テンキー

問題原文 atcoder.jp 問題要旨 789 456 123 0 みたなテンキーを考える。 最初カーソルが 0 においてあって、上下右左へ移動 or クリックで1回の操作と考える。 で割ったあまりが になるような数を入力するまで、最低何回の操作が必要か? 解法 「時間いっぱ…

ABC158 E - Divisible Substring

問題原文 E - Divisible Substring 問題要旨 0 ~ 9 からなる文字列 が与えられる。 の連続する区間を10進数と見立てたとき、それが 素数 の倍数になっているようなものの通り数はいくつか。 は素数 解法 これ(は?) at274.hatenablog.com まぁこっちの方が…

ABC164 E - Two Currencies

問題原文 atcoder.jp 問題要旨 金貨めっちゃたくさんと銀貨 枚を持って、 頂点 辺の無向連結グラフを頂点0から旅することを考える。 各辺には通行料が設定されており、銀貨 枚を払わないと通れず、移動に 分かかる。 また、各頂点には両替所が設定されてお…

ABC164 D - Multiple of 2019

問題原文 atcoder.jp 問題要旨 1 ~ 9 からなる文字列 が与えられる。 の連続する区間を10進数と見立てたとき、それが2019の倍数になっているようなものの通り数はいくつか。 解法 2019と10は互いに素なので、 ga 2019の倍数ならば、 も も2019の倍数。 これ…

ABC155 E - Payment

問題原文 atcoder.jp 問題要旨 の 種類の紙幣がある国を考える。 この国で 代金として を支払う時、 以上の額を支払うことで、自分が出す紙幣の枚数とお釣りとしてもらう紙幣の合計枚数を最小化せよ。 解法 ある桁の払い方を考えると、「その必要枚数ピッタ…

JOI難易度7 JJOOII 2

問題原文 atcoder.jp 問題要旨 J, O, I からなる長さ の文字列 が与えられる。 また、 J, O, Iを 個ずつ並べた文字列を「レベル のJOI文字列」と呼ぶことにする。 「ある位置の文字を削除する」という操作を最低何回行えば を レベル のJOI文字列にできるか…

ABC163 E - Active Infants

問題原文 atcoder.jp 問題要旨 人の幼児が横一列に並んでいる。左から 番目の幼児の活発度は である。 この幼児たちを1回だけ自由に並べ替える。 並び替える前左から 番目にいた幼児が左から 番目に移動した時、 のうれしさが生まれる。 幼児の嬉しさの合計…

ABC163 D - Sum of Large Numbers

問題原文 atcoder.jp 問題要旨 の 個の数字が与えられる。 この中から 個以上の数を選ぶ時、その和としてありうるものの個数を求めよ。 解法 不要なものを頑張って引こうとすると地獄をみるよ! こう言うのはちゃんと特殊な条件(今回だと 10^{100} とかいう…

JOI難易度6 横断幕

問題原文 https://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day1.pdf 問題要旨 × のグリッドが与えられる。各グリッドの値は 0, 1, 2 のいずれかである。 このグリッドから面積4マス以上の四角形領域を抜き出した時、4つの角にあたるグリッドの値…