鬱！ 鬱すぎてうつほ物語になった！w

主に食べたラーメンについて記録を残すために開設されたブログです。他のことも書くかもしれません。

C++での関数名オーバーロードしたインライン関数について (日記/備忘録)

競技プログラミング用C++コードテンプレに，標準入力のインライン関数を追加した．以下のような感じ．

inline void scan(int&a){scanf("%d",&a);}
inline void scan(vector<int>&v){int sz=v.size();rep(i,sz){scan(v[i]);}}
inline void scan(char&a){scanf(" %c",&a);}

scan(x) という一貫した形で標準入力を受け取れて嬉しい．

関数名は全てscanにした．つまり関数名のオーバーロードを利用した．

ところでオーバーロードされた関数名が呼ばれるとき，どの程度のオーバーヘッドがあるのだろうか．競技プログラミングでは速さが重要ゆえ，これを考えないわけにはいかない．

しかしながら今回の場合，インライン関数については関数の決定はコンパイル時に行われ，実行ファイル上ではすでに手続きが展開されているはずであるので，実行時のオーバーヘッドは無いものと考えてよいはずである． というかインライン関数でなくても呼ばれる関数はコンパイル時に決定されるのでは．

macOSでcube20.orgをコンパイルする

目的

CWEBという記法で書かれたソースコードをMacでコンパイル・実行したい。なんかエラーが出た。Linuxはチョットモデキナイ。なんとか解決したい。運良くできて気分がいいので記録しておく。

必要なものとか

OS: macOS High Sierra 10.13.3

Homebrew

brewで以下をインストール:
brew install gcc (gcc-7 (Homebrew GCC 7.3.0))
brew install cweb

cube20.orgとは

このページを見ている人には不要かと思われますが、一応説明。

cube20.orgは、ルービックキューブがいかなる合法な状態にあっても、そこから20手以下で6面が揃った状態に戻せることを証明した数学者やプログラマーなど計4人のグループによるウェブサイトです。合法な、というのは、小さいキューブをバラバラにしないで、各面の回転のみで実現できる、という意味です。ちなみにルービックキューブは登録商標です。

このサイトでは、彼らが証明に用いたルービックキューブのソルバープログラムのソースコードが公開されています。丁寧なことに使い方も説明されています。とりあえず置いてあるファイルを全てダウンロードしておきます。

彼らはこのプログラムをLinux上で動かしたっぽいです。まあVMなりでLinux使えよという話ではありますがMacでできないのかとも思いますよね？ 私は思いました。

CWEBって何

このソースコード、拡張子が.wなのですが、何でしょうこれ。CWeb systemと書いてあります。ググるとこのページが見つかります、分かりやすいと思います。細かいことはよく分かりませんが、どうやら1つのファイルから実行ファイルとそのドキュメントを生成できるようです。さらに、ソースコードはC/C++、ドキュメントはTeXによる記述であるようです。

これのコンパイルにはctangleとcweaveというコマンドが必要なようです。brew install cwebによってこの2つのコマンドが使用できるようになります。

ここまでで準備が整ったはずなので、指示通りmakeします。

clang: warning: -O4 is equivalent to -O3 [-Wdeprecated]
clang: warning: -O4 is equivalent to -O3 [-Wdeprecated]
clang: warning: -O4 is equivalent to -O3 [-Wdeprecated]
clang: warning: -O4 is equivalent to -O3 [-Wdeprecated]
clang: warning: -O4 is equivalent to -O3 [-Wdeprecated]
twophase.w:215:21: error: reference to 'mutex' is ambiguous
pthread_mutex_lock(&mutex);
                    ^
twophase.w:204:17: note: candidate found by name lookup is 'mutex'
pthread_mutex_t mutex;

なんかwarningが出て、直後にerror: mutexという参照が曖昧だと怒られました。 warningの雰囲気から、どうもここではclangではなくgccを使うことが想定されてるっぽいので、素直にそうしてみます。makefile内に6か所ある$(CXX)から始まる行がそれで、これはシステムのデフォルトのコンパイラを呼び出すみたいですね。これらを全てg++-7に置換してしまいましょう。

ここでもう一度makeしてみます。私は念のため新しく生成されたファイルは全て削除しました。すると

cubepos.w: In function 'int main(int, char**)':
cubepos.w:1620:9: error: 'getpid' was not declared in this scope
    srand48(getpid()+time(0)) ;
            ^~~~~~
cubepos.w:1620:9: note: suggested alternative: 'getenv'
    srand48(getpid()+time(0)) ;
            ^~~~~~
         getenv
make: *** [cubepos_test] Error 1

先ほどのエラーは消えましたが、今度はgetpidなんてものはないと怒られました。ググるとincludeが必要らしいことが分かります。 LinuxだとincludeなしでOKなことがあるんですかね。分かりませんがcubepos.wの適当な位置に2行追加します。

#include <sys/types.h> 
#include <unistd.h>

3度目の正直、makeします。

Done.
(No errors were found.)
This is pdfTeX, Version 3.14159265-2.6-1.40.18 (TeX Live 2017) (preloaded format=pdftex)
 restricted \write18 enabled.
entering extended mode
(./cubepos.tex
! I can't find file `cwebmac'.
l.1 \input cwebmac

Press Enter to retry, or Control-D to exit)
lease type another input file name:

C++ソースコードのコンパイルは無事完了したようです。今度はcwebmacというファイルがないぞと怒られました。これ何なんですかね、sudo tlmgr install cwebmacとしてみましたがダメでした。どこかからcwebmac.texみたいなのをダウンロードしてきて然るべき場所に置けばいいんでしょうか。どなたか教えてください。

ですが今はドキュメントは必要ありませんしそもそもサイトからダウンロードできるのでCtrl+Dで終了します。

これで6つの実行ファイルが生成されたはずです。お疲れ様でした。

参考

CWEBをC/C++に変換する方法 — cube20.orgをコンパイルする
Ambiguous Reference for type pthread_mutex_t - Stack Overflow
C++のTips - Unix系OSでプロセスIDを取得するには？
［カショ］の表記 | NHK放送文化研究所

銀行とATMまとめ

動機

筆者はATM利用手数料を支払うのはなるべく避けたい性分なため、コンビニATMを使うことは稀である。 一方で、ネットバンキングの簡便性に魅力を感じており、ネット銀行の口座も複数開設している。自前のATMを持たないネット銀行においては、既存の金融機関のATMもしくはコンビニATMを使わざるを得ない。
この記事では各ネット銀行で利用できるATMの種類、および入出金時の手数料についてまとめる。果たしてまとまるのか。

この記事で扱う銀行のリスト

ほぼWikipediaのコピペである。
これらのうちネット銀行に分類したもの以外は自前のATMを持っている。

ATMの設置場所

