2019-12-18

CODE FESTIVAL 2016 qual C Friction(800)

問題

考察

操作によって生じるコストを、生じる場所によって別々に考えてみることにします。そうすると、操作によってかかるコストの総和の下界が $\sum{(i列目とi+1列目で生じるコストの総和の最小値)}$ であることが分かります¹。これが達成可能かどうかを考えてみます。

列 $i$ に対する操作を整数 $i$ で表すことにします。まず、各 $i(1 \le i \le N-1)$ に対し、列 $i$ と列 $i+1$ の間で生じるコストの総和が最小となるような操作列を取ってきます。これらをもとに、全体に対する操作列を作ることを考えます。列 $i$ と列 $i+1$ の間でかかるコストは、列 $i$ と列 $i+1$ をどのような順番で操作したかだけによります。よって、全体に対する操作列の中で、 $i$ と $i+1$ が取ってきた操作列と同じ順番で並んでいればよいです。このような操作列は、まず $1$ と $2$ を並べてから、 $i=3,4,...,W$ を順番に適切な位置に(取ってきた操作列と同じ順番で現れるように)挿入すれば作ることができます。

これで下界が達成できることが分かりました。この下界を求めるためには $W=2$ の場合を解けばよく、DPを頑張るとできます。

#include<bits/stdc++.h>
using namespace std;
 
const int INF=1e9;
 
int main()
{
   int H,W; cin>>H>>W;
   vector<string> s(H);
   for(int i=0;i<H;i++) cin>>s[i];
 
   int ans=0;
   for(int j=0;j<W-1;j++){
      // cost[x][y]:=j列目がx個、j+1列目がy個の状態のときに操作にかかるコスト
      vector<vector<int>> cost(H+1,vector<int>(H+1));
      for(int x=0;x<=H;x++) for(int y=0;y<=H;y++){
         if(x==0 or y==0) cost[x][y]=0;
         else cost[x][y]=cost[x-1][y-1]+(s[x-1][j]==s[y-1][j+1]);
      }
      // dp[x][y]:=j列目がx個、j+1列目がy個の状態にするのにかかるコストの総和のmin
      vector<vector<int>> dp(H+1,vector<int>(H+1,INF));
      dp[H][H]=0;
      for(int x=H;x>=0;x--) for(int y=H;y>=0;y--){
         if(x+1<=H) dp[x][y]=min(dp[x][y],dp[x+1][y]+cost[x+1][y]);
         if(y+1<=H) dp[x][y]=min(dp[x][y],dp[x][y+1]+cost[x][y+1]);
      }
      ans+=dp[0][0];
   }
   cout<<ans<<endl;
   return 0;
}

まとめ

コスト(など)が複数の場所で生じるとき、各場所ごとに考える
下界が達成可能か

感想

コストを生じる場所ごとに考えるという思考が重要だったと思います。うまく言語化できていませんが、これはbit演算が出てくる問題で、各桁ごとに見るという思考と似ていると思いました。

全体に対して適当に操作したときにi列目とi+1列目の間で生じるコストは、i列目とi+1列目で生じるコストが最小になるように操作したときのコスト以上になっているはずだからです。↩

2019-12-17

第二回全国統一プログラミング王決定戦本戦C　Largest N(600)

atcoder.jp

問題

$H \times W$ のマス目が与えられます。各マスは黒か白で塗られています。このマス目に含まれる'N'の大きさの最大値を求めてください。ここで'N'とは、正方形状のマス目であって、両端の列のマス目と、左上から右下にかけての対角線上のマス目が黒で塗られているもののこととします。

制約

$1 \le H,W \le 3000$

考察

まずは全探索を考えます。グリッドに含まれるすべての正方形について、条件を満たしているか判定すればよいです。各マスについて、下と右斜め下にいくつの黒マスが連続しているかを前計算しておけば、 $O(1)$ で判定できます。しかし、正方形は $H \times W \times min(H,W)$ 個くらいあるのでこのままでは間に合いません。

次に高速化について考えます。正方形の右下を固定したときに、左上が満たすべき条件について考えます。右下の座標を $(i,j)$ とします。まず、左側のたて棒として使うものは、図の赤い線を超えていなければならないということが分かります。また、左側のたて棒は、図の緑の範囲に収まっていなければなりません。この2つの条件を満たしていれば、そのたて棒を使って'N'を作ることができます。
f:id:tekihei:20191217203504j:plain:w400

$(i,j)$ を右下とする最大の'N'は、この2つの条件を満たすたて棒のうち、最もインデックスが小さいものを使ったものです。このような縦棒は、赤い線を超えている縦棒のインデックスの集合をsetで持っておけば、二分探索で対数時間で求めることができます。この集合は、priority_queueに縦棒がどこまで伸びているかとインデックスのペアを持たせておくことで管理できます。

