atwiki-logo
  • 新規作成
    • 新規ページ作成
    • 新規ページ作成(その他)
      • このページをコピーして新規ページ作成
      • このウィキ内の別ページをコピーして新規ページ作成
      • このページの子ページを作成
    • 新規ウィキ作成
  • 編集
    • ページ編集
    • ページ編集(簡易版)
    • ページ名変更
    • メニュー非表示でページ編集
    • ページの閲覧/編集権限変更
    • ページの編集モード変更
    • このページにファイルをアップロード
    • メニューを編集
    • 右メニューを編集
  • バージョン管理
    • 最新版変更点(差分)
    • 編集履歴(バックアップ)
    • アップロードファイル履歴
    • ページ操作履歴
  • ページ一覧
    • ページ一覧
    • このウィキのタグ一覧
    • このウィキのタグ(更新順)
    • このページの全コメント一覧
    • このウィキの全コメント一覧
    • おまかせページ移動
  • RSS
    • このウィキの更新情報RSS
    • このウィキ新着ページRSS
  • ヘルプ
    • ご利用ガイド
    • Wiki初心者向けガイド(基本操作)
    • このウィキの管理者に連絡
    • 運営会社に連絡(不具合、障害など)
ページ検索 メニュー
早稲田大学チームvivid_turtle 知見共有@ ウィキ
  • ウィキ募集バナー
  • 目安箱バナー
  • 操作ガイド
  • 新規作成
  • 編集する
  • 全ページ一覧
  • 登録/ログイン
ページ一覧
早稲田大学チームvivid_turtle 知見共有@ ウィキ
  • ウィキ募集バナー
  • 目安箱バナー
  • 操作ガイド
  • 新規作成
  • 編集する
  • 全ページ一覧
  • 登録/ログイン
ページ一覧
早稲田大学チームvivid_turtle 知見共有@ ウィキ
ページ検索 メニュー
  • 新規作成
  • 編集する
  • 登録/ログイン
  • 管理メニュー
管理メニュー
  • 新規作成
    • 新規ページ作成
    • 新規ページ作成(その他)
      • このページをコピーして新規ページ作成
      • このウィキ内の別ページをコピーして新規ページ作成
      • このページの子ページを作成
    • 新規ウィキ作成
  • 編集
    • ページ編集
    • ページ編集(簡易版)
    • ページ名変更
    • メニュー非表示でページ編集
    • ページの閲覧/編集権限変更
    • ページの編集モード変更
    • このページにファイルをアップロード
    • メニューを編集
    • 右メニューを編集
  • バージョン管理
    • 最新版変更点(差分)
    • 編集履歴(バックアップ)
    • アップロードファイル履歴
    • ページ操作履歴
  • ページ一覧
    • このウィキの全ページ一覧
    • このウィキのタグ一覧
    • このウィキのタグ一覧(更新順)
    • このページの全コメント一覧
    • このウィキの全コメント一覧
    • おまかせページ移動
  • RSS
    • このwikiの更新情報RSS
    • このwikiの新着ページRSS
  • ヘルプ
    • ご利用ガイド
    • Wiki初心者向けガイド(基本操作)
    • このウィキの管理者に連絡
    • 運営会社に連絡する(不具合、障害など)
  • atwiki
  • 早稲田大学チームvivid_turtle 知見共有@ ウィキ
  • 立式と同値の言いかえ

早稲田大学チームvivid_turtle 知見共有@ ウィキ

立式と同値の言いかえ

最終更新:2019年06月01日 16:54

vivid_turtle

- view
メンバー限定 登録/ログイン
競プロで数学が絡む多くの問題は、立式して、命題の同値言い換えでうまく解くことができる。

いわれた通りに立式


これが一番見えやすいものである。複雑な関数でなければ数学の知見がそのまま使える。というか、解いてる本人の数学力によっては複雑な関数でも使えちゃう場合がある。

例 ABC112 - D(400)


https://atcoder.jp/contests/abc112/tasks/abc112_d

この問題で、自然数k, sをおくと
a_1+a_2+a_3+...+a_N = M = k * s
とかける。
そして、kを最大公約数だと考えて、これを最大化するのが目標。これをもってして式を見直すと、
a_1+1_2+...+a_N = k * s = k(b_1+b_2+..+b_N)
でb_nという自然数列で書ける。つまり
b_1+b_2+...+b_N = s
となる。
ここで、sを最小化すれば、kが最大になると気付く。sの最小条件はb_1=b_2=...=b_N=1の時であり、その時はs=Nである。
つまり、この問題はsがN以上であるという条件を満たした下で最大のkの求めるという課題である。これは約数列挙で簡単にできる。


例 天下一プロコン2019 - D(600)


https://atcoder.jp/contests/tenka1-2019/tasks/tenka1_2019_d

