房総半島を暴走

こんにちは。

前（そうだ、海に行こう - rotti_coderのプログラミング）みたいに、適当にでかけてきたので書いてみようと思います。

でかけている間、写真はなんと500枚くらいもとりました。ですから、たくさんの写真を使って書いていきます。

* *

でかけたのは、4月某日（金）です。え？学校はどうしたって？？　　

もちろんサボりました

そりゃあそうじゃないですか。新学期そうそう、毎日学校に行くなんて狂気ですよね。

普通にだるすぎます。

（ちなみに学校のお友達には、「用事があって…」と言いました）

こんなのダルいのに休んだらサボりって叩かれるんですよ。ひどい話ですよね全く。

ということでまずはここからつくば駅。

最初に、ICカードにお金をチャージします。いや、ICカードってホント便利ですよね。

今日は遠いところまででかけるつもり。ということで１万円もチャージしました。いくらなんでもこれで足りるでしょう。

つくば駅には、産総研が作ったポスターみたいなものがはられていました。

並木中等の競プロ仲間には、あまり研究に興味がない人が多いので、是非見てもらいたいものですねぇ。

…と思ったらM1の人向けでした。

そうか…そうだよなぁ、研究者になるためにはいっぱい勉強して、いい大学に入って、それからもいっぱい勉強して…ってやらないとな、真面目に勉強しないと

やべ、今日学校サボったじゃん

ってやってました。

まあ、気にせずでかけることにしましょう。TX（つくばエクスプレス）に乗ろうっと。えーと、次の快速は…

ないやんけ！

まあ別に区間快速でも遅くはないんですけど、なんか気になったので、せっかくですから常磐線に乗って東京に向かうことにします。

つくば駅から常磐線に乗るには、バスで土浦駅に行く必要があります。

つーことで、バス停へ。

さて、時刻表を確認してみます。次の土浦駅に行くバスはいつかな…

ほうほう、そんな感じになってるのね。んじゃ今の時間確認しとこっと…

あと一時間くらいバス来ないやんけ！！！！！

結局一時間くらい待ちました。

何を四天王！！！

つくば駅には当然、並木中等に行くバスもありますが、「コレに乗ったら何十分か遅れて学校に行くんだなー」と思いつつスルー。

どうでもいいけど、バスってかっこいいですよね。おっきくて。

ちなみにバスにはおじさまとおばさましか乗っていませんでした。平日のこんな時間なので当たり前体操。

そして、土浦駅に到着。

なんと、この日は一睡もしていませんでした。鬱鬱鬱鬱鬱鬱鬱鬱鬱鬱

遠くまで行くので、少しの居眠りが命取り。絶対に眠るわけには行きません。

ということでカフェインを購入。

足りなくなったら追加購入をしましょう。

特別快速があってありがたいですね。

そして朝ごはん兼昼ごはんの購入。

常磐線に乗って都会へ。

北千住で降ります。

お次は日比谷線に乗ります。

少し秋葉原に行く必要があったんでね。

日比谷線では、一番前の運転席が見える窓を独占。地下鉄は普通の電車よりも車窓が面白くないと思われそうだけど、暗いトンネルの中をライトで照らしながら走っているのを見るのもなかなかに楽しいものです。

駅が見える

秋葉原で降ります。

秋葉原で降りた理由というのは、都営新宿線に乗る、ということです。

え？？どういうことってなりますよね？？？

ぼくは、茨城住みなので、都内のオンサイトから変えるときはつくばエクスプレスの通っている秋葉原駅を必ず経由します。

で、オンサイトが開催される時、大体新宿から秋葉原まで行く、という場面があるんですよね。

普段は、総武線に乗って返っているんですけど、たまに新宿線に乗ったほうが早く秋葉原につけるというときがあるそうです。

僕は絶対ABC出るマンなので、早くつけばつくほどいいんですねぇ。

でも、新宿線は秋葉原に行くと言っても、JRやつくばエクスプレスの秋葉原駅とはちょっと遠い岩本町っていう駅につくんですよ。

所見じゃ迷ってしまう気がしてしまうので、一度くらい練習しておこうということです。

適当にあるいているとあっという間に駅を発見。なんだ、簡単ジャマイカ。

新宿線のホームはなんか暑かったです。なんでやねん！！！

新宿線って京王線と直通しているの？？すごいね。

せっかく乗ったので、新宿まで。ついでに新宿でぶらぶらしようという作戦。

