ferinの競プロ帳

競プロについてのメモ

Codeforces #401 A, B, C, D

A問題

問題概要

 3個の箱の中にボールを隠しました。規則にもとづいて箱の位置を交換します。移動させた回数が奇数のときは左と真ん中の箱、偶数のときは右と真ん中の箱を入れ替えます。移動させた回数と最後にボールがあった場所から最初にボールがあった位置を求めてください。箱の位置を左から0, 1, 2と表します。

解法

 ボールがどのように移動するのか実験してみます。

  0 1 2  0 1 2  0 1 2
0 o        o        o
1   o    o          o
2     o  o        o
3     o    o    o
4   o        o  o
5 o          o    o
6 o        o        o
7   o    o          o
8     o  o        o
9     o    o    o

 周期6で位置が変化しているため、移動させた回数nを6で割った余りからボールの初期位置を一意に求められます。


B問題

問題概要

 AくんとBくんはN桁の数字を持っています。二人はこの数字を使ってある勝負をします。左の桁から1桁ずつ数の大小を比べ、相手より小さければ負けになります。しかしBくんは勝ちたいので不正をし、決まった順序と違う順番で数を提示します。Bくんが負ける数を最も少なくしたときの負ける数、Aくんが負ける数を最も多くしたときのAくんが負ける数を示してください。

解法

 Aくんが出す数に対してBくんが出す数の適切な組み合わせさえ分かればいいため、AくんとBくんの持っている数の順番は関係ありません。
 まず、負ける数を最も少なくするときのことを考えます。Aくんが提示する数以上の数を出せば勝負に負けません。そこで、勝負に負けないギリギリの数を出し続けることを考えます。AくんとBくんが持っている数をそれぞれソートし、最も小さい勝負に負けない数を順番に決めていきます。n-(負けない数)とすることで最小の敗北数を求めることができます。
 次に、Aくんが負ける数を最も多くすることを考えます。同じ数では勝てないためAくんが出す数よりも大きい、最小の数を順に当てはめていくことで最大の勝利数を求められます。
 これらの貪欲法でO(N)で求められます。


C問題

問題概要

 n行m列(1<=n*m<=10^5)の表があります。この表の各マスには1つの整数(<=10^9)が書かれています。l行目からr行目(1<=l<=r<=n)が降順でない列が存在するかのクエリにk回(k<=10^5)答えてください。

解法

 dp[i] =(i行目から最も長く降順でない数列が続いている行)を求めておくことで各クエリに対しO(1)で答えることができます。各列について上から順に降順でない部分列が何行から何行にかけてあるのかを求めます。全てのマスについて1回ずつ探索するため計算量はO(n*m)です。


D問題

問題概要

 n個の文字列が与えられる。接尾字を消去することで文字列が降順に並ぶようにしたい。消去する文字数を最も少なくしたときの消去後の文字列を求めてください。

解法

 後ろから順番に降順になるような最も消去する文字数が少ない消し方をすることで求めることができます。n番目の文字列はn+1番目の文字列に対し降順となるように文字を消去する。そして、n-1番目の文字列は消去した後のn番目の文字列に対し降順となるように文字を消去する必要がある。したがって後ろから順番に処理していくことで求められる。

ARC022 B問題-細長いお菓子

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」で使う言語を指定します。

プラグインの導入

何も設定していない状態だとTopCoderのappletに付属しているエディタでコーディングすることになります。問題に沿ったテンプレートの作成やサンプルのローカルでの実行、普段のエディタでのコーディングをできるようにプラグインを導入しましょう。
以下のページから「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」をクリックします。
一回appletを再起動するとこのプラグインが反映されます。

practice(過去問)

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

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

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

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

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

トポロジカルソート

トポロジカルソートとは

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

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

入次数

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


DFS

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


トポロジカルソートした結果の数列が何通りあるか

bitDPでできます。
D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder
ABC041D - ferinの競プロ帳

閉路検出

トポロジカルソートを用いて有向グラフの閉路検出をできます。トポロジカルソートができればDAGであり閉路が存在しません。逆に閉路が存在すればトポロジカルソートは不可能です。入次数のコードで ans.size() == v であればトポロジカルソートができた、そうでなければできなかったと判定することができます。