都市銀行については各銀行店舗の他、商業施設等に設置されている。

ゆうちょ銀行ATMは郵便局の他、一部のファミリーマートでの利用が可能である。

セブン銀行はセブンイレブンやイトーヨーカドーなどで、イオン銀行はイオンやミニストップなどで利用できる。

その他のATM

イーネット

ファミリーマートやスリーエフに設置されているATMである。

ローソンATM

ローソンなどに設置されているATMである。

VIEW ALTTE

JR東日本の駅構内などに設置されているATMである。

2018/1/29 追記
住信SBIネット銀行のキャッシュカードで利用してみたところ、IC非対応であるようだった。

Patsat

株式会社ステーションネットワーク関西が運営しているATMである。 この会社は阪急電鉄と池田泉州銀行が共同で設立したものである。 筆者は詳しくないのだが、主に大阪、兵庫などの主要駅に設置されているようである。

ATM利用手数料

概要

ネット銀行以外の、自前でATMを用意している銀行については、一般に入出金共に手数料無料である。 まずはじめにネット銀行の各種のATM利用手数料について述べる。
TBD

ジャパンネット銀行

ジャパンネット銀行では、ゆうちょ銀行、セブン銀行のATMが利用可能である。入金・出金それぞれ月1回までは手数料無料である。 入出金共に、2回目以降は金額が3万円以上であれば手数料無料、3万円未満であればゆうちょ銀行の場合324円、セブン銀行であれば162円の手数料がかかる。

ソニー銀行

ソニー銀行では、三菱東京UFJ銀行、三井住友銀行、ゆうちょ銀行、セブン銀行、イオン銀行、イーネット、ローソンATMのATMが利用可能である。 これらのATMであればどれでも入金は無条件で手数料無料である。 セブン銀行、イオン銀行のATMでは出金も無制限で手数料無料であり、利用可能なそれ以外のATMでは、合計月4回まで出金手数料無料、5回目以降は108円の手数料がかかる。

楽天銀行

楽天銀行では、三菱東京UFJ銀行、みずほ銀行、ゆうちょ銀行、セブン銀行、イオン銀行、イーネット、ローソンATM、PatsatのATMが利用可能である。 これらのATMであればどれでも3万円以上の入金は手数料無料である。 それ以外の3万円未満の入金、金額を問わない出金は、毎月のランクに応じて決められる一定回数は無料、それを超えた利用では以下の通り手数料がかかる。 セブン銀行、イオン銀行、PatsatのATMでは216円、それ以外の利用可能なATMでは270円の手数料がかかる。 なお、VIEW ALTTEのATMでは入金はできないが出金のみ可能である。 手数料体系は後者と同一で、3万円以上の入金以外の利用には270円の手数料がかかる。

なお公式サイトには、毎月「ATM手数料無料回数」があると記載されており、これが3万円以上の入金を含むのかどうか明確な記述がないが、常識的に考えれば含まないだろう。

住信SBIネット銀行

住信SBIネット銀行では、ゆうちょ銀行、セブン銀行、イオン銀行、イーネット、ローソンATMのATMを利用可能である。 これらのATMであればどれでも入金は無条件で手数料無料、出金は毎月のランクに応じて一定回数無料である。 一定回数以降の出金には108円の手数料がかかる。 なお、VIEW ALTTEのATMでは入金はできないが出金のみ可能である。 手数料体系は他のATMと全く同一である。

TBD

追加する

で、結局？

ゆうちょATM・セブンATM 万能説
TBD: あとなんか書く

深まる謎

一部のファミリーマートではゆうちょATMが利用可能で、ほぼ24時間、ゆうちょキャッシュカードがあれば手数料無料で入出金ができるようである。これが意味するのが、"一部のファミリーマートにはゆうちょ銀行のATMと同等のものが設置されている"ということならば、ネット銀行のキャッシュカードがファミリーマートで利用可能である。果たして。
なおファミリーマートには通常イーネットATMが設置されているようである。

参考・出典

日本の銀行一覧 | Wikipedia

Patsat

提携ATM利用手数料 | ジャパンネット銀行

ATM利用手数料 | ソニー銀行

手数料一覧 | 楽天銀行

手数料無料で入出金する方法 | 楽天銀行

ATM | 住信SBIネット銀行

ATMでのお取引き(使えるATM) | セブン銀行

銀行ATMサービス | セブン銀行

Family MartでゆうちょATMが使えます！ | ゆうちょ銀行

GCJ 2017 ルールなど

GCJ (Google Code Jam) の登録が開始されました
自分用のメモです

公式サイト: https://code.google.com/codejam

スケジュール: https://code.google.com/codejam/schedule.html

規約とルール: https://code.google.com/codejam/terms.html

規約

不安な場合読んでおきましょう

ルール

問題を解いて、ソースコードと与えられる入力に対する出力を提出する
入力にはsmallとlargeの2種類があり、それぞれに別の配点がついている
smallの場合はデータセットをダウンロードしてから4分以内に提出する 間違えた場合は4分以内に再提出が可能で、4分が経過した後も別のデータセットをダウンロードして再チャレンジできる
largeの場合はデータセットをダウンロードしてから8分以内に提出する 8分以内なら再提出が可能だが、提出結果は競技時間中には分からず、また再チャレンジは不可能

(何か間違っていたら是非教えてください)

スケジュール

Registration

3/8(Wed) 04:00 - 4/9(Sun) 11:00 (日本時間、以下も基本的に全て日本時間)

Qualification Round

4/8(Sat) 08:00 - 4/9(Sun) 11:00 (27hr)

If you earn a minimum number of points during the qualification round, which will be displayed on the Contest website, you will advance to Round 1 of Code Jam.

コンテスト中に提示される点数を取ればOK

Round 1

  • Sub-Round A : 4/15(Sat) 10:00 - 12:30 (2hr 30min)
  • Sub-Round B : 4/23(Sun) 01:00 - 03:30 (2hr 30min)
  • Sub-Round C : 4/30(Sun) 18:00 - 20:30 (2hr 30min)

各サブラウンドで上位1000人ずつ Round 2 へ通過

Round 2

5/13(Sat) 23:00 - 25:30 (2hr 30min)

上位500人が Round 3 へ通過

Round 3

6/10(Sat) 23:00 - 25:30 (2hr 30min)

Onsite Finals

私にはあまり関係ない

日本語の情報

参考までに https://code.google.com/codejam/japan/rules.html

DCJ (Distributed Code Jam) について

If you advance to Round 2 of Code Jam, then you qualify to compete in the first round of Distributed Code Jam.

Round 2 の参加資格を得た場合、参加可能とのこと

よく分かってないんですが、分散処理するようなコードを書くらしいです
読んでおくと良さそうな記事 http://konjo-p.hatenablog.com/entry/2016/06/01/192236

