つちのこの日記

競プロと音ゲーがメインです。

AtCoder Beginner Contest 205 一言解説

30分で解き終わって暇だったので書きます。

A.kcal

$\frac{AB}{100}$ を出力します。

B. Permutation Check

与えられた配列をsortして、 $1,2,\dots,N$ になってるか確かめましょう。 std::iotaを用いると配列 $(1,2,\dots,N)$ が得られるのでこれを用いるのが簡潔でしょう。

C.POW

$C$ の偶奇で場合分けしましょう。 $C$ が奇数ならば $A,B$ の、 $C$ が偶数ならば $|A|,|B|$ の大小関係を判定すればよいです。

D.Kth Excluded

$X$ が小さい方から $K$ 番目 $\leftrightarrow X$ より小さい数が $K- 1$ 個あるという同値変形を行いましょう。

$X$ を二分探索し、判定にはsetのlower_boundを用いることでこの問題に答えられます。

E.White and Black Balls

カタラン数を知っていますか?カタラン数は競プロで頻出なので、知らなかった場合は覚えておくと良いでしょう。

知っていればあとはその考えを用いることで答えが $\binom{N+M}{N}–\binom{N+M}{N-K- 1}$ となります。

$M+K<N$ ならば答えが $0$ になることに注意しましょう。

F.Grid and Tokens

蟻本210ページのDiningとほぼ同じ問題です。辺を湧き出し口→行番号→駒→駒→列番号→吸い込み口の順番で貼ります。

aclのmf_graphを用いると実装が簡潔でしょう。

CodeForces div.1 バチャの記録

6/7からdiv.1バチャをすることになりました。

せっかくなので各回について記録と解けなかった問題の分析をメモっていこうと思います。

解けたけど消化しきれていない問題や、解けなかったけど大事そうな問題については個別に解説記事を書くかもしれません。

よろしくお願いします。

6/7 Codeforces Round #499 (Div. 1)

結果

ABCD4完

一言解法

  • A.こういうのは逆から見ます 1のやつがあったら無理で他は最小にすればよい、簡単でした
  • B.ちょっと悩んでしまった。。 クエリの回数見るとにぶたんで、最初のN回 1以上かという結果が自明なクエリを投げれば真偽が特定できます。
  • C.無限回見ました、GCDをとるだけ K進法のくだり、いりますか?
  • D.やることは割とすぐ見えて、各場所のbitを確かめてからdfsでどうなるかを決めます。実装が170行で破滅してしまいました。。

感想

A-CがDiv.1にしてはかなり簡単でびっくりしました、Dみたいな実装問でうまい実装方針にたどりつけるようにしたいです。

6/9 Codeforces Round #691 (Div. 1)

結果

AB2完

一言解法

  • A.gcdと差は相性が良いのではい
  • B.一瞬貪欲を疑ったがうまくいかないので実家のようなDPをします
  • C.逆置換をうまく処理する方法、初めて知りました(全然見えなくて飛ばした)
  • D.ARCとかにありそう、うーん
  • E.解けそうでしたが終了後に一個勘違いに気づきました。(翌日通しました、考察はEにしては軽かったですが実装でバグらせまくりました、、、)

感想

やー、CからEのどれか一つは通したかったですね。 Bで0.5出てくるのにint / 2 をして1ペナ出したの本当にもったいない、反省です。 E、めちゃくちゃ面白かったです。

6/11 Codeforces Round #580 (Div. 1)

結果

ABC3完

一言解法

  • A.+1と-1に着目するシンプルな構築
  • B.同じbitが立っている数が3つあれば終わりなことには気づいたのに、頂点数が120以下なことに全然気づかなくてロス、勿体なかったです
  • C.仮置きすると大体決まる 特定パートは未証明でやっちゃいました(反省)

感想

Bみたいなギャグをパッと通せるようになりたいです。

6/14 Codeforces Round #485 (Div. 1)

結果

ABCE4完

一言解法

  • A.多始点bfs
  • B.転倒数
  • C.反転させたやつとかにいい感じに辺を貼る、むずかしいです。。。
  • D.めんどそう
  • E.素因数ごとにイベントソートしてHL分解でパス和取得 面白かったです。

