2019-03-25

AGC032A - Limited Insertion 解説

解説

AGC二週連続でなんもわからんかったので腹いせのメモ

問題文

すぬけ君は空の数列 $a$ を持っています。
すぬけ君は $a$ に対して $N$ 回操作を行います。
$i$ 回目の操作では ${ 1 } { \leq } { j } { \leq} { i }$ を満たす整数 $j$ を選び、 $a$ の先頭から $j$ 番目に $j$ を挿入することができます。
長さ $N$ の数列 $b$ が与えられます。 $a$ 回の操作後に ${a}$ が $b$ と一致することがあるかどうかを判定し、可能ならばそれを達成する操作手順の一例を示してください。
問題リンクhttps://atcoder.jp/contests/agc032/tasks/agc032_a

与えられる数列が構築可能か判定してください。構築できるならその手順を示してください。という問題。
「 $a$ に要素を追加して $b$ にする操作」を一つの関数 $f$ とみると、 $a$ が入力されたときに $b$ が出力される関数 $f$ を見つけてくださいという問題に言い換えられる。
じゃあこの関数 $f$ を探したい気持ちになるのだけど、そもそも存在するかわからないし実際に構築するのは難しそう。
難しそうなので他の方法を考えてみる。まず関数 $f$ がどんな関数なのか考えてみると、関数 $f$ が存在するとき

$a$ というただ一つの入力に対して、 $b$ というただ一つの出力が得られる

このことから

「値域 $Y$ の各元 $y$ に対して、 $f$ で $y$ に写されるような定義域 $X$ の元 $x$ がちょうど一つ存在する」 https://ja.wikipedia.org/wiki/%E9%80%86%E5%86%99%E5%83%8F より

という条件を満たしており、関数 $f$ の逆関数がありそうなことがわかる。
ここで言う関数 $f$ の逆関数とは数列 $b$ を入力したときに数列 $a$ が返ってくる関数のこと。これを関数 $f^{-1}$ と書く。
ここで関数 $f^{-1}$ はどのようなものかを考えると関数 $f$ の逆なので、
「 $b$ から要素を削除して $a$ にする操作」だとわかる。つまり、

すぬけ君は数列 $b$ を持っています。すぬけ君は $b$ に対して $N$ 回操作を行います。
$i$ 回目の操作では ${ 1 } { \leq } { j } {\leq} {N}{-}{i}{+}{1}$ を満たす整数 $j$ を選び、 $b$ の先頭から $j$ 番目の $j$ を削除することができます。
長さ $N$ の数列 $b$ が与えられます。 $N$ 回の操作後に $b$ が空の数列 $a$ と一致することがあるかどうかを判定し、可能ならばそれを達成する操作手順の一例を示してください。

という問題を解けば、求めた操作の手順の逆が元の問題の答えになる。
この操作(関数 $f^{-1}$ )を求めるのは実際にシミュレートすればいいだけなので元の問題の操作手順を求めるよりも簡単。
関数 $f$ の存在を仮定して関数 $f^{-1}$ を求めてみる。具体的には $1$ -indexd で

$1$ . ${b_j } {=} {j}$ となる $j$ の中で $j$ が最も大きいものを削除する
$2$ . $1$ の操作を $b$ から要素が削除できなくなるまで繰り返す

${1}, {2}$ の操作をすればいい。数列から要素を取り除けるならば $N-i+1$ は常に数列の長さと等しいので特に気にしなくていい一番後ろにあるものを削除しなけばいけないのは、例えば
${b} : {1}, {2}, {3}$
という数列があったときに $1$ を取り除いてしまうと
${b} : {2}, {3}$
となり、 $2$ をどうやっても取り除けなくなるから。
このように削除できるもので一番後ろ以外を削除してしまうと、空にできる数列であっても空にできなくなってしまう。
逆に ${1}, {2}$ の操作を繰り返しても数列 $b$ を空にできないならば関数 $f^{-1}$ は存在せず、また関数 $f$ も存在しない。
このシミュレートには $O(N^{2})$ かかるので $O(N^{2})$ でこの問題を解くことができた。

$a$ から $b$ を構築できますかという問題で、 $b$ から $a$ を構築できますかという問題を考えるのは定石っぽい。

#include<iostream>
#include<list>
using namespace std;

