h3mky0's blog

主に競プロについて書きます

CSAcademy Round #46 D. Count Gigel Matrices

問題リンク:

https://csacademy.com/contest/archive/task/cntgigelmat

問題概要:

0と1を含むn*mの行列が与えられる. 主対角線と境界が全て1であるような部分正方行列の個数を数えてください.

解法:

まず「対角線を結ぶ2点を固定して, 条件を満たすかどうか」を考えてみましょう. これは事前に累積和をとることで, 1が並んでいるかどうかを前計算O(n^2), クエリO(1)で判定できます. しかしながら, 全てのペア候補について求める場合, 固定する部分がボトルネックとなり全体計算量はO(n^3)となります. 

高速化のために「ある1点を固定したとき対角線上の点として条件を満たすものの個数をまとめて数え上げられないか」を考えます. 便宜上, 左上の点をA, 右下の点をBとします. Bを固定したとき, 条件を満たすAの個数を数え上げたいです.

Aの候補はBの左方向に並ぶ1の数, 上方向に並ぶ1の数, 右上に並ぶ1の数の最小値(これをcとします)の範囲 にある点となります.一方で, Bの候補はAの右方向に並ぶ1の数, 下方向に並ぶ1の数の最小値(これをdとします)の範囲にある点となります. 

以上のことから次のような数え上げが考えられます. 

・各対角線上について独立に見ていく.

・Aならば[x,x+d]までyに1加算する

・Bならばxについて[y-c+1,y]までの区間和を求める.

二次元のクエリっぽくなりますが, xの小さい順にクエリをソートしておくことで1次元で対応できます. 区間和はsegment treeやBITを使ってO(logn)求めることができることから全体計算量はO(n^2log(n))となります.

提出コード:

gist92c7e540965178af8fe8cc1fc6f180fa

感想:

TLがかなり怪しかった. 

ICPC2021国内予選 参加記

https://icpc.iisf.or.jp/2021-yokohama/icpc.iisf.or.jp


ICPC2021国内予選に自分(hamray), gomatamagoさん, UさんとSA-naIStというチーム名で参加しました. 結果はAB2完の133位でした.

参加記念であったり, NAISTでのICPCへの取り組みみたいなことを調べる人(自分など)がいるかもしれないのでこの記事を書こうと思います.

ICPC国内予選までにやったこと

  • PGBattleに参加した
    • これも3人1組でチームを組む大学対抗のコンテストですが, それぞれ異なる問題を解くという点がICPCと異なる.
    • 全体50位. チーム全員がミスしていた感じだったので辛い雰囲気だったが, キリ番で賞品を頂いた. ありがとうございます.
  • 模擬国内予選に参加した
    • 全体55位, selectedで36位でギリ国内予選突破圏内.
    • Cの早解きが刺さった感じだったのでかなり油断はできない.
  • チーム内で週2, 3回ほど集まってバーチャルコンテストを開いた
    • 主にICPCの過去問や有志コンの問題など.
  • 個人として,
    • ICPCの過去問を埋めた. (去年の時点で400までは埋めていたので450↑を中心に).
f:id:becnical:20211107190727p:plain
AOJICPC埋め

ICPC国内予選本番の流れ

  • 本番前
    • 話し合ったところAをgomatamagoさん, BをUさん, Cを自分が解くことになった. もしCがヤバかったらBを見るかもしれないという話をした, 今思えばフラグだった.
  • 本番
    • とりあえずCを開く. 木の回転自体は全方位木dpでできると思ったが, 構文解析パートであったり, 入れ替えであったり細かいところをつめるのが面倒そう.
    • gomatamagoさんがAをAC
    • Cを考えていても具体的な実装方針が立たなかったのでCを飛ばしてBに移る.
    • Bは順々に確定していくと良いことが分かる. ただ, 連結判定あたりの言い換えがまとまらず, 良い実装が浮かばなかったのでUさんとgomatamagoさんに投げてDを見る.
    • gomatamagoさんが良さげな実装を思いついたのでデバッグをしてBをAC
    • この時点で1時間20分くらい(本番中はあまり気にしてなかったけどかなり時間が経っていますね...)
    • CDをうろうろするがCが明らかな重実装で, 現時点でDが最も通されていたのでDを考える. 最近フローの問題を解くことが多かったり, ABC143Fに似ていることもあったので色々嘘を生やすが, うまくいかず辛い.
    • 何もできずにコンテスト終了. 残念無念.
  • 反省
    • チームで1つの問題を考えるという練習があまりできていなかったかもしれない.
    • 自分が仕事するべきところでできていない. (本当に申し訳ない)