#include<bits/stdc++.h>
using namespace std;
 
int cntD[3010][3010];
int cntU[3010][3010];
 
int main()
{
   int H,W,K; cin>>H>>W>>K;
   vector<vector<int>> a(H,vector<int>(W,1));
   for(int i=0;i<K;i++){
      int r,c; cin>>r>>c;
      r--; c--;
      a[r][c]=0;
   }
 
   for(int j=0;j<W;j++){
      // 上にいくつ続いているか
      for(int i=0;i<H;i++){
         if(a[i][j]==0) cntU[i][j]=0;
         else cntU[i][j]=(i-1>=0? cntU[i-1][j]:0)+1;
      }
      // 下にいくつ続いているか
      for(int i=H-1;i>=0;i--){
         if(a[i][j]==0) cntD[i][j]=0;
         else cntD[i][j]=(i+1<H? cntD[i+1][j]:0)+1;
      }
   }
 
   auto solve=[&](int i,int j)
   {
      using P=pair<int,int>;
      using PriorityQueue=priority_queue<P,vector<P>,greater<P>>;
      set<int> S;
      PriorityQueue Q;
 
      int res=0;
      for(;i<H and j<W;i++,j++){
         if(a[i][j]==0){
            // 白マスがあればもう使えないので空にする
            S.clear();
            PriorityQueue().swap(Q);
            continue;
         }
 
         Q.push({i+cntD[i][j]-1,j});
         S.insert(j);
         // 'N'が作れるもののうち、インデックスが最小のものを取ってくる
         auto itr=S.lower_bound(j-cntU[i][j]+1);
         assert(itr!=S.end());
         res=max(res,j-*itr+1);
         // もう使えないものを消去
         while(!Q.empty() and Q.top().first<=i){
            S.erase(Q.top().second);
            Q.pop();
         }
      }
      return res;
   };
 
   int ans=0;
   // 正方形の対角線を全探索
   for(int j=0;j<W;j++) ans=max(ans,solve(0,j));
   for(int i=0;i<H;i++) ans=max(ans,solve(i,0));
   cout<<ans<<endl;
   return 0;
}

実は、最初の愚直な全探索に「すでに見つけた解以下のものは探索しない」という枝狩りをいれるとかなり速くなるみたいで、通ります(上のものより速いです)。なんでここまで速くなるかはよく分かってないです。

#include<bits/stdc++.h>
using namespace std;
 
int cntD[3010][3010];
int cntRD[3010][3010];
 
int main()
{
   int H,W,K; cin>>H>>W>>K;
   vector<vector<int>> a(H,vector<int>(W,1));
   for(int i=0;i<K;i++){
      int r,c; cin>>r>>c;
      r--; c--;
      a[r][c]=0;
   }
 
   for(int i=H-1;i>=0;i--){
      for(int j=0;j<W;j++){
         cntD[i][j]=(a[i][j]==0? 0:cntD[i+1][j]+1);
         cntRD[i][j]=(a[i][j]==0? 0:cntRD[i+1][j+1]+1);
      }
   }
 
   int ans=0;
   for(int i=0;i<H;i++) for(int j=0;j<W;j++) if(a[i][j]){
      for(int k=ans+1;k<=min(cntD[i][j],cntRD[i][j]);k++){
         if(cntD[i][j+k-1]>=k) ans=max(ans,k);
      }
   }
   cout<<ans<<endl;
   return 0;
}

まとめ

簡略化した図を描く
正方形は斜めに見ていく(対角線が同じ直線状にあるものを一緒に考える)

感想

最後の方がかなり適当になってしまいました。本番は、斜めに見ると良さそうだなぁとは思っていましたが、詰めきれませんでした。図を描くのは大事です。正方形を斜めに見るというのは、最大正方形を尺取り法で解くというので見たことがあります。

2019-12-16

第二回全国統一プログラミング王決定戦本戦参加記

前書き

運良く予選を通過することができたので(190位くらい)、本戦に参加してきました。オンサイト決勝は初参加です。

移動

東京駅には何度か行ったことがありますが、一人で行くのは初めてでした。迷子になったときのために早めに出ました。会場の最寄り駅(?)の神田駅に行くためには、東京駅で山手線に乗り換えれば良さそうで、少し心配でしたが、新幹線の出口の近くに標識があったので無事乗り換えられました。神田駅についたのが10:30頃で、少し道に迷いつつも11:00頃には会場に到着しました。受付開始の12:00まで時間があったので、近くでごはんを食べようと思ってうろうろしましたが、コンビニ以上の見つかりやすさと入りやすさのお店がなかったので、結局コンビニでおにぎりを買って食べました。

会場入り