int main(){
    int N;
    cin >> N;
    list<int> B;

    for(int i=0;i<N;i++){
        int b;
        cin >> b;
        B.emplace_back(b);
    }

    list<int> ans;

    while(!B.empty()){
        int idx = B.size();
        for(auto b = B.rbegin(); b != B.rend(); b++){
            if(*b == idx){
                ans.emplace_front(*b);
                B.erase(next(B.begin(),idx-1));
                break;
            }
            idx--;
        }
        if(idx == 0) break;
    }

    if(ans.size() != N) cout << -1 << endl;
    else{
        for(auto b : ans) cout << b << endl;
    }
}

2019-02-11

JOI2019本戦オープン参加記

その他

先日の「みんなのプロコン2019」で激冷えをして、精神が雀の涙ほどしか残っていませんでしたが出ました。(ア)
Twitterでよく見かける人たちが本選に出場しているのでね。例え試験期間であっても出ますよ。
あ、僕は予選Bランク落ちでした。(つらいね)
本戦は9:00からだったので9:30に起きた僕は「日本情報オリンピック起床部門Cランクだな」とか思っていたのですがオープンは10:00からでしたね。
URLエスパーして開始20分前にログインしてしまったけど大丈夫だったんだろうか...(これ後でTwitter見たらちょうどページが公開された瞬間っぽかったです)

一問目　

ビ太郎何？勇者なら剣で戦えや。
各行について左向きにOの出現回数、各列について上向きにIの出現回数の累積和をとって、マスがJのときにそのマスについてのOとIの累積和の積をとってそれらを足していくと答えになります。
ここの制約 (i, j, k, ℓ) (1 ≦ i < k ≦ H, 1 ≦ j < ℓ ≦ W) を見ていなかったために10分弱溶かしました(ア)
とりあえず27分で一問目AC！！！最低限の目標は達成です！

2問目

全然わからなかったし、小課題１通そうとしたら無限にバグらせるし、最悪だったけど、愚直にO(MN)の貪欲書いたら50点もらえた。3時間36分
TL見てたらpriority_queueでO(MlogN)に落とせるっぽいです。それはそうだな〜〜〜〜は〜〜〜〜〜〜お前、マジで、お前、は〜〜〜〜〜〜〜なんで出てこなかったんだ悔しい。
priority_queueが出てこなくて高速化できないのやめたい(去年のPCK予選でも似たようなことをやらかしたので)

3問目　

なんですかこれ？小課題3は奇偶で場合分けしたら上手く行くかなと思ったんですが無理でした。

4問目　

問題を見ましたが、読めませんでした。あとでTwitterをみたら解いている人が多かったので比較的簡単だったのかも知れません。僕にとっては簡単ではありませんが...

5問目

見ていません

総評

2完したかった...他の問題の部分点全く見えなかったの悔しい...
正直、本戦に通っていなくて良かったと思いました。つくばまで行って椅子を温め続けるだけ、というのは家で椅子を温めるよりも何倍も無力感が強いと思うので。
でもJOIは大規模オフ会的な面もあるので、行きたくなかったというと嘘になりますが。

僕は三年になる(予定)のでJOIにはもう出られませんが、PCK(パソコン甲子園)には出るつもりです。PCKでは本戦に行きたいですね。

冷えた後は一時間くらいあ〜〜無理〜〜〜〜競技プログラミングが世界一下手〜〜って感じで気分が沈みがちなんですが、1時間を過ぎると無性に競技プログラミングがしたくなってくるんですよね。不思議。

2018-12-09

JOIさん、何故グラフ問を出してくれないのですか

解説

JOI予選落ちが確定しました。グラフが比較的得意だったので、グラフを絶対に通そうと思って練習してきたんですが、今年はなぜか出ませんでしたね。とてもかなしいです(出してくれよ...)
Dが簡単だったという声をよく聞くんですが、僕は解けませんでした...(つら🌾) くちもちくんに解説してもらったんですが、ちょっと詰まらせたのでメモ。考え方が典型っぽいしね。

日本列島、沈没させるか？出現させるか？

　小課題１

制約が N≦2000, Ai≦2000 なので、海面の高さを全探索しても間に合います。面倒なので愚直に沈没シミュレーションをします。
i == 0 と i == N の時の場合分けが面倒なので、Aを1-indexedにして、A[0] と A[N+1]に０を置いておきます。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))

int main(){
    int N;
    cin >> N;
    vector<int> A(N+1);
    rep(i,N) cin >>A[i+1];
    A[0] = 0;A.push_back(0);

    int ans = 0;
    for(int h=0;h<=2000;++h){
        int cnt = 0;
        for(int i=1;i<=N+1;++i){
            if(A[i] > h && A[i-1] <=h) cnt += 2;
            else if(A[i] <= h && A[i-1] > h) --cnt;
        } 
        ans = max(ans,cnt);
    }
    cout << ans << endl;
}