個人的な感想

今回が4度目のICPC参加でした. ICPCを知って競技プログラミングを始めた人間なので, これまでに比べ国内予選を突破したいという気持ちが強かったですが非常に悔いの残る結果となってしまいました.
ICPCは最後になってしまいましたが, 競技プログラミングは続けます. 今後は, AtCoder黄になることや今後できるようになるかもしれないオンサイトへの参加を目標に頑張りたいと思っています. (学生限定のコンテストが終わっていくのは悲しい)

最後に, チームメンバやコーチ, 運営の方々ありがとうございました。

AOJ1604 Deadlock Detection

問題概要

次の処理を行う.
10個のスレッドのうち一つをランダムに選び命令を行う. 仮に命令が数字である場合, 他のスレッドにより数字に対応するロックが獲得されていなければそのロックを獲得する.
また, 命令が uである場合, そのスレッドが獲得したロックを全て解放する.
長さ nの命令列に対し以上の処理を行う場合デッドロックが起こりうるか判定してください.

考えたこと

初めにuを通過することでロックが全て解放されるので, あるu同士の間の命令列はそれぞれ独立したものと考えることができる.
k個の命令列があるとして,  C_0, C_1, ..., C_{k-1}としておく. また k番目の命令列の i番目の命令を C_{k, i}とする.
主にサンプル4から, デッドロックが起こりうるケースは C_{k, i} C_{k,i+1}の有向グラフを考えたとき有向閉路が存在するときだとわかる.
ただし,  C_{k, i}, C_{k, i+1}を使うには C_{k, 0} から C_{k, i-1}が有向閉路に含まれないことが条件となるため次のような動的計画法を行う.

 dp_{i, j, mask} : iを始点として, 最後に使ったロックがjであり, すでに使った頂点集合がmaskであるようなものが存在するかの二値テーブル.

これは,  dp_{i, i, (i番目のbit)}をtrueで初期化しておき, (u, v)の辺を加える際に直前までの頂点集合とmask andを見て被りがなければ辺を加えることができるので更新する.
最終的に vが始点と一致して,  dp_{s, u, mask}がtrueであれば有向閉路が存在することになる.

命令列Cに同じ数字が含まれるときも閉路が存在するのでそこだけ注意する.
全体の計算量はサンプル数50,  O(\max(n) * 10 * 2^{10})で通る.

提出コード


aoj1604.cpp

CSAcademy Round #26 (Div. 2 only) E. Critical Cells

リンク
https://csacademy.com/contest/archive/task/critical-cells/

問題概要

 N*Mのグリッド上に K個の特別なセルが存在する。
いま(1, 1)から(N, M)まで右方向と下方向のみを使って移動するとき、できるだけ多くの特別なセルを経由したい。

次の状態を満たすような特別なセルをBestと定義する。
ある任意の特別なセルを1つ選んで削除したとき、特別なセルの最大経由数が小さくなる。

このとき Bestな特別なセルの個数を求めよ。

制約

 1 \leq N, M \leq 10^9
 1 \leq K \leq 10^5

解法

まずセルを削除しない場合の最大経由数を求める。
下と右方向にしかできないことから、 (x_1, y_1), (x_2, y_2), ..., (x_m, y_m)のような列を考えたとき、 x_i \leq x_j 及び  y_i \leq y_jを満たせばよい。
これはx軸方向にソートしたときのy軸方向についての広義単調増加列(LIS)に一致する。

次にLISに含まれる候補が複数ある場合、特別なセルを削除しても最大経由数が変化しない場合があるためどの点がLISの候補なのかを求める。
LISの長さは逆順から見たときの広義単調減少列(LDS)の長さに一致することから、先頭と後ろからLIS(LDS)を求めて、 iについて l_i+r_i-1がLISの長さに一致するならば、候補に含まれることが言える。

(LISの求め方としては蟻本に載ってるような方法がありますが、セグ木を使うとLIS、LDSの両方について区間を変更するだけで簡単に求まるのでよいと思います。)

あとはある長さについて候補が1つだけのものをカウントすれば答えに一致する。

CSAcademy Round #42 (Div. 2 only) E. Xor Submatrix

問題概要

