ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC110 D - Factorization

問題
提出コード

解法

まずは素因数分解をし、それぞれの素因数についていくつ使われているかをカウントします。
こちらの記事と似たようなことをします。
2~ \sqrt{m}までを全探索し、imの約数である限りmiで割り続け、その数をカウントしていきます。
探索後に、mがまだ1でなければ、それは一番大きな素因数なので、それも個数1として別にカウントします。
そうしたら、その素因数を数列に配っていけばいいので、それぞれの素因数について配り方を考え、最後に積をとれば答えになります。
今回は数列の要素として1が許されているので、それぞれの素因数について、重複可能な組み合わせを考えていきます。
素因数を並べたあとに、n-1個の仕切りをどう置くか、について考えるイメージです。これは、素因数の数をxとしたときに、x+n-1個の中から仕切りのn-1個の選び方を数える問題に帰着できるので、
 _{n}H_x = _{x+n-1}C_{n-1} = _{x+n-1}C_{x}
をそれぞれの素因数について計算すれば答えが求まります。

ABC110 C - String Transformation

問題
提出コード
この問題、個人的にはD問題より難しかったです…

解法

Sの中から1つ文字を選択したとき、Sの中の同じ文字はすべて、置換後も同じ文字になってしまいます。そのため、S="aa"、T="bc"のようなものは答えがNoになります。
なので、Sの中である文字の種類を1つ選択したとき、Tの部分もすべて同じ種類の文字になっていないといけません。

また、Tの中から1つ文字を選択したとき、Tの中の同じ文字はすべて、置換前も同じ文字でないといけません。そのため、S="ab"、T="cc"のようなものは答えがNoになります。
なので、1つめの条件と同様に、Tの中である文字の種類を1つ選択したとき、Sの部分もすべて同じ種類の文字になっていないといけません。

ということで、26×26マスのテーブルをつくり、片方が置換前の文字、もう片方が置換後の文字とします。
S、Tについて全探索をし、SとTの文字について、テーブル上の対応する場所にビットをたてます。
そして、最後にすべての行、および列についてチェックし、その行(列)上でビットがたっている数が0、もしくは1になっていればSからTに置換することができます。
2個以上ビットが立っている行(列)が1つでも存在したら、答えはNoになります。

ABC086 D - Checker

問題
提出コード

解法

散らばっている情報を、まずはK×Kマスの中に押し込みます。
例えば、(x,y)がWという希望は、(x+K,y)、もしくは(x,y+K)がBという希望と同じであり、また(x+K,y+K)がWであるという希望とも同じです。
これを利用すると、白を0、黒を1と表現したときに、色の情報をcとして、(x,y)がcであるという希望は、
座標(x%K,y%K)が色(x/K + y/K + c)%2である、というものにすべて置き換えることができ、こうすることで、座標を0~K-1の中にすべておさめることができます。
まずはこの手法を用いて希望をすべてカウントしていきます。
これが終わったら、累積和を利用して、(0,0)から(i,j)マスまでの希望の合計をO(1)でとりだせるようにします。
あとは、マス目の取り方が2×K^{2}通りあるので、全てについて全探索して、累積和を利用することでそのときの希望を満たす個数を調べ、最大値を求めます。
f:id:emtubasa:20180913005328p:plain
図のように、交点の座標を全探索し、白と黒の4つの部分に分けて、希望を満たしている個数を足していきます。
これを、i,jについてと、白黒の2種類についてすべて全探索します。 あとは、最大値を求めれば完了です。

ABC086 C - Traveling

問題
提出コード

解法

ぱっとみ幅優先、っぽくみえて全然違いました。
プランのi番目の位置と時刻から、i+1番目の時刻に、指定された位置に行くことができるかどうかを全部調べていきます。
i=0のときはt、x、y全て0とします。
i番目の情報をt[i],x[i],y[i]と表記したとき、
t[i+1]-t[i] >= (x[i+1]とx[i]の差の絶対値) + (y[i+1]-y[i]の差の絶対値)かつ、
(t[i+1]-t[i]) - (x[i+1]とx[i]の差の絶対値) - (y[i+1]-y[i]の差の絶対値)が偶数
となっていれば計画を実行できます。
あとは全てのiでこれが言えるかどうか調べて、実行できればYes、できなければNoを出力すれば完了です。