感想

Cがむずかしかった、こういうのパッと思いつけるようになりたいです。 Eはかなり好きな感じでした。

6/16 Codeforces Round #692 (Div. 1)

結果

ABCE4完

一言解法

  • A.むずかしい お気持ちでUF
  • B.こういうのは0と1集めた方がいいのでBITでシミュ
  • C.よく考えると後ろ2つ以外自由 コストが2ベキなので貪欲が正当性を持つ
  • D.めんどそう
  • E.終了後に通しました どちらもすごい面白かったです
    • 方針その1 grundy数が $ 512 $ 未満なことに着目すると、連立方程式立てて履き出せる
    • 方針その2 操作が $f(x) = \sum cnt_i x^{i}$ をxor畳み込みでかけることに対応しているので、 $\frac{1}{1-f(x)}$ みたいなのを求める invは FWTしてから各点逆元とってIFWTすればもとまる

感想

Cまで割と素早く解けて成長を感じました。Eは知見が得られてよかったです。

yukicoder contest 291 のwriterをしました

はじめに

yukicoder contest 291 ご参加ありがとうございました! ご参加下さったみなさん、testerを引き受けて頂いたみなさん、本当にありがとうございました!

以下では各問題の講評を記します。ネタバレが含まれるので注意してください。

A.esreveR dna esreveR

原案,解法:PCT

FA:tuteさん(1分45秒)

割とシンプルで個人的には好きな問題です。1問目としてちょうどいい難易度だと思います。

B.Lamps on Graph

原案の原案:2020年度麻布中学入試数学第5問

原案,解法:nok0

tester:むかでさん

FA:uwiさん(6分49秒)

久々に算数の問題を見てたらめちゃくちゃ競プロっぽかったので改題して出題しました。 やることはただの貪欲なのですが、割と面白いと思います。

2問目にしてはやや難しかったかも?ごめんなさい。

C.Simple Sugoroku

原案,解法:nok0

tester:おてらさん

FA:SSRSさん(11分38秒)

すごろくとか考えてたら生えた問題です。Sugoroku 2より前に思いついたので、ABCですごろくが出てびっくりしてました。 後ろから全探索していくことで線形で解けます。(実はQCFium法で Ο(M2) が通ります)

最初の1時間、全然ACが出なくてびびっていました。

D.Matrix Eraser

原案:fairy_lettuce 解法:nok0

tester:ながたかなさん

FA:tabrさん(11分6秒)

writerの解法が嘘貪欲だったので(!?)、解法を提供しました。THE 典型枠ですがとても好きな問題です。知らなかった人は最大流で出来ることについて色々調べてみるといいと思います。

E.Many Complete Graphs

原案:PCT 解法:PCT

tester:蜜蜂さん

FA:NyaanNyaanさん(7分32秒)

沢山の組に辺を貼る時は超頂点っていうのはかなり典型的な気がします。

DとEでどちらが難しいか悩んでいたのですが、いい感じにD<Eになったようでよかったです。

F.Rotation ABC

原案,解法:nok0

tester:chineristさん

FA:tatyamさん(22分56秒)

Ad-hocだったり実験だったり枠。難易度評価が難しかったです。実験すればわかると思います(多分)

G.Swap Many Permutations

原案:nok0 解法:nok0,PCT

tester,賢い解法:tatyamさん

FA:hitonanodeさん(101分54秒)

むずめの数え上げ枠。必要十分条件エスパーして頑張って式変形すると畳み込みに帰着できます。 全然解かれないと思ってたのですが、結局5人もの方に解いていただきました!すごいです!!

なんと実は線形で解けます。 tatyamさんに畳み込みを使わない線形解を教えていただきました、ありがとうございます〜

H. Many Graph in Namori

原案:PCT 解法:PCT

tester:beetさん

全完阻止枠。誰も時間内には解けないと予想しています(beetさんが10時間掛かったらしいので)

↑結局ACは出ませんでした Ω\ζ°)チーン