長さ N, Mの配列 V, Uが与えられる。 このとき行列 Aを次のように定義する。
 A_{i, j} = V_{i} xor   U_{j}
このとき, 部分行列のxorの最大値を求める。

制約

 1 \leq N, M \leq 1000
 0 \leq V_{i}, U_{i} < 2^{29}

解法

xorの性質に従って, 次の3つに場合分けをする。
1. 部分行列の縦と横の長さが偶数
2. 部分行列の縦の長さが偶数または横の長さが偶数
3. 部分行列の縦と横の長さが奇数

1. の場合, 各 V_{i}, U_{i}は偶数回現れるため、xorは0となる。
2. の場合, 縦の要素か横の要素のxorが0になるため、1方向にのみ求めればよい。
3. の場合,  lx, ly, rx, ryを固定するとその領域のxor値を高速にもとめることができる。
いま横方向と縦方向は独立に考えられることから、横のxorを固定してそのxorに対して最大になるような縦のxorを選びたい。
これを高速に行う方法としてbinary trieというデータ構造がある。
kazuma8128.hatenablog.com

binary trieを使うことで集合 Sから xとのxorが最大になるような要素を答えるというクエリを高速に処理できる。
ここでの集合 Sは縦のxorであるため、 O(N^2)で求めることができ、後半部分は O(N^2 B)(Bは最大で29)で処理できるため間に合う。

AOJ2447 A Two Floors Dungeon

問題リンク
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2447

解法

1,2階の状態を一つのグリッドで表現するのでかなり分かりにくいが, 整理するとマスの位置, 今いるフロアの階数, スイッチの状態をもってBFSをすればよいことが分かる.
少し面倒なのが移動可能かどうかの判定だがどのスイッチが押されているとき変更されるかをあらかじめビットで持っておくとスイッチの状態とのAND演算をとるだけでよくなる. ^及び'A'~'J'ははじめ二階にあることに注意する.

実装例

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;


#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()

#define MOD 1000000007

template<class T1, class T2> inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
const double EPS = 1e-9, PI = acos(-1);
const double pi = 3.141592653589793238462643383279;

