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

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

Electrum-XVG で not connected となる件

目的

公式サイトからダウンロードできる Verge OSX Electrum Wallet でサーバに接続できない問題を解決する

環境など

筆者はMac版ですがElectrum系ならWindowsでもLinuxでもだいたい同じだと思います。実際、下で紹介するYouTube動画ではWindows版を使用しています。

Solution

YouTubeに的確で分かりやすい動画がアップロードされています: Fix Verge Electrum Wallet Network Issue

概要

デフォルトサーバが追加されましたが、バージョン2.4では適用されていません。 ファイルは編集可能なので自分で追記します。

/Applications/Electrum-XVG.app/Contents/Resources/lib/python2.7/lib/network.py

DEFAULT_SERVERS = {
    'electrum-verge.xyz':{'t':'50001', 's':'50002'},
    'electrum-xvg.stream':{'t':'50001', 's':'50002'},
    'electrum-xvg.party':{'t':'50001', 's':'50002'},
    'e1.verge-electrum.com':{'t':'50001', 's':'50002'},
    'e2.verge-electrum.com':{'t':'50001', 's':'50002'},
    'e3.verge-electrum.com':{'t':'50001', 's':'50002'}
}

これでネットワークに接続できるようになります。 要するに最初からあったelectrum-verge.xyzが使用不可となった、ということなんでしょうね。

YouTubeにはTor版を使えば解決したという動画も上がっていますが、これはTor版のデフォルトサーバは通常版とは別のものだからでしょう。試してないので確証はありませんが。

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による記述であるようです。

これのコンパイルにはctanglecweaveというコマンドが必要なようです。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言語の練習

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

明けましておめでとうございます!

競プロ力を高めるために毎日最低1問AC(7777) 今年もやっていきます

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

AtCoder Problems

1/01 (29th)

1

B: 鏡餅 - New Year Contest 2015 | AtCoder

まあ、新年ということでね(というのは半分嘘で、取り組んでいた問題が解けなかったので逃げた)
(貪欲に)条件を満たしつつ軽い方から取っていけばOK(なぜなら、この方法で完成する鏡餅の任意の段をより重いものに交換するのはナンセンスだから)

1/02 (30th)

1

B: 駐車場 - AtCoder Regular Contest 056 | AtCoder

ほぼ丸1日溶かしてなお解けなかった/editorialを見た
コストを今までに通った頂点の番号の最小値としたdijkstra法でOK(見ている頂点のうちコストが大きいものから確定させていく)
分かるとかなり単純で、実装も楽、割と鬱になった

1/03 (31st)

1

C: 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi ) - AtCoder Regular Contest 004 | AtCoder