会津大学競技プログラミング合宿2018参加記

ということで、9/19~9/21に行われた、会津大学の競プロ合宿に参加してきました。


目次


一日目

立命館大学の方々のセットで3時間8問のものでした。
チームはACPC_KotonohaSistersで、
とまとさん(@25__toma)、怒髪さん(@dohatsutsu)でした。

問題の担当ですが、自分がAとC、とまとさんがBとD、そして怒髪さんが全体の考察を担当しました。
コンテストページはこちらになります。

A問題

解法についてはこちらを。
…愚直にシミュレーションでいいかーと思っていたら、一回数えるだけで答えになっているといわれたのでなるほどと思いながらそれを書き起こしました。

B問題

積分をすると負けになるらしいです。制約を見ると、答えが球になることが確定しているので、体積を求めるコードを書いて終わりだそうです。

C問題

解法についてはこちらを。
一瞬、これどうやるんだろう…って思っていたら解法が天から降ってきたので、怒髪さんととまとさんがBの考察を行っている隙に実装しました。まぁ思いつけばあとはなんとでもなりそうかな、という感想です。

D問題

これぞ実装系、という感じの問題でした。
右手法を書いたことがないのと、あまりsetを使ったことがなかったので、とまとさんと怒髪さんに実装をお願いしました。
バグが取り切れなくて間に合いませんでしたが、バグを取り切った後でもTLEになってしまっていたようです。何も力になれず申し訳ないです…

E問題

考察がわからず悩んでいると、怒髪さんが実装してあっという間に通してくださいました。
単純な貪欲法で前から見ていくのに加えて、一つ先の要素を見る場合も加えるとうまくいくようです。

F問題

虐殺問題。残った時間で自分はDの実装に参加できなかったので、F、G、Hのどれかをやっていくしかなかったのですが、Gは怒髪さんが考察を終わらせていてセグ木の実装系だと判明していたためとばしました。
H問題はさすがに最後にあるので無理だろう、と重いランキングの様子を知っていたもののF問題を考えてみることにしました。
が、結論から言うと何もわからなかったです。
まぁほかの上位の方々が最後の方まで誰一人通せていなかったのでそれはそうと思いましたが…

G問題

セグ木を3段階の入れ子にする問題です。セグ木をRMQしか書いたことがないのでおそらく間に合わない、そしてDの実装をした方が可能性がありそうということで切り捨てられました。ですが数分でこの考察を終わらせた怒髪さんはさすがですとしか言いようがありません…(構文解析、ときたらこういうパターンがなくはないのでしょうか?)

H問題

問題を読み、1分くらい考えて離脱しました。最小カットなんですね…

感想

ということで4完でした。序盤の簡単な部分を通すことぐらいしかできていないので力不足を実感しました。とまとさん、怒髪さんありがとうございました。


二日目

会津大学の方々のセットで5時間12問のものでした。
チームは ACPC_ba で、
goodbaton(@goodbaton)さんとのペアでした。

自分は、A、C、Dを担当しました。
コンテストページはこちらになります。

A問題

自分の解法はこちらになります。
とりあえず上の方から貪欲法をしていきましたが、実はすべて500の倍数であるため、500についてのみ考えればいいらしいです。

B問題

実は最初自分が解く予定の問題でした。
めんどくさそうなので先にCを解き、そのあとこの問題に戻り実装をしたのですが、普通に考察が足りていなかったのでgoodbatonさんに通していただきました。
はやく片方のチームの人数を0にしたいので、片方はできるだけ相手が生き残るように、もう片方はできるだけ相手を倒せるように攻撃をしていきます。これは2パターン存在するので、それぞれについて調べた後小さい方を答えにすれば良いそうです。
自分はお互いが常に生き残るようにしか考えていなかったのでもちろん通りませんでした。

C問題

解法についてはこちらを。
今回の合宿中の3つのB問題、どれもCより難しいような気がします...
Cは割とサクっと通せたのでいいのではないかなと思います。

