CSAcademy Round #46 D. Count Gigel Matrices
問題リンク:
https://csacademy.com/contest/archive/task/cntgigelmat
問題概要:
0と1を含むの行列が与えられる. 主対角線と境界が全て1であるような部分正方行列の個数を数えてください.
解法:
まず「対角線を結ぶ2点を固定して, 条件を満たすかどうか」を考えてみましょう. これは事前に累積和をとることで, 1が並んでいるかどうかを前計算, クエリで判定できます. しかしながら, 全てのペア候補について求める場合, 固定する部分がボトルネックとなり全体計算量はとなります.
高速化のために「ある1点を固定したとき対角線上の点として条件を満たすものの個数をまとめて数え上げられないか」を考えます. 便宜上, 左上の点をA, 右下の点をBとします. Bを固定したとき, 条件を満たすAの個数を数え上げたいです.
Aの候補はBの左方向に並ぶ1の数, 上方向に並ぶ1の数, 右上に並ぶ1の数の最小値(これをとします)の範囲 にある点となります.一方で, Bの候補はAの右方向に並ぶ1の数, 下方向に並ぶ1の数の最小値(これをとします)の範囲にある点となります.
以上のことから次のような数え上げが考えられます.
・各対角線上について独立に見ていく.
・Aならば]までに1加算する
・Bならばについて]までの区間和を求める.
二次元のクエリっぽくなりますが, xの小さい順にクエリをソートしておくことで1次元で対応できます. 区間和はsegment treeやBITを使って求めることができることから全体計算量はとなります.
提出コード:
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に参加した
- 模擬国内予選に参加した
- 全体55位, selectedで36位でギリ国内予選突破圏内.
- Cの早解きが刺さった感じだったのでかなり油断はできない.
- チーム内で週2, 3回ほど集まってバーチャルコンテストを開いた
- 主にICPCの過去問や有志コンの問題など.
- 個人として,
- ICPCの過去問を埋めた. (去年の時点で400までは埋めていたので450↑を中心に).
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つの問題を考えるという練習があまりできていなかったかもしれない.
- 自分が仕事するべきところでできていない. (本当に申し訳ない)
AOJ1604 Deadlock Detection
問題概要
次の処理を行う.
10個のスレッドのうち一つをランダムに選び命令を行う. 仮に命令が数字である場合, 他のスレッドにより数字に対応するロックが獲得されていなければそのロックを獲得する.
また, 命令がである場合, そのスレッドが獲得したロックを全て解放する.
長さの命令列に対し以上の処理を行う場合デッドロックが起こりうるか判定してください.
考えたこと
初めにを通過することでロックが全て解放されるので, ある同士の間の命令列はそれぞれ独立したものと考えることができる.
個の命令列があるとして, としておく. また番目の命令列の番目の命令をとする.
主にサンプル4から, デッドロックが起こりうるケースはとの有向グラフを考えたとき有向閉路が存在するときだとわかる.
ただし, を使うには からが有向閉路に含まれないことが条件となるため次のような動的計画法を行う.
を始点として, 最後に使ったロックがであり, すでに使った頂点集合がであるようなものが存在するかの二値テーブル.
これは, をtrueで初期化しておき, の辺を加える際に直前までの頂点集合とのを見て被りがなければ辺を加えることができるので更新する.
最終的にが始点と一致して, がtrueであれば有向閉路が存在することになる.
命令列に同じ数字が含まれるときも閉路が存在するのでそこだけ注意する.
全体の計算量はサンプル数, で通る.
提出コード
CSAcademy Round #26 (Div. 2 only) E. Critical Cells
リンク
https://csacademy.com/contest/archive/task/critical-cells/
問題概要
のグリッド上に個の特別なセルが存在する。
いまからまで右方向と下方向のみを使って移動するとき、できるだけ多くの特別なセルを経由したい。
次の状態を満たすような特別なセルをと定義する。
ある任意の特別なセルを1つ選んで削除したとき、特別なセルの最大経由数が小さくなる。
このときな特別なセルの個数を求めよ。
制約
解法
まずセルを削除しない場合の最大経由数を求める。
下と右方向にしかできないことから、のような列を考えたとき、 及び を満たせばよい。
これはx軸方向にソートしたときのy軸方向についての広義単調増加列(LIS)に一致する。
次にLISに含まれる候補が複数ある場合、特別なセルを削除しても最大経由数が変化しない場合があるためどの点がLISの候補なのかを求める。
LISの長さは逆順から見たときの広義単調減少列(LDS)の長さに一致することから、先頭と後ろからLIS(LDS)を求めて、についてがLISの長さに一致するならば、候補に含まれることが言える。
(LISの求め方としては蟻本に載ってるような方法がありますが、セグ木を使うとLIS、LDSの両方について区間を変更するだけで簡単に求まるのでよいと思います。)
あとはある長さについて候補が1つだけのものをカウントすれば答えに一致する。
CSAcademy Round #42 (Div. 2 only) E. Xor Submatrix
問題概要
長さの配列が与えられる。 このとき行列を次のように定義する。
xor
このとき, 部分行列のxorの最大値を求める。
制約
解法
xorの性質に従って, 次の3つに場合分けをする。
1. 部分行列の縦と横の長さが偶数
2. 部分行列の縦の長さが偶数または横の長さが偶数
3. 部分行列の縦と横の長さが奇数
1. の場合, 各は偶数回現れるため、xorは0となる。
2. の場合, 縦の要素か横の要素のxorが0になるため、1方向にのみ求めればよい。
3. の場合, を固定するとその領域のxor値を高速にもとめることができる。
いま横方向と縦方向は独立に考えられることから、横のxorを固定してそのxorに対して最大になるような縦のxorを選びたい。
これを高速に行う方法としてbinary trieというデータ構造がある。
kazuma8128.hatenablog.com
binary trieを使うことで集合からとのxorが最大になるような要素を答えるというクエリを高速に処理できる。
ここでの集合は縦のxorであるため、で求めることができ、後半部分は(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の数字から異なる数字を選ぶときの組み合わせは通り, 数字の順番は通り, 数字間に演算子が入るので 通り, 括弧の組み合わせは通りあるので, 計967680通りあります。
全列挙しても間に合いそうですが, 括弧の処理が少し面倒なので次のような区間dpをします。
区間において作ることができる数字の集合
(なお, 集合を扱いたいのでc++のsetを使います)
注意点として, 今回の問題では除算が切り捨てではないので分子と分母をもつ有理数のクラスを定義してそのうえで四則演算を行います。
有理数を扱っているので最終的な集合において, 分子が正数, 分母が1であるような数字だけが欲しい数字になります。
数字の組み合わせはもちろんですが, 集合内の数字の順番によっても得られる結果は変わるため, すべての順番において区間dpをして, その結果をもとに連続する数字列の長さを求めます。
以上の処理を全ての数字の組み合わせについて行うことで答えが求まります。