ちょっと考えると数学的には簡単で、与えられた分数を { z } とすると、元の正しい平均値 { m } は0.5の整数倍であり、かつ { ( z , z+1 \rbrack } の範囲内に存在する必要がある
さらに、" { \left( m - z \right) \times N } が整数である"という条件を加えれば十分である
あとは実装をどうするかという話になり、いい機会なので有理数の加減算を行える構造体を実装してみた
ただし、今回は範囲もほぼ分かっているインスタンスの引き算のみが必要であったため、オーバーフローについてあまり考慮しておらず、また掛け算と割り算は実装していない

1/04 (32nd)

1

B: ニコニコレベル - 第3回 ドワンゴからの挑戦状 予選 | AtCoder

え、難しくないですかこれ?
同じコンテストのC問題(これ12/18に解いた)の方が明らかに簡単じゃないですか? (ここでプロにとってはどちらも違わないということに気付き死ぬ)
基本的なアイディアは、25が入り得る位置を、別々に長さn = s.lengthboolの配列で持っておいて、偶奇の組み合わせを考えて有り得るニコニコレベルを { \displaystyle O \left( n \right) } で計算するというもの
反省点: 2の位置の偶奇で場合分けして同じコードをコピペして繰り返したので見るに堪えないコードになってしまった(競プロではACこそが正義なので別にいいけど)

1/05 (33rd)

1

C: 積み重ね - AtCoder Regular Contest 006 | AtCoder

貪欲な感じでOK:
山の保存形式は、(結果的に常に昇順にソート済みとなる)intの配列で、一番上のダンボールの重さを置いておく(それ以外の情報は不要なので)
新しいダンボールに対して、既にある山のいずれにも乗せられない場合は新しい山とし(push_back)、乗せられる場合は乗せられるもののうち最も軽いものの上に乗せる(update)
したがってlower_boundだけ見ればよく、非常に簡潔なコードとなる

1/06 (34th)

1

B: 高橋ノルム君 - AtCoder Regular Contest 049 | AtCoder

“頻出手法"であるところの二分探索問題
高橋ノルム君が集まる最適な一点を求めるのは困難だが、ある時間 { T } が与えられたときに、時間 { T } 以内に全ての高橋ノルム君が集まることのできる領域が存在するかどうかの判定は { O(N) } で可能である
解の最大値は大体 { 10^{8} } 程度で、{ 10^{-4} } までの精度で求めればよく、全体で { O( 40 N ) } なので、この問題が解けた(提出したコードでは何故か解の最大値が { 2 \times 10^{12} } と設定されている)
躓いた点
1. 二分探索のhlの更新操作を逆にしていた
2. 整数部が8桁ぐらいだと小数点以下は6〜7桁程度の精度なので、適切に終了条件を設定しないと無限ループになる可能性がある(というかサンプルケース4つ目で実際になった)

メモ

LaTeXが用意されていたらしいので導入した
参考:
はてなブログの LaTeX 数式表示がデフォルトで MathJax 化された - 余白の書きなぐり
【健忘録】はてなブログでのLaTeX構文 - もう一人のY君

書式: [tex:{ \displaystyle(適宜付ける) hoge }]

Codeforces Round #390 (Div. 2)


1問しかできなかった
しかもミスってて1回Hackされたんで得点低い

Submission #23599266 - Codeforces

rating
1702 -> 1593

1/07 (35th)

ABC051 オンタイム
全完できたけど70分近くかかったのでパフォーマンスは良くないです……

1

A: Haiku - AtCoder Beginner Contest 051 | AtCoder

解説放送で文字置換とかsplitからのjoinとか色々紹介されてた

2

B: Sum of Three Integers - AtCoder Beginner Contest 051 | AtCoder

{ O ( K ^ 2 ) } でいいものを、まだまだ競プロ慣れが足らないからかおかしな書き方をした

3

C: Back and Forth - AtCoder Beginner Contest 051 | AtCoder

注意力が散漫すぎて1WAした
s, tにそれぞれ隣接する4マス*4マスのいずれの組み合わせのManhattan距離の和も等しい(※例外あり)のであとは交わらないようにするだけ

4

D: Candidates of No Shortest Paths - AtCoder Beginner Contest 051 | AtCoder

重み付き無向連結グラフにおけるいずれの2点間最短経路にも含まれない辺の個数を答える問題
競プロ慣れが足らず、Dijkstra法(しかも隣接行列を使う方)で使った辺を全ての辺の集合から引いていくのを { N } 回繰り返すとかいう面倒な方法をとった(set.insertを使ったのでたぶん { O ( N ^ 3 \log N ) } )
ちょっと考えれば、2点間の最短経路長が分かっていれば、その2点間を直接結ぶ辺が使われるかどうか分かるので、Warshall-Floydからの全辺チェックで { O ( N ^ 3 + M ) } というのが分かりやすい実装になる↓

1/08 (36th)

1

C: 偶然ジェネレータ - AtCoder Regular Contest 036 | AtCoder

dp[i][j][l] : i番目までの文字列 (1-indexed) において、i個のsuffixの (‘0'の個数) - ('1’ の個数) のうちの 最小値 + i が j で、最大値 + i が l であるようなパターンの数を持つ配列
負のインデックスは取れないのでiを足している
本当は300とか適当な数を足したかったのだが、MLEになったので仕方なく書き換えた(今気づいたけど、i+1番目のdpはi番目のdpのみによって決定できるから、そこを2つだけ持つようにすれば余裕でMLE回避できたのでは…… → 通りました: <> たぶんtmpの初期化とかdpへのコピーが遅くて遅くなってる(ホント?w))

1/09 (37th)

1

C: 億マス計算 - AtCoder Regular Contest 037 | AtCoder

(最大で)9億マス計算に出てくる全ての数のうち { K } 番目に小さいものを求める問題
まず与えられるaとbはそれぞれsortする
仮に9億マスの数字が全て求まっているとして、ある数 { m } が何番目かを調べることを考える(二分探索)
{ N } 要素の配列について、lower_boundupper_bound を取って、 { N } 個の配列についてそれぞれ足し合わせた和を出すことができる: { O ( N \log N ) }
それぞれの和 lbub が異なれば、それは { m } がいずれかのマスに出現することを意味し、さらに { lb \lt K \land K \leqq ub } であれば { m } が解である
{ K \leqq lb } であれば解は { m } より小さく、 { ub \lt K } であれば解は { m } より大きい
全体で { O ( N \log N \cdot \log ( Max (a_i) \cdot Max (b_i) ) ) } で解が求まるので、この問題が解ける
ただし実際には9億マスの計算結果を保持するとなると確実にMLEになるし、二分探索の一回一回で必要になる度に計算してるとTLEになる(と思う)ので、sort済みのaとbから上手く lbub を求める必要がある

1/10 (38th)

1

C: 積み上げパズル - AtCoder Regular Contest 010 | AtCoder

ブロックの色を適当な方法でint(0以上 { m } 未満)に変換し、次のDPを行う
dp[i][j][k] : i番目までのブロック (1-indexed) において、 各色が既に使われたかどうかのビット配列の値 が j で、 山の一番上にあるブロックの色 が k であるような積み上げ方の得点の最大値を要素に持つ配列
ただしこれだとMLEになるので、i+1番目のdpはi番目のdpのみに依存することを考え、temporaryな配列を使って同じ配列を使い回すようにする(一昨日のと同じ)
(普通(?)のDPだと配列の要素は何らかのパターン数であることが多い気がするので、個人的には)今回のDPは少し変則的で、初期化は INT_MIN などが適切である(要素が INT_MIN ならばそのパターンは存在しない)
最初の状態は、 dp[0][m] = 0 とする(色番号mはNULLみたいなイメージ)
遷移は、i番目のブロックを使わない場合と使う場合について、後者は { Y }{ Z } を適切に足してやるようにして更新していく(Maxを取っていけばよい)

1/11 (39th)

1

C: 幼稚園児高橋君 - AtCoder Regular Contest 039 | AtCoder

0番は無視します
1番は普通の map を使ったものです 1000ms超えますがこの問題の制限時間はやや緩めに設定されていることから想定解なんじゃないかなと思います
2番はそれ以降アクセスされることのない map の要素を削除するようにしたものです メモリ使用量は減っていますが実行時間は増えたり減ったりという感じです
3番と4番は unordered_map を使ったものです キーが vector<int> なのでHash関数オブジェクトを用意する必要があるらしいです こちらのサイトから拝借しました
3番は1番と同じで、削除をしない実装です 1番より速くなりました(遅くなったケースもある)
4番は2番と同じで、削除をする実装です メモリ使用量が(予想通り)減り、実行がかなり速くなりました
Hash関数を理解していないしそもそもコピペなのでなんとも言えないのですがある程度の有益情報が得られました

1/12 (40th)

1

B: 最短路問題 - AtCoder Regular Contest 044 | AtCoder

サンプルケースに答えが全て書いてある(775) と思ったが距離のminとMaxの間に存在しない距離がある場合もあって、でもそれは普通に実装すれば結局0になるはずなので大丈夫
……しかしこれは罠で、0の0乗が1になるようにしていたりすると0にならない可能性がある(やっぱり怖いし考えるのも面倒なので弾いちゃうのが楽)
関係ないんですが昔(約14か月前)に書いたコードがmain関数のわずか4行目(入力即sort)でWA確定しているということに気づけたので成長だと思います(伸びしろがいっぱいある!)

2 (再)

C: N!÷K番目の単語 - AtCoder Regular Contest 047 | AtCoder

数学

(1/30追記) 色々あって今こういう日付なのでまた今度書きます
以下からは記憶が薄い状態で書いた文章です

1/13 (41st)

1

C: ビーム - AtCoder Regular Contest 044 | AtCoder

(たしか)分からなかったのでeditorialを見た
この問題ではx軸とy軸は独立なので別々に考えると、1次元を考えればよくなる
x軸を考えるとして、ある時刻で高橋君が各列に存在するための移動回数の最小値を持っておく(その時刻にビームが飛んでくる場合はINFとかにしておく)
次の時刻への遷移は、INFではない場所はそのまま、INFのところは、左右の直近のINFではない列(最大2つ)の要素+距離に更新すればOK
後者で、INFではない列が存在しない場合は、高橋君は必ずビームに当たってしまうので-1を出力して終了する
問題はINFではない列を探すパートで、上のSubmissionではINFではない行/列の管理を vectorerase したり insert したりして実現していたので、 おそらく計算量だけ考えれば嘘解法で(1492msとか違法っぽい)、これを set で書き直したのがこちら↓
<>
計算量は幅もしくは高さを { N } として、 { O ( max ( T, Q N ) ) } から { O ( max ( T, Q \log N ) ) } に改善されている(たぶん)

知見:
1. vector_object.erase(v_iterator) を行うと、 v_iterator は削除された要素の次の要素を指すようになり、以降も普通にアクセス、演算が可能である
2. set_object.erase(s_iterator) を行うと、 s_iterator は削除された要素を指したまま変わらず、(おそらく) set から排除されていて、普通にアクセスしたり演算したりするのは不可能である (例えば簡単な実験で、 set<int>erase 実行後、単項インクリメントすると3つ後の要素を指した)
3. erase したり insert したりするときはなるべく set を使う
4. set はメモリを食う? (まあ木らしいしそうなんですかね(適当))

1/14 (42nd)

1

C: アットコーダー王国の交通事情 - AtCoder Regular Contest 035 | AtCoder

連結な重み付き無向グラフの全ての相異なる2頂点間の最短距離の和( { S } )を、辺の追加クエリごとに出力する問題
まずWarshall-Floyd法で全頂点間最短距離を求め、 { S } を計算する
クエリごとに、新しい辺が結ぶ2頂点間の距離よりも新しい辺の距離の方が小さければ更新し、 { S } についても以下のように更新する
1. 辺が結ぶ2頂点について、小さくなった差だけ { S } から引く
2. その他の任意の2頂点についても、新しい辺を使うことで最短距離を更新できるなら同様に { S } も更新する
以上で、計算量 { O ( N^{3} + K N^{2} ) } でこの問題が解けた

1/15 (43rd)

1

C: タコヤ木 - AtCoder Regular Contest 023 | AtCoder

コンビネーション関数 { { }_n C_k } を書いて、消えている部分の有り得るパターン数を計算して掛けていけば終わり
コンビネーション関数の計算量は { O ( k + \log mod ) } で、全体では最悪のケースで { O ( N \log mod ) } (0-indexedで { A_i } の3の倍数番目のみが欠損しておらず他が欠損しているようなケース)(たぶん)

1/16 (44th)

1

B: 同一円周上 - AtCoder Regular Contest 047 | AtCoder

実装がクソ面倒だった
各点について { ( x+y ) }{ ( x-y ) } を計算して保存しておいて、解が一意に定まる場合はまあ別によくて、 定まらない場合は適当に制約を加えて適当に解を求める(あんまりよく憶えてない)
計算量は今確認してみたら { O ( N ) }

1/17 (45th)

1

B: アリの高橋くん - AtCoder Regular Contest 042 | AtCoder

2次元平面上に1つの点と複数の線分が与えられ、点から各線分までの最短距離の最小値を求める問題
点から線分に下ろした垂線の足が線分上にあるかどうかの判定に余弦定理を使った

1/18 (46th)

1

C: AtColor - AtCoder Beginner Contest 014 | AtCoder

“一般にいもす法と呼ばれる累積和の応用テクを用いる” (AtCoder公式解説より引用)
競プロでよく見るのは1次元0次(合ってます?)のいもす法ですが、なんか配列の次元と関数の次数を一般化するといろいろできるらしいです
参考: https://imoz.jp/algorithms/imos_method.html

1/19 (47th)

1

C: 123引き算 - AtCoder Beginner Contest 011 | AtCoder

適当にシミュレーションで解けばOK
コード量を減らす(最低限の)努力はした(はず、たしか)

1/20 (48th)

1

C: 九九足し算 - AtCoder Beginner Contest 012 | AtCoder

{ ( 2025 - N ) } を1から9までで割って商が1から9、余りが0になったものだけ出力する

1/21 (49th)

1

B: あの日したしりとりの結果を僕達はまだ知らない。 - AtCoder Regular Contest 014 | AtCoder

普通にシミュレーションをする
ターンの管理、面倒なもの

1/22 (50th)

AGC009 オンタイム
Japan Russia Exchange Programming Contest 2017 と同じ問題とのこと
日露学生プログラミングコンテストについて:
https://atcoder.jp/post/67
http://jrex2017.contest.atcoder.jp/

1

A: Multiple Array - AtCoder Grand Contest 009 | AtCoder

後ろの方の要素を変更するには後ろの方のボタンを押さなければならないので、後ろから考えていく
計算量 { O ( N ) }

2

B: Tournament - AtCoder Grand Contest 009 | AtCoder

ある人をインデックスとして、勝利した相手の一覧を作成する
(例えば、入力例1なら { 1 → {2, 3}, 2 → {4}, 3 → {}, 4 → {5}, 5 → {} }となる)
ここで1回も勝利していない人の深さは、0であるとする(入力例1なら3, 5の人)
1回以上勝利している人の深さは、勝利した相手の深さをsortして大きい順に並べ、1, 2, 3, … をそれぞれ足したうちの最大値であるとする
このように定義した関数を書いて、1の人について(再帰的に)計算する
計算量 { O ( N \log N ) } (sortしてるので)

Codeforces Round #393 (Div. 2) (8VC Venture Cup 2017 - Final Round Div. 2 Edition)

6問中4問通せた

rating
1572 -> 1688 (+116) (Became Expert)

Publish Rating Change - Codeforces

A

Problem - A - Codeforces
Submission #24036364 - Codeforces

面倒、と言うほかない

B

Problem - B - Codeforces
Submission #24042128 - Codeforces

なんか小人?が { n } 人いて、そのうち { k } 番目の小人が得られる枕の個数の最大値を出力する
ただし、枕は { m } 個あって、小人1人につき1つは与える必要があり、隣り合う小人が得る枕の個数の差の絶対値は1以下でなければならない
解の二分探索を行う
{ k } 番目に頂点(高さ { mid } )が来る山を作ったときの枕の総数が { m } 以下であれば可能、というように判定
計算量 { O ( \log m ) }

C

Problem - C - Codeforces
Submission #24044183 - Codeforces

要するに、与えられる配列 { p } が1から { n } を循環するようにして、 { b } の総和が奇数になるようにすればよい
後者は簡単で、前者はUnion-Findを用いた(分断されたグループの個数だけ適切に要素を変更すれば全てを循環するようにできる)
計算量 { O ( n \alpha ( n ) ) } ( { \alpha } はアッカーマンの逆さんが考案したアッカーマンの逆関数)

D

Problem - D - Codeforces
Submission #24050796 - Codeforces

問題文を理解するのに10分くらいかかった(つらい、慣れが要る)
ごく基本的なDPで、 { i } 回目のtripの分までの合計の料金を3通り計算して、 3通りのうち最小値のみを残せばよい(Submitしたコードでは3通りとも保存している)
料金の計算に upper_bound を使うので、全体の計算量は { O ( n \log n ) }
DPのDAGっぽさを実感できる教育的な問題だと思う

1/23 (51st)

1

B: 花束 - AtCoder Regular Contest 050 | AtCoder

花束1と花束2の個数を軸とした2次元平面上での線形計画法で解こうとして、適当にコードにした結果、 どうやっても 08.txt だけがWAのままACできず、(多倍長整数をサポートする)Rubyで同じコードを書いてもWAのままだった
editorialには解の二分探索による解法が書かれており、こちらで実装したコードはACできた
友人に相談したところ、
double の精度が足りていないのでは?”
との提案を頂いたので、なるほどと思いデバッグし、解決を見た

知見: 128ビット整数とかいう裏技的なサムシングを使った
たぶんgccやclangにはデフォルトで実装されていて、ただし入出力等は実装されていないっぽいので以下の記事などをありがたくコピペして使おう
C++ (gcc) で 128 ビット整数を使う - 宇宙ツイッタラーXの憂鬱

参考: 存在が見られるらしい
C/C++における整数型の昇格 - Qiita

1/24 (52nd)

1

B: ドキドキデート大作戦高橋君 - AtCoder Regular Contest 045 | AtCoder

全体を覆うM個の区間が与えられて、取り除いても全体が覆われている状態を保つような区間を出力する問題
まず、いもす法で各インデックスが含まれる区間の個数を計算する
次に、1つの区間にしか含まれていないインデックスを区切りとし、 各インデックスを先頭とした区間で、取り除いてもOKなもののうち、末尾のインデックスの最大値を計算する
後は与えられた各区間について、取り除いてもOKかどうかを見ればいい
計算量は { O ( N + M ) }

1/25 (53rd)

1

B: 高橋幼稚園 - AtCoder Regular Contest 039 | AtCoder

if文を1個書いてコンビネーションを書くだけ

1/26 (54th)

1

A: A - B problem - AtCoder Regular Contest 039 | AtCoder

あり得る6パターンの変更を書くだけ

1/27 (55th)

1

C: Factors of Factorial - AtCoder Beginner Contest 052 | AtCoder

書こう書こうと思っていた素因数分解ライブラリをとうとう書いた
素数列挙はエラトステネスの篩で、 { N } 以下の素数を列挙する場合 { O \left( N \log \log N \right) } らしく、 AtCoderのコードテストで試したところ、 { N = 10^{7} } で300ms、メモリ使用量40MB程度だった
正直実行時間とかメモリ使用量とかは全然改善の余地があるだろうけどとりあえず書きましたよ、ということで
素因数分解の計算量は、素因数が全て列挙済みの場合は { O \left( A \left( N \right) \right) } ( { A } は素因数の個数) であり、 { \sqrt N } を超える素因数を持つ場合は { O \left( \pi \left( \sqrt N \right) \right) } である(よく分かってない)
問題のほうは、素因数分解さえできれば楽勝

1/28 (56th)

1

C: 約数かつ倍数 - AtCoder Regular Contest 034 | AtCoder

これも素因数分解さえできれば楽勝
計算量 { O \left( \left( A - B \right) \pi \left( \sqrt N \right) \right) }

1/29 (57th)

1

C: 変わった単位 - AtCoder Regular Contest 015 | AtCoder

とりあえずグラフの形式にする
辺を有向にして適切な係数を設定する
整数だけで解決したかったのだがどうやってもオーバーフローするのでdoubleで解くことにしたら誤差が出てWAを連発してしまった
適当に誤差吸収っぽいことをしたら通ってしまって、イマイチ解けた気がしない
頂点数がそんなに多くないので多倍長整数有理数クラスを持つRubyとかでやるといいんじゃないでしょうか
計算量 { O \left( N \right) }

1/30 (58th)

1

D: Walk and Teleport - AtCoder Beginner Contest 052 | AtCoder

ABCとはいえD問題にしては易しめな問題
普通に西から東へ順に訪れていけばよい
計算量 { O \left( N \right) }

1/31 (59th)

1

B: 格子グラフ - NJPC2017 | AtCoder

各辺に適切なIDを与えてsetか何かに入れていけばOK
計算量 { O \left( N \right) }