さて、新宿でおさんぽ！と思いきやここで雨〜〜！！！！

バカヤロ〜〜〜！！！！

まあでもそんな土砂降りじゃないし、これから学校行くわけでもないので雨に濡れながらおさんぽ続行

新宿西口駅前と〜♪

デパートにも遊びに行きます。

つくば駅にも昔は西武があったんですけどね。４、５年前？それくらいになくなってしまいました。

西武があった頃の方が良かったなぁ…って感じがしますねぇ、ええ。

そろそろ、本命の場所に向かいます。

どこかって？そう、千葉！！！！
今日は千葉に行くためにでかけたんです！！！！！

ってことで出発！！！

と行きたいところですが、中央線の快速が来るまで時間がかかる、ってことで新宿駅の中をぶらぶら。

こんなカッコいい掲示板があるんですね。

雨の新宿駅

都会に住んでる人からすれば、見慣れた光景でしょうけど、茨城っていう田舎に住んでるぼくには面白すぎて写真をめちゃくちゃとってしまいました。

そろそろ中央線の快速に。

そして、総武線の快速に乗り換えます（御茶ノ水で総武線の各駅停車に乗り換えた）。

初めて見たんですけど、こんな感じなんですね。

各駅停車の方がかっこよくないスカ？？

まあ速けりゃなんでもいいんでとりあえず乗ります。

快速は爽快ですね。各駅停車をどんどんどんどん追い抜かしていきます！！！！！！！！！！！！！！！！！！！！！！！！！！！！

ってことで千葉に到着。

そして、ここで房総半島の周りを走る、外房線（太平洋側を走る電車）に乗ります。

シン・モハラン？？

ド田舎千葉を疾走。え？茨城も田舎だ！だって？

そうですよ！！茨城は田舎ですよ！！！！！

…あの、別に思想があるわけじゃなくて、なんとなくデッカくしただけです。びっくりしたでしょ〜。

なんと、この乗った電車、途中で止まるんですって！！！

バカヤロ〜〜〜！！！！！

ここで次の電車をホームで待つことにします。

…寒い！！！！！！！！！！！！！

ホームが寒すぎます！！！

千葉って寒いっすね。薄着で来たのも悪かったんですけど、寒すぎて死にます死ぬ死ぬ死ぬ。

あんまりにも寒くてホームで丸まってました。

そうこうしているうちに、次の電車が。アレ…？なんかさっきまでのと違う…？

まあそんなことはどうでもいいんで早く乗ります。

あったけ〜〜〜〜！！！！！！！！

そうこうしているうちに、この電車も止まってしまいました。アレレー

と思ったらすぐに反対側から折返し運転する電車が。ありがて〜〜

この電車は木更津行きらしいです。木更津…？なにか聞き覚えがありますね。

そ、競技プログラミング強い人がいる木更津高専、Twitterでよく見ていたんでね。

しばらく乗っていると海が…！

ずっと乗っているのもあれなので、海を見に行こうと途中の駅で降りました。千倉駅ってところです。

かなり房総半島の先っぽの方

かすかな波の音を頼りに海に向かいます。

み、みえた〜〜！！

晴れている方が良いきもしますが、曇りの日でもそれはそれで海は良いものです。

来てよかった！

もともと天気が悪い、というのは承知の上ででかけていました。
なぜかって？？体ダルいし疲労感半端ないし…学校に行くなんて到底考えることができなかったのと、今までも曇りの日や雨の日など天気の悪い日のお出かけは避け続けていたので、そういう日を避けるなら一度くらいは経験したほうがいいんじゃないかって言い聞かせてやってた、というわけです。

そういうわけで海辺でのんびり。

骨…？いや、これは流木。でもちょっと怖い。

海の近くにファミマがあったので、食料を調達。やきそば弁当とファミチキを購入。

ファミチキは、駅まで歩いている間に食べることにします。

てくてくと歩いていると、５時を知らせる音楽がながれてきました。

アレですよ、曲名思いつかないんですけど…、あれ、あれ…童謡です童謡。

懐かしい気持ちになった後、早く帰ろうと思いました。

なんとか駅まで帰還。房総半島の周りを走っている電車は大体一時間に一本くらいしか来ないので、これを逃すと相当痛い。

駅ではTikTokらしきものをとっているJKの二人組を発見。めっちゃ楽しそう。

それを見ると、やっぱり今日学校に行けば良かったかなぁーってちょっと思いました。やっぱり一人は淋しいものです。

