AtCoder 連続ACチャレンジ 2017/1 - 鬱！鬱すぎてうつほ物語になった！w

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

1/04 (32nd)

1

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

え、難しくないですかこれ？
同じコンテストのC問題(これ、12/18に解いた)の方が明らかに簡単じゃないですか？ (ここでプロにとってはどちらも違わないということに気付き死ぬ)
基本的なアイディアは、2と5が入り得る位置を、別々に長さn = s.lengthのboolの配列で持っておいて、偶奇の組み合わせを考えて有り得るニコニコレベルを $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. 二分探索のhとlの更新操作を逆にしていた
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_bound と upper_bound を取って、 ${ N }$ 個の配列についてそれぞれ足し合わせた和を出すことができる: ${ O ( N \log N ) }$
それぞれの和 lb と ub が異なれば、それは ${ 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から上手く lb と ub を求める必要がある

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ではない行/列の管理を vector に erase したり 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) }$