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

テクニカル、これを呼吸できればプロっぽくなれる
実装はそこまで大変ではない
尺取法で、現在の区間に含まれる各ブロックの味の番号をインデックス、それぞれの味の位置を要素とした配列を持っておき、長さのmaxを更新していく
それぞれの味のブロックは最大で1つまでしか含まれてはいけないので、含まれる場合は位置[0, N)を、含まれない場合は負の値などを置いておけばよい

7

C: ロミオとジュリエット - AtCoder Regular Contest 022 | AtCoder

木の直径を求める問題
よく使われる有名な方法でAC通したけど余裕のあるときに木DPしてみたい

12/03

(再) 1

C: 高橋君とカード / Tak and Cards - AtCoder Regular Contest 060 | AtCoder
C: 高橋君とカード / Tak and Cards - AtCoder Beginner Contest 044 | AtCoder

教育的なDP問題
計算量はO(N³×max(x))

12/04 (1st)

1

C: Gr-idian MST - CODE FESTIVAL 2016 qual B | AtCoder

クラスカル法(のちょっと応用)
クラスカル法さえ知っていれば解ける

2

C: Boxes and Candies - AtCoder Regular Contest 064 | AtCoder

端から貪欲に見ていけばよい
コード汚くなった、と思ったが割とシンプルだった

12/05 (2nd)

1

A: AtCoder *** Contest - AtCoder Beginner Contest 048 | AtCoder

string 3つ終わり

2

B: Between a and b ... - AtCoder Beginner Contest 048 | AtCoder

剰余に関する問題
WAやらかしたし実装も微妙に煩雑になってしまうし何かいい方法があれば……

3

D: An Ordinary Game - AtCoder Regular Contest 064 | AtCoder

地頭の良さが問われるタイプの問題
無理だった(editorial見た)
こういう｢中間の状態や遷移に関わらず最終的にはこうなる｣みたいな考え方に慣れよう

12/06 (3rd)

1

E: Cosmic Rays - AtCoder Regular Contest 064 | AtCoder

コストが実数の2頂点対最短路問題
priority_queueを使うダイクストラ法で実装していて、そのコードはAOJのGRLでAC通せたものだったけどこっちで全然ACできなくて、実数の誤差とか、ある2つのバリアの中心同士を結ぶ線分が他のバリアと干渉するかもしれない、けどそれは大丈夫っぽいとか色々考えて、最終的にintのオーバーフローが原因というギャグだった(死にたくなった)
辺が密なのでオリジナルのダイクストラ法の方がlogVがないぶん速いっぽい
ループ回数10⁹のワーシャル-フロイド法でも間に合った

AOJ > GRL
1a ダイクストラ法

12/07 (4th)

1

C: 列 - AtCoder Beginner Contest 032 | AtCoder

基本は尺取法でOKだが、制約をよく見ていろんなケースを考えて場合分けしないといけない
サンプルケースが親切でよかった

2

B: 解像度が低い。 - AtCoder Regular Contest 017 | AtCoder

端から順に狭義単調増加な部分を検出してansに足していけばいい

AOJ > GRL
1b ベルマン-フォード法
2a クラスカル法

12/08 (5th)

1

C: 無駄なものが嫌いな人 - AtCoder Regular Contest 017 | AtCoder

最初変なことしようとしてできなくてeditorialを見たら半分全列挙と書いてあったので実装した
たしか蟻本のチュートリアル的なセクションにも同じようなのがあった気がするけど、あれは4分割してたから配列にして4回ループにしないとさすがにやばそう(うろ覚え) 全然違った
ビット演算による全列挙、もうちょっと見た目のいい実装できるだろうか

12/09 (6th)

1

B: こだわりの名前 - AtCoder Regular Contest 019 | AtCoder

小文字アルファベット(26種)からなる文字列が与えられて、そのうち1文字を別の小文字アルファベットに変更したとき、全体が回文にならないような変更のしかたが何通りあるか出力する
やるだけだけど場合分けと算数が難しい

12/10 (7th)

1

A: うるう年 - AtCoder Regular Contest 002 | AtCoder

うるう年かどうか判定する
SECCON CTFでやばかったので消費した

12/11 (8th)

1

A: GPA計算 - AtCoder Regular Contest 003 | AtCoder

成績が与えられるのでGPAの平均を出力する
SECCON CTFからの課題提出でやばかったので消費した

12/12 (9th)

1

A: 大好き高橋君 - AtCoder Regular Contest 005 | AtCoder

arc005_3を解いていたが日付が変わりそうになったので消費した

12/13 (10th)

1

C: 器物損壊！高橋君 - AtCoder Regular Contest 005 | AtCoder

