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

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

銀行とATMまとめ

動機

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

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

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

ATMの設置場所

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

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

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

その他のATM

イーネット

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

ローソンATM

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

VIEW ALTTE

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

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

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 / LU / D の状態を適当に持っておいてカウント

D

Problem - 752D - Codeforces
Submission #23303139 - Codeforces

1回pretestでWAをもらった
まず、与えられた小さい文字列がそれ自体が回文でないstring(a)と回文であるstring(b)に分けて、各stringbeautyの降順にソートする
(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 のロゴが入った手ぬぐいやらタオルがゲットできます(ゲットできるとは言ってない)

おわり

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