AtCoder 連続ACチャレンジ 2017/3

競技プログラミング

AtCoderで1日1AC 2016/12/04スタート

AtCoderの問題の解法に関するネタバレを含みます。見たくない方はご注意ください。また、このページは得られた知見っぽいものを自分用にメモしておくものです。解法を知りたい場合は、まずAtCoderの大半の問題ページに掲載されている解説、あるいは解説放送を参照してください。

AtCoder Problems

3/01 (88th)

1

D: タコヤキオイシクナール - AtCoder Regular Contest 008

問題概要

一次関数が $N$ 個並んでいる。各関数は最初 $f(x) = x$ で初期化されている。関数のうちの一つを変更するクエリが $M $ 個与えられる。各クエリが順に実行されたとき、全ての関数を合成した関数に $1$ を入力したときの出力の最大値と最小値を出力せよ。

  • $1 \leqq N \leqq 10 ^{12}$
  • $0 \leqq M \leqq 10 ^5$

考察

分からなくてググったら、1次関数を複数回くっつけた合成関数は変わらず1次関数であることが分かった いや、なぜ気付かなかった(アホだから)(2次関数とかになると思い込んでた)
実装は、以下のリンクからパク 写経 参考にしました
データ構造と代数

記事中でも触れられているけど、こういう形でテンプレート化しておくと非常に再利用性が高く、競プロのライブラリとして最適であると感じる
RMQやRSQといった単純なモノイドは用意しておけばいいし、多少複雑なモノイドでもその単位元と演算のみに注目すればよいので、変なミスをしなくて済む

Segment Tree本体の操作については、図があって分かりやすいのでこちらも参照:
Efficient and easy segment trees

今回は $N$ が大きすぎるので座標圧縮を行う
クエリの先読みが出来ない場合(対話形式)は、動的構築というのを行うらしい(また別に用意する必要がありそう)

Segment Treeの練習をする:
http://hogloid.hatenablog.com/entry/20121227/1356608982

3/02 (89th)

1

C: データ構造 - AtCoder Regular Contest 033

問題概要

std::set に、小さい方から $X$ 番目の要素へのアクセスおよび削除を高速に行う処理を追加したデータ構造を実現せよ。クエリは $Q$ 個与えられる。

  • $1 \leqq Q \leqq 2 \times 10 ^5$
  • 要素 $N$ は、$1 \leqq N \leqq 2 \times 10 ^5$

方針

SegTreeかBIT+二分探索
計算量はおそらく $O \left( Q \left( \log N \right) ^2 \right)$

3/03 (90th)

1

D: ARCたんクッキー - AtCoder Regular Contest 017

問題概要

長さ $N$ の配列 $a_i$ が与えられる。区間に定数を足すクエリ、もしくは区間のGCDを求めるクエリの2種類のクエリが $M $ 個与えられるので、処理せよ。

  • $1 \leqq N \leqq 10 ^5$
  • $1 \leqq M \leqq 10 ^5$
  • 常に $1 \leqq a_i \leqq 10 ^9$

方針

これは結構悩んだ SegTreeっぽいのは分かるが、実装しようと考えるとうまく行かない
区間更新区間アクセスSegTreeでは、区間Addを行うとき、各セグメントのGCDが定数時間で更新できる必要があるが、それは(単純には)不可能である
結局、区間Addによって、配列の要素の差分は高々2要素しか変化しないことを考えて、単一更新区間GCD、区間Add単一アクセスの2種類のSegTreeを併用した
後者は実際の配列 $a_i$ を表し、前者はその差分 $a_{i+1} - a_i$ を表す
区間GCDクエリに対して、その区間に含まれる全ての差分のGCDと、区間に含まれるいずれかの要素とのGCDが求めるGCDであるので、十分高速に処理できる
一応注意点としては、差分は正とは限らず、かつ単位元は $0$ である上、コンパイラ組み込みの__gcd関数では非正整数を入力したときの動作がよく分からなかったので、モノイドの演算をちゃんと定義して使用した

区間更新 SegTree について

結論: 作用素モノイドと作用演算子の区別を意識する

以下のように考えると、(それが厳密に正しいかどうかはさておき)とりあえずコードを追えると思う

モノイドについてはまあいいとして、これを作用素モノイドと呼ぶことにする
次に作用演算子(と呼ぶことにするもの)を考える
その定義イメージは次の通り: 作用素モノイドの元 $m$ に対して、作用される集合の任意の元 $a$ があって、 $m(a)$ と表記できる作用が考えられるとき、この $m$ を作用演算子とする
今回の例では、二項演算が和であるモノイドに対し、そのモノイドの任意の元から生成される、作用される集合(整数)を引数とする作用Addを定義している (ただし、実装においては後者も二項演算の形になっている)
つまりモノイドの定義に演算が含まれ、演算が作用を規定するので、モノイドが作用を規定するとも言え、これを作用素モノイド、つまり作用のもととなるモノイドと呼ぶのも妥当である

前述の通り、実装においては作用も二項演算の形で表現しているため、遅延伝播を実現するdeferred_actionには、作用演算子そのものではなく、作用させるべきモノイドが置かれている

3/04 (91st)

RCO presents 日本橋ハーフマラソン 予選 オンタイム
マラソン形式は初挑戦だったかも

1

A: Multiple Pieces - RCO presents 日本橋ハーフマラソン 予選

問題概要

$0$ から $9$ までの整数が書かれた $H$ 行 $W$ 列のグリッドが与えられる。このグリッドからいくつかのオクトミノを切り出すことを考える。ただし、各オクトミノは重複してはいけない。各オクトミノはスコアを持ち、書かれた8つの整数の積がスコアである。全てのオクトミノのスコアの和が得点となる。

方針

まず9が書かれたマスを核として、隣接するマスのうち最大のものを結合させる。ピースどうしがマージされることもあるかもしれない。9のマスが完了したら次は8について、その次は7について……というように順次オクトミノを作っていく。大きい数字はなるべく大きい数字どうしで組み合わせた方が総得点が大きくなるだろうという推測に基づく。

なおオクトミノの全列挙が可能だったらしい

2

B: Food Collector - RCO presents 日本橋ハーフマラソン 予選

おみくじ をしました

反省

A問題の方針は開始30分で思いついたのだが、実装に異常に時間がかかってしまった
実行時間10秒をフルに使って山を登るようなことをしたことがないので、端的に言えば慣れが足りない

3/05 (92nd)

みんなのプロコン オンタイム

1

A : Yahoo - みんなのプロコン

2

B : オークション - みんなのプロコン

3

C : 検索 - みんなのプロコン

問題概要

$N$ 個の文字列 $S_i$ が与えられる。このうち $A_i$ ( $1 \leqq i \leqq K$ ) 番目の文字列のみがヒットするような検索ワードのうち、長さが最小のものを出力せよ。

  • $1 \leqq N \leqq 10 ^5$
  • $1 \leqq K \leqq N$