D問題

自分の解法はこちらになります。
とりあえず幅優先を書いて更新していけばいいのかなぁと思っていたのですが、普通にTLEをしてしまったので、考察で押し通すことにしました。
個数制限のある重複順列の式や配列の添え字関係で、例によってバグをたくさん生み出してしまったのでかなり時間がかかってしまい、goodbatonさんにデバッグを手伝っていただき、答えが合わないケースをあぶりだしてもらいました。
なんとか通せたのでよかったですが…

E問題

goodbatonさんが、原点から、1日目に食べたドーナツの中心座標に引いた直線の傾きを求めればいいということを発見したのですが、なぜか通らなくて数十分二人で悩むハメになりました。
sample2が実はこのコーナーケースにあたっていて、実は1日目に食べる範囲は、もともとのドーナツの範囲からはみ出している可能性がある、というものになっていたのですが、先ほどの直線の式でもたまたま通ってしまうため、気づきにくい、というものでした。
この問題の制約を見ると、xとyが整数という表示がどこにも存在しないのですが、実は整数であるみたいです。
かなり時間を取られてしまいました。

F以降

自分がDの実装をバグらせていたり、EやHについて考えている間に、気づいたらG、I、Kが解かれていました。
特にKはオンサイト上でのFirst ACになっていたみたいです(似たような問題を解いたことがあるとおっしゃっていました)。

感想

割と簡単な部分も手をお借りしてしまったので、申し訳なかったです。
2人ペアはかなり忙しく、お昼ご飯を食べる時間がない上、どうしても相談をするとPCでの実装が何もできなくなってしまうので、個人個人で別の問題を解く時間が多く、最初の数時間はお互いがバグを抱えていた関係でなかなか正解数が伸びませんでしたが、結果的にgoodbatonさん一人で怒涛の追い上げをしてくれました。本当にありがとうございました。


三日目

北海道大学の方々のセットで、3時間7問のセットでした。
チームは acpc_yonkanRTAで、
ばたこ(@btk15049)さん、kawabys(@s1230151)さんとのチームでした。

自分はAとDの実装を、ばたこさんがBとEに加えてほぼ全ての問題の考察とデバッグ、kawabysさんがCの実装を、そして自分とkawabysさんの2人でFを解きました。
コンテストページはこちらになります。

A問題

自分のチームの解法はこちらになります。
はい、バグりました。
普通に3重ループ回せばいいものを再帰で書き始めてしまい、結局ループに書き直したのですが、それでも開始と終了関連で細かいところのミスが目立ち、ばたこさんにデバッグをしてもらいながらやっとのことで通しました。ほかのチームはほとんどすんなり通していたので、実装力の差を改めて感じました。

B問題

愚直にやると通らないのでいろいろ工夫をする必要があるのですが、実装がかなり重いらしいので、ばたこさんにすべてお任せしてしまいました。
自分の大学の友人は割とBを実装した人が多かったみたいで、一人ですごいなぁってコンテスト終了後に思っていました。実はコンテストが終わってから問題を読んだのですが、Aをバグらせた今自分にできる自信はあまりないです。

C問題

これもコンテストが終わってから問題を読みました。やりたいことはなんとなくわかるのですが、やはりAをバグらせた今…

D問題

チームの解法はこちらになります。 Aを終わらせた時点でDの解法をばたこさんが見つけてくださっていたので、それを自分が実装することになりました。
言われた通りに一発で実装できなくて少し悔しいですが、Aほど大変なことにはなってなかったのでまだマシかなと思います。

E問題

コンテスト後の解説を聞いてへぇ~とはなりましたが、実装する方針が全く見えていないので、時間があるときに実装しようかなと思っています。

F問題

チームの解法はこちらになります。
3日間の中で唯一、後半の問題で自分のコードが通った+大方の考察をした問題です。
実験をすると割と貪欲にやってしまっていいことがわかるので、必要な情報は結構少なく、1クエリあたりO(|S|)ぐらいで求めることができます。コーナーケースをkawabysさんに見つけていただきました。
コンテスト後の想定解の解説を聞いているとき、そんな問題だったっけ…?って思うレベルには違う解法だったのは秘密です。

