PIONE's note

競技プログラミングをやっていません

【解答例】ABC147 C - HonestOrUnkind2

atcoder.jp

bit全探索について、まさに典型と思える問題だったのでメモとして残す。
前回のABC146 Cは二分探索で、今回はbit全探索。まさに入門アルゴリズムの典型がCに配置されてると感じた。

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int a[20];
int x[20][20];
int y[20][20];

int counter(int x){
  if(x==0) return 0;
  return counter(x>>1)+(x&1);
}

signed main()
{
  int n;
  cin>>n;
  
  for(int i=1; i<=n; i++){
    cin>>a[i];
    for(int j=1; j<=a[i]; j++){
      cin>>x[i][j]>>y[i][j];
    }
  }
  int ans=0;
  // bits ビットが立っているところが人iが正しい証言をしていることを意味する
  for(int bits=1; bits<(1<<n); bits++){
    bool ok=true;
    // 最大15人の人iについてのループ
    for(int i=1; i<=n; i++){
      // ビットiが立っている時だけ処理する
      // 正しい証言をしていると仮定しているもの(=ビットが立っている)だけ確認すればよい
      // iが立っていないものは「不確か」であって、「不正確であること」では無い事に注意
      if(!(bits & (1<<(i-1)))) continue;
      // 各人iの証言についてのループ
      for(int j=1; j<=a[i]; j++){
        // 矛盾しないかを判定する
        // 0^1 (bits上は不親切と仮定したのに正直者であると証言してしまっている)
        // 1^0 (正直者と仮定したのに不親切と証言してしまっている)
        if(((bits>>x[i][j]-1)&1) ^ y[i][j]) {
          // bits上正しいと仮定した人iの証言が全て矛盾しなければここを通らず、
          // bitsの立っているビットの数が、正直者の数と同値になる
          ok = false;
          break;
        }
      }
    }
    if(ok) chmax(ans, counter(bits));
  }
  cout<<ans<<endl;
}

参考にさせていただいた実装

atcoder.jp

余談ですが、直近3回ほどのABCを受けてみてC問題、D問題が手強くなっている感触があり、個人的には嬉しい傾向だなと思っています。

EDPC J - Sushi

atcoder.jp

期待値DPの問題
難しかったので、要復習としてメモ.

実装は以下の記事を参考にほぼ写経させていただきました.

www.hamayanhamayan.com

qiita.com

実装

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

#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;

// dp[c1][c2][c3] := 1個残りがc1個, 2個残りがc2個, 3個残りがc3個である状態にするまでの操作回数の期待値

int N, A[303], C[4];
double dp[303][303][303];

signed main() {
  cin >> N;
  rep(i, 0, N) cin >> A[i];
  rep(i, 0, N) C[A[i]]++;

  rep(c3, 0, N + 1) rep(c2, 0, N + 1) rep(c1, 0, N + 1) {
      int sm = c1 + c2 + c3;
      if (sm == 0) continue;

      dp[c1][c2][c3] = 1.0 * N / sm;
      if (c1) dp[c1][c2][c3] += dp[c1 - 1][c2][c3] * c1 / sm;
      if (c2) dp[c1][c2][c3] += dp[c1 + 1][c2 - 1][c3] * c2 / sm;
      if (c3) dp[c1][c2][c3] += dp[c1][c2 + 1][c3 - 1] * c3 / sm;
  }

  coutd(dp[C[1]][C[2]][C[3]]);
}

【解答例】Codeforces Round #597 (Div. 2) C. Constanze's Machine

codeforces.com

DPに関して学びになる問題だったので、メモとして残す.

漸化式

  • dp[i] := s[i]まででn or uが連続する区間においていたずらできる回数

この問題で漸化式を上記の様に定義すると、dpテーブルの遷移はフィボナッチ数列と同じになることに気付く.
遷移がフィボナッチと同じになるdpは典型の一種なので、おさえておきたい.

実装

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

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
using ll = long long;

ll mod = 1e9 + 7;
char u = 'u';
char n = 'n';

const int maxlen = 100010; // 文字列の最大長
ll dp[maxlen];