方針

まず文字列をソートして、ヒットさせたい文字列が連続しているかどうかを確認する
あとは何か細々としたサムシングを行う(がんばる)

3/06 (93rd)

1

D : 工場 - みんなのプロコン

問題概要

毎日 $K$ 個ずつ製品を生産する工場がある。 $D$ 日目に $A$ 個の注文が入るというクエリと、D日目までに合計で何個の製品を売ることができるかを出力させるクエリの2種類のクエリが $Q$ 個与えられるので処理せよ。ただし各注文に対しては、在庫の個数を超えない限り $0$ 以上 $A$ 以下の範囲で売る個数を自由に選択できる。

  • $1 \leqq Q \leqq 10 ^5$
  • $1 \leqq K \leqq 10 ^9$
  • $1 \leqq D \leqq 10 ^9$
  • $1 \leqq A \leqq 10 ^9$

方針

座標圧縮はいいとして、SegTreeに落とし込むためにどういうモノイドを定義するかというのが難しく、コンテスト中は着席してしまった
結局、<1つ前の日にち, 今の日にち, これまでに売った個数の合計, $A - {}$(今回の注文で売った個数), 今回の注文の処理後に残っている在庫の個数> の5つの変数をまとめたものをモノイドとした
今回のように、モノイドは数学的な定義に厳密に従ったものでなくても問題ない

3/07 (94th)

1

D: 旅行会社高橋君 - AtCoder Regular Contest 039

問題概要

$N$ 頂点 $M $ 辺からなる連結な単純無向グラフが与えられる。同じ辺を2度以上通らずに、頂点 $A, B, C$ をこの順で辿ることができるかどうかを判定させるクエリが $Q$ 個与えられるので処理せよ。

  • $3 \leqq N \leqq 10 ^5$
  • $1 \leqq M \leqq 2 \times 10 ^5$
  • $1 \leqq Q \leqq 10 ^5$

方針

まず橋を検出し、橋以外の辺によって接続されている頂点をUnion-Findでuniteする
こうすると橋によって接続される各領域を頂点とした木を形成できる
この各領域内部には橋が存在しないため、任意の3頂点(重複していてもよい)を同じ辺を2度通らずに任意の順番で辿ることができるのではないかと推測でき、これはおそらく正しい
あとは適当に高速な方法で $A, C$ の経路上に $B$ が存在するかどうかを確かめればよい

雑記

二重辺連結成分分解と呼ぶらしい
有向グラフだと強連結成分分解？

橋を列挙するにはlowlink以外にもimos法というのがあるらしい(解説スライド参照)

LCAを求める方法もいろいろあって、今回のはDoublingと呼ばれるものだが、Heavy-Light Decomposition してからLight edge を辿って求めるという方法もあるらしい(2chで見た)(理解はしてない)

3/08 (95th)

1

D: 経路 - AtCoder Beginner Contest 037

問題概要

$H \times W$ のマス目があり、各マスには整数が書かれている。スタートを自由に決め、上下左右に隣接しているマスのうち、今いるマスより大きい整数が書かれたマスに移動することを0回以上繰り返す。このときの経路の総数を出力せよ。

  • $1 \leqq H, W \leqq 1000$
  • マス目の整数の範囲は、 $1 \leqq a \leqq 10 ^9$

方針

簡単で、各マス目から辿ることのできる経路の数をメモ化再帰で計算し、全ての合計を出力すればよい

3/09 (96th)

1

D: 塗り絵 - AtCoder Beginner Contest 036

問題概要

$N$ 頂点の木がある。各頂点を白または黒で塗り分けるとき、塗り分けるパターンは何通りあるか出力せよ。ただし、隣り合う2頂点がいずれも黒く塗られることは許されない。

  • $2 \leqq N \leqq 10 ^5$

方針

簡単で、適当な頂点を根として根付き木にした後、葉からボトムアップに、各頂点が白または黒で塗られた場合、その頂点を根とする部分木の塗り分けが何通りあるか、というのを順次計算すればよい

3/10 (97th)

1

D: へんてこ辞書 - AtCoder Beginner Contest 030

問題概要

面倒なので略

方針

ステップ数が $N$ 以下であるような場合は普通にシミュレーションすれば十分で、$N$ よりも大きい場合は、シミュレーションを行う中で必ず同じ単語を2度調べることになる
これを適当な方法で検出し、あとはループになるので普通に余りを計算すればよい

3/11 (98th)

1

D: Big Bang - AtCoder Beginner Contest 022

問題概要

2次元座標平面上に、点が $N$ 個与えられる。これらの全ての点に対して、以下の操作を順に実行する。

  1. 同じ向きに同じ距離だけ平行移動させる
  2. 原点を中心に同じ角度だけ回転させる
  3. 原点を中心に $P$ 倍に拡大する

この結果の $N$ 個の点の座標が与えられるので、 $P$ を計算し出力せよ。

  • $1 \leqq N \leqq 10 ^5$
  • $1 \leqq P$

方針

仮に全点間距離を計算できれば、 $P$ はそれらの和の比である
一般的に言えば、ある点の集合、およびそれらの位置関係が部分的にでも特定できれば、 $P$ を計算するために必要な要素数は少なくなる
この要素数が少なくなるような、都合よく対応関係が分かるものというと、凸包、となる

雑記

これ、まあ典型なんでしょうけど、分かったときは感動しました
一見無理っぽいものが、凸包という考え方を知っているだけで解決できる、という

3/12 (99th)

AGC011 オンタイム

1

A: Airport Bus - AtCoder Grand Contest 011

頑張ってシミュレーションする

2

B: Colorful Creatures - AtCoder Grand Contest 011

累積和をとって上手いことやる

3/13 (100th)

1

D: Half Reflector - AtCoder Grand Contest 011

まあいろいろ実験してみて、挙動がなんとなく分かって、時間内に実装はできなかった
deque<int> に連続したセクションの情報を格納する手法にした
最終的にBABA…BABAみたいな形で固定される

3/14 (101st)

1

C: Squared Graph - AtCoder Grand Contest 011

問題の読み込み、言い換えができず解説放送を見て実装した
Union-Findと二部グラフ判定でOK

3/15 (102nd)

1

D: レースゲーム - AtCoder Regular Contest 001

解説スライドを見て、幾何に関する操作が分かっていれば解ける
本質的なところは凸包が高速に計算できるということと、この問題特有の部分で言えば交差したときの処理だと思う

知見:
変数の参照は便利！ ただしアドレスの再代入は不可能

3/16 (103rd)

1

D: 多重ループ - AtCoder Beginner Contest 021

コンビネーション

3/17 (104th)

1

D: 大ジャンプ - AtCoder Beginner Contest 011