ひとり寂しく焼きそばをむしゃむしゃ。あんまりおいしくない

電車に乗り遅れないように…と急いで食べていたら早く食べすぎてしまいました。せっかくなので駅の写真をパシャリパシャリ。

きれいですねぇ。せっかくならお友達と来たかったかもナ。

これって”エモい”ってやつですかね、インスタに上げたらバズっちゃうんじゃないかしら。

まぼくはTwitterしかやってないのでそんなことはしないんすけどね。

大体、インスタに”一人で！学校サボって！エモいとこ来ちゃいました〜^^”なんて言ったらインキャだとかボッチだとかブサイクとかひどいこと言われちゃいそう、そんな気がします。

Twitterやってる人のインスタに対する印象なんてそんなもんですヨ。

さて、あとは帰るだけ。房総半島の東京湾側の方を回って千葉に向かいます。

途中で三浦半島が見えました。房総半島から見えるんですね。

そこから京葉線に乗った後、武蔵野線へ。帰宅ラッシュと重なってバカみたいに混んでました。まあぼくは細いのでなんとか乗れましたけどネ。

そしてようやくTXに。やっと帰れます。

TXちゃ〜ん！！大好きだよ！！

ICカードの残金はこんな感じでした。めっちゃ使ったな…

前は茨城の県北、高萩、今回は千葉の房総半島と行ったので、次は群馬、栃木、ダ埼玉あたりにいきたいところですね。

ってことで今回はこの辺で。なんか前にかいたやつよりあまり面白くないような気もしますが、疲れてるからしょうがないネ。

あと、写真はたくさん撮ったものの、それは主に前半で、後半は疲労が爆発して疲れて写真をとれていませんでした。ちょっともったない。

写真を取るのに集中して旅が楽しめないというのも困りますが、やっぱり写真があったほうが楽しいですよね（こういうブログの見栄えも良くなるし）。

ってことでいい経験になりますた。今度は誰か一緒に行きましょう。誘っておくんなまし。

↓前
rotti-coder.hatenablog.com

そうだ、海に行こう

嫌なことが多くストレスばかり溜まる退屈な毎日に嫌気がさし、急に思い立って海に行くことにした。

土浦駅から常磐線に乗って北の方を目指すことにした。

なんかたまたま臨時列車が止まっていて、なんだこれは？？ってなってたら超高級寝台列車らしい。

いつかはこういうものを乗り回せる経済力を獲得したいものだ。

地域またげないって聞いて、ICカードどこまで使えるか不安になったのでネットで調べてみたが意外といわきより先まで使えて便利だなってなった。

この日は偕楽園に臨時で止まった。偕楽園に行くのもいいかなと一瞬思ったものの、人が多すぎてうんざりしたのでそのまま電車を乗り継ぐことに。

水戸を超えると、どんどん山が見えてきて嬉しくなってくる。

ついでに海も。

ちなみにこの日はICPCが開催されていた。
電車に乗りながら、東大つえーってやってました。

本当はいわきまでいくつもりだったけど、電車にずっと乗っているのも少し退屈だし、何より帰りの交通費が足りなくなってくるのではという心配に駆られ、高萩駅で降りることに。

地元の高校生が集まっているのを見て、一人で来た自分が虚しくなる…

が

僕は一人がいいと思って来たことを思い出し、これでいいのだと納得する。

冗談のように、文字を大きくしてしまったが、これは本当のことだ。人と遊ぶのは楽しいが、人と会うのが嫌になることも時にあるのが人間なのだ。

高萩は、田舎だけあってとても静かだ。静かだ。こんなに静かなのは久しぶりだ。来てよかったと本当に思った。そう、こういうのを僕は求めていたんだ。

駅からは山が見えるが自然と見えない海の方に向かう。なんとなく、見えてなくても海への方向はわかるのだ。

さすが生命の源の海だけある。

浜辺に来てみると人は一人としていない。夏は海水浴をしにきた人でこむんだろうなぁ…とまだ遠い夏に思いを馳せながら波打ち際に向かう。

晴れてはいるものの、さすがに冬。海からの冷たい風が体と心にしみる。

誰の足跡かな

…海を見るのは、やはりいい。

海を堪能したあとは駅に戻る。すると途中で吉野家を発見。何かが抜けて空いてしまった心と体に牛丼をつぎ込もう。

吉野家はあまり来ないので注文方法がわからなく、危うく恥をかくところだった。