上下左右に移動できるスタートとゴールと通路と壁がある2次元平面が与えられて、壁を2回まで破壊することでスタートからゴールまで行けるかどうか判定するという問題
高さと幅は500以下で、普通にDFSすればいい……のだが、
再帰関数を書いて実行すると(おそらく stack overflow で) Runtime Error を吐かれ、いろいろ枝刈りしたりしたけど1個だけREが取れなかったので、再帰を使わずqueue (Last In, First Out)を使うようにしたら1発でACできた
今回割と簡潔に(？)書けたのでなるべくqueueを使って書こうという気持ちになった
でもたぶん面倒な問題は再帰で書いてもある程度面倒だろうから腹を括らなければならない

1段階ずつ連結成分に接する壁を破壊することを2回繰り返した後スタートからゴールまでコスト0で行けるかどうか見る方法だと47msで、直接コスト2以下で行けるかどうかを見る方法だと410msだった(別々のテストケースだが)

最大で499 * 500 * 2 * 2 ≒ 10⁶本の有向辺を全列挙してpriority_queueを使ったdijkstra法で138msで思ったより早かった(たぶんElogV ≒ ~~10⁸~~10⁷くらいなので)

(12/24 修正)

12/14 (11th)

1

D: Teleporter - AtCoder Grand Contest 004 | AtCoder

9日にやろうとしていた問題、約10個のテストケースでTLEが取れず死んでいた
木の高さがK+1以下になるように繋ぎ替えよという問題で、回数を最小にするには高さがKになっているところ(ただし根、つまり首都の直下を除く)の直上で切ることを貪欲に繰り返せばよい
editorial見て考え方自体は合っていることを確認したがどうしようもなくなったのでプロ達のコードを見てはぇ〜ってなったのを思い出しながら書いた
でもなんかやはりというかk==1のときだけ場合分けすることになってなんだかアレ
この問題に限らず我流に拘っちゃうの悪い癖なんだけど抜けない性分

12/15 (12th)

1

B: さかさま辞書 - AtCoder Regular Contest 003 | AtCoder

stringをreverseしてvectorをsortしてstringをreverseするだけ

12/16 (13th)

1

C: 擬二等辺三角形 - 天下一プログラマーコンテスト2015予選B | AtCoder

さんすう難しいよお

真面目にメモすると、

(x, x+1, x+2)の組を数える
(y, x, x+1)の組を数える(ただし y >= 2, y <= x-2)
- yの上限を決定するのがxである場合(y <= x-2)
- yの上限を決定するのが周長Lである場合(y <= L - (2*x + 1))
(x, x+1, y)の組を数える(ただし y >= x+3)
- yの上限を決定するのが三角形の構成要件である場合(y <= 2*x)
- yの上限を決定するのが周長Lである場合(y <= L - (2*x + 1))

という感じ

12/17 (14th)

1

C: AND Grid - AtCoder Grand Contest 004 | AtCoder

答えを、見ました
必要なもの: 地頭の良さ、柔軟さ、発想力、自由な思考、数学的センス、数学的素養、などのうちいずれか1点

12/18 (15th)

1

C: スキーリフトの相乗り - 第3回ドワンゴからの挑戦状予選 | AtCoder

やるだけ

2

C: Lining Up - AtCoder Regular Contest 066 | AtCoder

書くだけ

12/19 (16th)

1

D: Xor Sum - AtCoder Regular Contest 066 | AtCoder

時間中には解けなかった問題で、全体でも約35人しか解けていなかった
解説を読んでもよく分からず、解説放送でrngさんが説明していた(これはアルゴリズムは理解できた)通りに実装するとACとなったが、計算量が間に合っているのか確信を持てない
よく考えると確かにO((logN)^2)となっているような気もする
実装は再帰+メモ化

12/20 (17th)

1

A: eject - CODE FESTIVAL 2014 Hard | AtCoder

連立漸化式 (Wolfram|Alpha大先生に解いてもらった(クズ))

RSolve[{a[i+1]==(1-p)*a[i]+p*b[i], b[i+1]==p*a[i]+(1-p)*b[i], a[0]==0, b[0]==1}, {a[i], b[i]}, i]

1回WAになったがテストケース名が優しさにあふれていてp==0とp==1のとき例外処理することでAC
今回初めてスマホでC++(というかC)書いた(なおGoogle Keepで一部のインデント支援のみ)

12/21 (18th)

1

A: 来月は何月？ - AtCoder Beginner Contest 011 | AtCoder

呼吸問題
課題でやばかったので

12/22 (19th)

1

C: 魂の還る場所 - AtCoder Regular Contest 014 | AtCoder

ハッタリ
なんで N ≦ 50 やねん

12/23 (20th)

1

D: ほんとうのたたかい - AtCoder Regular Contest 019 | AtCoder