問題概要

2次元座標平面の格子点上を原点から上下左右に移動することを $N$ 回繰り返したとき、座標 $(X, Y)$ にいる確率を出力せよ。

  • $1 \leqq N \leqq 1000$
  • $-10 ^9 \leqq X, Y \leqq 10 ^9$

方針

結局コンビネーションを計算することになって、オーバーフローまたはアンダーフローしないように適度な範囲になるように$4$を割ったり掛けたりして最終的に確率が求まるようにしたら通った
たぶん大丈夫だけど、TLEになる可能性も微妙にあるような気もする

3/18 (105th)

ARC070 オンタイム

rating 1901 -> 1976

1

C: Go Home - AtCoder Regular Contest 070

問題概要

$\frac{ \left( n - 1\right ) n } {2} \lt X \leqq \frac { n \left( n + 1 \right) } {2}$ を満たす整数 $n$ を出力せよ。

雑記

あ、ついこないだコドフォでやったやつだ！

2

D: No Need - AtCoder Regular Contest 070

問題概要

正整数が書かれた $N$ 枚のカードがある。カード $i$ に書いてある正整数を $a_i$ とする。カード $i$ について、このカードを要素に含むカードの集合のうち、合計が $K$ 以上 $K + a_i - 1$ 未満のものが存在するとき、またこのときのみ、カード $i$ は"必要である"とする。この条件を満たさない、すなわち"不必要な"カードの枚数を出力せよ。

  • $1 \leqq N \leqq 5000$
  • $1 \leqq K \leqq 5000$
  • $1 \leqq a_i \leqq 10 ^9 \left( 1 \leqq i \leqq N \right)$

方針

あるカード $i$ が不必要かどうか判定したいとき、そのカード以外のカードからなるの集合のうち、集合の和が $K$ 未満であるようなものを列挙すればよいので、 $O \left( N K \right)$ で可能である
$N$ 枚について判定するには愚直にやって $O \left( N ^2 K \right)$ となるので、間に合わない
ここで、カードがソート済であるものとして、カード $i$ が必要であるならば、カード $j \left( i \lt j \leqq N \right)$ も必要である、という性質から、二分探索によって $O \left( N K \log N \right)$ まで落とすことができ、次に述べる方法では $O \left( N K \right)$ まで落とすことができる:

大きいカードから順に見ていき、部分集合によって $0$ 以上 $K$ 未満の和を作ることができるかどうかを順次更新していく
あるカード $i$ について、それまでに $K - a_i$ 以上 $K$ 未満の和を作ることができていれば、そのカードは必要である
今までに作ることのできた和の最大値を持っておけば、この判定は $O \left( 1 \right)$ である
この操作を行うことにより、いくつかの必要なカードを検出することはできないかもしれないが、必要なカードのうち最も小さいものは必ず検出できるので、結局この問題を $O \left( N K \right)$ で解くことができた

3

D: NarrowRectangles - AtCoder Regular Contest 070

方針(部分点のみ)

DPをする
長方形の幅を $W$ とすると $O \left( N W ^2 \right)$

3/19 (106th)

1

A: 25個の文字列 - AtCoder Beginner Contest 025

3/20 (107th)

1

D: 覚醒ノ高橋君 - AtCoder Regular Contest 009

問題概要

$A$ 個のそれぞれ連結な重み付き無向グラフが与えられる。各グラフの頂点数は $2$ 以上 $7$ 以下である。全てのグラフから全域木になるまで辺を取り除く操作を行う。この操作において、取り除いた辺の重みの和をコストとする。考えられる操作のうち、 $k$ 番目に小さいコストを出力せよ。

  • $1 \leqq A \leqq 77$
  • $1 \leqq k \leqq 7,777,777$
  • 辺の重みは、 $1 \leqq cost \leqq 77$

考察

問題概要は簡略化して書いたが、問題を読んでもらえば分かる通り、まず一つのグラフをいくつかのグラフに分割し、各グラフについて全域木にするためのコストの一覧を計算しなくてはならない
一覧を計算し終えたら、DPで $k$ 番目に小さい和を計算するだけである
総パターン数は、最大で $7 ^5 = 16807$ の $77$ 乗もあるので、 $k$ より大きい適当な数で丸める必要がある
DPの計算量は、辺の重みを $c$ 分割後のグラフの頂点数を $M $ として、 $O \left( A \cdot c M A \cdot c M \right) = O \left( \left( A c M \right) ^2 \right)$ となり、厳しいのでは、と思いきや、C++は思っていたよりもかなり速かったようで、むしろunordered_mapを使うよりも速かった(ハッシュの衝突が発生していたと考えられる)

3/21 (108th)

1

D: サプリメント - AtCoder Beginner Contest 017

問題概要

略

方針

DPっぽいのでDPをする
ある日に $i$ 番目までのサプリメントを摂取し終わるとして、その最終日に摂取する最も番号の小さいサプリメントは何か、ということを考えれば、$i$ 番目までのサプリメントの摂取方法の数が分かる
これは累積和を取ることで $O \left( N \right)$ で計算できる
SegTreeを使えば $O \left( N \log N \right)$ となるが、累積和を取らなくてよいぶん楽になる

3/22 (109th)

1

D: マス目と整数 / Grid and Integers - CODE FESTIVAL 2016 qual A

問題概要

縦 $R$ 行、横 $C$ 列 のマス目があり、そのうち $N$ 箇所のマス目には非負整数が書かれており、具体的にはマス $\left( r_i, c_i \right)$ に $a_i$ が書かれている $\left( 1 \leq i \leq N \right)$ 。このとき、残りのマス目に非負整数を書き込むことによって、隣り合うマス目どうしの差分が全ての行において完全に等しくなるようにできるかどうかを判定せよ。

  • $2 \leq R, C \leq 10 ^5$
  • $1 \leq N \leq 10 ^5$
  • $\left( r_i, c_i \right)$ は全て相異なる。
  • $0 \leq a_i \leq 10 ^9$

方針

既に書かれている整数によって差が固定される列番号の集合をUnion-Findによって保持する
事前に各部分集合の差分の情報を示す連結なグラフを作成しておき、DFSを行い、初期状態で矛盾が生じていれば検出する
最後に、各部分集合について、全ての行における最も小さいマスについて、そのマスが埋まっていようがいまいが決定することができるので、負であれば検出する

3/23 (110th)

1

D: 高橋くんの苦悩 - AtCoder Beginner Contest 015

問題概要

$N$ 枚のスクリーンショットがあり、 $i$ 枚目のスクリーンショットは幅 $A_i$ と重要度 $B_i$ を持つ。これらのスクリーンショットを幅の合計 $W$ 以下かつ枚数 $K$ 以下の制限のもとで選択したときの重要度の合計を最大化したい。最大値を出力せよ。

  • $1 \leqq W \leqq 10000$
  • $1 \leqq N \leqq 50$
  • $1 \leqq K \leqq N$
  • $1 \leqq A_i \leqq 1000$
  • $1 \leqq B_i \leqq 100$