int dp[55][55][2][1<<10];
int dxy[5]={-1,0,1,0,-1};
int mask[55][55];
vector<string> M(55);
bool canmove(int y, int x, int floor, int swi) {

  if(M[y][x] == '|') return true;
  int carry = 0;
  if((M[y][x] >= 'A' && M[y][x] <= 'J')||(M[y][x] == '^')) carry = 1;
  int mask2 = mask[y][x] & swi;
  carry = (carry + __builtin_popcount(mask2)) % 2;
  return floor == carry;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(7);
  
  int W, H; cin >> W >> H;
  
  REP(i,H) cin >> M[i];

  int S; cin >> S;
  REP(i,H) REP(j,W) REP(k,2) REP(l,(1<<S)) dp[i][j][k][l] = INT_MAX;
  
  
  REP(i,S) {
    REP(j,H) {
      string s; cin >> s;
      REP(k,W) {
        if(s[k] == '*') {
          mask[j][k] |= (1 << i);
        }
      }
    }
  }

  int sy, sx, gy, gx;
  REP(i,H) {
    REP(j,W) {
      if(M[i][j] == '%') {
        sy = i, sx = j;
      }
      if(M[i][j] == '&') {
        gy = i, gx = j;
      }
    }
  }
  dp[sy][sx][0][0] = 0;
  queue<tuple<int, int, int, int>> q;
  q.push(make_tuple(sy, sx, 0, 0));
  while(q.size()) {
    auto[y, x, floor, swi] = q.front();
    q.pop();

    if(M[y][x] == '|') {
      if(dp[y][x][floor^1][swi] > dp[y][x][floor][swi] + 1) {
        dp[y][x][floor^1][swi] = dp[y][x][floor][swi] + 1;
        q.push(make_tuple(y,x,floor^1,swi));
      }
    }else if(M[y][x] >= 'A' && M[y][x] <= 'J') {
      int tmp = 0;
      if(mask[y][x] & (1 << (M[y][x]-'A'))) tmp = 1;

      if((swi >> (M[y][x]-'A')) & 1) {
        if(dp[y][x][floor^tmp][swi & ~(1 << (M[y][x]-'A'))] > dp[y][x][floor][swi] + 1) {
          dp[y][x][floor^tmp][swi & ~(1 << (M[y][x]-'A'))] = dp[y][x][floor][swi] + 1;
          q.push(make_tuple(y,x,floor^tmp,swi & ~(1 << (M[y][x]-'A'))));
        }
      }else{
        if(dp[y][x][floor^tmp][swi | (1 << (M[y][x]-'A'))] > dp[y][x][floor][swi] + 1) {
          dp[y][x][floor^tmp][swi | (1 << (M[y][x]-'A'))] = dp[y][x][floor][swi] + 1;
          q.push(make_tuple(y,x,floor^tmp,swi | (1 << (M[y][x]-'A'))));
        }
      }
    }else if(M[y][x] >= 'a' && M[y][x] <= 'j') {
      int tmp = 0;
      if(mask[y][x] & (1 << (M[y][x]-'a'))) tmp = 1;

      if((swi >> (M[y][x]-'a')) & 1) {
        if(dp[y][x][floor^tmp][swi & ~(1 << (M[y][x]-'a'))] > dp[y][x][floor][swi] + 1) {
          dp[y][x][floor^tmp][swi & ~(1 << (M[y][x]-'a'))] = dp[y][x][floor][swi] + 1;
          q.push(make_tuple(y,x,floor^tmp,swi & ~(1 << (M[y][x]-'a'))));
        }
      }else{
        if(dp[y][x][floor^tmp][swi | (1 << (M[y][x]-'a'))] > dp[y][x][floor][swi] + 1) {
          dp[y][x][floor^tmp][swi | (1 << (M[y][x]-'a'))] = dp[y][x][floor][swi] + 1;
          q.push(make_tuple(y,x,floor^tmp,swi | (1 << (M[y][x]-'a'))));
        }
      }
    }
    
    for(int i=0; i<4; i++) {
      int ny = y + dxy[i], nx = x + dxy[i+1];
      if(M[ny][nx] != '#' && canmove(ny, nx, floor, swi)) {
        if(dp[ny][nx][floor][swi] > dp[y][x][floor][swi] + 1) {
          dp[ny][nx][floor][swi] = dp[y][x][floor][swi] + 1;
          q.push(make_tuple(ny,nx,floor,swi));
        }
      }
    }
  }

  int ans = INT_MAX;
  REP(i,2) {
    REP(j,(1<<S)) {
      ans = min(ans, dp[gy][gx][i][j]);
    }
  }
  if(ans == INT_MAX) ans = -1;
  cout << ans << endl;
  return 0;
}

Project Euler 93: Arithmetic expressions

2021年初投稿です。最近はProject Eulerを埋めているのでそこの問題から。

問題概要

集合 {1, 2, 3, 4} の各数字をちょうど一度用い, また四則演算 (+, -, *, /) と括弧を使うことにより, 異なる正の整数を作ることができる.
例えば,
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) - 1
36 = 3 * 4 * (2 + 1)
12 + 34 のように数字をつなげることは許されないことに注意しよう.
集合 {1, 2, 3, 4} を使うと, 36 を最大とする 31 個の異なる数が得られる. 最初の表現できない数に会うまで, 1 から 28 の各数を得ることができる.
最長の連続した正の整数 1 から n の集合を得ることができる, 4 つの異なる数字 a < b < c < d を見つけよ. 答えを文字列 abcd として与えよ.
(http://odz.sakura.ne.jp/projecteuler/?Problem+93から引用)

解法

1~9の数字から異なる数字を選ぶときの組み合わせは9C4 = 126通り, 数字の順番は4!通り, 数字間に演算子が入るので 4^3通り, 括弧の組み合わせは5通りあるので, 計967680通りあります。
全列挙しても間に合いそうですが, 括弧の処理が少し面倒なので次のような区間dpをします。
  dp[i][j] :=区間[i,j[において作ることができる数字の集合

(なお, 集合を扱いたいのでc++のsetを使います)

注意点として, 今回の問題では除算が切り捨てではないので分子と分母をもつ有理数のクラスを定義してそのうえで四則演算を行います。
有理数を扱っているので最終的な集合において, 分子が正数, 分母が1であるような数字だけが欲しい数字になります。

数字の組み合わせはもちろんですが, 集合内の数字の順番によっても得られる結果は変わるため, すべての順番において区間dpをして, その結果をもとに連続する数字列の長さを求めます。
以上の処理を全ての数字の組み合わせについて行うことで答えが求まります。