AtCoder ABC186E - Throne

ABC 一次合同方程式 拡張ユークリッドの互除法

問題概要

atcoder.jp

解説

x 回目にはじめて玉座に座ることができるとすると

S+Kx≡0\ (mod\ N)
⇔Kx≡-S\ (mod\ N)

と立式できる。

K と N が互いに素のとき

N を法とした K の逆元が存在するので

x≡-SK^{-1}\ (mod\ N)

で求められる（モジュラ逆数 - Wikipedia）。

K と N が互いに素でないとき

K と N の最大公約数を g\ (g>1) と置き、K を g で割った商を K'、N を g で割った商を N' とすると

K=gK'
N=gN'

となり、K' と N' は互いに素になる。
元の式 S+Kx≡0\ (mod\ N) について考えると、整数 m を用いて

S+Kx=Nm
⇔S=Nm-Kx
⇔S=gN'm-gK'x
⇔S=g(N'm-K'x)

のように表せられ、S は g の倍数である必要があることが分かる。つまり、S が g の倍数でないときは解なしとなる。S が g の倍数であるとき、S を g で割った商を S' とすると

⇔gS'=g(N'm-K'x)
⇔S'=N'm-K'x
⇔S'+K'x≡0\ (mod\ N')
⇔K'x≡-S'\ (mod\ N')

となり、冒頭の式に帰着することが分かる。

逆元の求め方

x が mod\ N における K の逆元であるとは

Kx≡1\ (mod\ N)

が成立することである。これは整数 y を用いて

Kx-1=Ny
⇔Kx+Ny=1

のように表せられ、y が存在すると逆元が存在するということになる。上式を満たす x は拡張ユークリッドの互除法によって求めることができる。

拡張ユークリッドの互除法とは

整数 a, b が与えられたときに

ax+by=gcd(a,b)

を満たす x, y を1つ求めるアルゴリズムである。

ソースコード

#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;

#define all(a) (a).begin(), (a).end()

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

// {g, x, y} : a x + b y = g
tuple<ll, ll, ll> extgcd(ll a, ll b){
    if(b == 0) return {a, 1, 0};
    ll g, x, y; tie(g, x, y) = extgcd(b, a % b);
    return {g, y, x - a / b * y};
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int t; cin>>t;
    while(t--){
        ll n, s, k; cin>>n>>s>>k;
        ll g, x, y; tie(g, x, y) = extgcd(k, n);
        if(s % g != 0){
            cout << -1 << endl;
        }
        else{
            n /= g, s /= g, k /= g;
            ll ans = ((-s * x) % n + n) % n;
            cout << ans << endl;
        }
    }

    return 0;
}

AtCoder 青になりました

昨日の AGC で 念願の AtCoder 青になったので、記念としてポエムを残しておこうと思います。

競プロを始めるまで


高校生のとき、情オリに出ていた友人がいたため、「競プロ」という存在自体は知っていました。が、プログラミングをやったこともなく、数学が特別得意という訳でもなかったので、特に興味を持ちませんでした。

紆余曲折あり、気が付いたら情報系の学科に進んでいました*1。B2 から学科の専門科目が始まり、そこで初めてプログラミング（C 言語）をやりました。しかし、全く慣れることができず、ほぼ学科同期から書き方を教えてもらいながら課題を解く、といったような散々な感じでした。当時、

「自然数 N が 1 つ与えられる。その自然数 N の各桁の数字の和 S を求めよ。」

といった問題にも全く歯が立たなかったのを今でも鮮明に覚えています。

このままではまずいと思い、プログラミングの練習をしようと色々探して偶然見つけたのが yukicoder でした。パズル感覚で問題を解くことが面白く、暇なときにぼちぼちやっていました*2。この頃から少しずつハマっていき、螺旋本・蟻本を買ったり、競プロer の方々をフォローしたりしました。

B3 になって、大学の競プロサークルに入ったのと同時に、AtCoder に取り組むようになっていきました*3。

灰 → 茶


まず C++ を最低限使えるようにしました。また、yukicoder の星 1, 1.5 あたり、AtCoder の 200 点や簡単な 300 点を解いたりしていたと思います。

必要だったスキル
  • if, for, while 文や配列
  • 全探索
  • 競プロに慣れる

茶 → 緑


AtCoder の簡単な 400 点を解いていたと思います。また、螺旋本や蟻本の簡単なページを読んでいた気がします。
旧 ABC の C まで早解き、あわよくば全完が可能になってくると突破できると思います。僕自身もこの頃に初めて全完していました。

必要だったスキル
  • C++ の STL
  • UnionFind
  • 累積和
  • 貪欲法
  • GCD, LCM
  • 簡単な DP
  • エラトステネスの篩

緑 → 水


緑になったことで更にモチベが上がり、螺旋本を大体読んだ気がします。また、AtCoder の過去問埋め、特に ABC-C 埋めを頑張っていました。

あとは、会津合宿 2018 に参加して強い人達を間近で見たこともかなり刺激になりました。

必要だったスキル

水 → 青


ここからが長かったです。実際、1 年とちょっとかかりました。
自分の場合、ポテンシャルで水色を保つのは確実に無理なので、AtCoder で難しい 400 点に挑んだり、500 点以降の問題に着手したりと、とにかく問題を解いていきました。また、実装力が乏しかったので、ICPC 対策も兼ねて AOJ の問題を中心に解いているときもありました。解いていく中で、分からない箇所は公式解説に加え、他の方の解説ブログやコードを見て、腑に落ちるまで考えることを心掛けていました*4。

また、蟻本の中級編を読んだり、サークルの勉強会で水色からすると高度なアルゴリズムを学んだりと、コンテストに出たときに使えるように知識を蓄えていきました。

2019 年 1 月末 ～ 2019 年 8 月末の約 7 ヵ月間はレートが停滞し、かなり辛かったです。特に、初令和 ABC で早解き全完 & 初黄パフォを出した回が unrated になったときは応えました…。いつかレートが上がると信じて地道に精進し、積極的にコンテストに参加するようにしていました。

7 ヵ月分の精進の成果か分かりませんが、ABC140, 141, 142 そして AGC039 の直近のコンテスト 4 回で +165 することができ、念願の青色を達成することができました。これらのコンテストでは「以前解いたあの問題の解法を少し変えたらいけそう」といったように、今までやってきたことが活きてきたのを感じる瞬間が多く、感慨深かったです*5。

必要だったスキル
  • Segment Tree（平方分割）
  • トポロジカルソート
  • 強連結成分分解
  • 木の直径
  • 行列累乗
  • 三分探索
  • 文字列アルゴリズム（KMP, Z-algorithm とか）
  • Grundy 数（Nim）
  • 桁 DP
  • bit DP
  • 幾何アルゴリズム
必要じゃなかったが知ってるスキル
  • フロー
  • 最小費用流
  • LCA
  • 橋・関節点の高速列挙
  • 文字列アルゴリズム（Manacher とか）

現状


青になった記録として色々残しておこうと思います。少しでも参考になれば幸いです。






まとめ


こうして書いてみると、プログラミングが全くできない状態から少し書けるようになったのは競プロのおかげだなあとしみじみ感じます。
当面の目標として、競プロを楽しみながら青を維持していきたいです！

長々と読んでいただき、ありがとうございました！

*1:高校時代は宇宙工学をやりたかったはずなんですよね。

*2:人生初 AC は #202476 (C) No.388 階段 (1) - yukicoder らしいです。

*3:B2 の終わりに軽く AtCoder をやっていたんですが、アカウント名が適当だったりしたので作り直しました。

*4:Slack で自分専用のワークスペースを作って解法を記録したりしていました。

*5:あと、この 4 回はラバーダックデバッグをしました。これが地味に良かったかも？

DDCC2019 本戦 参加記

大会参加記

記事を書くのがかなり遅れましたが、1 月 19 日に開催された DDCC2019 に参加してきたので、まとめたいと思います。

 

予選

C 問題の数え上げに時間がかかり、結果は 3 完遅解きで 416 位でした。コンテスト終了後に、去年の新卒枠が 430 位前後みたいなツイートを見かけたので、微妙だなあという気持ちになりました。

最終的に、新卒枠 + 繰り上がり というかなりギリギリな形で初オンサイト通過を決めることができました。来年以降のボーダーの参考になれば幸いです。

 

前日

かなり天気が悪い日で、東京に行くまでが大変でした。JR が止まっていて、離陸の 30 分前に空港に着いたりしました。これがオンサイトの恐ろしさか…(？)

東京に着いてからは、偶然同じホテルに泊まっていた monkukui 君とラーメンを食べに行きました（野菜大盛りがこういうやつだと思ってなかったんですよね）。

 

当日

起床 AC し、余裕をもって会場に向かいました。しかし、受付締め切りの 10 分前にホテルに PC を忘れたことに気が付き、全力で戻りました（なんのために東京に来たんだって感じですね）。ホテルが近かったので間に合い、そんなこんなでコンテストが開始しました。

 

A 問題を読むと、氷マスが最も多く連続している箇所の前または後ろの雪マスを変える場合が秒数の最小値だとわかったので、実装し、AC（9:02）。この時点で 75 位だったので割と頑張れているのでは？と感じる。

続いて B 問題。まずは 200 点を取りに行こうと考え、手元で O(N^4) くらいになるように実験をする。すると、順列を逆にした数列に対して、先頭から隣り合うものを swap していき、その度に条件を達成しているか判定する、というような方法で間に合うことがわかり、とりあえず b を AC（46:20）。C 以降を見ても無理そうなので、B に絞る。しかし、計算量を落とす方法を考え続けるも、結局わからずそのままコンテストが終了。

 

その後は、昼食を食べ、装置実装部門という名の実質 30 分椅子を温めるコンテストを終え、社内見学に行きました。社内独自の通貨があることを聞いたり、ジム・プール・ビリヤード場を見たりなど、予想外なことが沢山あって面白かったです。

戻ってくると、装置実装部門の決勝がありました。めちゃくちゃ正確に液体を運んでいて、すごいなあと思いました。懇親会では、会津合宿で関わった方々を中心に交流できました。

このあたりで順位表の凍結が溶けていたので見てみると、176 位になっていました。初めレート順になっていたときは 180 位あたりだったので、最終的にかなり妥当な順位になってしまいました…。

 

帰りの飛行機もこれまた偶然 monkukui 君と同じ便だったので、一緒に帰りました。油そば美味しかったです。

 

まとめ

ギリギリ通過でしたが、DDCC に行けてとても良い経験になりました！また、とても楽しかったです！

またオンサイトに行けるように精進したいです。

AtCoder ABC115D - Christmas

ABC 二分探索 再帰

本番通せなかった上に、再帰ではなく二分探索を用いて解いたので書いておきます。

問題概要

atcoder.jp

 

解説

1 \leq N \leq 50 より、単純に下から X 層を探索をすると間に合わないことがわかります。ここで、バーガーのレベルが上がるごとに、バーガーの全長が指数的に長くなることを考えると、二分探索で解けそうな気がしてきます。実際この問題は二分探索で解くことができて、次のように 5 つの場合に分けて考えます。 ただし、現在レベル i バーガーを見ているとし、下から X 層目の位置を考えます。また、mid はレベル i バーガーの中心のパティを指すようにします。

 

下から X 層目が、

1. i バーガーの最も下にあるバンであるとき

　二分探索を終える。
 
2. i バーガーの最も下にあるバンよりも上で、i バーガーの中心のパティよりも下にあるとき（下の i-1 バーガーに含まれるとき）

　次に mid が下の i-1 バーガーの中心を指すように、ub=mid-1, lb++ とする。
 
3. i バーガーの中心のパティであるとき

　下の i-1 バーガーすべてと i バーガーの中心のパティを食べるので、答えにそれらを加え二分探索を終える。

 4. i バーガーの中心のパティよりも上で、i バーガーの最も上にあるバンよりも下にあるとき（上の i-1 バーガーに含まれるとき）

　次に mid が上の i-1 バーガーの中心を指すように、lb=mid+1, ub-- とする。また、下の i-1 バーガーすべてと i バーガーの中心のパティを食べるので、答えにそれらを加える。

 5. i バーガーの最も上にあるバンであるとき

　i バーガーをすべて食べるので、それを答えに加えて二分探索を終える。

 

n=0 で 2, 4 の分岐に入ったときは、レベル 0 のパティを足すことに注意が必要です。

 

ソースコード

二分探索をする前に n バーガーまでのパティの含まれる数、バーガーの全長を求めておきます。 

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ll n, x; cin>>n>>x;
    vector<ll> cntP(60, 0), l(60, 0);
    cntP[0]=1, l[0]=1;
    for(int i=1; i<=n; i++){
        cntP[i]=cntP[i-1]*2+1;
        l[i]=l[i-1]*2+3;
    }

    ll lb=1, ub=l[n];
    ll ans=0;
    while(n--){ // [lb, ub]
        ll mid=(lb+ub)/2;

        if(x==lb){
            break;
        }
        else if(lb<x && x<mid){
            ub=mid-1;
            lb++;
            if(n==0) ans++;
        }
        else if(x==mid){
            ans+=cntP[n]+1;
            break;
        }
        else if(mid<x && x<ub){
            lb=mid+1;
            ub--;
            ans+=cntP[n]+1;
            if(n==0) ans++;
        }
        else if(x==ub){
            ans+=cntP[n+1];
            break;
        }
    }
    cout << ans << endl;
}

 

ICPC2018 国内予選 体験記

ICPC

昨日(7/6(金))、ICPCの国内予選がありました。
忘れないうちに書いていこうと思います。

ICPCに参加するのは今回が初でした(初めてプログラミングコンテストに参加したのが今年の1月なため)。
問題形式・提出方法の違いや、チーム戦であるなど普段のコンテストとは異なるため、色々と不安がありました。

チームはICPC出場経験のあるM1の先輩と、B3の2人で構成されていました。
基本的にM1の先輩に解いてもらい、自分で書けそうだったり、バグを発見したりしたときに交代・助言するという戦略でいこうとなっていました。


当日
部屋にあるプリンタに何故か接続できないトラブルがあったりしましたが(違うプリンタに接続できました)、16:30にコンテストが始まりました。

Aは先輩がすぐに通してくれて、BとCの考察に移りました。見た感じBが重そうだったので、先輩と僕で考察し、Cをもう1人に考察してもらいました。

Bは紙を折るたびに配列を更新すればよさそうだと考え、実装しました。しかし、高さと幅が逆になってしまったり、サンプルの3つ目のように元々紙があった場所より外に折った紙がくる場合を考えていなく、配列外参照をしたりして、バグ取りに時間がかかってしまいました。一方、Cを考察していた人が解けそうだと言っていたので、先輩にBを解いてもらっている間に僕もCを見ました。ICPCは時間制限が普段のコンテストよりも厳しくないと聞いていたので、しゃくとり法だけで通せるのでは？と考え、紙コーディングしました。その間に、Bは大まかな方針は合っていたため、開始から約1時間半で通すことができました。

そしてすぐにCに取りかかりました。紙コーディングしたものを写すだけだったので、やや実行に時間はかかったものの、約10分でACできました。自分の書いたコードが通ったときはめちゃめちゃ嬉しかったです。

残り時間が1時間ちょっとだったので、最も解ける可能性のありそうなDに取りかかることにしました。DFSでいけそうだと思いましたが、僕はそこまで実装力がないので、ここもまた先輩頼りになりました…。枝刈りも用いましたが、DFSがうまくいかず、開始から3時間経過しコンテストが終了しました。

最終的にABCの3完だったので、自分の中では頑張ったほうなのでは思いながら順位表を見ると、同じ大学の4チーム中自分たちのチーム以外の3チームがABCDの4完で、とても悔しかったです(圧倒的に自分が精進不足なので当たり前なんですが)。
あと、反省点は、Bより先にCを解くべきだったということですね…。

最後に
・ICPC対策として、AtCoder以外の問題(実装メイン)も解く
・蟻本を読んで正確にアルゴリズムを使えるようになる
などを意識しながら、来年は国内予選通過を狙えるくらい、精進しようと思いました。

また、色々とサポートしてくださったHCPCの皆様ありがとうございました！

ニュージーランド短期留学

留学

かなり短期ですが、3/3～3/14までニュージーランド(以下NZ)に留学に行ってきました。

今回が人生初めての海外で、色々な経験をしたのでまとめたいなと思います。

大学に留学体験記レポートを提出しないといけないので、その下書きとしての役割も兼ねています。


この留学は大学が提供しているプログラムの1つで、
そもそもどうして留学に行こうと思ったかというと

・英語力の向上
・コンフォートゾーンからの脱出
・生体工学について学べるプログラム
・短期間なので長期留学の疑似体験をできる

の4つが挙げられます。

それでは、早速振り返っていきます。


3/3

3日は夕方から飛行機に乗ったので、移動日でした。

空港で待ち合わせ場所についての行き違いがあり、引率の先生と中々会えずかなり焦りました。

また、NZは食品や植物に関する入国審査が厳しいと聞き、持って来ていたインスタントたまごスープを空港で捨てる羽目になりました…。

さらに、国際線の荷物検査で飲み物を持ち込めないことを知らず、お茶を捨てられました。

海外に行くときは飲食物に気を付けましょう。



羽田からNZに向かう飛行機は約11時間かかり、3日の夜発→4日の昼着という感じでした。

座席の前にタッチパネルがあり驚きました。

そのタッチパネルでは映画を見れたり、音楽を聴いたり、世界地図で今飛行機がどこを飛んでいるかを見れたりしました。

幸いにも僕が見たかった映画『君の膵臓を食べたい』があったので、それを見て泣きそうになったりしてました(浜辺美波さんが可愛い)。

初めて食べた機内食はこんな感じです。


3/4

昼頃にNZの空港に着き、宿泊施設へ向かいました。

トイレ、シャワー、冷蔵庫などもあり、思っていたよりも綺麗なところでした。


宿泊費はおよそ1万円


時系列で書いていこうと思ってましたが、既に記憶が曖昧なので、
ここからは

・見たもの
・食べたもの
・学んだこと

の3つについて書いていきます。


見たもの

みなさんはNZに対してどんなイメージを持っているでしょうか。

NZは羊がとても多く、おおよそ国民:羊=1:7だと知っていたので、勝手に自然が広がっているイメージを持っていました。

しかし実際に都市オークランドを歩くと、スカイタワーを中心にとても栄えていて驚きました。

人通りも多かったです。



一方で、都市から少し離れると自然を楽しむことができました。

週末にワイへケ島(オークランドからフェリーで約40分)に行ったのですが、そこには息を呑むほど美しいビーチがありました。

また、NZの象徴でもある羊も見ることができました。

島の景色が綺麗すぎてなんかとても不思議な感覚でした。



ワイへケ島で泊まったコテージから見える風景

都会も自然も両立していていいなぁと感じました。


あと、オークランドのシンボルでもあるスカイタワー(328m)に登りました。

聞くところによると、南半球で最も高い建物らしいです。

タワーの入り口がどこにあるか分からず、カジノに辿り着いたりもしました。



展望台からの景色


高い建物にありがちなガラス床


オークランド博物館にも行きました。

時間の都合上全部見て回ることができなかったので残念です。




食べたもの

一緒に留学に行った友達が教えてくれたのですが、NZを代表する食べ物といえばフィッシュ&チップスらしいです。

イギリスで誕生した食べ物なのですが、NZは元イギリス植民地なので、そのときに広まっていったと考えられています。

入国してすぐにフィッシュ&チップスを買ったのですが

一面茶色。

NZの洗礼を受けました。


食に関して意外だったのが、様々な国・種類の料理店があることでした。

日本食も人気らしく、「sushi」や「yakitori」の看板を街の中で見ることも多かったです。


マレーシア料理



タイ料理(多分)




ハンバーガー(1枚目はバーガーキング)




日本食


ちなみに、朝食はほぼ毎日

シリアル+牛乳とトースト+マヌカハニーのはちみつ(これも有名らしい)、そして紅茶

というような感じでした。


学んだこと

先述しましたが、生体工学について学ぶ留学プログラムでした。

生体材料やbioMEMSの導入の授業が英語で行なわれたので、それはつまり

日本語でも100%理解できないであろう内容を英語で聞く

ことを意味しています。かなりハードでした。事前にその範囲を予習していかないと太刀打ちできません。


授業は日本の学生用にアレンジされたものと、実際に現地の大学(オークランド大学)の授業に出席するものの2種類ありました。

特に後者では手も足も出ないことが多々ありました…。

ちなみにオークランド大学は世界大学ランキングではNZの中で1位らしいです。恐れ多い。





今回の経験を通して生体工学のことについて以外に学んだことが3つあります。

分かってはいましたが、1つ目に英語の重要性です。

生の英語を体験してみて、現在のスピーキング力とリスニング力ではほぼ何もできないことが明確に分かりました。

いずれ長期の研究留学をしたいなーと考えているので、英語の学習を欠かさずやっていきたいです。


2つ目に大学のシステムが大きく異なるということです。

オークランド大学の授業に出席した際感じたこととして、授業が非常にインタラクティブに行なわれていました。

日本(少なくとも自分の大学)の生徒よりも講義に集中している印象を受けました。

あと、PhDの学生は研究室ではなくプロジェクトに所属し、複数の先生を持つので、より深く勉強ができると知りました。

また、そのプロジェクト下では給与がもらえ、そのため熱心に取り組められる仕組みになっていることも学びました。


3つ目に、これが特に感じたことなのですが、外国人は非常に受容性があるということです。

これはどういうことかというと、他者を受け入れる精神が日本よりあるということです。

日本は無宗教国家であるので、宗教に対して抵抗を持つ人が少なくありません。

また、「出る杭は打たれる」というような考えが根付いているように思えます。

実際にNZではマレーシア人やオランダ人、アメリカ人など様々な国・価値観の方がともに暮らしていました。

また、外国の方はオープンであり、他者と関わるのを好む傾向にあるという印象を受けました。


まとめ

正直申し込んでからは「行くの面倒だなぁ」などと思ってたのですが、終わってみるとあっという間で、とてもいい経験になったと思います。

また、一緒に行ったメンバーや引率の先生がとても優しく、何度もサポートしてくれました。感謝しかありません。

先述しましたが、長期の研究留学をしたいと考えているので、これからはより英語の学習に力を入れて精進していきたいと強く感じました。