読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

ARC022 B問題-細長いお菓子

ARC 競技プログラミング

arc022.contest.atcoder.jp

重複した数が存在しない最大の領域を求める問題です。重複した数が存在するかどうかの判定ををunordered_setで行いました。unordered系のデータ構造はじめて使ったんですが衝突さえしなければO(1)でできるの便利ですね… 解いているときに開かれていたCFでunorderedを殺すテストケースがあったそうなので最初にメモリをちゃんと確保しておくように気をつけたい。
バケツサイズを変えたりや挿入する値のXORを取る必要があるらしい。 
nitcoder000.hatenablog.com


XOR

競技プログラミング

排他的論理和(XOR)についての性質のメモ

A^B = (A&!B)|(!A&B)
    = (A|B)&(!A|!B)
    = (A|B)&(!(A&B))
  • A^B = B^A(交換則)
  • A^A = 0
  • A^B = 0 ならば A = B

a, b, c…が0か1のとき、

a^b^…^c = 1 (1が奇数個)
           0 (1が偶数個)

TopCoderの設定

競技プログラミング


TopCoderについての設定や問題の解き方についてのメモです。OSはWindows10です。

登録方法

 TopCoderにアクセスし右上の「LOG IN」をクリック、「COMMUNITY LOG IN」をクリックし画面下中央の「join now」から登録します。
f:id:ferin_tech:20170222230210p:plain
名前、国、ユーザー名、メールアドレス、パスワードを入力します。入力したメールアドレスにメールが送られてくるため、メールの認証を行います。

applet

ダウンロード

 TopCoderではWeb ArenaかJavaAppletのどちらかを用いて問題の閲覧や提出を行います。ここではapplet版について書きます。TopCoderにログインし、上部中央の「learn」から「Competive programing」をクリックします。「launch appret arena」をクリックするとappletのダウンロードが始まります。
f:id:ferin_tech:20170222230242p:plain
f:id:ferin_tech:20170222230310p:plain

Javaの更新

 ダウンロードしたAppletを実行した際、Javaのバージョンが最新でない場合はJavaのインストールが必要だと言われます。画面の手順通りにJavaの更新をしましょう。

セキュリティ例外

 セキュリティ設定によってブロックされたアプリケーションというエラーが表示された場合、TopCoderのAppletを例外に設定する必要があります。スタートメニューから「Java」→「Javaの構成」としてJavaコントロールパネルを表示します。セキュリティタブの例外サイト・リストに「http://www.topcoder.com」を追加することでセキュリティ例外に追加できます。

設定

 ここまでくればappletを実行できるはずです。appletを起動しIDとパスワードを入力してログインしてください。まずはフォントサイズの設定をします。画面上部のタブの左から3つめの「Option」から一番下の「Setup User Preferences」をクリックします。
f:id:ferin_tech:20170222230406p:plain
「Editors」、「Problems/Messages」、「Challenge」、「Additional Fonts」タブにsizeの設定があるので適当な大きさに設定しましょう。(自分は18です。)次にデフォルトの言語を指定しましょう。「Editors」タブの「Default Language」で使う言語を指定します。

プラグインの導入

以下のページから「CodeProcessor」「TZTester」「FileEdit」をダウンロードします。
About TopCoder - Overview
「Option」タブから「Editor」を選択します。Common ClassPathに「TZTester.jar」「FileEdit.jar」のパスを追加します。
Addボタンを押してダイアログに以下のように入力します。
 Name - CodeProcessor
 EntryPoint - codeprocessor.EntryPoint
 ClassPath - CodeProcessor.jarのパス(Browseから選択)