方針

DPをする
$O \left( W N ^2 \right)$

3/24 (111st)

1

D: バレンタインデー - AtCoder Beginner Contest 018

問題概要

略

方針

女子の選び方は高々 $_ {18} C _ 9 = 48620$ 通りで、各選び方について各男子の幸福度を計算し、大きいほうから $Q$ 人を選んだときの合計が、その女子の選び方における幸福度の最大値であるので、全ての選び方について計算すればよい

3/25 (112nd)

1

D: トランプ挿入ソート - AtCoder Beginner Contest 006

方針

要するにLIS(最長増加部分列)を求めればよい

雑記

LISの $O \left( N \log N \right)$ のアルゴリズム、賢すぎませんか

3/26 (113rd)

1

D: 禁止された数字 - AtCoder Beginner Contest 007

方針

余事象を考えて桁ごとに見ていく

雑記

std::string は存在しているだけで重い、それはそう

3/27 (114th)

1

3/28 (115th)

1

3/29 (116th)

1

3/30 (117th)

1

3/31 (118th)

1

AtCoder 連続ACチャレンジ 2017/2

競技プログラミング

AtCoderで1日1AC

メモ:2016/12/04スタート

AtCoder Problems

2/01 (60th)

1

D: バスと避けられない運命 - AtCoder Beginner Contest 012 | AtCoder

要するにWarshall-Floydで全頂点対最短経路を求めた後、各頂点から他の頂点への距離の最大値のうち最も小さいものを選べばよい
計算量 { O \left( N ^ 3 \right) }

2/02 (61st)

1

A: カードと兄妹 - AtCoder Regular Contest 038 | AtCoder

自明
計算量 { O \left( N \log N \right) }

2/03 (62nd)

1

B: P-CASカードと高橋君 - AtCoder Regular Contest 005 | AtCoder

適当にシミュレーションすればよい

2/04 (63rd)

AGC010 オンタイム
頭がいい人向けのセットだった

1

A: Addition - AtCoder Grand Contest 010 | AtCoder

簡単

2

B: Boxes - AtCoder Grand Contest 010 | AtCoder

必要条件をドカドカ追加していったら十分条件も満たしていたパターン
そのままでは考えづらいので、石を取り除くのではなく、逆の操作、すなわち1個も石が置かれていない状況から置いていくと考える
まず、数列の総和が1回の操作で追加される個数の倍数になっていない場合 NO
ここで、何回操作が実行されたかが分かる( { M } 回とする)
1回の操作で、 { i } 番目の箱と { i + 1 } 番目の箱の差は { 1 } だけ大きくなる──選択された箱が { i + 1 } 番目でない限りは.
つまり、1回も選ばれなかった箱( { k } 番目とする)には { k - 1 } 番目の箱よりも { M } 個多い石が入っている
そうでない場合、その箱は1回以上選択されたことになり、 { M } との差から、何回選択されたかも分かる
ここで差を { d } としたとき、 { M - d } が5の倍数でない場合 NO
選択された回数の合計が { M } でない場合 NO
以上の条件を全て満たせば YES
計算量 { O \left( N \right) }

2/05 (64th)

1

C: Cleaning - AtCoder Grand Contest 010 | AtCoder

なぜ時間内に通せなかったのか……死罪レベル、木に慣れてなさすぎる
まず次数が2以上の適当な頂点を根として根付き木を構成する
ある頂点を引数とし、その頂点から根へと向かう辺を通る回数を返す関数 { f } を考える
葉 { i } については明らかに { A_i } が戻り値である
葉でも根でもない頂点 { i } については、子を引数とした { f } の戻り値の集合と { A_i } によって戻り値を計算することができる
このとき、 { A_i } の値によっては答えが NO となる
根についても同様の判定を行う
計算量 { O \left( N \right) }

2/06 (65th)

1

D: Decrementing - AtCoder Grand Contest 010 | AtCoder

解説放送を見た
偶奇の性質に気付けるか、とかいう地頭の良さを問われるので本当にダメ
手番の管理

2/07 (66th)

1

B: アメーバ - AtCoder Regular Contest 041 | AtCoder

範囲外アクセスに注意しながら上から見ていけばいい

2/08 (67th)

1

B: メタ構文変数 - AtCoder Regular Contest 033 | AtCoder

特に難しくない
計算量 { O \left( \left( N_A + N_B \right) \log \left( N_A + N_B \right) \right) }

2/09 (68th)

1

C: 01文字列 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦 | AtCoder

0と1が切り替わるところ(先頭と末尾を含む、 { N } 個とする)を起点として、 { N } パターンのコストを比較すればよい
計算量 { O \left( T \right) }

2/10 (69th)

1

D: 偶数メートル - AtCoder Regular Contest 036 | AtCoder

(editorialを見るとものすごく実装が軽い方法が書いてある)
偶数メートルで行き来できる街の集合をUnion-Findで管理する
各集合に、奇数辺が含まれるかどうか(つまり2部グラフでないかどうか)の情報を持たせておく(HasOddとする)
以下のフローチャートを上から辿る

  1. x, yの間に偶数辺が追加される場合
    1. 既に同じグループのとき、変化なし(終了)
    2. x, yの間が奇数辺で接続されているとき、x, yをUniteし、HasOddをTrueにする(終了)
    3. x, yのいずれかのHasOddがTrueのとき
      1. x, yのいずれにも奇数辺で接続された集合が無いとき、Uniteし、Unite後の集合のHasOddをTrueにする(終了)
      2. x, yのいずれかに奇数辺で接続された集合が有るとき、その集合も含めてUniteし、Unite後の集合のHasOddをTrueにする(終了)
    4. x, yのいずれかに奇数辺で接続された集合が有るとき
      1. x, yのいずれにも奇数辺で接続された集合が有るとき、適切にUniteし、Unite後の2つの集合を奇数辺で接続する(終了)
      2. x, yのいずれか片方にのみ奇数辺で接続された集合が有るとき、適切にUniteし、Unite後の2つの集合を奇数辺で接続する(終了)
    5. x, yのいずれにも奇数辺で接続された集合が無いとき、普通にUniteする(終了)
  2. x, yの間に奇数辺が追加される場合
    1. 既に同じグループのとき
      1. 奇数辺で接続された集合が有る場合、その集合をUniteする
      2. 集合のHasOddをTrueにする(終了)
    2. x, yの間が奇数辺で接続されているとき、変化なし(終了)
    3. x, yのいずれかのHasOddがTrueのとき
      1. x, yのいずれにも奇数辺で接続された集合が無いとき、Uniteし、Unite後の集合のHasOddをTrueにする(終了)
      2. x, yのいずれかに奇数辺で接続された集合が有るとき、その集合も含めてUniteし、Unite後の集合のHasOddをTrueにする(終了)
    4. x, yのいずれかに奇数辺で接続された集合が有るとき
      1. x, yのいずれにも奇数辺で接続された集合が有るとき、適切にUniteし、Unite後の2つの集合を奇数辺で接続する(終了)
      2. x, yのいずれか片方にのみ奇数辺で接続された集合が有るとき、適切にUniteし、Unite後の2つの集合を奇数辺で接続する(終了)
    5. x, yのいずれにも奇数辺で接続された集合が無いとき、普通にx, yを奇数辺で接続する(終了)