まとめと感想

優勝はSSRSさんでした!!おめでとうございます!! 参加していただいたみなさん、並びにtesterを引き受けてくださったみなさん、ありがとうございました! セットとして出題するのは今回が2回目ですが、共同作問はいつもとは違った刺激があり、またお互いに問題を強化したりできるので凄い楽しかったです。 作問は問題をただ解くのとは違った楽しみがあるので、とてもおすすめです!

またいつかyukicoderにはセットを出したいと思っているので、その時はよろしくお願いいたします。 最後になりますが、ありがとうございました!!

キーエンス プログラミング コンテスト 2019 - F Paper Cutting(赤diff, 900点) 形式的冪級数解

問題リンク

atcoder.jp

 

問題概要

縦に $H$ 本、横に $W$ 本の線が引かれた長方形の紙がある。

一回の操作では、まだ選択してない線を一つ選択し、その線で紙を切る。その後紙の破片の個数をスコアに加算する。

操作をちょうど $K$ 回行う時、全ての操作方法に対するスコアの総和を求めよ。

制約
  • $1 \le H, W \le 10^7$
  • $1 \le K \le H + W$

解説

本解説では $[x^n]f(x)$ で形式的冪級数 $f$ の $n$ 次の項の係数を表すこととする。

$i$ 回目の操作で縦の線を選択した時のスコアの増加分の期待値を求めることを考える。これを $\mathcal{Ο}(1)$ で求められれば、この問題に $\mathcal{Ο}(K)$で答えられる。

考察を容易にするために、操作は 0_indexedで考える(つまり、操作は $0$ 回目から $K - 1$ 回目まで行う)。

$i$ 回目の操作の前に既に選択された縦線の個数を $j$ 本と固定してみる。この時、既に選択された横線の個数は $i - j$ 本である。

このような状態になっている確率は、 $ \frac{\displaystyle \binom {H-1}{j} \displaystyle \binom{W}{i-j}}{\displaystyle \binom{H+W-1}{i}} $ であり、この時得られるスコアは $ ( j + 2 )( i - j + 1) $ である。

ゆえに、 $i$ 回目の操作で縦の線を選択した時のスコアの増加分の期待値は以下の数式で表せる。 $$\displaystyle \sum_{j = 0} ^ i \left( \frac{\displaystyle \binom {H-1}{j} \displaystyle \binom{W}{i-j}}{\displaystyle \binom{H+W-1}{i}}( j + 2 )( i - j + 1) \right) \tag{*}$$ 

分母は $j$ に依存せず楽に計算できるので、後は分子を上手く扱う。

分子を $\binom {H-1}{j}(j + 2) $ と $\binom{W}{i-j}(i-j+1)$ に分けて考える。

一つ目については、 $$f(x) = \sum_{i = 0}^{\infty}\binom{H-1}{i} x^i$$ と置けば、 $$xf'(x) = \sum_{i = 0}^{\infty}{i \binom{H-1}{i} x^i}$$ であるから、

$$\begin{split} \binom {H-1}{j}(j + 2) & = [x^j] 2f(x) + xf'(x) \cr & = [x^j]( (H+1)x + 2)(1+x)^{H-2} \cr\end{split} $$ と表すことができる。

同様に、二つ目については $u := i-j$ と置けば

$$\begin{split} \binom{W}{i-j}(i-j+1) & = \binom{W}{u}(u+1)) \cr & = [x^u]( (W+1)x + 1)(1+x)^{W-1} \end{split} $$ と表せる。

ゆえに $${(*)} = \frac{1} {\binom{H+W-1}{i}}\displaystyle \sum_{j = 0} ^ i \left( [x^j] (H+1)x + 2)(1+x)^{H-2} × [x^{i-j}]( (W+1)x + 1)(1+x)^{W-1} \right)$$

これは畳み込みの形となっているので、求めるものは $$\frac{1} {\binom{H+W-1}{i}} [x^i] (1+x)^{H+W-3}( (H+1)x + 2) ( (W+1)x + 1) $$ と簡潔に表示できた。