CodeProcessorをクリックし、Configureを押して設定を開きます。
画面上部の「Editor EntryPoint」にfileedit.EntryPointと入力して「Configure」をクリックします。
画面上部の「Enter directory to read/write problems to」にソースを置きたいファイルパスを書きます。
問題を開くとこの問題にあったソースファイルがこのパスに生成されます。
「Code Template」タブに切り替え、Languageを使用する言語に変更しテンプレートを編集し、「Save」ボタンをクリックしてください。include文やREPマクロなどを使いたい場合はこのテンプレートを編集します。
「CodeProcessor Script」に tangentz.TZTester と書き「Verify」をクリックします。

practice(過去問)

画面上部の「Practice Room」タブからSRMを選択し、解きたい問題セットを選択してください。選択すると問題のページに移動します。「Select one」から解く問題を選択すると問題が開かれます。問題を開くとプラグインで指定したパスにテンプレートとなるファイルが生成されます。エディターでこのファイルを開き、コーディングし、ローカルで実行することでサンプルが実行され、正解か不正解かが表示されます。提出する際は画面下部の「Compile」をクリックし「Submit」をクリックすることで提出できます。

TopCoder Arenaで「セキュリティ設定によってブロックされたアプリケーション」の解決方法 - tshitaの備忘録Ⅱ
TopCoderでCodeProcessor+TZTester+FileEdit - Gulfweed

yukicoder No.58 イカサマなサイコロ

yukicoder

No.58 イカサマなサイコロ - yukicoder

モンテカルロ法をはじめて使ったのでその記録です。
モンテカルロ法とは乱数を用いてシミュレーションを行う方法です。この問題では次郎君の試行として1から6までの範囲の乱数をN回求め、太郎君の試行として4から6までの範囲の乱数をK回、1から6までの範囲の乱数をN-K回求めます。これを10^6回試行し、(太郎君が勝った回数)/(試行回数 = 10^6)を計算することで答えを求めました。

トポロジカルソート

競技プログラミング

トポロジカルソートについて調べた内容のメモです。

トポロジカルソートとは

閉路がない有向グラフの各有向辺が順方向になるようにソートすることをトポロジカルソートと呼びます。DAG(有向無閉路グラフ)にのみ行うことができ、トポロジカルソートが行えればそのグラフはDAGであるといえます。
トポロジカルソート | グラフ | Aizu Online Judge

トポロジカルソートのアルゴリズム

入次数

入次数が0の頂点があれば、その頂点をソート後の結果に追加しその頂点と隣接した頂点の入次数をマイナス1する。これを入次数が0の頂点がなくなるまで繰り返すことでトポロジカルソートをすることができます。計算量はO(V+E)です。
有向非巡回グラフ(DAG)をトポロジカルソートする - マツシタケイタの技術ブログ(勉強中)


DFS

全ての点から深さ優先探索を行い、その帰りがけ順がトポロジカルソートの結果になります。計算量はO(V+E)です。

Topological sort

ABC015-D問題

ABC 競技プログラミング

abc015.contest.atcoder.jp

ナップザック問題でk個のみつかえるという制約を加えたような問題です。ナップザック問題で持つ状態に加えて今までに使用したスクリーンショットの枚数を状態として持つことで解けます。まずメモ化再帰で実装しました。

次に動的計画法で実装しました。

ABC008-D問題

ABC 競技プログラミング

abc008.contest.atcoder.jp

 蟻本で似た問題(P121, Bribe the Prisoners)を見たことがあったので同じように考えて実装しました。機械を動かしたあとその機械で取った金塊で分断された場所は互いに関係しない独立した場所です。なので、ある機械を動かしたときに得られる金塊の数は
(1)機械を動かして得られる金塊
(2)分断されたそれぞれのエリアで得られる金塊
の和になります。それぞれのエリアについて再帰的に考えていけば得られる最大の金塊数を求められます。dp[sx][sy][fx][fy]を左上を(sx, sy)、右下を(fx, fy)としたエリアで得られる金塊としてメモ化再帰で実装しました。境界条件の部分は番兵法つかったほうが良さそう…

 範囲内を全て探索しているところを機械がある点に絞れば100点の制約でも間に合いました。