2/11 (70th)

ABC054 オンタイム

1

A: One Card Poker - AtCoder Beginner Contest 054 | AtCoder

.

2

B: Template Matching - AtCoder Beginner Contest 054 | AtCoder

4重ループでOK
KMP法とやらで { O \left( N ^ 3 \right) }
FFTで { O \left( N ^ 2 \log N \right) }
らしい(解説放送より)

3

C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder

next_permutation関数を使ってみたかったので使ってみた

4

D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder

40という数字を見て反射的に半分全列挙を実装したが実は初めてだった
あとDPらしい
半分全列挙: { O \left( 2 ^ \frac{N}{2} N + N ^ 2 Max \left( a_i \right) Max \left( b_i \right) \cdot Max\left( a_i, b_i \right) N / Max \left( M_a, M_b \right) \right) }
DPはやってないので解説放送のメモ
簡単なほうのDP: { O \left( N ^ 3 Max \left( a_i \right) Max \left( b_i \right) \right) }
難しいほうのDP: { O \left( N ^ 2 Max \left( a_i + b_i \right) \right) }

2/12 (71st)

1

C: ウサギとカメ - AtCoder Regular Contest 025 | AtCoder

叙述トリック: 「カメがウサギより速いことはないだろう」という無意識な思い込みにより時間を溶かした
Dijkstra法 + 尺取法でOK (尺取しなかったけど)
{ O \left( N M \log N \right) } (想定解っぽいけど結構ギリギリ)

2/13 (72nd)

1

E: Rearranging - AtCoder Grand Contest 010 | AtCoder

※まず解説放送を見る

  1. 入力をsortする
    • 以降の処理はここで確定させたインデックスで行う
  2. gcdが1でない組に辺を張る
    • 辺は隣接リストで管理し、各リストはsortしておく
      • これにより、一貫して昇順で各要素を扱うことができる
  3. 各連結成分について、木を構築する
    • 逐次、最小のノードを辿っていくDFS
    • このとき、各連結成分のうち最小の要素を根として関数を呼ぶ必要があるが、前述のsort済みのデータ構造により、訪問済みでないものを前から順に見ていけばOK
      • 後述の理由のため、根としたものは set<int, greater<int> > に保存しておく
    • 同じ連結成分の要素は、上手い順序で並べることによってそれより辞書順で小さくすることができないような状態にすることができる、ということが重要
  4. 木から最終的な配列を構築する
    • 各ノードについて再帰的に子ノードを引数として関数を呼び、各配列をマージした配列を返すのだが、この配列は以下の要件を満たすもののうち辞書順最大のものでなければならない:
      • 0番目は呼ばれたノードである
      • 各配列の相対的な順序は不変である
  5. 答えを出力する
    • 異なる連結成分どうしは自由にswapできるので、各連結成分に対応する配列を根の要素について降順に出力すればよい

{ O \left( N ^ 2 \right) } だと思うけどpush_back多用してたり再帰してたりするせいか遅い

知見:
この問題のような出力形式はほんの少しだけ面倒だが、行末にスペースが付いていても別に問題ない

2/14 (73rd)

1

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder

※まずeditorialを見る

ビットDPをする
うさぎの部分集合があって、これに属する各うさぎがこの部分集合の中で最下位であるときの場合の数をメモ化再帰で求める
{ O \left( 2 ^ N N \right) }

2/15 (74th)

1

D: 道路の老朽化対策について - AtCoder Beginner Contest 040 | AtCoder

※まず解説動画とeditorialを見る

Union-Findを使えないか考えて上手くやって使う
(およそ) { O \left( \left( M + Q \right) \alpha \left( N \right) \right) }

2/16 (75th)

1

D: 三角形の分類 - AtCoder Beginner Contest 033 | AtCoder

※まずeditorialを見る

固定した点からの偏角を列挙するとき、前後1周分、合計 { 6 \pi } の大きさの区間が必要 (前後0.5周、合計 { 4 \pi } で十分かと思うがバグ取りできなかった)
誤差吸収は必要
上記の提出は高速化のための再提出5回目のもので、二分探索→尺取法のオーダー改善(全体では定数倍改善に留まる)はいいとして、 push_backの順番を変えて3周分の偏角のsortを削除したらかなり速くなった:
前 L.65〜69 → 後 L.65~73
今回のように、sortが支配的になってしまうような場合は考える価値がある
コード量の割にメモリを使っていないらしいのでまだまだ高速化できそう
{ O \left( N ^ 2 \log N \right) }

2/17 (76th)

1

D: 破れた宿題 - AtCoder Regular Contest 007 | AtCoder

分からなかったし解説が無かったのでググった 頭がいい人向け
初項が即決定でき、あとは意外と多い場合分けを淡々と書いていくと通せる
こういう数値と文字列の相互変換が多かったり、数値の桁数が不明な問題はPython使うのが手っ取り早いと思う
25行目、これでOKなのは、初項が2桁以上であるならば、必ず10の倍数であるという事実による
(主にPythonを使ったために)計算量はよく分からないが { O \left( N \right) } か { O \left( N ^ 2 \right) }

2/18 (77th)

ARC069 オンタイム
競プロ引退

1

C: Scc Puzzle - AtCoder Regular Contest 069 | AtCoder

Sをなるべく多く使う

2

D: Menagerie - AtCoder Regular Contest 069 | AtCoder

4通り試す

2/19 (78th)

1

E: Frequency - AtCoder Regular Contest 069 | AtCoder

前から狭義単調増加な部分だけ拾ってリストアップしておく
次に後ろから見ていってリストのどこに属すべきか計算する
{ O \left( N \log N \right) }

2/20 (79th)

1

A: 掛け算の最大値 - AtCoder Beginner Contest 026 | AtCoder

Go言語の練習

2/21 (80th)

1

B: N重丸 - AtCoder Beginner Contest 026 | AtCoder

Go言語の練習

Divide by Zero 2017 and Codeforces Round #399 (Div. 1 + Div. 2, combined)

4問提出 ゼ ロ 点

