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

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

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に解いた)の方が明らかに簡単じゃないですか？ (ここでプロにとってはどちらも違わないということに気付き死ぬ)
基本的なアイディアは、2と5が入り得る位置を、別々に長さn = s.lengthのboolの配列で持っておいて、偶奇の組み合わせを考えて有り得るニコニコレベルを { \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. 二分探索の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) }

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) }

AtCoder 連続ACチャレンジ 2016/12

競技プログラミング

競プロ力を高めるために毎日最低1問AC(7777)
2016/12/04スタート(突発)

AtCoder Problems

12/01

1

A: グラフ / Graph - CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel) | AtCoder

CF2016のあさプロ
クラスカル法を知らなかった
知っても、満点解法では任意の2点間を結ぶパスについて、そのパスに含まれる辺のコストの最大値を保存しておかなければならなくて、Union-Findに↓こういう機能を足す必要があった

Union Findで集合の要素をたどる -

違うやり方はあるのでしょうか？ (反語ではなく疑問)
ACできた後、プリム法でAC通そうとずっと唸ってたけど同じ方法では原理的に無理だという結論に至った(丸1日溶かした)

12/02

(1〜4はCF2016のチームリレー)

1

D: 魔方陣2 / Magic Square 2 - CODE FESTIVAL 2016 Relay (Parallel) | AtCoder

ちょっと紙で算数してみるだけ

2

A: 合成抵抗 / Equivalent Resistance - CODE FESTIVAL 2016 Relay (Parallel) | AtCoder

さすがに呼吸

3

J: 連結チェスボード / Connected Checkerboard - CODE FESTIVAL 2016 Relay (Parallel) | AtCoder

本番ではチームの人が相談しながら通してた
いざ考えてみると分からないのでeditorial見ました 賢くなろう
ヒント: 重複がないように気をつける

4

H: 早起き / Early Bird - CODE FESTIVAL 2016 Relay (Parallel) | AtCoder

尺取り法というものらしい
端のところだけ気をつければいける
今思いついたけど配列を2倍にして同じデータを繰り返すようにすれば端の処理(余りを取る)要らなかったのでは……(なんかchokudaiさんがFinalの解説で似たようなこと言ってた気が)

5

A: スーパーICT高校生 - AtCoder Regular Contest 022 | AtCoder

割と面倒だった
もう少し綺麗な実装できるだろうか(正規表現？)

6

B: 細長いお菓子 - AtCoder Regular Contest 022 | AtCoder