signed main() {
  string s;
  cin >> s;
  int len = s.size();

  if (s[0] == 'w' || s[1] == 'w' || s[0] == 'm' || s[1] == 'm') {
    cout << 0 << endl;
    return 0;
  }
  
  fill(dp, dp + maxlen, 1);
  
  if ((s[0] == u || s[0] == n) && s[0] == s[1]) dp[1] = 2;
  for (int i = 2; i < len; i++) {
    if (s[i] == 'w' || s[i] == 'm') {
      cout << 0 << endl;
      return 0;
    }
    if (s[i] == u || s[i] == n) {
      if (s[i] == s[i - 1] && s[i - 1] == s[i - 2]) dp[i] = (dp[i - 2] + dp[i - 1]) % mod;
      else if (s[i] == s[i - 1]) dp[i] = 2;
    }
  }

  ll ans = 1;
  rep(i, maxlen - 1) {
    if (dp[i] == 1) continue;
    if (dp[i + 1] == 1) ans = (ans * dp[i]) % mod;
  }

  cout << ans << endl;
}

目の不自由なConstanzeにいたずらするAkkoゆるさねえ。

【解答例】KUPC 2019 F - カズマ王国の陥落

atcoder.jp

DPについて学びになる問題だったので、メモとして残す.

考えたこと

最初考えたのは、各拠点のモンスターは、自身が攻撃できる街の中で勇者の撃退可能数が最も少ない街を貪欲的に選んでいけば、答えが求まるのではというものでしたが、これには反例があります.

反例

  • 街が2つあり、それぞれの街の勇者の撃退可能数が街1は2、街2が3である
  • 拠点が2つありモンスター数は3体ずつ、拠点1は街1と2の両方を攻撃可能、拠点2は街2しか攻撃できない

この場合に上記の貪欲法を適用すると、拠点1のモンスターは街1を攻めて、1ダメージを与えるが、拠点2のモンスターはダメージを与えることができない.
一方、拠点1、2のモンスターが総じて街2を攻撃した場合、3ダメージを与えることができる.

DPで解く

各拠点がどの街を攻撃するかを独立して考える貪欲法は、上記のようにうまくいかないので、以下のように漸化式を定義しDPで解きます.

漸化式
dp[i]:=街iまでで、与えられるダメージの最大

よって、dp[N]に求めたい解が格納されます.

実装

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pll = pair<ll, ll>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
 
ll N, A[3005], M, L[3005], R[3005], B[3005];
ll dp[3005];
vector<pll> Monster[3005];
 
signed main() {
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> A[i];
    cin >> M;
    for(int i = 1; i <= M; i++) {
        cin >> L[i] >> R[i] >> B[i];
        Monster[L[i]].push_back({R[i], B[i]});
    }
    for(int pos = 1; pos <= N; pos++) {
        ll num = 0;
        for(int nowpos = pos; nowpos >= 0; nowpos--) {
            // nowposまでの街に与えられるダメージの総和 + nowpos+1~posの街に与えられるダメージの総和 ← これの最大値をdp[pos]に格納する
            chmax(dp[pos], dp[nowpos] + max(0LL, num - A[pos]));
            for(int j = 0; j < Monster[nowpos].size(); j++) {
                // (nowposがL[i]であるMonsterであるもののうち、) pos <= R[i]を満たすMonsterであるか
                if(Monster[nowpos][j].first >= pos) {
                    // num ... nowposがL[i]であるMonsterの総数. つまり、nowpos ~ posを攻撃できるMonsterの攻撃の総和
                    num += Monster[nowpos][j].second;
                }
            }
        }
        cerr << dp[pos] << endl;
    }
    cout << dp[N] << endl;
    return 0;
}

参考にさせていただいた実装

https://atcoder.jp/contests/kupc2019/submissions/7956445

【解答例】AGC 039 A - Connection and Disconnection

atcoder.jp

制約

1 ≤ | S | ≤ 100
1 ≤ K ≤ 109

考えたこと

SとKの制約から、文字列を連結させてから操作回数を数えようとすると、O( | S | * K ) となり間に合いません.
そのため、Sに対して、どの隣り合う2文字も相異なるような操作回数を求めて、それをK倍する方針で解きます.

まず、同じ文字がX回連続する部分を、隣り合う2文字が相異なるようにするには、X / 2回操作を行えばよいです.

例)
aaa -> axa ( 3 / 2 = 1 回)
aaaa -> axax ( 4 / 2 = 2 回)

次に考えなければならないこととして、文字列の連結部分が同じ文字だった場合、連結後の連続する文字数に対して2で割らないと、正しい操作回数が求まらない、ということです.

例えば、K = 2, S = "aaabaaa"とすると、連結後は、aaabaaaaaabaaaとなります.
この場合の操作回数の最小は5回で、操作後の文字列は例えばaxabaxaxaxbaxaとなります.
これは、先頭と末尾で連続するaaaに対する操作2( = (3 / 2) * 2 )回と、連結部のaaaaaaに対する操作3( = 6 / 2 )回の和です。

