Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

東京海上日動 プログラミングコンテスト2020 復習

今回の成績

スクリーンショット 2020-06-18 21.23.33.png

パフォーマンスは1270くらいでした。

今回の感想

この次の日のABCが悪すぎて全て持っていかれましたが、この回ももう少し戦えたかなと思いました。
しかし、結果的に黄diffと橙diffの問題を復習で解き切ることができたので、良かったかなと思います。
高難易度は冷静に時間をかければ(3時間くらい)できるので、このスピードを少しずつあげられる努力をしていきたいなと思います。
パフォーマンスはよくないですが、戦えるなと感じる回でした。最近このような回が続いているので、コンテスト中に解き終わることができるように

A問題

前から三文字を出力します。

A.py
s=input()
print(s[:3])

B問題

この問題をバグらせ続けたせいでパフォーマンスが200くらい下がりました。カスすぎる。
追いかけるAと逃げるBで相対速度を考えれば良いです。これがあるから自分が嫌いです。
コンテスト中でも平常心を失わないようにしたいですね。

B.py
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
if a<b and v<=w:
    print("NO")
elif a>b and v<=w:
    print("NO")
elif a<b:
    if -((a-b)//(v-w))<=t:
        print("YES")
    else:
        print("NO")
else:
    if -((-a+b)//(v-w))<=t:
        print("YES")
    else:
        print("NO")

C問題

区間の更新と見ただけで(実装したこともない)遅延セグ木を使おうとしました。データ構造やアルゴリズムに頼ろうとする姿勢では問題は解けません。全然駄目ですね。

問題文を読めばわかるように、それぞれの操作で電球の照らすことのできる区間が広がっていきます。また、電球の光の強さは操作時にその電球を照らしている電球の個数になります。 ここで、それぞれの操作時に電球の強さ$B_1,B_2,…,B_N$が与えられるとき、$i$番目の電球は$i-B_i$から$i+B_i$番目の電球を照らします。つまり、それぞれの電球が照らす電球をチェックする($0$を初期値とする長さNの配列を用意して照らされる区間の全ての電球を$+1$する)ことを繰り返せば、一回の操作は$O(N^2)$で実行可能です。また、照らされる区間を全て$+1$するのは効率が悪く、imos法を使うことで$O(N)$に計算量を落とすことができます

ここで、一見計算量は$O(NK)$と思えますが、実験をすると$K$回ではなく$\log{N}$回程度で終わらすことができることに気付きました。イメージとしては下図のように最小の光の強さが約2倍になっていくのが決め手になりました。自分の考察が不安でも最大ケースを作って確かめればTLEになるかは簡単に確認することができます

以上より、$O(N \log{N})$なので制限時間内のプログラムを書くことができます。

C.py
from itertools import accumulate
n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(k):
    b=[0]*n
    for i in range(n):
        b[max(0,i-a[i])]+=1
        if i+a[i]+1<n:
            b[i+a[i]+1]-=1
    a=list(accumulate(b))
    if a==[n]*n:
        break
print(" ".join(map(str,a)))

D問題

まず、個数制限のあるナップザック問題を基本に方針を組み立てれば良さそうというのは問題を見れば疑う余地はありません。

この前提の下で、ある頂点の先祖及びその頂点自身にあるものからアイテムを選ぶことができるので、根から子の頂点へとアイテムを順に選んでいけば(トップダウン)通常のナップザック問題と同様に考えることができます。この場合はクエリでの計算を避けることができるので、DPによる前計算で$O(NW_{max})$,クエリの計算で$O(Q)$となりますが、$NW_{max}$は最大で$2^{18} \times 10^5$となるのでこの方針では計算を間に合わせることができません。(1)

それに対し、クエリ内で計算を行うことを考えると、与えられた頂点から親の頂点へとアイテムを順に選んでいけば良い(ボトムアップ)ので、先ほどと似たナップザック問題を考えればDPによるクエリの計算で$O(Q W_{max})$となります。しかし、$Q W_{max}$は最大で$10^5 \times 10^5$となるので、この方針でも計算を間に合わせることができません。(2)

しかし、(1)と(2)は共に$10^{10}$程度であるので基本方針は間違ってないと考えられ、前計算をうまく行ってクエリの計算を効率よく行うことを考えます。

まず、(1)より前計算では$N$個の全ての頂点でDPを行うと間に合わないので$K$個の頂点でDPを行うとします。この時、DPの計算量は$O(KW_{max}\log{N})$で$W_{max}$が最大で$10^5$なので、$K$は最大で$10^3$程度であれば制限時間内に前計算を行うことができます。

ここで、クエリの計算では与えられた頂点から親の頂点へとアイテムを順に選んでいくので、より根に近い頂点のアイテムは繰り返し選ばれる可能性が高いことがわかります。したがって、$K$個の頂点は根に近い頂点の中から選べばクエリの計算をより高速に行うことができます(共通部分は事前に計算すると効率化できる!!)。また、$K\simeq2^{10}-1$であることから深さが$9$の頂点まではDPによる前計算が済んでいるものとできます。さらに、$N<2^{18}$より頂点の深さが最大でも$17$なので、深さ$10$から$17$の最大$8$つの頂点上にあるアイテムについてのみ計算すれば良いことがわかります。

したがって、$L=8$として$L$個の頂点にあるアイテムから選ぶ際の価値の最大化を考えれば良いです。ここで、DPを用いるとクエリの処理は$O(QLW_{max})$となり間に合いませんが、全列挙すると$O(Q2^L)$なので$Q2^L \simeq10^7$より、クエリの処理も間に合わせることができます。(ナップザック問題の基本は全列挙であることを忘れずに!!)

また、全列挙すると間に合わないが半分のみ列挙して後からまとめると間に合うような問題のことを半分全列挙と呼ぶらしいです。次に類題がでたら解けるようにしたいです。これを知っていれば、クエリで全列挙する方法が$O(Q N)$であり、半分全列挙で$O(Q \sqrt{N})$に計算量を落とせるという発想の仕方ができたかと思います。

また、クエリにおいて半分全列挙した後にDPで作成した配列へのアクセスは$O(1)$でなければならないので、DPで作成する配列にはそれぞれの重さW以下で最大のアイテムの価値を保存する必要があることにも注意が必要で、通常のDPで重さWで最大のアイテムの価値を求めた後に累積最大値を求めておく必要があります。

以上を実装して以下のようになりますが、実装が下手でPythonとPyPyで通せずC++では通せました。実装もだんだんうまくなっていければと思います。

D.cc
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
//#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

ll n;vector<pair<ll,ll>> vw;vector<vector<ll>> dp;
ll c1,c2;

void dfs(ll i){
    if(i==1){
        dp[i-1][vw[i-1].S]=vw[i-1].F;
    }else{
        ll j=i/2;
        FORD(k,c2,0){
            if(dp[j-1][k]!=0 or k==0){
                ll ne=k+vw[i-1].S;
                if(ne<=c2)dp[i-1][ne]=max(dp[j-1][k]+vw[i-1].F,dp[i-1][ne]);
            }
            dp[i-1][k]=dp[j-1][k];
        }
    }
    if(i*2<=c1 and i*2<=n)dfs(i*2);
    if(i*2+1<=c1 and i*2+1<=n)dfs(i*2+1);
}

signed main(){
    //入力の高速化用のコード
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    cin>>n;
    vw.resize(n);
    REP(i,n)cin>>vw[i].F>>vw[i].S;
    c1=1<<10;c2=100000;
    dp.resize(c1);REP(i,c1)dp[i].resize(c2+1);
    dfs(1);//cout << 1 << endl;
    REP(i,c1)REP(j,c2)dp[i][j+1]=max(dp[i][j],dp[i][j+1]);
    ll q;cin>>q;
    REP(i,q){
        ll v,l;cin>>v>>l;
        vector<ll> cand;
        while(v>c1){
            cand.PB(v);
            v=v/2;
        }
        ll r=SIZE(cand);//cout << r << endl;
        ll ans=0;
        REP(j,1<<r){
            ll v_sub=0;ll w_sub=0;
            REP(k,r){
                if((j>>k)&1){
                    v_sub+=vw[cand[k]-1].first;
                    w_sub+=vw[cand[k]-1].second;
                }
            }
            if(w_sub<=l)ans=max(ans,dp[v-1][l-w_sub]+v_sub);
        }
        cout<<ans<<endl;
    }
}
D_TLE_py
n=int(input())
vw=[list(map(int,input().split())) for i in range(n)]
#vmax=max(i[0] for i in vw)
#前計算用のDPを用意する
#1~2^10までは計算で先に求めておく
dp=[[0]*(10**5+1) for i in range(2**10)]
#前計算
def dfs(i):
    global n,vw,dp
    j=i//2
    for k in range(10**5,-1,-1):
        if dp[j-1][k]!=0 or k==0:
            if k+vw[i-1][1]<=10**5:
                dp[i-1][k+vw[i-1][1]]=max(dp[j-1][k]+vw[i-1][0],dp[i-1][k+vw[i-1][1]])
            dp[i-1][k]=max(dp[j-1][k],dp[i-1][k])
    if i*2<=2**10 and i*2<=n:
        dfs(i*2)
        if i*2+1<=2**10 and i*2+1<=n:
            dfs(i*2+1)
dfs(1)
for i in range(2**10):
    for j in range(10**5):
        dp[i][j+1]=max(dp[i][j],dp[i][j+1])
q=int(input())
for i in range(q):
    #それぞれの部分木をたどる
    #こっちで残りを全探索
    v,l=map(int,input().split())
    cand=[]
    while v>2**10:
        cand.append(v//2)
        v=v//2
    r=len(cand)
    ans=0
    for j in range(2**r):
        v_sub=0
        w_sub=0
        for k in range(r):
            v_sub+=vw[cand[k]-1][0]*(j>>k)&1
            w_sub+=vw[cand[k]-1][1]*(j>>k)&1
        if w_sub>l:
            continue
        else:
            ans=max(ans,dp[v-1][l-w_sub]+v_sub)
    print(ans)

E問題

包除原理であることはすぐに分かったのですが、自分の実装では間に合う気がせず解きませんでした。しかし、後々計算すればギリギリ通せることが分かったので、こちらの記事にて解説しています。

以下はC++で高速化して無理やり通した方針なので参考にしない方が良いかと思います。

また、以下ではDP[i][s,t]=(i個の数を選んだ時に論理積がsで論理和がtとなるような方法の数)として個数制限ありDPを実装しており、正確に実装すると無理矢理通すことができました。計算量的には間に合わないと思うので汎用的な方法ではありませんが、二次元以上のDPの場合はmapを使うと高速化できること,unordeed_mapではpairをキーにする場合が未定義であること,個数制限ありDPではDPで用意する配列の後ろ側から決めれば仮に保存する用の配列が必要ないかつ高速化できること,の三つを学びました。

E.cc
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,k,s,t;cin >> n >> k >> s >> t;
    vector<ll> b(n);REP(i,n)cin >> b[i];
    vector<ll> a;
    REP(i,n){
        bool f=true;
        REP(j,18){
            if((s>>j)&1 and !((b[i]>>j)&1)){
                f=false;break;
            }
            if(!((t>>j)&1) and (b[i]>>j)&1){
                f=false;break;
            }
        }
        if(f)a.PB(b[i]);
    }
    n=SIZE(a);
    k=min(n,k);
    //cout << n << endl;
    //cout << n << endl;
    //unordered_mapはpairをキーにできない
    //dp_subを用意すると遅い(用意しないだけで数倍変わる)
    //逆順にやればOK
    vector<map<pair<ll,ll>,ll>> dp(k);
    REP(i,n){
        FORD(j,k-2,0){
            for(auto l=dp[j].begin();l!=dp[j].end();l++){
                dp[j+1][MP((l->F.F)&a[i],(l->F.S)|a[i])]+=(l->S);
            }
        }
        dp[0][MP(a[i],a[i])]=1;
    }
    ll ans=0;
    REP(i,k)ans+=(dp[i][MP(s,t)]);
    cout << ans << endl;
}

F問題

Eまで解いて満足したので今回は割愛します。

DaikiSuyama
PythonとC++で競技プログラミングをしていました。最近は機械学習を勉強しています。 FXや株の自動売買、音楽の自動生成に興味があります。 [今]Djangoを勉強しています。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away