一番スタンダードな普通の牛丼を頼むことにする。並盛は少ないかな…でも大盛りは多いかな…と思っていると中盛を発見。早速中盛を頼もうとする前に僕の貧乏センサーが反応。なんと大盛りと中盛の値段が同じなのだ。

迷わず大盛りを注文。

普段の僕ならこれくらい一瞬で食べてしまうのだが、この頃は食欲がなく、食べきれるか少し不安になった。

無理やりお腹にぶち込んで満腹に。

一旦駅に戻って、帰りの電車の時刻を確認する。一番早くて30分後に来るらしい。

体力的にも、山に登るのは大変そうなので、そのへんを散歩してみることに。

色々と見つかって散歩は楽しい。

僕の勝ち

駅の周りをウロウロしていると、かわいいポスターをつけたお店を発見。バイトをするならこういうところがいい。

駅に戻って帰りの電車に乗る。常磐線は個人的になかなか好きである。

帰りも行きと同じように常磐線一本で土浦まで帰ってもいいが、それはちょっとつまらないのではなかろうか。
そういうことで別ルートを開拓することにする。

水戸を通らないことで有名な水戸線に取手駅から乗車する。

電車内には通学途中のスヤスヤJK、楽しそうな老夫婦、お酒グビグビよっぱらいおっさん、ヘンテコなクソガキしかいなく、とても平和。

なかなかに景色のよいところを走る。非常に楽しい。

もう少し乗っていたいという衝動を抑えるのに苦労したが、お金がないと無理やり自分に言い聞かせ涙目で下車。

関東鉄道常総線に乗ることにする…ところがここでハプニング発生。

ご存知の方も多いと思うが、現在SuicaとPasmoは半導体不足という名目のもと、販売を中止している。困ったものだ。
つまり、最近になって新しいICカードがほしいとなると、JR東海やJR西日本などに出向いてTOICAやICOCAを購入する必要があるのだ。
かわいそうな少年ロッチはなんとわざわざ一人で名古屋まで出向いてTOICAを購入し、愛用していたのだが、なんと関東鉄道常総線はTOICAを使用することができないのだ

ふざけんなーーーーーーーーーーー！！！！！！！！！！！！！！！

しかも、関東鉄道常総線はJRではないため、

１　下館駅に入場する←ICカードをピッ
２　下館駅の中にある関東鉄道常総線の改札を通ろうとする
３　TOICAは使えないと怒られる
４　急いで下館駅の改札を出る←ここで入場料が取られる！
５　きっぷを購入する
６　下館駅の改札を通過する
７　下館駅内の関東鉄道常総線の改札を通過する
８　やっと電車に乗れる

…というクソめんどくさいことをしなければならなく、あやうく乗り遅れるところだった（しかも入場料余分に取られたし…）。

そして、電車が発車する前から二度と関東鉄道常総線には乗らないと決意をしたのだが、走り出してからその決意は壊れた。

…なかなかに車窓がいい。

なんというか、趣があるのだ。いや、何が趣なのかよく理解していないというのが正直なところなのだが、結構雰囲気がいいのだ。

どこまでもまっすぐ続く一本の線路、遮るものは何もない。電車は僕一人だけを載せ、走っていく。

ふと窓から横を見ると、畑やら田んぼしかない。都会に住んでいると見えない地平線がよく見える。

ガタゴトガタゴト…電車は動く…

結構運賃が高かったので、たぶんもう二度と乗らないと思うけど、一度くらいは乗ってみてもいいと思った。是非みなさんも機会があれば乗ってみてください。

…そういうわけで、海だけを見に行く僕の旅は終了したのだ。さて、ABCのために走って帰りますかと。タッタッタッタッ…

街頭のない暗い道に軽快な足音が響き渡った…

ABC342 A~E問題

atcoder.jp

スポンサーがHUAWEIでしたね。

A問題　Yay!

mapを使えばあっという間に実装終了。

#include <bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  map<char,int>dict;
  cin >> s;
  for(int i=0;i<s.size();i++){
    if(dict.count(s[i])==0)dict[s[i]]=1;
    else dict[s[i]]++;
  }
  for(int i=0;i<s.size();i++){
    if(dict[s[i]]==1)cout << i+1 << endl;
  }
  return 0;
}

B問題　Which is ahead?