島の左端で+2して右端で-1することで島があれば1足すという操作を実現しています。

小課題2

よく考えると高さを全探索する必要はなくて、「海面がちょうどA[i]が沈む高さの時」だけ島の数が増減するのでこの時だけ見ればよいです。(僕はこれが出てきませんでした。たぴ。）より具体的には、A[i]について「海面の高さがA[i]未満」の時の島の数が分かればよいです。（A[i]以下にすると、全部mとかのコーナーケースに引っ掛かるので未満にしました。海面が０の時を調べればいいんですがめんどうなので)
N ^ 2が間に合うので

#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))

int main(){
    int N;
    cin >> N;
    vector<int> A(N+1);
    set<int> st;
    for(int i=1;i<=N;++i)cin >> A[i],st.insert(A[i]);
    A[0] = 0; A.emplace_back(0);

    int ans = 0;
    for(int h : st){
        int cnt = 0;
        for(int i=1;i<=N+1;++i){
            if(A[i] >= h && A[i-1] < h) cnt += 2;
            else if(A[i] < h && A[i-1] >= h) --cnt;
        } 
        ans = max(ans,cnt);
    }

    cout << ans << endl;
}

このようにA[i]をsetに突っ込んであげて、小課題１と同じように島の数を調べていきます。

小課題３

制約が・1≦N≦100000(=105) ・0≦Ai≦1000000000(=109) (1≦i≦N) なので、N ^ 2が通りません。今までの方法ではできないので、別の方法を考えます。よく考えると、島の数はある高さまで増加して、そこから減少していきます。なので高さを昇順か降順に見ていき、今の島の数を持っておいて島の数を増減させればNでいけそうです。

個人的には沈めたいんですが、全部０の時の場合分けが面倒なので†出現†させます。

#include<bits/stdc++.h>
using namespace std;
using P = pair<int,int>;
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))

int main(){
    int N;
    cin >> N;
    vector<int> A(N+1);  A[0] = -1; 

    for(int i=1;i<=N;++i) cin >> A[i];
    auto res = unique(A.begin(),A.end());
    A.erase(res,A.end());

    priority_queue<P,vector<P>> que;
    for(int i=1;i<A.size();++i) que.push({A[i],i});
    A.emplace_back(0);
    que.push({0,1});

    int island = 0,ans = 0; 
    int now_h = 1e9+7;
    int p[3] = {-1,0,1};

    while(!que.empty()){
        P h = que.top(); que.pop();
        int cnt = 0;
        if(now_h != h.first) ans = max(ans,island);
        now_h = h.first;
        if(A[h.second-1] < h.first) ++cnt;
        if(A[h.second+1] < h.first) ++cnt;
        island += p[cnt];
    }
    cout << ans << endl;
}

高さを降順にとりだすのは、priority_queueにぶん投げます。同じ高さの区画をすべて取り出してから更新するようにするとこわれません(n敗)

f:id:UGIS:20181209230827p:plain

次に島の数の増減を考えます。図を描くと

A[i]が両隣より高いとき島が増える
A[i]が両隣のどちらか片方だけより高いとき、島の数は変わらない
A[i]が両隣よりも低いとき島が減る

ことがわかります。 ifを書くのは面倒なので、隣より高ければcntを+1してcntに応じて増減させています。ここで、僕はもっと早く気が付くべきだったんですが、下の図のようなときにこわれます。

f:id:UGIS:20181209230832p:plain

これは、ひとつずつ見ていったときに、島が増える条件を満たすものがないからです。同じ高さが連続しているときにこわれることがわかったので、連続しているものを圧縮したい気持ちになります。そこで登場するのがuniqueちゃんです。

この関数は、隣り合った重複要素を除いた要素を、範囲の先頭に集める。この関数によってコンテナから直接要素が削除され、コンテナの要素数が減るようなことはない。コンテナから実際に要素を削除する場合は、この関数の戻り値として、先頭に集められた重複なし範囲の末尾の次を指すイテレータが返るため、そのイテレータを介してコンテナのerase()メンバ関数などを呼び出し、削除を行うこと。

これ、ただ単に重複要素を後ろに持ってくるだけだと思っていたんですが、隣合う重複要素限定なんですね... これを使うことで連続している部分を圧縮できます。これで、こわれることがなくなったのでこの問題が解けました。

必要ない部分を見ない、前回の値を使って更新していくというのは典型感があるのでこれを機にしっかり身に着けていきたいですね

2018-06-30

絶対値ぽまえ絶対許さん