$(1+x)^N$ の 任意の項の係数は、適切に階乗とその逆元を求めることで $\mathcal{Ο}(1)$ で求められるので、$i$ 回目の操作で縦の線を選択した時のスコアの増加分の期待値も $\mathcal{Ο}(1)$ で求められる。

縦線が選ばれる確率は $\frac{H}{H+W}$ 、横線が選ばれる確率は $\frac{W} {H+W}$ であるから、先ほどの期待値にこの確率を掛け合わせ、$i = 0$ から $K - 1$ まで足し合わせることでこの問題を $\mathcal{Ο}(K)$ で解くことができた。

実装の際には階乗と逆元の計算を適切に行うことや、負の二項係数にライブラリが対応していない場合 $H=W=1$ の時に正しい答えが返されないことに注意されたい。

ソースコード 

 

長いので折り畳み(includeやmodintは省略)
const int CombMAX = 20000010;
mint fac[CombMAX + 1], finv[CombMAX + 1], inv[CombMAX + 1];

struct Combinationinit {
    Combinationinit() {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        for(int i = 2; i <= CombMAX; i++) {
            fac[i] = fac[i - 1] * i;
        }
        finv[CombMAX] = fac[CombMAX].pow(MOD - 2);
        for(int i = CombMAX; --i;) {
            finv[i] = finv[i + 1] * (i + 1);
        }
    }
} Combinationinit_;

//nCk
mint COM(int n, int k) {
    if(n < 0) return COM(-n, k) * (k % 2 ? -1 : 1);
    if(n < k or k < 0) return 0;
    return fac[n] * finv[k] * finv[n - k];
}

mint COMinv(int n, int k) {
    if(n < 0) return COMinv(-n, k) * (k % 2 ? -1 : 1);
    if(n < k or n < 0 or k < 0) return 0;
    return finv[n] * fac[k] * fac[n - k];
}

//nPk
mint PER(int n, int k) {
    if(n < k or n < 0 or k < 0) return 0;
    return fac[n] * finv[n - k];
}

int h, w, k, i;
mint res;
int main() {
    scanf("%d%d%d", &h, &w, &k);

    for(i = 0; i < k; i++) {
        mint tres = COM(h + w - 3, i) * 2
                  + COM(h + w - 3, i - 1) * (h + 2 * w + 3)
                  + COM(h + w - 3, i - 2) * (h + 1) * (w + 1);
        mint yres = COM(h + w - 3, i) * 2
                  + COM(h + w - 3, i - 1) * (w + 2 * h + 3)
                  + COM(h + w - 3, i - 2) * (h + 1) * (w + 1);
        res += (tres * h + yres * w) * COMinv(h + w - 1, i);
    }

    cout << res * PER(h + w, k) / (h + w) << endl;

    return 0;
}

yukicoder contest 276 で Writer をやった話

前書き

yukicoder contest 276で単独Writerをやりました、nok0です。セットを投稿するのは初めてでしたが、楽しんで頂けていれば嬉しいです!

今日単独コンテストを開催できたのは、yukicoder及びyukiさん、testerを心良く引き受けてくださった皆さん、全問の難易度等をチェックしてくれたくまー(@kuma_program)くんのおかげです、本当にありがとうございます。

自己紹介と諸々

最近AtCoderで黄色になりました。競プロ歴はまだ1年もないのですが、折角競プロというコンテンツに割とどっぷり浸かってしまったので、創作もやりたくなり、セットを出させていただきました!これらの問題を作ったのは多分青の頃なので、レートにあまり関係なく、作問は楽しめると思います(多分)。

 問題ごとの解説及び講評(注:問題のネタバレを大いに含みます)

A.OR XOR

tester:zkou(@meander_uts1)くん

First AC:hitonanodeさん(01:44) (以下、FAの時間は(分:秒)で表記します。)

一問目なので、易しい考察で解けること、及びに典型要素が学べることを重視してこの問題を置きました。bit演算を扱う問題はbit毎に着目すると良いことが多いです。結局xorが0なことから、この問題は