人iが前から何番目にいるかを格納する配列を作ってo(1)でアクセスできるようにすれば通ります。

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<int>p(n);
  for(int i=0;i<n;i++)cin >> p[i];
  vector<int>num(n);
  for(int i=0;i<n;i++)num[p[i]-1]=i+1;
  int t;
  cin >> t;
  int a,b;
  for(int q=0;q<t;q++){
    cin >> a >> b;
    if(num[a-1]<num[b-1])cout << a << endl;
    else cout << b << endl;
  }
  return 0;
}

C問題　Many Replacement

mapをうまいこと使えば解けるんですねぇ。

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin >> n;
  string s;
  cin >> s;
  map<char,char>dict;
  map<char,vector<char>>dict2;
  for(int i=0;i<n;i++)dict[s[i]]=s[i];
  set<char>st;
  for(int i=0;i<n;i++)st.insert(s[i]);
  for(auto itr=st.begin();itr!=st.end();++itr)dict2[*itr].push_back(*itr);
  int t;
  char a,b;
  cin >> t;
  for(int q=0;q<t;q++){
    cin >> a >> b;
    if(a==b)continue;
    for(int i=0;i<dict2[a].size();i++){
      dict2[b].emplace_back(dict2[a][i]);
      dict[dict2[a][i]]=b;
    }
    dict2[a].clear();
  }
  for(int i=0;i<n;i++)cout << dict[s[i]];
  cout << endl;
  return 0;
}

D問題　Square Pair

素因数分解して、それぞれの因数の個数を2で割ったときのあまりが完全に等しい値同士をかけてあげると平方数になります。
あと０は何をかけても平方数になることに注意です。

https://atcoder.jp/contests/abc342/submissions/50588801#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}
int main()
{
  int n;
  cin >> n;
  vector<long long>a(n);
  for(int i=0;i<n;i++)cin >> a[i];
  map<vector<long long>,long long>dict;
  set<vector<long long>>st;
  vector<long long>ans;
  long long count=0;
  for(int i=0;i<n;i++){
    if(a[i]==0){
      count+=1;
      continue;
    }
    ans.clear();
    vector<pair<long long,long long>>num=prime_factorize(a[i]);
    for(int ipp=0;ipp<num.size();ipp++){
      if(num[ipp].second%2==0)continue;
      ans.emplace_back(num[ipp].first);
    }
    sort(ans.begin(),ans.end());
    if(st.count(ans)==0){
      st.insert(ans);
      dict[ans]=1;
    }
    else dict[ans]++;
  }
  long long ans2=0;
  for(auto itr=st.begin();itr!=st.end();++itr){
    if(dict[*itr]==1)continue;
    ans2+=dict[*itr]*(dict[*itr]-1)/2;
  }
  if(count>=1){
    ans2+=(n-count)*count;
  }
  if(count>=2)ans2+=count*(count-1)/2;
  cout << ans2 << endl;
  return 0;
}

E問題　Last Train

後ろからダイクストラをすればよいです。
本番でペナをつけずに一発で通せて嬉しかったです。

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,m,a;
  cin >> n >> m;
  vector<vector<long long>>train;
  vector<vector<int>>graph(n);
  vector<long long>hako2;
  for(int i=0;i<m;i++){
    hako2.clear();
    for(int ipp=0;ipp<6;ipp++){
      cin >> a;
      hako2.emplace_back(a);
    }
    train.push_back(hako2);
    graph[hako2[5]-1].emplace_back(i);
  }
  vector<long long>amount(n,-1);
  amount[n-1]=4e18;
  int iti=0,hako;
  priority_queue<pair<long long,int>>prq;
  prq.push(make_pair(2e18,n));
  while(prq.size()>0){
    hako=prq.top().second;
    prq.pop();
    for(int i=0;i<graph[hako-1].size();i++){
      hako2=train[graph[hako-1][i]];
      if(amount[hako-1]<hako2[0]+hako2[3])continue;
      if(amount[hako2[4]-1]>=min(hako2[0]+(hako2[2]-1)*hako2[1],(amount[hako-1]-(amount[hako-1]-hako2[0]-hako2[3])%hako2[1])-hako2[3]))continue;
      amount[hako2[4]-1]=min(hako2[0]+(hako2[2]-1)*hako2[1],(amount[hako-1]-(amount[hako-1]-hako2[0]-hako2[3])%hako2[1])-hako2[3]);
      prq.push(make_pair(amount[hako2[4]-1],hako2[4]));
    }
  }
  for(int i=0;i<n-1;i++){
    if(amount[i]==-1)cout << "Unreachable" << endl;
    else cout << amount[i] << endl;
  }
  return 0;
}