テクニカル、これを呼吸できればプロっぽくなれる
実装はそこまで大変ではない
尺取法で、現在の区間に含まれる各ブロックの味の番号をインデックス、それぞれの味の位置を要素とした配列を持っておき、長さの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(N3×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がないぶん速いっぽい
ループ回数109のワーシャル-フロイド法でも間に合った

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 ≒ 106本の有向辺を全列挙してpriority_queueを使ったdijkstra法で138msで思ったより早かった(たぶんElogV ≒ 108107くらいなので)

(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)2×loglogN)
sを求めるのを、誤差が出る可能性もあったが標準のpow関数を使ったので計算量はO((logN)2×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弾
クエリの個数は105なので1クエリあたりO(1)かO(logN)(N ≦ 105) くらいで処理しなければならない
ヒットした行を区切りとして全体を(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)

解けなかった、D

縦横の範囲を絞って計算量を減らそうとした方針はよかったらしい が、2時間溶かしても通せなかった
愚直にシミュレーションはまず無理、初めの1手で半分削っても駄目、となると全体にわたって折り返しコピーみたいなのをする必要があって……実装できなくね？ (<-ここで終了)

rating
1654 -> 1702

Publish Rating Change - Codeforces

12/31 (28th)

1

C: 節約生活 - AtCoder Regular Contest 007 | AtCoder

boolの配列にしてN通りに回転(と呼ぶことにする)させた配列を作ってその中から1個以上選ぶのを全通り試す
少ない方から試して全ての時間がtrueとなる時点で終了とするとやや早いが面倒なので全通り試す

競プロ初心者のためのCODE FESTIVALの楽しみ方

競技プログラミング

この記事は、 eeic Advent Calendar 2016 その2 の5日目の記事として書かれたものです。

f:id:celtek:20161201011036p:plain:w500

競プロ初心者が運良く CODE FESTIVAL 2016 の予選を通過し、11/26-11/27の本戦に参加してきた日記です。予選を通過する方法と本戦の楽しみ方を紹介します。Advent Calendarに書くものとしてふさわしいのか疑問ですが、大目に見てください。
注意点:
1点目: この記事では言語仕様の話やアルゴリズムの話はしません。分からないので。
2点目: プロの皆さんは温かい目で見てください。
3点目: 記事が結構長いです。コンテンツの量が多かったので。
4点目: CODE FESTIVALというのが正しい表記です。間違っても"CodeFestival"などと書かないように注意してください。よろしくお願いします。

CODE FESTIVAL とは

CODE FESTIVAL とは、RECRUIT / Indeedが主催するプログラミングコンテスト(プロコン)のイベントです。プロコンと言うだけではかなり幅広い意味ですが、ここでは特に競技プログラミング(競プロ)のコンテストのことを指します。競プロとは一言で言えば、指定されたフォーマットの入力に対して条件を満たす出力を返すプログラムを早く正確に完成させるゲームです。(ここまでテンプレ)
システムはAtCoderのオンラインジャッジを使用しています。AtCoderとはプロコンを定期的に開催したり、今回のように他の会社にシステムを貸し出したりしている会社です。ちなみにこの社長が本戦会場で問題の解説をしてくれたりライトニングトークをしたりしていて生で見られました。
参加資格は、日本在住の｢学生（高専4~5年生、高専専攻科、専門、短大、大学、大学院）または既卒4年以内の未就業者｣、参加人数は合計220人となっています。ただし今年から海外在住の学生も20人まで参加できるようになり、国際コンテストとなりました。なぜ20人に制限されているかというと、そうしないと参加者が海外の方ばかりになってしまうからです。
参加資格をよく見てみると、社会人はもちろん、高校生以下のつよい人々(西日暮里の有名な高校とか神戸の難しいところとかに多い)も本戦に参加できないことが分かります。つまりチャンスということです。私が競プロを始めたのがちょうど1年前で、その間ブランクも多かったことを考えると、興味のある方は今からでも始めると来年のコドフェスに参加できます。
まとめると、(他のコンテストと比較して)日本の大学生が参加しやすいオンサイトのプロコンです。こういうイベントは他にないと思うので、興味があれば是非。

予選

リクルートのウェブサイトで申し込みをしたら、予選コンテストを通過する必要があります。予選は複数回実施され、いずれかで通過すればOKです。今年は2時間で5問が出題されるコンテストでした。
予選A 予選B 予選C
予選Aでは、4問以上解いた人と、3問解いた人の中で早かった人が通過できました。リンクから問題を見てみてください。3問目までは簡単っぽいことが分かると思います。3問を14-15分で解ければ勝ちです。BとCについては、既に通過した人はカウントされないので、Aより通過難易度は下がっていたと思われます。普通にアルゴリズムの勉強をしている人ならきっと通過できるでしょう。

以下は日記です。

(1日目) 会場入り(12:00)

遅刻した。(12:15)
席に着いたら弁当が置いてありました。殻が付いたままのゆでたまごと、サンドイッチとあと何かがあったのだけは憶えています。(本戦中に食べました)

(1日目) CODE FESTIVAL 2016 Final

問題はこちら
本戦です。配点が以下のようになっていて、1600点以上とるとCODE FESTIVAL パーカーが貰える、というものでした。 パーカーを貰える最小限の得点の取り方は、ABCDe, ABCE, ABCFの3通りが考えられます。(小文字:部分点)

f:id:celtek:20161201002941p:plain:h450
(カッコ内:部分点)

ABCまで解き、Fはグラフっぽかったので早々に諦め、Dを捨てEの満点を狙おうと考えました。
駄目でした。Eの部分点すら取れませんでした。いつの日かパーカーをゲットし必ず中級者を名乗ってやる、と固く心に誓いました。
ちなみにDはそんなに難しくなかったので冷静な思考ができる人はまずそっちを解いていたようです。

(1日目) tourist氏 講演

tourist氏とは、ベラルーシ出身、現在ITMOというロシアの大学の学生で、競プロ界では知らない人はいないレベルに"強い"方です。(私は競プロ界の人間ではないので知りませんでした)
彼はプログラマの両親の影響で7才のときに競プロを始めたそうです。7才。
事前にTwitterで収集した質問にtourist氏が回答するという形で1時間ほど続きました。｢今まで行ったことのあるカリブ海の島で一番好きな島はどこですか｣という質問があったこと以外はよく憶えてないです。(カリブ海は行ったことないそうです)

(1日目) 本戦問題解説

会場内でchokudaiさん(AtCoderの社長)が本戦の問題の解説をしていました。同時にラジオで放送されていたみたいです。

chokudaiさん｢◯◯知ってますか？ 皆さんさすがに◯◯は大丈夫ですよね？｣
周りの人々 (頷く)
私 (知らん……)

みたいなのがあって勉強しなきゃなあと痛切に思いました。

(1日目) 秋葉拓哉氏 トークライブ

秋葉さんがペアプログラミングするトークライブ。コーディングしている人が誰だか分からなかったのですが、その隣で秋葉さんがツッコミを入れていました。
倒すべき敵は｢チョク=ダーイ｣(第1形態、第2形態、最終形態)で、問題とそれぞれの制約は以下のような感じでした。(細かい数字は違うかも)

チョク=ダーイとW×Hブロックの板チョコを使ったゲームをする。プレイヤーは長方形の板チョコを、2つの長方形に分割されるように折って割る。次のプレイヤーは2つに分割されたチョコのうち一方を選び、それを2つに割る。選ばなかった方は捨てる。これを繰り返し、最後の1×1のチョコ片をとった方が負けである。チョコの高さと幅は常に整数でなければならない。自分が先攻であるとき、自分が勝てるかどうか判定せよ。

制約
第1形態 1 ≦ W, H ≦ 5
第2形態 1 ≦ W, H ≦ 100
最終形態 1 ≦ W, H ≦ 109

ライブでは時間ギリギリでチョク=ダーイ最終形態を倒すことができました。やったー！
(なおchokudai氏とは別人なのでそこはよろしく、とのこと)

(1日目) 夕食

f:id:celtek:20161201010634p:plain:w500

会場にビュッフェコーナーがあり、各自欲しいものをバイキング形式でとりました。メニューは以下。

f:id:celtek:20161201010344p:plain:w500

寿司の、なくなる速さ。
途中で食べすぎて気持ち悪くなってきた私は、"イタリアンサラダ"というのが小さなプラスチック容器に一口サイズの牛肉とレタスとオリーブの実が入っているもので食べやすかったので、それを無限にヒョイヒョイ食べていました。

(1日目) CODE FESTIVAL 2016 Exhibition

問題はこちら

f:id:celtek:20161201012253p:plain:w500

本戦上位陣によるエキシビションマッチ。3人1チームのチーム戦で、ACM-ICPC形式(PCはチームで1台のみ)、1時間で2問というコンテストで、各チームの部屋の様子は会場のスクリーンに写されています。日本チーム、海外チーム、ゲストチーム(Indeed社員)の3チームで、おそらく大方の予想は海外チームの勝ち、であり、開始前のコメントも

司会 ｢勝てると思いますか？｣
日本チーム ｢勝てないと思います｣
海外チーム ｢予測不可能だと思います｣
ゲストチーム ｢皆さんの予想通りだと思います｣

のような感じでした。
会場も同じような空気だったのですが、40分経ってもどのチームも得点できず苦戦していて、結局開始50分でゲストチームがBをACした以外に得点はありませんでした。そんなわけでゲストチーム優勝ということで、本当に予測不可能でしたね。
個人的に印象に残っているのは、オープンコンテストのほうで5人の方がACを出している点です。チームを組んで協力していたのかもしれませんけど、それでもすごいなあ、と。

(2日目) 会場入り(08:00-09:00)

遅刻しませんでした！(08:20)
席に着いたら弁当が置いてありました。内容は鮭おにぎり、牛肉の佃煮(？)のおにぎり、唐揚げ、たくあん、ゆでたまご(殻無し)でした。
あとディスプレイにDoS攻撃するように指示がありました。公式DoS攻撃というセンセーショナルなワードの誕生です。

f:id:celtek:20161201020629p:plain:w500

(2日目) CODE FESTIVAL 2016 Elimination Tournament

問題: Round 1 Round 2 Round 3

おそらく去年まで｢あさプロ｣と呼ばれていたもの。今年は勝ち抜きトーナメントになっていました。
Round 1では本戦の順位が近い8人のグループ内で勝ち抜きを行い4人を選ぶ。Round 2では、隣のグループとマージして同じことを繰り返す。最終的な勝者は会場の約1/8となる、というルールです。
結果ですが、私は駄目でした。勝つとシールが貰えたので悔しいです。

(2日目) 昼食

弁当が5種類ほど山積みしてあって、各自好きなものを1つ選ぶというもの。私は焼き肉弁当をいただきました。またたまごかよ。

f:id:celtek:20161205002625p:plain:w500

(2日目) ライトニングトーク

いろんな人が10分ぐらいずつ話していました(たぶん)。私は最後のchokudaiさんのトークしか聞けませんでした。そのお題は｢権威あるプログラミングコンテスト ICFPC2016 で堂々の世界第1位に輝いた私が教えるハンドスプリング徹底入門｣

f:id:celtek:20161201022920p:plain:w500

ハンドスプリングとは地面に手をついて前転とかやるアレです。 曰く、TopCoderのオンサイト決勝などでは選手入場フェーズがあり、大抵の選手は両手でガッツポーズをとるなどショボいことしかしない、しかしそこでハンドスプリングを行うとどうか？ 手軽に一芸披露することができる！ ハンドスプリングは競プロerに有用！！！ という論理らしいです。(普通はそういうオンサイトに行くこと自体無いのですが)
手順は次の通り。

  1. 手を上に上げる
  2. 手を勢いよく地面に振り下げる
  3. 脚を勢いよく上に上げる
  4. ぐるっと回る
  5. ね、簡単でしょ？

(2日目) CODE FESTIVAL 2016 Relay

問題はこちら

チーム対抗、リレー形式のコンテスト。1チーム11人(うち1人は海外勢)で、各チームにコーディングスペースが与えられ、11問の問題をかわるがわる解く。同時に複数人がコーディングするのは禁止で、必ず1人が1問を実装しなければならない。誰がどの問題を解くのかは自由だが、一度決めた担当は変えてはならない。 チームのスペースでアルゴリズムなどの相談をすることが可能で、実質的に各メンバーに問われるのは実装力だけ。ただしこれもコーディングスペースからチームスペースに戻って言語仕様などをメンバーに聞くことが可能。
以上のようなルールで、20チームの対抗コンテストとなりました。海外の人とのコミュニケーションが上手くとれるか不安だったのですが、始まってみるとチームで話し合いながら問題を片付けていくのが楽しく、英語もまあなんとか伝わるので杞憂でした。というか海外の人は大体の問題の答えが分かるので、こちらで分からなければとりあえず英語で聞いてみる、というのが効率的で、そういうゲームでした。
と、ここまで読むとなんだかすごくチームに貢献したように思えますが、私が実装したのは2問目、しかも本来5分もかからないはずのものを10分ぐらいかけて書いたようなレベルであり、賢い私はそのことをちゃんと自覚していたので、チームでは積極的にゴミの片付け等の雑用を行っていました。
チームの人がつよい人ばかりで、最終的に全ての問題をACすることができました。何もしていないのにすごい達成感を味わうことができました。

(両日) その他のコンテンツ

オープン控室

要するに休憩スペース。暇な時はここでずっと｢セット｣というカードゲームをしていました。私は初めて知ったのですが、競プロ？数オリ？界隈では有名、人気っぽいです。他にも色々なボードゲームが置いてありました。

書道コーディング

半紙に墨汁で競プロっぽい作品を書くコーナー。創造性。

コード川柳

Twitterでハッシュタグを付けて競プロっぽい川柳をツイートする。センス。

体力測定

背筋とか垂直跳びとか。よい競プロはよい体力づくりから。

太鼓の達人

ランキングの課題曲は残酷な天使のテーゼ(難易度:むずかしい)。トップ層は確か70万点台でした。

UFOキャッチャー

CODE FESTIVAL のロゴが入った手ぬぐいやらタオルがゲットできます(ゲットできるとは言ってない)

おわり

というわけで、初心者が気をつけるべき唯一のコンテンツはチームリレーです。ここさえ上手く乗り切ればあとは適当でもなんとかなります。
コドフェスは競プロ以外にもいろいろ遊べて初心者でも楽しめるプロコンイベントです。参加できるのは(ほぼ)学生のうちだけで、コンテストを通して学べることも多いですし、あわよくば中級者になれるかもしれないので、是非みなさん参加しましょう。

Initial Article

ラーメン

ラーメンを食べるのが好きな人が、食べたラーメンについての記録を残すのを主目的として開設されたブログの最初の記事です。
2016年11月現在、渋谷･恵比寿あたりを主戦場として活動しています。

基本的に人に見てもらおうとは考えていませんが、万が一検索して出てきてしまった場合、一つの参考になる程度にはしたいと思っています。(そんなに上位に来るとも思えませんが)

というわけで早速、テストも兼ねて直近で食したラーメンについて書きます。ほとんど恵比寿です。

2016/10/27 AFURI 恵比寿

f:id:celtek:20161112024035p:plain 柚子塩ラーメン 980円

超有名店(らしい)。恵比寿と言ったらここ。
スープ、澄んでいて洗練された旨み。麺、どことなく蕎麦のようでスープと絡む。胡椒との相性良し。 文句のつけようがない。次行ったとき個別記事でもっと書きたい。

2016/11/04 おおぜき中華そば店

f:id:celtek:20161112024909p:plain 味玉にぼしそば 880円

恵比寿神社の前にある。神社は嫌いではないのでアド。
スープ、煮干しのエグみ無く旨い。肉、玉子ともレベル高くうまくまとまっている印象。 煮干し系が好きなら行って損はない。

2016/11/07 よってこや 恵比寿本店

f:id:celtek:20161112030817p:plain 塩らーめん 半熟煮玉子入 850円

見た目がチェーン店っぽい。ラーメン以外の料理も多い、けれどラーメン目的なので。
いわゆるとん塩。豚骨が入ると臭みが強くなる印象がありあまり好きではないのだが、ここのラーメンは臭みは少なく豚骨の良さをうまく出している。 玉子、トロットロで旨い。アオサ、良いアクセントになっている。個人的に好きなタイプのとん塩。

2016/11/09 うさぎ

f:id:celtek:20161112031551p:plain 味玉醤らぁめん 850円

ずっと来たかった店。渋谷から徒歩圏内。
商品名から分かるが魚介系のスープ。鰹とあと何か、な気がする。とにかく旨いの一言。 肉、ホロとして最高、優勝。玉子、濃厚。麺、やや太めで食べごたえあり。 また行きたい。

2016/11/09 函館らーめん しお貫

f:id:celtek:20161112032409p:plain 塩らーめん 670円

恵比寿駅から徒歩10分強。やや遠い。最もシンプルな塩ラーメンが670円と安い。 寡黙な雰囲気。これぞラーメン店といったところか。
スープ、コンパクト。鶏ダシと思われる。無限に飲める味。肉、本場っぽい(ラフテーのような)。 立地が悪くても存続する店。

(書くのに結構時間がかかってしまった……)
とりあえず以上です。紹介部分だけ"だ･である"調になってしまいましたがまあいいでしょう。
文章化する想定をしていなかったので内容が薄くなっています。次回からある程度ちゃんと書きます。(本当？w)