Nの立っているbitそれぞれについてをA,B,Cのいずれか2つに割り振る。ただしA,B,Cが全て正という条件を満たすために、A,B,C全てに一つ以上bitを割り振らなくてはいけない。

という問題に言い換えられます。そうすると、構築可能な条件もわかりやすかったのではないでしょうか?

解説にも書きましたが、Nの一番下の立っているbitを N & (-N) で取り出せるということを使うと実装が簡潔です。余談ですが、初めて私がこのテクニックを知ったのはsnukeさんの解説放送(確かBITを実装する回)だったはずで、めちゃくちゃ感動した記憶があります。

講評:いい感じに1問目としての役割を果たしてくれました。思ってたよりWA率が高かったですが、多くの皆さんが解いてくれたようでよかったです。

B.Random Array Score

tester:zkou(@meander_uts1)くん

First AC:sugarrrさん(02:27)

数学問兼ギャグ問枠です。

最初は各要素がi回目に選ばれた時の、総和の増加分の期待値を求めて、それを足し合わせることで答えを求めようとしてましたが(それでも普通にできます)、よく考えると各操作で期待値が2倍になることがわかります。 操作が少し難しそうに見えて答えがすごいシンプルに表されるのが面白いと思って出題しました。

ちなみに、問題文中の期待値が有理数で表せるというところはひっかけで、単純に整数で表すことができます。

講評:難易度自体は割と予想通りのものになりました。ただ、数学要素が強い問題だったので、寒色コーダーの方でも苦戦する方も一定数いらっしゃったようです。

C.Sum of Inversions

tester:NOYA(@NOYA08096071)さん

First AC:tatyamさん(10:23)

簡単な典型枠です。真ん中に着目するといいことがある場合が多いってことだったり、転倒数は座圧してBITに載せることで計算できるといったことだったりは、高難易度だと当然のように要求される典型事項なので、もし知らなかった場合はこの問題を通して学んでいただければ嬉しいです。

講評:どちらかと言えば考察力よりも実装力、基礎的なデータ構造の使い方を問うつもりの問題でした。実装が重めでしたがかなり解かれていて、みなさんの競プロ力の高さを感じました。

D.Strange Graph Shortest Path

tester:zkou(@meander_uts1)くん

First AC:beetさん(02:21)

典型枠2(このセット、典型が多い気がしてきました)、コストがintに収まりきらない最小費用流のverifyにお使いください。解法ではなく設定から作ったのですが、よく見ると蟻本に乗っていました。蟻本は本当に情報の密度が濃いので、この問題が解けなかった方は今一度読み返すといいかもしれません。

もともと想定はdijkstraしてから経路復元し辺の長さを変更し、再度dijkstraだったのですが、冷静になると大嘘でした(これを落とすためのケースがkiller-01で、k-th-shortest-pathをk = 1からある程度のkまで回して最短になったものを採用するコードを落とすためのケースがkiller-02です)。killer-02はtesterさんに考えてもらったので、感謝です。

ところでこの問題、c_i > d_i でも解けるんでしょうか?何かご存知の方いれば教えてくださると嬉しいです。

講評:中度典型枠でした。知っている方は爆速で通した(beetさんは早すぎて本当にびっくりました)一方、知らなかったり思いつかずDijkstraの嘘解法に走ってしまい、ペナを量産している方も見受けられました。概ね想定通りの難易度でした。

E.Random Tree Score

tester:まつかわ(@tpyneriver)さん

First AC:hos.lyricさん(07:43)

グラフ枠かつ冪級数を用いた数え上げ枠。次数の積という条件を扱いやすくするために、次数を固定して考えてみると解説の式が実験なりなんなりで出てくるはずです。(Cayleyの公式をこの補題から証明したことがある人なら秒だったかもしれません。)そこにさえ辿り着けば、単純な冪級数の累乗で答えが表示できます。最初は Ο(NlogN) 想定でしたが、非本質で落とすのも違う気がするのと、logの区別は難しいので、Ο(Nlog^2N)でも余裕で通る制約にしました。 