rating
1603 -> 1461 (-142) (Became Specialist)

A

Problem - A - Codeforces

慢心した コーナーケース考えてなかった

B

Problem - B - Codeforces

慢心した コーナーケース考えてなかった

C

Problem - C - Codeforces

80分くらい着席してたと思う
適当に書いて出したらpretestは通った(今回pretestガバガバだったらしい)
周期を持つっぽいが計算量とか正当性とか本当にこれでいいのか分からんし未だ解けた気がしない

D

Problem - D - Codeforces

よく考えると簡単なDPなのでわ？w っつって意気揚々と出したのだが問題文の謎の { \epsilon } に惑わされた

2/22 (81st)

1

D: あまり - AtCoder Regular Contest 042 | AtCoder

愚直な計算を実行するならば、計算量は { O \left( \log A + \left( B - A \right) \right) } となる
また { X = 1 } または { A = 0 } または { P - 1 \leq B - A + 1 } の場合も自明
よって { X \geq 2 } かつ { A \geq 1 } かつ { \left( B - A \right) \gg 10 ^ 8 } かつ { P > 2 \times \left( B - A \right) } のとき、ある種の工夫が必要となる
解を { P } と { B - A } の比から推定し(解説スライド)、推定した解が { B - A } の区間を平方分割した区間のいずれかに属しているかどうかを、 推定した解に { X ^ {-1} \pmod P } を { \sqrt { B - A } } 回掛けることで判定する
このときの計算量は推定する解の個数を { M } として、 { O \left( \sqrt { B - A } _ { \left( 1 \right) } \log \sqrt { B - A } _ { \left( 1 \right) } + M \sqrt { B - A } _ { \left( 2 \right) } \log \sqrt { B - A } _ { \left( 1 \right) } \right) }
ただし、(1)が付されているのは区間の個数、(2)が付されているのは区間の幅である
第1項は区間の区切れ目を計算しsortする時間、第2項は実際にその近傍の区間に推定した解が存在するかどうかを確認する時間であり、 他に { X ^ {-1} \pmod P } などを前もって計算しておく必要がある
しかし今回、テストケースが弱すぎるのでこのようなアルゴリズムは必要なかった

2/23 (82nd)

1

B: バウムテスト - AtCoder Regular Contest 037 | AtCoder

頂点の集合をUnion-Findで管理しておいて、各連結成分に存在する辺の個数を適当な方法で数えればOK

ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)

4完 / 7問

rating
1461 -> 1615 (+154) (Became Expert)

Publish Rating Change - Codeforces

A

Problem - A - Codeforces
Submission #24919305 - Codeforces

シミュレーション

B

Problem - B - Codeforces
Submission #24923123 - Codeforces

素数を1で塗って合成数を2で塗る
コーナーケースに気をつける

C

Problem - C - Codeforces
Submission #24940185 - Codeforces

{ k } の累乗を絶対値 { 10 ^ {14} } 程度まで計算しておき、与えられた { a _ i } の累積和を計算しておく
あとは後ろから、順次累積和をキーとする要素をmapに追加していき、区間の始まりを固定し、 検索すべき累乗から固定された区間の始まりに対応する累積和(offset)を足した値をキーとしてmapで検索し、個数を数える(分かりづらい)
{ O \left( n \log \left( Max \left( a _ i \right) n \right) \right) } (検索がlogオーダーの場合)

知見:
mapでOKだったものをunordered_mapにすると衝突して遅くなる場合がある(まあそれはそう)

D

Problem - D - Codeforces
Submission #24934995 - Codeforces

各スイッチを頂点とし、いずれかの照明に共有されているスイッチ同士を辺で接続したグラフを構成した
初めに照明がONである場合はグラフの重みは1、そうでなければ0として、 スイッチが押されるか否かで分類される2部グラフであるかの判定をDFSで行った
(AtCoderの偶数メートルを思い出した)
これは充足可能性問題の特殊なケースである2-SATと呼ばれる問題で、蟻本にも載っているらしい
参考:
充足可能性問題 - Wikipedia
2-SATと強連結成分分解 - naoya_t@hatenablog

(ライブラリを書く) (蟻本をやる)

2/24 (83rd)

1

C: 飛行機乗り - AtCoder Beginner Contest 030 | AtCoder

普通にシミュレーションすればOK
{ O \left( N \log N + M \log M \right) }
尺取すれば{ O \left( N + M \right) }

2/25 (84th)

Mujin Programming Challenge 2017 オンタイム

1

A: Robot Racing - Mujin Programming Challenge 2017 | AtCoder

よく考えると簡単な問題で、前から順に"詰まっている"ところを見ていけばOK
具体的には、奇数番目に必ずロボットが存在しているように、基本は一つ空けで左詰めする処理をしてから、偶数番目に存在しているところを見ていく
{ O \left( N \right) }

2

B: Row to Column - Mujin Programming Challenge 2017 | AtCoder

個人的にAより簡単な問題で、普通に盤面を埋めようと考えれば自然に解ける
ただしちょっと注意が必要なケースがあって、盤面に一つも黒が存在しないケースと、目的の列に初めに一つも黒が存在しないケースは考慮する
シミュレーションしても時間的に余裕だったがたぶん必要ない
{ O \left( N ^ 2 \right) }

2/26 (85th)

Codeforces Round #402 (Div. 2)

4完 / 6問 今回は惜しかった……

rating
1615 -> 1644 (+29) (Became Expert)

A

Problem - A - Codeforces
Submission #25033372 - Codeforces

やるだけ

B

Problem - B - Codeforces
Submission #25034720 - Codeforces

英語をよく読む(必ず解が存在するって書いてある)

C

Problem - C - Codeforces
Submission #25036357 - Codeforces

全て後で買うと仮定して、最低でも { k } 個は今買わなければいけないので差額をsortして、k個は必ず今買い、または差額が負であればk個を超えても今買う

D

Problem - D - Codeforces
Submission #25049077 - Codeforces

クッソくだらないミスで落とした
二分探索
{ O \left( | t | \log | t | \right) }

E

Problem - E - Codeforces
Submission #25046561 - Codeforces

実装ゲー
アルゴリズムとしては1ビットずつ見ていけばいいだけ 特に落とし穴もない
(だいたい) { O \left( nm \right) }

1

A: A - AtCoder Beginner Contest 013 | AtCoder

気付いたら23:59だったので

2/27 (86th)

1

C: 高速フーリエ変換 - AtCoder Typical Contest 001 | AtCoder

正直まだよく分からない 特に逆変換
まず複素数が絡む時点でやばい、あとすごい誤差が大きくなって最終的に小数点以下を四捨五入した
計算量はたぶん { O \left( N \log N \right) }

2/28 (87th)

1

B: 名前の確認 - AtCoder Beginner Contest 011 | AtCoder

Go言語の練習