三角形を作れるという条件をうまく立式化したい。三角不等式という三角形の成立条件を表す有名な絶対不等式があり、三辺をa, b, cとすると、
|a + b| > c ⋀ |a - b| < c
を(a, b, c) = (b ,c ,a)と置換してできる変数群において成立する。{ここで、問題設定で
a + b + c = T(定数)}
といえる。このことを利用すると、△不等式を
|T - c| = T - c > c つまり c < T/2
とわかる。同様にa < T/2, b < T/2であるとわかる。この時、不等式|a - b| < cは必ず成り立つことがわかる(実験すれば分ける)
つまりこの問題は、
{a < T/2 ⋀ b < T/2 ⋀c < T/2
を満たすa, b, cを作れる振り分け方}を求めたい。確率論でよくある余事象の手法を使うと
U - {a >= T/2 ∨ b >= T/2 ∨ c >= T/2}
を計算すればいいとわかる。
ベンズを書いて、包除原理で考えると、
A := a >= T/2, B := b >= T/2,C := c >= T/2 とすれば、U - A - B - C + (A ⋀ B) + (B ⋀ C) + (C ⋀ A) - (A ⋀ B ⋀ C)とわかる。
(A ⋀ B ⋀ C) = 0であり、(A ⋀ B)は他の2つと同じ値となり、Tが奇数の時は0, 偶数の時は動的計画法でA = B = T/2になる場合の数を計算できる。Aは、動的計画法で
dp[i][j]:=i番目の数まで足して和がjの場合の数
dp[i][j] += dp[i - 1][j] * 2(採用しない場合、B or Cに振り分けるで2通り)
dp[i][j] += dp[i - 1][j - ar[i]];(採用する場合)
と解ける。(A >= T/2 の時、B, C <= T/2である)

よって、動的計画法でそれぞれの集合に該当したものを計算し、足し引きすれば解ける。
「立式と同値の言いかえ」をウィキ内検索
LINE
シェア
Tweet
早稲田大学チームvivid_turtle 知見共有@ ウィキ
記事メニュー

メニュー

  • トップページ
  • プラグイン紹介
  • メニュー
  • 右メニュー
  • アルゴリズム別知見
  • 個別問題知見



リンク

  • @wiki
  • @wikiご利用ガイド




ここを編集
記事メニュー2

更新履歴

取得中です。


ここを編集
最近更新されたページ
  • 1504日前

    bitsetでの定数倍改善
  • 2118日前

    しゃくとりの大原則
  • 2118日前

    アルゴリズム別知見
  • 2121日前

    グリッド上の構築
  • 2122日前

    ARC096-D
  • 2122日前

    ARC092-D
  • 2122日前

    個別問題知見
  • 2126日前

    ダブリングの使い所さん
  • 2132日前

    文字列と動的計画法
  • 2132日前

    数え上げのDPのさまざま(知らなかったこと)
もっと見る
最近更新されたページ
  • 1504日前

    bitsetでの定数倍改善
  • 2118日前

    しゃくとりの大原則
  • 2118日前

    アルゴリズム別知見
  • 2121日前

    グリッド上の構築
  • 2122日前

    ARC096-D
  • 2122日前

    ARC092-D
  • 2122日前

    個別問題知見
  • 2126日前

    ダブリングの使い所さん
  • 2132日前

    文字列と動的計画法
  • 2132日前

    数え上げのDPのさまざま(知らなかったこと)
もっと見る
ウィキ募集バナー
新規Wikiランキング

最近作成されたWikiのアクセスランキングです。見るだけでなく加筆してみよう!

  1. MadTown GTA (Beta) まとめウィキ
  2. AviUtl2のWiki
  3. R.E.P.O. 日本語解説Wiki
  4. 機動戦士ガンダム EXTREME VS.2 INFINITEBOOST wiki
  5. シュガードール情報まとめウィキ
  6. ソードランページ @ 非公式wiki
  7. ドラゴンボール Sparking! ZERO 攻略Wiki
  8. シミュグラ2Wiki(Simulation Of Grand2)GTARP
  9. 星飼いの詩@ ウィキ
  10. Dark War Survival攻略
もっと見る
人気Wikiランキング

atwikiでよく見られているWikiのランキングです。新しい情報を発見してみよう!

  1. アニヲタWiki(仮)
  2. ストグラ まとめ @ウィキ
  3. ゲームカタログ@Wiki ~名作からクソゲーまで~
  4. 初音ミク Wiki
  5. 検索してはいけない言葉 @ ウィキ
  6. 機動戦士ガンダム バトルオペレーション2攻略Wiki 3rd Season
  7. 発車メロディーwiki
  8. Grand Theft Auto V(グランドセフトオート5)GTA5 & GTAオンライン 情報・攻略wiki
  9. オレカバトル アプリ版 @ ウィキ
  10. SDガンダム ジージェネレーションジェネシス 攻略Wiki
もっと見る
全体ページランキング

最近アクセスの多かったページランキングです。話題のページを見に行こう!

  1. 過去の行動&発言まとめ - 鹿乃つの氏 周辺注意喚起@ウィキ
  2. マイティーストライクフリーダムガンダム - 機動戦士ガンダム EXTREME VS.2 INFINITEBOOST wiki
  3. 魚拓まとめ - 鹿乃つの氏 周辺注意喚起@ウィキ
  4. 参加者一覧 - ストグラ まとめ @ウィキ
  5. 1103環境(遊戯王) - アニヲタWiki(仮)
  6. 前作からの変更点 - 機動戦士ガンダム EXTREME VS.2 INFINITEBOOST wiki
  7. 魔獣トゲイラ - バトルロイヤルR+α ファンフィクション(二次創作など)総合wiki
  8. コレクター・ユイ - アニヲタWiki(仮)
  9. サーヴァント/一覧/クラス別 - Fate/Grand Order @wiki 【FGO】
  10. 画像倉庫 - 鹿乃つの氏 周辺注意喚起@ウィキ
もっと見る

  • このWikiのTOPへ
  • 全ページ一覧
  • アットウィキTOP
  • 利用規約
  • プライバシーポリシー

2019 AtWiki, Inc.