まつかわさんのtester解は、全然違うことやってます、すごいです。めちゃくちゃいい感じのpdf解説を書いていただいたので、そちらも合わせてご覧ください。

講評:やや難しめの数え上げ問題でした。割と非想定で通されている気がするので、コードをみて勉強した後に、解説及びここのブログに追記します。難易度は想定よりやや易しめだったでしょうか。

F.Inconvenient Kingdom

tester:hamamu(@hamamu_kyopro)さん

First AC:maroon_kuriさん(16:26)

ボス問枠、行列木定理を用いた数え上げを線形代数で高速化する問題。もともとはもっと簡単な問題でしたが、hamamuさんからの数々の助言のおかげでボス枠になりました。hamamuさんには問題文の日本語直してもらったりテストケースについて助言を頂いたり愚直解をチェックしていただいたり、、本当に頭が上がりません、めちゃくちゃお世話になりました。

この問題は、行列木定理に感動して作りました。全域木の個数が多項式時間で数え上げられるの、本当にすごくないですか?? 高速化の方法も割とシンプルでかなりお気に入りです。連結成分が2個以上の場合はちょっと場合分けがめんどいのですが、そこは頑張りましょう。

講評:思ってた以上に通されました。赤コーダーだったり本当に強い方々との力の差を痛感しました。hitonanodeさんの解が5msで、本当に脳内が???です、どうやってるんでしょう?

問題の準備にあたって

これ、めちゃくちゃ大変でした。そもそも作問って

原案の準備→解説の準備→問題文の準備→テストケースの準備→確認

って感じでなかなかやることが多いです。特に大変なのが問題文の準備で、わかりやすい日本語書くのって、めちゃくちゃむずいんですよね。長い文章をまとめあげる自信がなかったので、今回のセットは極力ストーリーをカットしました。