12:00頃に会場に入りました。受付では名札とウイダーinゼリーをいただきました。座席は決まっており、二人で一つの長机を使う形でした。トークショーが始まるまでは、vimでクリップボードに貼り付ける方法を調べたり(?)、最近(昨日から)使い始めたonline-judge-toolsの使い方を確認したりしていました。そうこうしているうちにトークショー(インタビュー?)が始まりました。若くて強い競技プログラマーがたくさんいるんだなぁとなりました。

コンテスト

コンテストは13:15から開始でした。カウントダウンがあったので緊張しました。配点は2-3-6-8-8-?だったので、6までは解きたいなぁと思っていました。

A問題
$A_{i} \lt A_{j} \gt A_{k}$ なる $(i,j,k) (i \lt j \lt k)$ の組の個数を求める問題です( $N \le 5000$ )。3つあるときは真ん中を固定するとうれしくて、これも真ん中を全探索すれば $O(N^{2})$ で解けます。 $N$ が大きくてもBITを使うと解けるみたいです。

B問題
文字列 $s$ を空でない6つのsubstringに分割して、"NIKKEI"のように3番目と4番目、2番目と6番目の文字列を等しくする方法が何通りあるかという問題です。2個ずつ区切る境界を全探索すればいい気がしたのでその方向で考えました。3つに分けた文字列のうち、真ん中が同じ文字列を2つくっつけた形になっていればよくて、そうであれば最初の文字列と最後の文字列の後ろ何文字かを一致させる方法だけ答えを加算すればよいです。計算量は $O(|s|^{3})$ で $|s| \le 500$ なので間に合います。

ここまではうまくいっていて、順位表見たら44位だったのでビックリしました。online-judge-toolsは神です。

C問題
01からなる $H \times W$ のグリッドから、最大のNを見つけるという問題です。ここでNとは正方形のグリッドであって、両端の列と、左上から右下への対角線がすべて1であるもののことをいいます。とりあえず正方形の左上と右下を全探索すれば3乗くらいで解けそうで、高速化を考えていました。setとmultisetを使えばできそうだなぁとなって実装を始めましたが、考察が詰めきれていなかったので、途中でできない気がして諦めてしまいました。解説を見た感じ方針は大体あってそうだったので、悔しいです。聞いたところによると全探索も枝狩りをするとかなり早くなって通るみたいです。まだ想定解を理解していないので、理解したら解説を書こうと思います。

結果はABの2完で114位でした。AC数的にCに取り組んだのは良かったっぽいですが、1.5hかけてCが解けないのは実力不足を感じました。

表彰式

入賞された皆さん、おめでとうございます。

懇親会

圧倒的コミュ症力を発揮して一人懇親会をしていました(完)。2人以上集まっているところに入っていくのは難しいです。頑張って近くにいたpotooooooooさんに話しかけて、コンテストの結果について話したり、コンテストの戦略について教えていただいたりしました。またオンサイト決勝にこれるように頑張ろうと思いました。

帰宅

電車に乗り遅れて1h待ちました。ここは田舎です。

まとめ

せっかくのオンサイトコンテストだったので、もっと懇親会で話しかけていればなぁと思いました。強くなってまた参加したいです。まだまだ実力不足なのでいっぱい問題を解きたいと思います。

2019-12-12

CODE FESTIVAL 2016 qual B Greedy customers(700)

atcoder.jp

問題

要素数 $N$ の数列 $A$ に対して、以下の操作を行う。
操作: $\max A_{i}$ 以下の正の整数 $P$ を選び、初めて $P$ 以上になるような要素から $P$ を引く。ただしこの操作によって要素が $0$ になってはいけない。
この操作を最大で何回行えるか。

制約

$1 \le N \le 100000$
$1 \le A_{i} \le 10^{9}$

解法の概要

前から順番に操作を行っていく。それより前の最大値が $mx$ のとき、 $A_{i} \gt mx+1$ ならば $(A_{i}-1)/(mx+1)$ 回操作を行う。 $A_{i} = mx+1$ ならば $mx$ を $mx+1$ に更新する。

考察

1. 前から順番に操作を行っていくとしてよい

連続する2回の操作に注目します。この2回の操作の対象のインデックスをそれぞれ $i,j$ とします。 $i \gt j$ だった場合、操作の順番を入れ替えられることが(図を書くと)分かります。また、この2回の操作による結果は変わりません。よってバブルソートの要領で、操作の対象を広義単調増加にすることができます。したがって前から順番に操作を行う場合だけを考えれば良いです。

2. 後のことを考えるとできるだけ小さくするのが良い