G問題

既出の問題らしいです。
kawabysさんの考察によって区間DPを使いそう、というところまで出ていたのですが、結局時間が足りず解けませんでした。

感想

序盤の問題は3日間の中で一番ボロボロでしたが、後半の問題はまぁFの基本方針を自力で解けたので良かったのかな?と思います。
考察よりかはまだ実装系の方がいける、と思っていたのでA問題は割とトラウマレベルでした。いまだになぜ再帰を書こうとしたのかわかりません...

まとめ

3日間、普段とは全く違う環境でさまざまな人とチームを組むことができたのは幸せなのではないかなと思います。来年以降は、むしろひっぱっていけるような存在になれるように精進を続けていこうというモチベーションが生まれました。かなり問題のストックがたまったので、1問1問も重いですし地道に消化していこうかなと思います。参加者の皆様、3日間貴重な経験をさせていただきありがとうございました。

ということでここからはおまけです。
といっても写真を羅列していくだけです(たいしたものを撮っていないです)。
f:id:emtubasa:20180922004312j:plain 行きの新幹線の様子です。思ったより時間が短くてあまりできませんでした…(帰りもずっとやっていました)

f:id:emtubasa:20180922004424j:plain 会津若松駅です。この時点で、そこそこの参加者の方々が近くにいたため、多くの人がここで写真を撮っていました(もちろんツイートもしていました)。

f:id:emtubasa:20180922004533j:plain 大学の入り口です。木の陰になっていて文字が何も見えないです。

f:id:emtubasa:20180922004559j:plain 名札です。とくに書きたいことはないです。エミリアはかわいいですね。

f:id:emtubasa:20180922004642j:plain
1日目の夕ご飯です。喜多方ラーメンです。

f:id:emtubasa:20180922004757j:plain 1日目の夜です。この後もボードゲーム等をしていました。


2日目の写真は存在しません。気づいたらその日が終わっていました。


f:id:emtubasa:20180922005058j:plain お昼ご飯(の後)の写真です。会津大学の学食で食べました。元々はこちらになります。


f:id:emtubasa:20180922004936j:plain 会津大学ドミニオンというボードゲームをしている様子です。これをしていたおかげで帰りの電車に乗り遅れかけました。


ということで以上になります。観光はあんまり(ほぼ)していないのですが、それでも会津にしかないものに多少は触れていたと思います。
また来年も参加できるといいですね。

AOJ 2894 Aizu Competitive Programming Camp 2018 Day 3 F 01 文字列と窓 (Binary String with Slit)

問題

解法

サンプルの最後のケースで実験をすると、なんとなく見えてきます。
まず、移動の手段をすべて書くと、

  1. 01 → 10

  2. 10 → 01

  3. 10 → 11

  4. 11 → 10

の4通りしか存在しません。
そして、SとTが一致していない、一番左側の部分を一致させるには、それより右側にある1のビットを、全て消去する必要があります。
1を消去するには、4つめのパターンを使用する以外に方法がありません。
そして、4つめのパターンを使用するには、一番右側の1を、左にシフトする必要があり、これはパターン1を使用する以外に方法が存在しません。
ということで、まずはパターン1と4を駆使することで、SとTのズレの一番左側に移動する必要があります。

上の動作が終了すると、あとは右側に移動して、SとTのズレを修正していく必要があります。
今度は、パターン2とパターン3を使用して、1を右に移動させつつ、必要な数だけ1を増やすことになります。
これをサンプルケースの一番最後と照らし合わせると、ちょうど答えと一致します。
また、処理の前半部分は、

  • (Sの中で最も右側にある1の位置) - (SとTのズレの中で最も左側にあるもの)

が処理回数の最小値になり、後半部分は

  • (Tの中で最も右側にある1の位置) - (SとTのズレの中で最も左側にあるもの)

が処理回数の最小値になります。
SとTのズレの中で最も左側にあるものをa、
Sの中で最も右側にある1の位置をb、
Tの中で最も右側にある1の位置をcとしたとき、

  • b + c - 2×a