みんなだいすき素数！を使ってなんか上手い感じにやったらモダンアートができた

ところで、これが初めてのARC-D問題のACでした

f:id:celtek:20161223015242p:plain

12/24 (21st)

1

D: アルファベット探し - AtCoder Regular Contest 006 | AtCoder

ARC-Dを解こうシリーズ第2弾
H*Wの盤面上の連結成分(と呼ぶことにする)を調べる問題
A B Cそれぞれのマス目の個数で区別するようにした
実装としては普通だと思うけどどうなんでしょう、解説が無いので分かりませんちなみに初めてtupleとかいうのを使ってみた

12/25 (22nd)

AGC008 オンタイム

1

A: Simple Calculator - AtCoder Grand Contest 008 | AtCoder

頭が回ってなかったので1WAした
絶対値を考えてやればいいのだがx==0またはy==0のときちょっと厄介

2

B: Contiguous Repainting - AtCoder Grand Contest 008 | AtCoder

最終的に、連続するK個のマスのうち、少なくとも1箇所が必ず全てのマスで同じ色となり、その1箇所を自由に選んだ上で、その他のマスの色も自由に選べる、ということは分かる
それが十分条件でもあるか？というと、頭が回ってなかったのでコンテスト中は確信を持てなかったのだが冷静に考えるとまあたぶんそうでしょう
与えられた数列と、与えられた数列の各要素と0とのmaxを取った別の配列(altered)のK個のスライド？の和？みたいなのと、alteredの全要素の和をそれぞれO(N)で予め計算しておいて、i番目から始まる連続するK個を同じ色にしたときの最大のスコア(O(1))の 0≦i≦N-K での最大値(O(N))が答え (全体の計算量O(N))

3

C: Tetromino Tiling - AtCoder Grand Contest 008 | AtCoder

テトリスを2×(2×K)マスに制限したとき、この長方形を全て埋めるには、T型とS型(Z型)のテトロミノは使えない
なのでO型、I型、L型(J型)だけを考えれば楽勝……と思いきや頭が回ってなかったので1WA
LIJの組み合わせを使うか否かで考えてmaxを取るようにした(2つ以上組む意味はないので0もしくは1)

得られた知見:
AtCoder Problemsがちゃんと更新されれば事後的に連続AC日数も復旧する

Codeforces Round #389 (Div. 2, Rated, Based on Technocup 2017 - Elimination Round 3)

初めて参加した
全6問あって4問通せた

A

Problem - 752A - Codeforces
Submission #23288841 - Codeforces

呼吸問題

B

Problem - 752B - Codeforces
Submission #23304721 - Codeforces

swapしている文字の組をmap<char, char>で持つようにして、文字の不一致を検出するごとに、すでに別の文字とマッチングされていないかをチェック&mapに追加
というようにしてSubmitしたらpretestは通ったがHackされた(Hackerの存在、普通にありがたい)(ていうかpretestで落としてくれ…(しかしHackerのためにpretestは緩く設定されている))
実は2周(便宜的にこう呼ぶ)する必要があって、1周目では一致する文字もset<char>などにリストアップするようにして、2周目で不一致を検出したら一致した文字リストに含まれていないかどうかをチェックする、などとしなければならない
2周目で一致を検出して不一致リストに含まれていないかをチェック、でもよい(というかその方がコードが短いはず)

C

Problem - 752C - Codeforces
Submission #23293931 - Codeforces

R / L と U / D の状態を適当に持っておいてカウント

D

Problem - 752D - Codeforces
Submission #23303139 - Codeforces

1回pretestでWAをもらった
まず、与えられた小さい文字列がそれ自体が回文でないstring(a)と回文であるstring(b)に分けて、各stringでbeautyの降順にソートする
(a)の処理は楽で、ペアのbeautyの和が正のものを上から取っていく
(b)も基本は同じだが、取った文字列のbeautyの最小値(x)と、取らなかった文字列のbeautyの最大値(y)を保存しておく(この(b)の処理が不十分でWAだったっぽい)
最後に、max(0, max((-x), y))を足せば答え

得られた知見:
C++の reverse(begin(string), end(string)) は、(sortと同じで) string 等の配列っぽいオブジェクトを(破壊的に)逆順にするvoidを返す関数で、stringを返すわけではない(あたりまえ)

rating
(1500 -> ) 1654

Publish Rating Change - Codeforces

12/26 (23rd)

1

D: K-th K - AtCoder Grand Contest 008 | AtCoder