あるところまで操作したときの累積maxが $h$ であった場合と、 $h'(h' \lt h)$ であった場合を考えます。累積maxが $h$ であったときにそれより後ろに対して行う操作は、累積maxが $h'$ であるときにも行うことができます。つまり、累積maxが $h'$ のときの、それより後ろに対して行える操作列の集合は、累積maxが $h$ のときに行える操作列の集合を含んでいます。よって要素を小さくすることで(累積maxが大きくなることはないので)、それより後ろに対する結果が悪くなることはないです。

3. 1,2を踏まえてやってみる

2より $a_{1} = 1$ とするのが良いです。操作回数の上界は $a_{i}-1$ で、達成可能です。次に $a_{2}$ 以降を見ていきます。 $P \ge2$ でなければならないことと、 $1$ 以上残さないといけないことから、操作回数の上界は $(a_{i}-1)/2$ です。これは $2$ が出てくるまでは、累積maxを変えずに達成することができます(1回以上操作できる場合は、 $2$ を $(a_{i}-1)/2-1$ 回引いてから、 $(a_{i}-1)/2+(a_{i}-1)\%2$ を引くことで1にできます)。 $2$ が出てきた場合は、累積maxが $2$ に変わります。それ以降は $3$ が出てくるまで、同様にして累積maxを変えずに上界を達成することができます。これを繰り返すことで、各場所で上界を達成しているので、最適解を得ることができます。

実装

ACコード

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;

int main()
{
   int N; cin>>N;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i];

   Lint ans=a[0]-1;
   int mx=1;
   for(int i=1;i<N;i++){
      if(a[i]==mx+1){
         mx++;
      }else{
         ans+=(a[i]-1)/(mx+1);
      }
   }
   cout<<ans<<endl;
   return 0;
}

まとめ

操作の順番を入れ替えてみる
現在最適な選択をとりつつ、あとの選択肢が減らないように(?)できるならば貪欲にする
最大値を求める問題で、上界を達成できるか考える

感想

慣れていないので記事を書くのが大変でした(おかしなところがありそう(あります))。証明が書けません。

2019-09-11

4月から9月までの振り返り

次に進むために4月から現在(9月)までの約5ヶ月間を振り返って反省をしました。年末にまた振り返ろうと思います。誰の役にも立ちませんが、とりあえず公開しておきます。

月ごとに振り返る
- 4月
- 5月
- 6月
- 7月
- 8月
- 9月(今日は9/11)
反省点はどこか?
競プロを続けられなかった理由
継続するためには?
- どういうことだと継続できるか
- 続けるために実践するテクニック
これからすること・意気込み

月ごとに振り返る

4月

大学に入学する。大学に慣れるまでは少し大変だった。筋トレがしたかったので、その前段階として食事管理(栄養バランスの計算)をしていた。4月後半は競技プログラミング(競プロ)をしていた。

5月

序盤はゴールデンウイークだったのでひたすら競プロをしていたが、ゴールデンウィークが明けると失速していった。学業のほうが忙しかったからかもしれない(レポートは大変だった)。

6月

中間テストがあったのでその勉強を頑張った(主に~~(ほとんど)~~線形代数)。競プロ熱が戻ってきて再開するも、分からないことが重なって辛くなって、また失速していった(7月に国内予選あるのに)。6月の後半くらいから筋トレ(週3)を始めた。

7月

競プロをほとんどやっていない状態のまま、ICPC国内予選を迎える。全くチームに貢献できなかった(ホチキス持ってきたくらい)。来年は頑張ろうとモチベーションが上がったものの、何を思ったのか競プロをしていたデスクトップパソコンを押し入れに収納したので、全く競プロをやらなくなった。

8月

壊れていた3DSを修理したため、ゲームの沼にはまってしまい、生活習慣が崩壊する。朝から晩まで(昼から朝まで)ゲームをしていた。中旬に一週間ほど授業があったので、一時的に生活習慣が戻るも、また崩壊。気が付けば一か月で240時間ほどゲームをしていた。

9月(今日は9/11)

このままじゃヤバイと思ったのか生活習慣が元に戻った。とりあえず筋トレを再開した。ダメなところを反省して、同じことを繰り返さないために、4月から現在までの振り返ることにした。

反省点はどこか?

継続しなかったこと。現在まで継続できていることが一つもない。途中でやめると成長が止まるし、どんどん衰えてしまうのでもったいない。

競プロを続けられなかった理由

つらかったから
競プロをする環境がなくなったから(パソコンを押し入れに収納したため)
ゲームにはまってしまったから

継続するためには?

どういうことだと継続できるか

継続することによって成果が得られること
その成果が満足のいくものであること

続けるために実践するテクニック

毎日続ける -> する/しないの選択肢を作らない
その日の目標を達成するまで、他のことをしない

これからすること・意気込み

競技プログラミングと筋トレを継続する。次に振り返る時に、4月から現在までより有意義だったと思えるような過ごし方をしたい。