上記の様に連結部分に考えず、単にSの中で必要な操作回数を求めてK倍すると、aaabaaaの操作回数は2回なので、解は4となり一致しません(aaabaaaaxabaxaに変換後連結すると、axabaxaaxabaxaとなり、連結部に同じ文字が連続してしまう).

私は上記の様な方針で解きましたが、連結部分に対する操作回数の数え方をどうするかによって、実装の仕方は分かれると思います.


それでは上記内容を実装してみます.

実装

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

using ll = long long;

signed main() {
  string s;
  ll k;
  cin >> s >> k;
  
  ll n = s.size();    // sの長さ
  ll ans = 0;         // 必要な操作回数
  ll top = 0;         // sで先頭で同じ文字が連続している数
  ll back = 0;        // sで末尾で同じ文字が連続している数
  ll same_char_cnt;   // iから数えて連続する同じ文字の数

  // sの中で同じ文字が連続する部分について数を数える
  for (ll i = 0; i < n; i += same_char_cnt) {
    same_char_cnt = 1;
    for (ll j = i + 1; j < n; j++) {
      if (s[i] == s[j])
        same_char_cnt++;
      else
        break;
    }

    // 先頭で連続する同じ文字数をtopに保存する. 先頭に対する操作回数はここでは数えない
    // 例えばsが、"aaabccdddaa" なら、先頭の"aaa"部分について3を格納する
    if (i == 0) {
      top = same_char_cnt;
      continue;
    }

    // 末尾で連続する同じ文字数をbackに保存する. 末尾に対する操作回数はここでは数えない
    // 例えばsが、"aaabccdddaa" なら、末尾の"aa"部分について2を格納する
    if (i + same_char_cnt >= n) {
      back = same_char_cnt;
      continue;
    }

    // 文字列の途中で連続する同じ文字に対する操作回数をansに加算する.
    // 例えばsが、"aaabccdddaa" なら、"b", "cc", "ddd" の3つの部分について計算を行う
    ans += same_char_cnt / 2;
  }

  

  if (top == n) { 
    // sが1種類の文字だけで構成される場合
    ans = (n * k) / 2;
  } else {
    // sが2種類以上の文字で構成される場合

    // sの途中部分に対する操作回数をk倍する
    ans *= k;

    if (s[0] == s[n - 1]) 
      // 先頭と末尾の文字が一致する場合
      
      // 1つの接点部分の操作回数は(top + back) / 2 回となる
      // 接点は k-1 箇所ある
      ans += (top + back) / 2 * (k - 1) + top / 2 + back / 2;
      
    else
      // 先頭と末尾の文字が一致しない場合
      ans += k * (top / 2 + back / 2);
      
  }

  cout << ans << endl;

  return 0;
}

IntelliJ Mac版ショートカットをまとめ

仕事でIntelliJを使い始めたのでショートカットなどをまとめてみました。 ソースはこれです↓

Javaプロジェクトの作成を通じて、IntelliJの便利な機能を一通り試すことができる内容となっています。これからIntelliJを仕事で使うことになったという人には、開発前に一読しておくことで作業効率上げることができると思います。
私もIntelliJを使う以前は仕事ではEclipseを使っており、ショートカットや用語の相違に始めは四苦八苦しましたが、本書を一読する過程でかなり整理できました。
また、本書はCommunity版とUltimate版で説明を分けてあるため、両方のユーザにとって親切な内容になっていると思います。

