3匹の猫

みみねこの競プロ精進メモ

2019/2020 日本情報オリンピック(JOI)2次予選参加記

お疲れさまです。ABC3完とD部分点で330点でした

A - ポスター (Poster)

NN列の大きさのポスターSがあり、それぞれのマス3色で塗られている。このポスター S をポスター T の配色にしたい。次の3つの操作をコスト 1 で何回でもできる:

  • 好きなマス一つを好きな色に塗る
  • ポスターを時計回りに 90 度回す
  • ポスターを反時計回りに 90 度回す

ST にするためにかかる最小コストを求めよ。
1 \le N \le 500

考察・解法・実装など

どの操作をどの順番で行っても結果は同じなので、先に S を回転させる操作を終わらせればあとはマスを T の色に塗るだけ。 S の回転させ方はたかだか4通りなので全部シュミレーションする。 O(N^2)


B - いちご (Strawberry)

いちごが N 個ある。いちご i は地点 A_i にあり、 T_i 分後に熟す。収穫するのにかかる時間は 0 分である。熟す前は収穫できない。
地点 0 からスタートし、隣り合う地点を移動するのに 1 分かかる。全部のいちごを収穫して地点 0 まで戻るのに最短で何分かかるか。
1 \le N \le 10^5
0 \le A_i \le 10^9
0 \le T_i \le 10^9

考察・解法・実装など

どのように動いても地点 0 から一番遠いいちごのある地点 A_{max} までは移動しなければならないので、とりあえず地点 A_{max} に移動し、地点 A_{max} から地点 0 に戻るまでの道中でいちごを収穫するというルールを作るとわかりやすい。具体的には、常に負の方向(地点 0 の方向)に進みつつ、いちごがある地点まで来たらいちごを収穫し、この時まだ熟していなければその場で熟すまで待つ、というような貪欲法で解ける。O(N)


C - 桁和 (Digit Sum)

1 以上 N 以下の整数のうち、以下の条件を満たすものはいくつあるか。

  • 「現在の数の各桁の和を現在の数に足して値を更新する」という操作を 0 回以上行ったとき N になる

1 \le N \le 10^6

考察・解法・実装など

タイトルが令和に見えた。

操作が一通りしかない、ということは、ある数を操作した後にどんな数になるかは一意に定まる、ということ。ここから、動的計画法で解いた。

dp[i ] := 操作を繰り返すと i になる数の個数

とし、すべての要素を 1 で初期化する(∵操作を 0 回行うとその数自身になれる)。配るDPで 1~N まで遷移を進めていくと答えが求まる。DP配列の要素数の最大値は 999999 から遷移したときの 1000053 であるので、空間計算量的にも余裕がある。O(N)


D - テンキー (Tenkey)

テンキー(電卓などでよく見る、0 が左下にある配置のもの)とテンキー中の数字を指し示すカーソルがある。カーソルは最初 0 を指している。テンキー上で次の二つの操作をコスト 1 で何回でもできる:

  • カーソルを上下左右好きな方向に 1 マス分動かす
  • カーソルが指している数字を入力する。すでに文字が入力されている場合、その数字列の最後尾に追加する。

M で割って R 余るような数を一つ入力するためにかかる最小コストを求めよ。
2 \le M \le 10^5
1 \le R < M
小課題(30点):M=10^5

考察・解法・実装など

入力する数を A とすると、A=Mi+R(i = 0, 1, 2, \dots ) が成り立つ。

まずは小課題について考える。小課題の制約が M=100000 ちょうどで、R は最大でも 5 桁であることを考えると、i=0 として A=R とするのが望ましいことがわかる(A の候補を書き出してみるとわかるが、下から数桁は常に同じ数列であり、 i が増えるごとに上位桁の分を余計に入力しなければならなくなる)。実装については、各数字について「一つ前に入力した数字の位置と今入力したい数字の位置のマンハッタン距離」と「数字を入力するためのコスト」の総和を求める関数を組めばよい。ある一桁の数字を指定したとき、その座標がすぐ求まるようにすると良い。O(logM)

小課題の制約がないパターンの解法は未だわからない。解法を求めて読んでいる人には申し訳ないがほかのサイトをあたってください。i の値を 0~10^6 程度まで全探索するコードを提出したが、WAが出てしまった。貪欲や全探索ではなさそうで、テンキーの配置の特性を利用した解法、というのも考えづらい。テンキーを押す回数 C を固定したときに押せる数を列挙してその中に A があるか探す、というのも考えたが、 C の最大値が 30 である(例えば90909 を入力したときなど)のでこちらはTLEしそうである。


E - じゃんけん式 (Rock-Scissors-Paper Expression)

じゃんけんの手 R S P と独自の演算+ - * と括弧 ( ) から成るじゃんけん式を考える。じゃんけん式の中でじゃんけんの手がいくつか ? に変えられている。長さ N のじゃんけん式 E の答えが A となるような ? の埋め方は何通りあるか、10^9+7 で割った余りを答えよ。
1 \le N \le 2*10^5
Eは正しいじゃんけん式
小課題1(20 点):N \le 15
小課題2(20 点):N \le 200

考察・解法・実装など

小課題も解けなかった。これがいわゆる構文解析の問題であるのは分かっているが、構文解析をしたことがなかった。一応時間いっぱいまで粘ってみたものの、WAが出てしまった。

まず ? が登場しない式を考える。 E の先頭と末尾にそれぞれ () を付けて考えると、一番内側の括弧の中の式には + - * の演算だけが登場する(ほかの括弧の存在を気にする必要がない)。* の方が優先度が高く、優先度が高い演算は前から処理するという規則より、* を計算してから + - を計算することで括弧内の式を一つのじゃんけんの手とすることが出来る(はず)。これを内側から処理していけば最終的に式全体を一つの手とすることが出来る。計算量が少し怪しい(O(N)になりそう)。

? の扱いについて、? を含む「じゃんけんの手」を  \{ この手がRとなるような組み合わせの総数, この手がSとなるような組み合わせの総数, この手がPとなるような組み合わせの総数 \} とする。R\{1, 0, 0\}?\{1, 1, 1\} という風に置くとうまくいきそうだと考えた。あとは上記の考察を拡張して、最終的なじゃんけんの手の A の部分を出力すればよい。

これを実装して提出したがWAが出た。実行時間は72msだったので、単純な実装ミスか、もっといい解法が存在するかの2択である。


感想

個人的に解けそうで解けない少し解ける難易度の問題ばかりで楽しかった。JOI予選初参加だったが、既に高3の年齢なので本選出場資格はなかった…。