が答えになります。
が、このままではコーナーケースが2パターン存在します。
一つ目が、
S = 011000
T = 010001
という、右に1を移動させるだけで完了するパターン、
二つ目が、
S = 010001
T = 010000
という、左に1を移動させるだけで完了するパターンです。
先ほどの基本方針をそのままに、この2パターンも対処できるように式を書き直すと、

  • max(b-a,0) + |c-min(a,b)|

となります。
あとは、a、b、cをそれぞれ求めて、答えをクエリごとに出力していけば、無事にACすることができます。
提出コードはこちらになります。

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

int a, b, c, q, x, y;
string s, t;

int main() {
  cin >> q;
  while(q--) {
    a = inf;
    cin >> s >> t;
    for(int i = 0; i < s.size(); ++i) {
      if(s[i] != t[i]) a = min(a, i);
      if(s[i] == '1') b = i;
      if(t[i] == '1') c = i;
    }
    if(a == inf)
      cout << 0 << endl;
    else {
      x = max(b - a, 0);
      y = c - min(a, b);
      if(y < 0) y *= -1;
      cout << x + y << endl;
    }
  }
  return 0;
}

AOJ 2892 Aizu Competitive Programming Camp 2018 Day 3 D しりとり圧縮 (Shiritori Compression)

問題

解法

この解法はばたこ(@btk15049)さんから聞いたものになります。

  • dp[i] = i番目の単語までで、消去できる単語数の最大値

とします。
すると、i番目の単語を利用して、それより前の単語を消すかどうかの2パターンにまず分かれます。
i番目の単語を利用しない場合は、dp[i-1]になるので省略します。
i番目の単語を利用する場合、1~i-1番目の単語のなかからj番目を選んだときに、i番目とj番目の先頭の文字が同じ場合、j~i-1番目の単語が消去できます。
これはi-j個です。あとは1~j-1番目の消去数を最大にすればいいのですが、これはdp[j-1]を参照すれば求まります。
ということで、

  • dp[i] = max(dp [ i -1] , dp [ j - 1 ] + i - j)

という式ができました。
ですが、このままでは間に合わないので、計算量を落とします。
文字xがi番目、j番目、k番目に存在したとします(i<j<kにします)。
このとき、iからk-1番目を消すパターンは、iからjを消すパターンにk-jを加えたものを考えることと同じです。
そして、jからk-1番目を消すパターンは、iからjを消さないパターンにk-jを加えたものになります。
ということで、iからjを消すパターンと消さないパターンのどちらの方が消去数が大きいかのみについて知っていれば、kを利用して消去するパターンの最大値を求めることができます。

  • now[i][x] = i番目の文字がxのとき、消去数の最大値

とすると、一つ前の文字xがj番目であるとき、

  • now[i][x] = max(dp[i-1],now[i-1][x]+i-j)

  • now[i][x以外] = now[i-1][x以外]

となります。
i-jは、dp[i]について全探索しているとき、iが動くたびにインクリメントをすれば、jの位置を知らなくても求めることができます。未出現だったときの対策として、初期値を負の大きな値で行っておくといいです。
now[i][x]について、iの添え字を消去して書き直すと、

  • now[x] = max(dp[i-1],now[x])

  • now[x以外] = now[x以外] + 1

  • dp[i] = max(dp[i-1],now[x])

になります。

提出コードはこちらになります。
コンテスト中のコードは配列外参照の可能性があったため、下から6行目のみ書き換えています。

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

int now[27];
int dp[100005] = {0};
int n;
string s, dummy;

int solve();

int main() {
  int i;
  cin >> n;
  for(i = 0; i < n; ++i) {
    cin >> dummy;
    s += dummy[0];
  }
  for(i = 0; i < 26; ++i) now[i] = -1000000000;
  cout << solve() << endl;
  return 0;
}

int solve() {
  int i, j, nown;
  for(i = 0; i < n; ++i) {
    nown = s[i] - 'a';
    now[nown] = max(now[nown], dp[max(i - 1, 0)]);
    if(i != 0) dp[i] = max(dp[i - 1], now[nown]);
    for(j = 0; j < 26; ++j) ++now[j];
  }
  return n - dp[n - 1];
}