ショートカット一覧

  • Command + , : 設定画面を表示(MacではPreferences、それ以外ではSettingsと名称が異なるため注意)
  • Plugins -> Browse repositories : プラグインのインストール
  • Ctrl + Space : コード補完
  • Option + return : クイック修正
  • Shift × 2 : コマンド検索
  • Command + Z : Undo(取り消し)
  • Command + Shift + Z : Redo(やり直し)
  • Command + F : Find(検索)
  • Command + R : Replace(置換)
  • Command + D : `Duplicate(行、選択は似の複製)
  • Command + Shift + F : Find in Path(プロジェクト内で検索)
  • Command + Shift + R : Replace in Path(プロジェクト内で置換)
  • Command + 1 : Project(プロジェクトツールウィンドウにフォーカスを移動)
  • Command + N : New(新規ファイル作成)
  • Ctrl + Shift + D : Debug context configuration(HTMLファイルをブラウザでプレビュー)
  • Option + ↑ : Expand Selection(同じ構文内を全選択)
  • Option + ↓ : Shrink Selection(Expand Selectionの選択範囲を縮小)
  • Option + Command + V : 変数の抽出
  • Option + Command + N : 変数のインライン化(変数にカーソルをあてた状態で)
  • Option + Command + L : コードフォーマット
  • Shift + F6 : リネームリファクタリング
  • Command + F1 : Inspectionの警告内容確認
  • Option + return : Intention Action(警告の解消)
  • Command + Shift + return : ステートメント補完(書きかけのコードの補完. 行末の;の入力の手間を削減できる)
  • Ctrl + R : アプリケーションの実行
  • Ctrl + Shift + R : カーソル位置でアプリケーションを実行
  • F2 : (エラー発生時)エラーのある個所にカーソルを移動
  • Command + T : リファクタリングのポップメニューを表示
  • Command + F8 : 選択中の行にブレークポイントを設定(コードの左側をクリックしても設定できる)
  • ブレークポイントを右クリックするとCondition欄でブレーク条件を指定できる
  • Evalute and logをチェックするとブレークポイントに達したタイミングで式を評価した結果を記録する
  • Ctrl + Shift + D : デバッグを実行
  • Command + Option + R : 再開
  • F8 : ステップオーバー
  • F7 : ステップイントゥ
  • Option + Shift + F7 : 強制ステップイントゥ
  • Shift + F8 : ステップアウト
  • Option + F9 : カーソルまで実行
  • Option + F8 : 式評価
  • Command Shift F8 : Breakpointsダイアログを表示
  • Ctrl + Shift + T : テストケースへ移動(テストケースがない場合作成を促す)
  • Ctrl + Shift + R : テストケースの実行
  • Command + R : テストの再実行
  • Command + B :
  • (シンボル参照箇所にカーソルがある場合)シンボルの定義場所へジャンプ
  • (シンボル定義場所にカーソルがある場合)シンボル利用箇所の一覧表示
  • Option + F7 : シンボル利用箇所を一覧表示(Findツールウィンドウ表示)
  • Command + Option + F7 : シンボル利用箇所を一覧表示(ポップアップ表示)
  • Command + [ : ジャンプ前の元のコードに戻る
  • Command + ] : ジャンプ先のコードにもう一度戻る
  • Command + U : 子クラスから親クラスへ移動
  • Option + Command + B : 子クラス、実装クラス一覧をポップアップ表示
  • Ctrl + Tab : 直前に開いたタブを開く(2つ前の開くにはCtrlを押したままTabを2回押しCtrlを離す)
  • Command + E : Recent Files(最近開いたファイル一覧をポップアップ表示)
  • Command + ↑ : ナビゲーションバーにフォーカスを当てる
  • ナビゲーションバーを開いている状態は、現在のファイル、ディレクトリにフォーカスが当たっているのと同じ状態
  • Command + Shift + Delete : 最後の編集個所に戻る
  • Shift × 2 : Search Everywhere(ファイル名、クラス名、シンボル名を指定して検索)
  • Command + Shift + O : ファイル名に限定して検索
  • Command + O : クラス名に限定して検索
  • Option + Command + O : シンボル名に限定して検索
  • Command + Option + A : チェンジリストに追加
  • Command + K : コミット
  • Command + Shift + K : プッシュ
  • Command + T : プル
  • Ctrl + V : VCS操作

その他、知っておくと便利なもの

Postfix complex

ポストフィックス補完

式の後に特定のキーワードを入力した後にTabを押すと、キーワードに応じた自動補完が走る

JavaScript

  • 式.log : console.logで出力
  • 式.var : 変数に代入
  • 式.if : 条件文にしたif文を構成
  • 式.not : 条件を反転

Java

  • psvm : mainメソッド作成
  • 式.if : 条件文にしたif文を構成
  • 式.not : 条件を反転
  • 式.sout : System.out.printlnを生成し、引数に式を渡す

重要な設定について

Project作成関連

  • Enable Auto-import

外部ライブラリの依存が追加された際に自動反映させるための設定

Mavenの場合の設定

Preferences -> Build Execution -> Deployment -> Build Tools -> Maven -> Importing
Import Maven projects automaticallyチェックボックス

手動反映の場合、Maven ProjectツールウィンドウのReimport All Maven Projectsボタンを押す

Inspection関連

Intention Action(Option + return)のSafe delete 'Main'のメニューを展開して設定を以下の中から選択できる

  • Edit inspection profile setting : Inspectionの設定画面を開く
  • Fix all 'Unsed declaration' problems in file : ファイル内で同様の問題をすべて修正する
  • Run inspection on ... : 該当のInspectionのヒット個所を、プロジェクト内の他のファイルからも探す
  • Disable inspection : 該当のInspectionを無効化する
  • Suppress all inspections for class : このクラス内のInspectionをすべて無効化
  • Suppress for class : このクラスで該当のInspectionを無効化
コーディング中にコンパイルエラーを表示するかの設定

Preference -> Build, Excection, Deployment -> Build Tools -> Compiler
Build project automaticallyチェックボックス

IntelliJにおける用語について

同じProjectという用語でも、IntelliJEclipseでは別の概念を指している

Eclipse IntelliJ
Workspace Project
Project Module

IntelliJにおける用語の関係性は、Project > Moduleとなっており、ProjectはModuleより広い概念

IntelliJにおける用語の概念

  • Project : 複数のModuleをまとめる場で、配下のModuleに共通した設定を保持する
  • Module : プロダクションコードやテストコードといったソースコードを管理する

まとめ

覚えること多すぎぃ!
とりあえず、移動、実行、デバッグに関するショートカットを覚えれば、操作性向上を実感できそう。
慣れてきたら、コード補完に関するものや、Postfix complexを覚えればさらに良さそう。ステップアップで少しずつ覚えていくことが大事ですね。

【解答例】ABC 142 D - Disjoint Set of Common Divisors

atcoder.jp

題意

2つの正整数A、Bが与えられるので、その公約数のうちいくつかを選ぶ。
このとき選んだ値は、それぞれが互いに素である必要がある。
選べる公約数の最大の個数はいくつか?

制約

1 <= A, B <= 1012

考えたこと

互いに素である、というのは2つの整数が1以外に公約数を持たないことを指します。

この定義から、AとBの公約数からそれぞれが互いに素である数を選び取っていくには、約数の中から素数を選び取っていけばよいと考えられます。
これなぜかというと、素数以外の約数を選択する場合を考えると素数である約数を選択する場合に比べて、損をすることはあっても得をすることはないとわかるからです。

例として、A=6, B=12の場合を考えます。その公約数は、1, 2, 3, 6なります。
素数のみを選択した場合、2, 3を選択することになり、1を含めると公約数は合計3個を選ぶことができます。
一方、素数ではない6を選ぶ場合、2, 3と共通の約数を持つため、1を含めて合計2個となり、素数を選ぶ場合より1個損です。

上記のように素数以外の約数を選択すると、その数の1以外の約数を選択できなくなるため、素数である約数を選択する場合に比べて不利であるとわかります。
よって、A、Bの素数である公約数、つまり、素因数を数えることで、解が得られると判断できそうです。

では、2数の素因数の求め方ですが、これは以下の2つの手順で効率的に求めることができます。


1. 最大公約数Gを求める 2. 試し割り法により、2~√Gの値にある素因数を求める

最大公約数はユークリッドの互除法により、効率的に求めることができます。

さて、最大公約数を求めた後の試し割り法が重要です。
最大公約数Gを求めて、2~Gまで愚直に素因数判定を行うと(O(G))、AとBが同じ値で1012に近い素数であった場合、Gはその素数となります。このままでは間に合いません。

そこで、試し割り法という工夫を適用します。
これは、整数Gの素因数を調べるのにGまで調べる必要はなく、√Gまでを調べれば良いというものです。(詳しくはリンク先を参照)

これでループ部分の時間計算量を√Gまで落とすことができ、実行時間に間に合うようになります。

実装

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

using ll = long long;

// greatest common divisor (最大公約数)
ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }

int main(){
  
  // input
  
  ll a,b; cin>>a>>b;          // a, bの上限は10^12であることに注意
  
  // solution
  
  ll G=GCD(a,b);

  ll ans=1;                   // a, bがどのような値でも、1は必ず選ぶことができる
  
  for(ll i=2; i*i<=G; i++){   // √Gまでループを行い素因数判定を行う
    
    if(G%i==0){               // 素因数判定
      ans++;
      while(G%i==0) G/=i;     // Gの素因数からiを除外していく
    }
    
  }
  
  if(G!=1) ans++;             // √Gのループを抜けた時Cが1でないならば、その時のGは素数である
  
  cout<<ans<<endl;
  
}

感想

教養的知識を2つ組み合わせて解く、アカデミックな内容でとても面白かったです。
問題を読んですぐに方針は立てられたものの、実装に時間が掛かってしまったので、GCDや素因数分解などのアルゴリズムの基本とも言えるものについては、ライブラリ化するだけではなく、いつでも書けるようにしておく必要がある、と学びになりました。




......ところで、「互いに素」という単語を見聞きして、私はリズと青い鳥を連想します。