けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Yes/No判定問題

JOI 2019 本選 C - たのしいたのしいたのしい家庭菜園 (AOJ 0660)

結構苦手系。想定解法かはわからないけどやってみた 問題へのリンク 問題概要 'R', 'G', 'Y' の 3 種類の文字で構成された長さ の文字列 が与えられる。これに以下の操作を行って「隣り合う 2 文字が同じになることはない」ようにしたい。それが可能となる操…

AtCoder AGC 008 D - K-th K (800 点)

実装は手こずったものの、それなりに自信のある Greedy を提出できて一発 AC できてよかった 問題へのリンク 問題概要 1 〜 の値を 個ずつもつ長さ の数列であって、 各 について、 番目の値が 個目の である という条件を満たすものを 1 つ構築せよ。条件を…

AtCoder ABC 110 C - String Transformation (300 点)

ごめんなさい!!!!! コンテスト中に僕が AC した解法は嘘解法でした (てんぷらさんたちに教えてもらいました)!!! 嘘解法 :https://beta.atcoder.jp/contests/abc110/submissions/3251109 S と T の各文字の個数をカウントして、それぞれ個数ベクトル…

AtCoder ARC 102 F - Revenge of BBuBBBlesort! (1200 点)

メッチャ楽しい問題!!! 問題へのリンク 問題概要 (ARC 102 F) 1 〜 N の順列が与えられる。 連続する三要素が単調減少のとき、それをひっくり返す という操作を好きなだけ行って、恒等順列にできるかどうか判定せよ。 制約 1 <= N <= 3 × 105 解法 (全然…

AOJ 2727 M and A (200)

これ、問題文を一目見て簡単な問題だと気づけるようになるには、それ自体のトレーニングが必要そうなん 問題へのリンク 問題概要 文字列 S, T が与えられる。 S のうち偶数番目だけを抜き出してできる文字列を S1 S のうち奇数番目だけを抜き出してできる文…

2018 codeFlyer 本選 F - 配信パズル (800 点)

本番中なんとか解けたけど、すごくグチャグチャしたん。 問題へのリンク 問題概要 すぬけ君は、 日間にわたって、毎日次のようなパズルを解こうとしている。 すぬけ君の持っている端末に、縦 行、横 列からなる格子状の盤面が毎日配信されてくる。それぞれの…

AOJ 2401 恒等式

せっかく構文解析の練習を少ししたので 問題へのリンク 問題概要 -(a+b)=(-a*-b) (a->b)=(-a+b) ((a*T)+b)=(-c+(a*-b)) のような式たちが恒等式かどうかを判定せよ。すなわち、a や b や c に true と false をどのように当てはめても結果が一致するかどうか…

2018 codeFlyer 本選 D - 数列 XOR (600 点)

本番、最後には綺麗な解法になったけど、何度も WA を出して大変だったん。 問題へのリンク 問題概要 要素の数列 が与えられる。この数列に以下の操作を好きな回数だけ繰り返して数列 にできるかどうかを判定せよ。 【操作】 を xor に置き換えるか、 を xor…