解説

codeFlyer （bitFlyer Programming Contest）オープンコンテスト B - 交通費

まず、問題文を読んで入力を作ります。

制約をよく読むと　

$X_{i} < X_{i + 1}$ ( $1 \leq i < N$ )　

なので、すでにソートされていることが分かります。制約的にn^2だと間に合わないですし、二分探索を使ってくださいと言っている気がするので、二分探索を使いましょう。

使いどころとしては

X：1 5 10 20 30　、c＝７、d＝3　

を例にとると、

｜1-7｜ > 3 　　｜20-7| > 3　

なのでこの時はd円でよいことが分かります。

つまり、計算すればいいところは

初めて｜Xn - C｜ <= d となるところから　｜Xn - C｜ > d となるところまで

ということが分かります。ここを二分探索で調べます。

しかし、このままではまだ不十分です。よく考えると

X:590 593 633 642 743 859 872　、ｃ=642,d=850108511

のときのようにdがクソデカだと、どうしてもすべてのXnについて

｜Xn - C｜ <= d 　　になってしまい、計算量がn^2になってしまいます。

ここで、絶対値の計算する必要ある？と気が付ければこの問題は解けます（僕は気が付けませんでした。つらいね）

はい。絶対値で表記されていますが、別に絶対値のまま計算する必要はないんですね。

というのも、

Xn <= C　の時、　｜Xn - C｜　= C - Xn　 (例｜16 - 64｜ = 64 - 16 = 48)

Xn >= C　の時、　｜Xn - C｜　= Xn - C (例｜334 - 57｜　= 334 - 57 = 277)

となるからです。そうすると、

初めて｜Xn - C｜ <= d となるところから　｜Xn - C｜ > d となるところまで

を部分数列Yとすると、

C*(項の数) - 数列YのC以下の数の和 + 数列YのC以上の数の和- C*(項の数)

と(それ以外の項)*dを足せば求められそうです。累積和を使いましょう。

X：590 593 633 642 743 859 872, c=633,d = 20 を例にとると、

｜Xn - C | > d ｜Xn - C｜<= d　｜Xn - C | > d

　590 593 <-| 　　 633 642　　　|-> 　743 859 872

　　　　　　　　｜　　部分数列Y ｜

このような構成になっていることがわかるので、

数列YのC以下の数の和　の求め方を考えるとC以下の項までの和から( | Xn - C | <= d )

になるまでの和を引くと求められそうです。

項の数も、C以下の項の数 - ( | Xn - C | <= d )になるまでの項の数　で求められます。

数列YのC以上の数の和　も同様に　｜Xn - C｜ > d　になるまでの和 - C以下の和で求められて、項の数も同じようにして求められます。

それ以外の項は　数列Xの項の数 - 部分数列Yの項の数　で求められることが分かります

これまた二分探索でC以下の項で一番大きいものを探してやればいいです。

これでこの問題は解決です。

2018-03-19

２.Atcoder Grand Contest21 Digit Sum 2

解説

A - Digit Sum 2

問題文

N 以下の正の整数の 10 進法での各桁の和の最大値を求めてください。

制約

1≤N≤10¹⁶
N は整数である

自力では分からなかったので、正解者のコードを見て考察。

Nの条件から、全探索は不可能。

ですが、そもそも探索する必要がありません。

何故かというとN以下の正の整数の各桁の和が最大になるときは必ず、

・6999

・9

・89

・2999

先頭、一番左の桁以外が９になるからです。

０～９の整数の中で一番大きいのは９ですから当然ですね。

つまり、この問題は

１.桁の数 - １回合計に９を足す

２.先頭の桁の数字を合計に足す

という操作だけで十分そうです。

ですが、例えばN = 7000 のとき。

7000以下で各桁の和が最大値を取るのは、6999のとき、33です。

しかし、上の1、2の操作を行うと 9 + 9 + 9 + 7 = 34　となってしまいます。

ではどうやって解決するか。例を出して見ていきます。

N = 6997の時、各桁の和が最大値を取るのは 5999の時 32。

N = 5879の時、各桁の和が最大値を取るのは 4999の時 31。

N = 3279の時、各桁の和が最大値を取るのは 2999の時 29。

N = 114514の時、各桁の和が最大値を取るのは 99999の時 45。

規則性が見えてきたと思います。どれも最大値を取るのは下N -1桁が 9 の時。

そして、先頭桁の数が、-1 されています。

ここから、

1.桁の数 - １回合計に９を足す

2.先頭の桁の数字 - 1 を合計に足す

この二つの操作で求められそうです。

