■
日本沈没 (Japan Sinks)
感想
JOI予選の4問目にしては比較的優しい難易度だったのではないでしょうか.
問題概要
今のところ問題は公開されていないので言及は控えます.
解法
こういうのは大体,数列Aの最大値から降順に処理するとうまくいきます.
具体的にはmaxAからminAまでのある数をiとすると今から高さi以上の島を陸地にすると考えます.
この時にi+1の時の島の数がわかればiの時の島の数がわかります.
詳しく説明すると,iの時,陸地にするその両サイドがすでに陸地だったらどうなるでしょうか？
答えはi+1の時に出した陸地の数が一つ減りますね.
同じように片側だけすでに陸地なら？
答えは変わりません.
両サイドとも沈没しているのら？
答えはi+1の時の陸地の数から一つ増えますね.
あとはこれを実装すればよいです.
これでACできる！！！！わけではないんですよね…
コーナーケースがあります！！！！！
それは数列Aの要素が全部0の時です！！！（これ考えた人、性格が悪s）
注意点
この手の問題はCodeforcesでよく問われる気がしますので、Codeforcesをやろう！
おーじのゆるゆる精進日記 #5
Christmas
感想
再帰のいい練習問題です.
問題概要
レベル0バーガーはパティ1枚.
レベルLバーガーは(パン1枚)+(レベルL-1バーガー)+(パティ)+(レベルL-1バーガー)+(パン1枚)で構成される.
下からX層の中で何枚のパティがありますか？
解法
レベルLバーガーの内容はレベルL-1バーガーがわかればわかります.
よって再帰関数f(n,x)をレベルnバーガーの下からx層に含まれるパティの枚数として定義します.
ここからは公式の解説と同じような解法になりますのでこちらで(https://img.atcoder.jp/abc115/editorial.pdf)許してください><
この問題はなかなか言語化するのが難しいです.
とにかくレベルLバーガーに関して下から再帰で実装をしていきます.
そのままだとTLEするためレベルL-1の層の厚さやレベルL-1のパティの枚数を前計算してあげればokです.
注意点
再帰大事！！！
おーじのゆるゆる精進日記 #4
パスタ (Pasta)
感想
みなさんはこれくらいのDPの実装は一瞬で済ませるんだろうなあ(泣)
問題概要
トマトソース,クリームソース,バジルソース,のパスタがある(美味しそう).
3日連続して同じパスタを選んではならない.
K日分のパスタの予定(何ソースにするか)があらかじめ定まっている.
条件を満たす予定は何通り?
解法
動的計画法を考える.
dp[i][j][k] := i日目にパスタj,i - 1日目にパスタkを食べる通り数
まずはDPの初期化ですが、これがなかなか厄介です.
4つに分けて説明します.
①一日目と二日目のパスタの予定があらかじめ定まっているとき
dp[2][(二日目の予定)][(一日目の予定)] = 1
②一日目のみパスタの予定があらかじめ定まっているとき
dp[2][1][(一日目の予定)] = 1
dp[2][2][(一日目の予定)] = 1
dp[2][3][(一日目の予定)] = 1
③二日目のみパスタの予定があらかじめ定まっているとき
dp[2][(二日目の予定)][1] = 1
dp[2][(二日目の予定)][2] = 1
dp[2][(二日目の予定)][3] = 1
④一日目も二日目もパスタの予定が定まっていないとき
全通り1(これは自明なので)
あとは遷移です.
遷移は以下の2通りです.
①i日目予定があらかじめ定まっているとき
dp[i][(i日目の予定)][j] += dp[i - 1][j][k]
(なおj,kは1以上3以下の整数で一日目の予定とjとkが等しい時はこの処理はしない)
②①じゃないとき
dp[i][j][k] += dp[i - 1][k][l]
(なおj,k,lは1以上3以下の整数でjとkとlが等しい時はこの処理はしない)
なぜj=k=lの時に処理を行わないかというと、3日連続して同じパスタを選ぶことは禁じられているからです.
注意点
とりあえず必要な情報は遷移に取り入れてみる.
おーじのゆるゆる精進日記
Pair Distance
感想
絵を描こう.
問題概要
a[i]とa[j]の差の絶対値の合計を求めよう.
この時1 ≦ i < j ≦ Nが成立しなければいけない.
解法
ソートしたくなる.(絵を描けばわかる)
後は、その区間が何回出てくるかを掛ける.
注意点
絵を描こう！
直感を信じよう！(コンテスト中にソートしたいなあ,うーんやめよってなったので)
おーじのゆるゆる精進日記
Sum AND Subarrays
感想
上からビットを立ててそれを実現できるかという解法で実装を試みましたが実装できず.
問題概要
K個の数値の論理積を最大化しよう.
解法
論理積ということは一つでも0のビットがあればそのビットは立たない.
より上の方のビットが立っていれば嬉しい.
計算量的にも余裕があるので上からこのビットを立たせられるかの探索が思いつく.
あとは実装.
具体的にはこれまでの答えをans,部分列の値をdataとすると,ansと立たせたいビットでorを取ります.(これをBとする)
そして、値を一つ一つ比べてB & data = Bが成り立つ個数を調べます.
これがK個以上であればそのビットは立たせられます.
ビットは高々40回ほど回せばおっけーなのでTLEはなさそう.
注意点
論理積の基本A & B = Aが及ぼすあれこれを把握する.
今回では1LL<<i(0≦i≦40)みたいな感じでするとうまく立たせたいビットを動かせますよ！！これぐらい知っといてよ俺...
おーじのゆるゆる精進日記
前書き～
自分に変化を与えさらなるレート向上を図るため、解法の整理や何がダメだったかを言葉にするという目的から精進日記をつけることにしました.
緩いです(多分)
チップ・ストーリー ～白銀編～
感想
コンテスト中に解けなかったのでとても悲しかった.
解法は出ていたが数学ができず...
問題概要
100 × 100 のマスにP[i] × Q[j]を入れる.
PとQは何通りかな？
解法
Nが100000以下であることからO(N)ができることに気づく.
ここで数列Pの最大値maxPを回すことができる.
この時maxQはN / maxPとなる.
後はこれが何通りあるかを下記の式で求めます.
(maxP^10 - (maxP - 1)^10) × maxQ^10
注意点
maxP^10 - (maxP - 1)^10の計算の際に負の世界に突っ込んでしまうことがある.
その時はMODを足しといて余りを取ろう！
以上です～(ドワンゴのB問題も書こうかな)