僕の提出
https://atcoder.jp/contests/abc342/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=rotti

半分全列挙

その名の通り、半分ずつ全列挙するアルゴリズムです。

早速、どんな問題で使えるかです。

問題

N個の商品があります。
i個目の商品の値段はAi円です。
何個かの商品を買うとき、ちょうどぴったり値段の合計がX円になる組み合わせはありますか？
もしあるなら買う商品の番号も出力してください。

制約
1<=n<=40
1<=A[i]<=1e9

実行時間は2sec以内

みたいな問題とか。

半分全列挙を知らなければ、パット見、bit全探索でときたいな…となるかもしれません。
しかし、単純なbit全探索だと最大で計算量が2^40となってしまい、間に合いません。

半分全列挙

このときに半分全列挙で解くことができます。
半分全列挙はbit全探索と対して変わりません。

…というのも、例えば商品の個数が40個あったとき、一度に全探索しようとすると計算量が2^40になってしまいますが、半分ずつ、20個ずつ全探索すれば計算量が2^20*2となり、実行時間に間に合わせることができます。

Bit全探索ができるのなら、半分全列挙の実装もそこまで難しくはないと思います。

AOJにちょうどいい問題があります
onlinejudge.u-aizu.ac.jp

使うコインの枚数が決められているのが少々やっかいですが意外と少しコードを足すだけで大丈夫です。
半分全列挙を使わないで単純な全探索で通る（例えばN<=20）の場合は普通のBit全探索で通したほうが実装が楽になります。

#include<iostream>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
int main()
{
  int n,k;
  long long l,r;
  cin >> n >> k >> l >> r;
  vector<long long>a(n);
  for(int i=0;i<n;i++)cin >> a[i];
  if(n<=20){
    long long ans=0;
    for(int tmp=0;tmp<(1<<n);tmp++){
      bitset<20>s(tmp);
      int cnt=0;
      for(int i=0;i<n;i++)if(s[i])cnt++;
      if(cnt!=k)continue;
      long long count=0;
      for(int i=0;i<n;i++)if(s[i])count+=a[i];
      if(l<=count && count<=r)ans++;
    }
    cout << ans << endl;
    return 0;
  }
  vector<vector<long long>>num(21);
  for(int tmp=0;tmp<(1<<20);tmp++){
    bitset<20>s(tmp);
    int cnt=0;
    long long count=0;
    for(int i=0;i<n;i++)if(s[i])cnt++;
    for(int i=0;i<20;i++)if(s[i])count+=a[i];
    num[cnt].emplace_back(count);
  }
  for(int i=0;i<21;i++)sort(num[i].begin(),num[i].end());
  long long ans=0;
  for(int tmp=0;tmp<(1<<(n-20));tmp++){
    bitset<20>s(tmp);
    int cnt=0;
    long long count=0;
    for(int i=0;i<(n-20);i++)if(s[i])cnt++;
    if(cnt>k || k-cnt>20 || num[k-cnt].size()==0)continue;
    for(int i=0;i<(n-20);i++)if(s[i])count+=a[i+20];
    int left=-1,right=num[k-cnt].size(),mokuteki;
    while(left+1!=right){
      mokuteki=(left+right)/2;
      if(num[k-cnt][mokuteki]+count<l)left=mokuteki;
      else right=mokuteki;
    }
    int hako=right;
    left=-1,right=num[k-cnt].size();
    while(left+1!=right){
      mokuteki=(left+right)/2;
      if(num[k-cnt][mokuteki]+count>r)right=mokuteki;
      else left=mokuteki;
    }
    ans+=(right-hako);
  }
  cout << ans << endl;
}

提出結果
onlinejudge.u-aizu.ac.jp

ABC197F

atcoder.jp

問題文を言い換えます。

"""
最初は頂点１と頂点Nにコマが一つずつ置かれています。

一回の行動で、２つのコマを辺を使って同時に移動させます。

ただし、どちらも同じアルファベットのかかれた辺を使う必要があります。
"""

ここがわかればもう解けたも同然！（だよね…？）