テストケースの準備はめんどくさいんですが、今回はRimeを使うことでめちゃくちゃ楽になりました。詳しくはbeetさんのブログをご覧ください。(とてもわかりやすくまとまっています。

後書き

作問はなかなか大変ですが、めちゃくちゃ楽しいので、是非皆さんもやりましょう!ちょっと前に作問でかなりやらかしてしまったのですが(本当にごめんなさい。。)、今日は無事に終わることができて安心しました!(しかもclar0を達成しました!!)本当にありがとうございました!

 

bit

ICPC2020 国内予選 参加記

昨日はICPC2020国内予選に参加しました。チームは毎度おなじみのSPJ(クマー、zkou、私)です。

本番の記録

  • 16:30〜

あれ?サイトに繋がりません。めちゃくちゃ焦ります。電話をしても繋がりません。なんか10分ぐらいしたら急に治りました。

  • 16:40〜

打ち合わせの通りに私がA、zkouがBを通します。クマーがCで苦戦しているので見ていくと、3乗根っぽいのはわかりますが解けません。(ここ戦犯ポイント1) めちゃくちゃみんなで高速化を考えてると、愚直解の実行が終わっています。ここまでで1時間くらい使ったのが結果的にはかなり痛かったね、、、

  • 17:40〜

DとEを並列に読みます。Dは構文解析パートは易しそうで、その後の解法について制約等からbitDPとかを考えるんですけど、これが良くなかったです。(戦犯ポイント2) 答え決め打って頑張るとかまでは思いついていたので、どうして順序を割り振ってbit全探索が出てこなかったのか、、、 結果的にDを通していれば余裕で予選通過だったので非常に悔やまれます。

Eは最初木DP?とか思うんですけど、全然木じゃなかったです笑(くまーにおこられました) 

  • 18:30〜

EがbitDPで高速ゼータ変換してうんちゃらするとかいう方針をzkouが思いつきます。(天才) 私は高速ゼータ変換良くわかっていないので(これは良くない)、一人でDを考えていました。

Dがよくわからないので、Fを見にいくと、これは部分永続Union-Findで勝てそうな問題に見えます。 辺の長さが小さい順からUFの辺を削除していって(これは部分永続Union-Findで簡単にできます(逆から辺を貼ればいいので))、最大じゃなくなった頂点集合を消していき、最終的に頂点集合のサイズが1となったときに残っている頂点が答えっぽいことに気付きます。これはどう見てもΟ(NMlogN)くらいかかりそうなんですけど、ちょっと高速化すればここまでにはならなさそう?と思ってコードを書き、実装すると5分くらいでデータセット1が終わります。

ノリノリで提出すると、WAと出てイライラします。入力と出力をじーっと比較すると、なんと1行まるまる飛んでいます。(N,M)=(1,0)のコーナーケースが入っていたそうです(ひどい) ここを直してFをACしました。

  • 19:00〜

くまーとzkouがEを頑張って書いているのですが、サンプルすら合いません。デバッグを応援しながらDを考えるのですが、全然解けません。デバッグを応援していると、終了直前でなんとかEが通り、そのまま終了。

結果は23位で大学内8位、予選敗退でした。

f:id:tsuchinok:20201107102445p:plain

感想

初めての参加ということもあり、緊張しましたがコンテスト自体は非常に楽しかったです。結果も、黄黄青の3人チームにしては上出来だと思いますが、Dが通せなかったのがとても悔しいです。

来年はもっと強くなってリベンジしたい、そう思いました。

 

WUPC4thに参加しました。

初めてのチーム戦でしたが、とても楽しかったです!運営の皆さん、及びにチームメイトに感謝です。

 

チームメイト

クマー : 同学年の強い青コーダーです。(すごい)

zkou : 同学年の強い青コーダーです。(すごい2)

: 普通の青コーダーです。

 

今日チームでACできた問題について解いた順番に軽くコメントします。

 

A : 2が含まれる時だけ気をつけます。流石にすぐに実装できました。(2分)

B : zkou君と割となやみました。a[i]とa[i+1]についてb[i] = a[i + 1], b[i + 1] = -a[i]とし、奇数の時だけ調整するという方針でやったのですが、もっといい方針がありましたね、、思いつきませんでした。(13分)

C : 問題を色々見て回ってから、簡単そうなCにいきました。コドフォでエスパー力とギャグセンスを鍛えていたので、すぐにわかりました。良かったです。(25分)

M : 問題文をみてすぐに全方位木DPなことはわかったのですが、実装の順番的に後回しになっちゃいました。すぐに書けることは割と明らかだったので、途中で実装順を変えた方がよかった気がします、反省です。(1時間2分)

なんとAからMまで実は全部私が実装してたみたいですね、びっくり、、 

J : SCCしてからどうするかわかんないよ〜っていってたらクマーが解いてくれました、凄い。(1時間19分)

E : この問題はzkou君がずっと考えてて、最後の実装だけ私が手伝ってACしました。まだ解法がよくわかってなくて、考えたいです。(2時間0分、1ペナ)

G : クマーとずっと悩んでて、私はΟ(N ^ 3)を投げようとしてクマーに止められてました(おい) でもコンテスト後に実際それで通してる人もいて、うーんになりました。zkouがすぐに閃いてくれて、実装を私がしてACしました(実装が下手で1ペナ出したの、謝罪、、) (2時間27分、3ペナ)

I : 私が他の問題考えてる間に、二人で解いてくれたみたいです。まだよくわからないけど、対角線付近しか絡まないギャグ問題っぽい?(3時間13分)

D : これはむずかったけど、みんなで考えて無事AC、diの積にmod N 上での逆元が存在すること気づかずにう〜〜んってなってました。(4時間4分、2ペナ)

K : 私とzkouで一生悩んでたのですが、クマーが点対称使うんじゃない?って言ってくれたおかげですぐに細部まで詰められて、AC。クマーに感謝です、、(4時間39分)

 

結果

11完で、全体では22位でした!初めてのチーム戦にしてはわりと上出来だった気がします。 (チームメイトが強すぎた、)

 

総括

初めてのチーム大会でしたが、とても面白かったです!コンテスト中の分担などの立ち回り、まだまだ詰められる部分ばかりだと思うので、これから頑張っていきたいですね〜