ちょっとまって！

それじゃ6999とか4999とか最初から先頭以外9の数字だとおかしくなるじゃん！

と思う方はちゃんと解き方を理解できています。

そうです。先の二つの操作だと、6999のときに、5999の各桁を足してしまいます。

ならばどうすればよいかと言うと

6999などの最初から先頭以外9の数字を存在できなくすればいいだけです。

は？と思うかもしれませんが理屈は簡単です。

１を足して繰り上げてしまえばいいのです。

7688でも、7933でも最大値をを取るのは6999の時だけです。別に1を足したくらいじゃに何も変わりません。

対して、6999に1を足せば7000です。

そして、7000の桁は４桁なので9+9+9

７から1を引いて６。

合計で３３です。　少し戻って確認してみてください。6999の時は33です。

なにも変わらないですね。

最終的に、問題を解くために必要な工程は３つ。

1.N に 1を足す

2.Nの桁数 - 1回合計に9を足す。

3.合計に先頭の数　- 1を足す。

これで、この問題は解決です。

2018-03-15

競プロ初心者の秘密ノート　1.Atcoder Beginner Contest 081B - Shift only

この記事はコンテスト参加歴二回の競技プログラミング初心者の僕が

解いた問題を解説することで理解しているかを確認する。という目的で書くものです。

これはどんな処理なのか。なぜ、その処理を行うのか。を明確にするのが目標です。

用語、組み込み関数などプログラミングに関する知識が無に等しいのでそのあたりも。

1.Atcoder Beginner Contest 081B - Shift only

問題

黒板に NN 個の正の整数 A1,…,ANA1,…,AN が書かれています。
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます

・黒板に書かれている整数すべてを，2 で割ったものに置き換える．

すぬけ君は最大で何回操作を行うことができるかを求めてください．

【解法】

f:id:UGIS:20180315202627p:plain

けんちょんさんの写経になっております・・・

無限ループから抜け出す方法が思いつかなかったんや。

けんちょんさんはQiitaなどで競プロ等の記事を書いている方です。初心者向けの記事もいくつかあり、どれも本当に丁寧に解説して下さっているので、僕はとても助かっています。ありがとうございます。

方法としては

１、数字が何個書かれているか受け取る。

２、書かれている数字を受け取る。

３、問題文から、書かれた数字が偶数である限り操作を続ける必要があるので
　　ループさせます。何度ループさせれば良いかこの時点では分からないので

　　無限に回します。

４、bool型を使います。
　　bool型はture(1)かfalse(0)しか値を持つことができません。
　　ここでは、奇数があるかどうかを判定するのに使います。
　　あればture、無いならfalseです。

　　なぜ、偶数ではなく奇数を見つけるのかと言うと、奇数がある時点で

　　操作が行えないからです。ループの終わりが明確になるんですね。

　　最初は奇数があるか分からないので、falseにしておきます。

５、for文で書かれた数字が偶数であるかどうか判定をしていきます。

　　１つずつ調べます。全探索です。

　　奇数があった場合、先程のbool型の値をtureにします。

６、ループを抜けるための処理です。

　　奇数があるときにループから抜け出せるようにします。
　　if文は条件式がtureの時だけ後に続く処理を行います。
　　このためにboolを使う必要があったんですね！
　　（別にboolじゃなくてもできるけど）
　　breakを使うことでループから抜け出します。

７、ここからは奇数がなかった場合の処理です。
　　すぬけ君は，黒板に書かれている整数がすべて偶数であるとき

　　次の操作を行うことができます．
　・黒板に書かれている整数すべてを，2 で割ったものに置き換える．
　　と、あるのでfor文ですべて2で割ったものに置き換えます

８、操作が行われた回数をカウントします。

　　６、の後ならどこでもいいです。

【別解】といってもほとんど同じですが

f:id:UGIS:20180315232410p:plain

可読性が消えた（）

上の７を５の下に持ってきただけ。

与えられた数を２で素因数分解して、２の最小個数を数えれば解けるのではと思ったのが間違いだった。全然できなくて時間が消えました。人間には簡単にできても機械にやらせるのは難しい。

問題文

一問目

2問目

3問目

4問目

5問目

総評

日本列島、沈没させるか？出現させるか？

小課題１

小課題2

小課題３

問題文

制約

解いた問題を解説することで理解しているかを確認する。 という目的で書くものです。

1.Atcoder Beginner Contest 081B - Shift only

一問目　

3問目　

4問目　

　小課題１

解いた問題を解説することで理解しているかを確認する。という目的で書くものです。