結構簡単なBFSの実装で通りま〜す

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,m,a,b,iti=0;
  char s;
  cin >> n >> m;
  vector<vector<pair<int,char>>>graph(n);
  for(int i=0;i<m;i++){
    cin >> a >> b >> s;
    graph[a-1].push_back(make_pair(b,s));
    graph[b-1].push_back(make_pair(a,s));
  }
  vector<vector<int>>dp(n,vector<int>(n,1e9));
  dp[0][n-1]=0;
  vector<pair<int,int>>stack;
  stack.push_back(make_pair(1,n));
  int ans=1e9;
  while(stack.size()>iti){
    a=stack[iti].first;
    b=stack[iti].second;
    for(int i=0;i<graph[a-1].size();i++)for(int j=0;j<graph[b-1].size();j++){
	if(graph[a-1][i].second!=graph[b-1][j].second)continue;
	//交差する場合
	if(graph[a-1][i].first==b && graph[b-1][j].first==a)ans=min(ans,dp[min(a,b)-1][max(a,b)-1]+1);
	if(dp[min(graph[a-1][i].first,graph[b-1][j].first)-1][max(graph[a-1][i].first,graph[b-1][j].first)-1]<=dp[min(a,b)-1][max(a,b)-1]+2)continue;
	dp[min(graph[a-1][i].first,graph[b-1][j].first)-1][max(graph[a-1][i].first,graph[b-1][j].first)-1]=dp[min(a,b)-1][max(a,b)-1]+2;
	stack.push_back(make_pair(graph[a-1][i].first,graph[b-1][j].first));
      }
    iti++;
  }
  for(int i=0;i<n;i++)ans=min(ans,dp[i][i]);
  if(ans>=1e9)cout << -1 << endl;
  else cout << ans << endl;
  return 0;
}

ABC194E問題

公式の解説に載ってなかったので。

atcoder.jp

まず、優先度つきキューなどに、配列Aに含まれていない要素（MEXになりうる数）を入れます。

優先度つきキューは、入っている要素の中の最小値を高速で取り出すことができるので、これでMEXを高速で求めることができます。

また、multisetなどに、配列Aをそのまま入れます。

その後はimos法の要領で、multisetなどにどんどん要素を追加したり削除したりします。

その時は、multisetをいい感じに操作します。

まず、削除する時は、multisetから一つだけ削除します。そして、multisetに含まれているその要素の数がもし0になった場合は、優先度つきキューにその要素を入れます。
追加するときは、multisetに追加するだけで優先度つきキューには何の操作もしません

これでは、ただ優先度つきキューから最小値を取り出してもただしいMEXにならない場合があるので、ちゃんと工夫をします。

MEXを求める時、優先度つきキューから最小値を取り出しますが、もしそれがmultisetに含まれている場合は優先度つきキューから削除し、もう一回最小値を取り出す…というのをmultisetに含まれていない数値が出るまで繰り返します。

こうしてMEXを求めることができます。

multisetに含まれているかどうかをmultisetで確認すると、いくら平衡二分木でも同じ要素が大量に入っていた時などは実行時間がかかるようなので、判定をする用のsetを用意しておくと通ります。

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,m,hako;
  cin >> n >> m;
  vector<int>a(n);
  for(int i=0;i<n;i++)cin >> a[i];
  priority_queue<int,vector<int>,greater<int>>prq;
  multiset<int>st;
  set<int>st2;
  for(int i=0;i<m;i++)st.insert(a[i]),st2.insert(a[i]);
  for(int i=0;i<n+10;i++)if(st2.count(i)==0)prq.push(i);
  int ans=1e9;
  for(int i=m;i<n;i++){
    hako=prq.top();
    while(st2.count(hako)>0){
      prq.pop();
      hako=prq.top();
    }
    ans=min(ans,hako);
    auto itr=st.find(a[i-m]);
    st.erase(itr);
    if(st.count(a[i-m])==0)prq.push(a[i-m]),st2.erase(a[i-m]);
    st.insert(a[i]);
    st2.insert(a[i]);
  }
  hako=prq.top();
  while(st2.count(hako)>0){
    prq.pop();
    hako=prq.top();
  }
  cout << min(ans,hako) << endl;
  return 0;
}

atcoder.jp

ABC341 A~E問題

F問題あともうひと押し…

atcoder.jp

A問題　Print 341

1010.....1みたいに出力すればいいです。

n=int(input())
for i in range(n):
  print("10",end='')
print("1")

B問題　Foreign Exchange

それぞれの国で両替をできるだけ行うという貪欲で解けます。