コンテスト中に通せなかった問題
最後に出力する配列を普通に1次元で持っていたら実装がキモくなって、あと解の存在条件の判定もしづらくなってしまった
解説動画では、各行に(最終的な)解の配列における数字1〜Nの位置がそれぞれ昇順で保持されているようなN×Nの2次元配列を持つようにしていて、この方が格段に見通しが良い
AC通せたけどやっぱりコードがややキモくなってしまった(vector.eraseの多用とか)のでなんとかしたい…(しかし実装が重くなってもミスなくガッと書けるというのは重要だろうし、うーん)

12/27 (24th)

1

C: THE☆たこ焼き祭り2012 - AtCoder Regular Contest 008 | AtCoder

見た目がゴツイ問題
単一始点最短路問題についてよく考えてみると、一般の有向グラフにおいて、始点からの全ての頂点への最短路のパスの合併は、木になっているんじゃないかという気がしてくる

ある始点から全ての頂点へのある最短路を考えると、有向木の構造を成し、最短路木と呼ばれる。
また、ある始点から全ての頂点への全ての最短路も、重みが正の場合にはDAGによって表現することができる。

最短路問題 - yukicoder

つまり、合併が木になるような最短路の集合を構成することができるようである
だとすれば、最短路のコストが大きい順に目的地を決めて投げていけば、1秒に1個しか投げられないという条件は"あなた"のみについて考えればよい、と分かる
あとは単純に隣接行列を計算しておけばダイクストラ法によって解ける
maxとminを間違えないように気をつけよう！

12/28 (25th)

1

E: Cookies - CODE FESTIVAL 2016 Final (Parallel) | AtCoder

※editorialを見た
クッキーを食べる回数を決め打ちするというアプローチ……分からなかった
回数は最大でも40回(logN)で、各フェーズでクッキーを焼く秒数sの最大値と、sを1だけ減らすフェーズの数を求める計算量はべき乗を含めるとO((logN)²×loglogN)
sを求めるのを、誤差が出る可能性もあったが標準のpow関数を使ったので計算量はO((logN)²×loglogN)

コミケ

参加のため、3問ストックを用意しました
あとは24時間の範囲内でSubmitするだけです~~(もはや本末転倒)~~

12/29 (26th)

1

B: 割り切れる日付 - AtCoder Regular Contest 002 | AtCoder

ARC002-Aが｢うるう年｣で、これを関数化してやって組み込む
遅くても次の年の1月1日までには割り切れる日付がやって来るので愚直にループを回す

TopCoder Single Round Match 704 Div.1

1問解けた

Level One

https://community.topcoder.com/stat?c=problem_statement&pm=14468

まず、構成する木の直径は自明なので、有り得るeccentricityの最小値が分かる
構成不可能な条件を満たすケース(各eccentricityの頂点の個数)を弾いていって、あとは適当にやればよい
最初、頂点の順番が指定されていることを忘れてコードを書いていたのだが、これが吉と出たようで、問題を単純化するのは重要であることが分かった(それはそう)

https://community.topcoder.com/stat?c=coder_room_stats&rd=16849&rm=329506&cr=40447295

コーディングに58分もかかったので得点は 119.98/300 でした
ひとまず6割取るのを目指します

Rating: (1492 → ) 1290 → 1327

12/30 (27th)

1

D: grepマスター - AtCoder Regular Contest 014 | AtCoder

ARC-D~~の簡単なのを見つけよう~~を解こうシリーズ第3弾
クエリの個数は10⁵なので1クエリあたりO(1)かO(logN)(N ≦ 10⁵) くらいで処理しなければならない
ヒットした行を区切りとして全体を(N+1)個の区間に分ける
すると、各行から上下にx, yずつ伸びるときに、各行と隣り合う区間のみを考えればよいことが分かる
つまり、各区間の表示される行数は、max(各区間の行数, x+y)である
したがって、各区間の行数を要素とする配列を予めソートしたものと、その配列の累積和の配列を持っておけば、各クエリに対して、完全に埋まる区間の行数の和と、完全に埋まる区間とそうでない区間の境目の2つがO(logN)で計算できるので、あとは左端と右端を別個で考えればこの問題が解ける

Codeforces Good Bye 2016

8問中3問しか通せなかった

A

Problem - A - Codeforces
Submission #23423415 - Codeforces

nが10以下なので愚直に引けばよい
より効率的にやるなら平方根とか考えればいい気がする

B

Problem - B - Codeforces
Submission #23428746 - Codeforces

単純なシミュレーション
ちゃんと漏れなく条件を書き連ねればOK

C

Problem - C - Codeforces
Submission #23434951 - Codeforces

まず、指定がDiv.1のみであればInfinity
(0など)適当な初期値を仮定して、Div.2であると指定されている全ての時点でratingが1899以下であるような最大のオフセットを足す
つまり、Div.2の時点のratingの最大値が1899であるような初期値を計算する
その後、Div.1である全ての時点でratingが1900以上であるかを確認する(1899以下の時点が存在すればImpossible)