n=int(input())
a=list(map(int,input().split()))
for i in range(n-1):
  x,y=map(int,input().split())
  a[i+1]+=(a[i]//x)*y
print(a[n-1])

C問題　Takahashi Gets Lost

全探索で通ります。
陸地である地点全てから行動をして、途中で海にはみださなかった時、その最終地点が現在いる地点として考えられるものです。
Pythonだと、下手な書き方をすると間に合わないらしいですね。

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int h,w,n,a,b,ans=0;
  bool check=true;
  cin >> h >> w >> n;
  string s;
  cin >> s;
  vector<vector<char>>rotti(h,vector<char>(w));
  for(int i=0;i<h;i++)for(int ipp=0;ipp<w;ipp++)cin >> rotti[i][ipp];
  for (int i=0;i<h;i++){
    for(int ipp=0;ipp<w;ipp++){
      if(rotti[i][ipp]=='#')continue;
      a=i;
      b=ipp;
      check=true;
      for(int k=0;k<n;k++){
	if(s[k]=='U'){
	  if(a==0 || rotti[a-1][b]=='#')check=false;
	  else a--;
	}
	else if(s[k]=='R'){
	  if(b+1>=w || rotti[a][b+1]=='#')check=false;
	  else b++;
	}
	else if(s[k]=='D'){
	  if(a+1>=h || rotti[a+1][b]=='#')check=false;
	  else a++;
	}
	else if(s[k]=='L'){
	  if(b==0 || rotti[a][b-1]=='#')check=false;
	  else b--;
	}
	if(check==false)break;
      }
      if(check)ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

D問題　Only one of two

Nの約数の個数、Mの約数の個数、NとMの最小公倍数の個数がわかれば、包除原理で求めることができます。
ですから二分探索で通ります。

#include <bits/stdc++.h>
using namespace std;
long long kouyaku(long long a,long long b){
  while(a>0 && b>0){
    if(a<b)b=b%a;
    else if(a==b)return a;
    else a=a%b;
  }
  return max(a,b);
}
long long koubai(long long a,long long b){
  return a*b/kouyaku(a,b);
}
int main()
{
  long long n,m,k;
  cin >> n >> m >> k;
  long long count=koubai(n,m);
  long long left=min(n,m),right=9223372036854775807,mokuteki;
  while(left+1!=right){
    mokuteki=(left+right)/2;
    if((mokuteki/n+mokuteki/m-(mokuteki/count)*2)<k)left=mokuteki;
    else right=mokuteki;
  }
  cout << right << endl;
  return 0;
}

E問題　Alternating String

セグメントツリーや平衡二分木などで、任意の区間に同じ番号が連続している地点があるかどうかを高速で求めることができるようにすればよいです。

#include <bits/stdc++.h>
using namespace std;
class seguki{
public:
  //1index
  vector<int>num;
  int siz=1;
  void init(int n){
    while(siz<n)siz*=2;
    for (int i=0;i<siz*2+1;i++)num.emplace_back(0);
  }
  void update(int a,int b){
    a=siz+a-1;
    num[a]=b;
    a/=2;
    while(a>=1){
      num[a]=num[a*2]+num[a*2+1];
      a/=2;
    }
  }
  void henkou(int a,int b){
    a=siz+a-1;
    num[a]+=b;
    num[a]%=2;
    a/=2;
    while(a>=1){
      num[a]=num[a*2]+num[a*2+1];
      a/=2;
    }
  }
  int sm_num(int l,int r,int a,int b,int u){
    if(r<=a || b<=l)return 0;
    else if(l<=a && b<=r)return num[u];
    int m=(a+b)/2;
    int L=sm_num(l,r,a,m,u*2);
    int R=sm_num(l,r,m,b,u*2+1);
    return L+R;
  }
};
int main()
{
  int n,t,a,l,r,hako;
  cin >> n >> t;
  string s;
  cin >> s;
  seguki rotti;
  rotti.init(n);
  for (int i=0;i<n-1;i++)if(s[i]==s[i+1])rotti.update(i+1,1);
  for(int q=0;q<t;q++){
    cin >> a >> l >> r;
    if(a==1){
      if(l!=1){
	rotti.henkou(l-1,1);
      }
      if(r!=n){
	rotti.henkou(r,1);
      }
    }
    if(a==2){
      hako=rotti.sm_num(l,r,1,rotti.siz+1,1);
      if(hako==0)cout << "Yes" << endl;
      else cout << "No" << endl;
    }
  }
  return 0;
}