AtCoder Beginner Contest 113
C - ID
問題
考察
個にグループ分けされる、順序付きの
個の要素があり、グループごとに順番に番号を振って最後に与えられた順に番号を出力する。
愚直に入力をグループ分けしてまずソートして番号を振ったのち、すべての要素を合体して与えられた順にソートし直せばよい。重いけど構造体で管理しようか。
コード
struct city{ll num, pref, year; str id;}; bool comp_year(city a, city b){ return a.year<b.year; } bool comp_num(city a, city b){ return a.num<b.num; } int main(){ ll n,m; cin >> n >> m; vector<city> prefs[n]; REP(i,m){ city temp; temp.num = i; cin >> temp.pref >> temp.year; temp.pref--; prefs[temp.pref].push_back(temp); } vector<city> all; REP(i,n){ sort(prefs[i].begin(),prefs[i].end(),comp_year); ostringstream sout; sout << setfill('0') << setw(6) << i+1; str pref_str = sout.str(); REP(j,prefs[i].size()){ ostringstream sout2; sout2 << setfill('0') << setw(6) << j+1; str order_str = sout2.str(); prefs[i][j].id = pref_str + order_str; all.push_back(prefs[i][j]); } } sort(all.begin(),all.end(),comp_num); REP(i,all.size()){ cout << all[i].id << endl; } return 0; }
D - Number of Amidakuji
考察
横列、高さ
の縦棒に対して適当に横棒を入れてあみだくじをつくり、一番左から出発して
番目に到達するあみだくじの個数を求める。
動的計画法で「高さにおける左から
本目へ到達するあみだくじの横棒の置き方」をカウントしていけばよい。
から
への推移は、高さ
での横棒の置き方すべてに対して、あみだくじとして不適切なものを除いて適宜加算を行う。今回は
がキーとなる。
なお、さらに考察するとでも行ける模様。
sigma1113.hatenablog.com
コード
const ll p = 1000000007; int main(){ ll h, w, k; cin >> h >> w >> k; ll dp[h+1][w]; fill(dp[0],dp[h+1],0); REP(i,w){ if(i==0) dp[0][i] = 1; else dp[0][i] = 0; } REP(i,h){ REP(j,1<<(w-1)){ bool ignore = false; REP(l,w-2){ if(j>>l&1&&j>>(l+1)&1){ ignore = true; } } if(!ignore){ REP(l,w){ if(l!=0&&j>>(l-1)&1) dp[i+1][l]+=dp[i][l-1]; else if(l!=w-1&&j>>l&1) dp[i+1][l]+=dp[i][l+1]; else dp[i+1][l]+=dp[i][l]; dp[i+1][l] %= p; } } } } cout << dp[h][k-1] << endl; return 0; }
雑感
なぜか今回は日曜開催で、参加できず。実は水色CoderになったのでいずれにせよUnratedだったのですが。
Dは難しいですね。
ハロウィーンなのでMacの背景をスクリプトから変更する
今日はハロウィーンですね。Bingの背景がこれになってました。
以前WindowsやAndroidの背景をBingの画像に設定するアプリを紹介したのですが、Macのアプリは有料でした。
nexusuica.hatenablog.jp
今回はBingの背景画像を取り込んで背景に設定するプログラムを自前で書いてみました。
流行りのPythonで実装
Bingの背景画像は以下のURLからjson形式でフェッチできます。
このjsonから画像のURL部分を取り出し、ファイルをローカルにダウンロードしたのち、AppleScriptでMacのデスクトップの背景に設定します。実装はなんでもよかったのですがPythonでやってみました。
import json import urllib.request import subprocess from os.path import join, expanduser #ディレクトリを指定 dir = join(expanduser("~"), 'Documents/bing-wallpaper') #画像をフェッチ url = "http://www.bing.com/HPImageArchive.aspx?format=js&n=1" response = urllib.request.urlopen(url) content = json.loads(response.read().decode('utf8')) print(content['images'][0]['url']) image_url = "http://www.bing.com"+content['images'][0]['url'] date = content['images'][0]['fullstartdate'] print(image_url) filename = date+".jpg" filepath = join(dir, filename) urllib.request.urlretrieve(image_url,"{0}".format(filepath)) #背景に設定 script = """/usr/bin/osascript<<END tell application "System Events" set picture of every desktop to POSIX file "%s" end tell END""" subprocess.Popen(script%filepath,shell=True)
あとはこのスクリプトを定期的に実行させてやれば毎日画像が変わります。cronを設定してもよいのですが面倒だったのでBetterTouchToolでスリープ解除後に実行させるように設定しました。
nexusuica.hatenablog.jp
これで毎日背景に飽きません。Bingの画像は季節感もありますしクオリティが高いので良いですね。ハッピーハロウィーン！
紅葉の谷川岳に登ってきた！
関東を代表する紅葉の名所
曇りや雨が続いていた10月でしたが、先週末は久しぶりにすっきりとした晴れ予報。これはどこかに行かねばという使命感から、谷川岳に行くことを決断しました。今まで行ったことがなく一度は行きたいと思っていたので、この紅葉の時期に行かないという選択肢はありませんでした。
ただ、世の中だいたい考えることは似通っているので、週末の谷川岳は大変な混雑になると予想できました。最も混雑すると言われる紅葉の時期の晴れた週末に、どれだけ混雑を避けて行けるか、綿密な作戦を練って向かいました。
越後湯沢に前泊
マイカーで谷川岳に行く場合は、できるだけ朝早く出発すれば混雑は避けられます。ただ、マイカーだと往復とも運転しなければならないため、登山もするとなると負担が大きく躊躇してしまいます。一方で、公共交通機関のみを使って谷川岳に行くとなると選択肢がかなり狭まってきます。
谷川岳の登山口とロープウェーの駅は上越線の土合駅から徒歩20分ほどのところにあり、水上駅や上毛高原駅からバスも出ています。ただ、東京から順当に行って最も早く到着する乗り継ぎだと混雑は避けられないので、ここは裏をかいて新潟県から南下することにしました。越後湯沢駅周辺に宿泊し、始発の上り列車に乗ることで、土合駅には6:37、登山口には7時前に到着し、ロープウェーの営業開始とほぼ同時に到着することができます。今回は越後湯沢駅から徒歩5分ほどの温泉のある宿に素泊まりし、翌朝早く出発しました。
ロープウェーで一気に登る！
土合駅からロープウェーの土合口駅までは徒歩20分ほど。到着した頃にはすでにチケットを買う長い列ができていました。もっと遅かったら大変なことになっていただろうな…と想像しつつ列に並ぶも、列の進みは速く意外とすぐにチケットを買ってロープウェーに乗ることができました。朝一番はロープウェーに乗るための列は全くできていませんでした。
ロープウェーに乗り込んで見下ろすと、朝日を浴びて色づいた木々がとても綺麗でした。
天神尾根から山頂を目指す
谷川岳山頂を目指すルートとして最もポピュラーなのが、ロープウェーを降りてから天神尾根伝いに進むルート。まずはこのルートで素直に山頂に向かいました。かなり冷え込んでいたこともあり、木がは凍ってツルツルになっている部分があって怖かったです。「魔の山」谷川岳、恐るべしです。初心者向けコースとはいえ途中に岩場もあり、ナメてかかってはいけません。
山頂の1つのトマノ耳まではロープウェイから2時間半程度が目安。山頂が近づくと高い樹木はなくなって徐々に視界が開けてきて、山肌の紅葉が目に入るようになってきます。
山頂からは大絶景
谷川岳の山頂についた頃は雲ひとつない快晴。360度の大パノラマでした。
オキノ耳からは一ノ倉沢もよく見ることができ、特に紅葉が綺麗でした。
オキノ耳からトマノ耳に戻る途中、急に雲の中に入って視界が悪くなるタイミングがありました。この日は天気自体は崩れませんでしたが、山の上はこのようなこともあるので油断できませんね。
下山はスリリングな岩場
山頂からの帰り、本来はまたロープウェーに乗るつもりでしたが、時間的な余裕があったので西黒尾根から足で下山することに。ロープウェーができる前はメインで使われていた登山道ですが、急な岩場・鎖場があり、高度感があってかなりスリリングです。
山頂付近は急な岩場の連続でヒヤヒヤしっぱなし。上りよりも下りが怖いです。1時間ほどスリルに耐えきると、樹林帯に入ってひたすら進んでいきます。この樹林帯はちょうど紅葉が進んでいて気持ちが良かったです。
家に帰るまでが山行です
西黒尾根を駆け下り、土合駅まで徒歩で戻ります。時刻は12:30。まだまだ時間は余裕です。
電車が来るまで少し時間があったので、「日本一のモグラ駅」として有名なこの土合駅のモグラ具合を見ていくことにしました。土合駅の下り線のホームは地下のトンネルの中にあり、地上の改札からはなんと500段近くの階段を下っていかないと到着できません。エスカレータやエレベータはなく、頼れるのは自分の足だけです。登山の後に往復できる自信がなかったので、上から覗いて写真を撮ってみました。今度時間と体力に余裕があるときに階段を登ってみたいです。
なぜこんなことになっているのかというと、以前上越線が単線だったときは地上のホームを使っていたものの、複線化する際にトンネルを掘ったことで地下にホームを設けざるを得なくなったからです。上越線は貨物列車も多く走っている重要な幹線なので、複線化は絶対必要だったのだろうと思います。
土合駅から水上駅までは電車で10分ほど。途中ループ線を通るのが見どころです。ループ線は途中の湯檜曽駅から見ることができました。
水上駅では時間つぶしも兼ねて昼食。駅前のそば屋「くぼ田」で舞茸天ぷらのそばを頂きました。舞茸はみなかみの特産で、サクサクに揚がっていて美味しかったです。
水上駅は最近は高崎駅からSLの運行があり、以前訪問したときと比べて駅が綺麗に整備されていました。ただ駅前はまだまだ寂しい感じがあるので、これから活性化していってほしいところです。
水上駅からは上越線と吾妻線を乗り継ぎ、小野上温泉駅へ。ここで日帰り温泉「さちのゆ」に立ち寄りました。
内風呂と露天風呂、サウナの3点を揃えた入浴施設で、410円ととてもリーズナブル。泉質は弱アルカリ性でお肌すべすべヌルヌルでした。特に露天風呂が開放的で好印象でした。日曜の夕方と一番混む時間帯でしたが、東京の芋洗い状態に比べればまだまだ余裕でした。
わざわざ吾妻線に乗って小野上温泉に行ったのには理由があります。それは、臨時列車「はちおうじやまどり」に乗車するためです。「はちおうじやまどり」は「リゾートやまどり」というゴージャスな車両で運転される全車指定の臨時快速列車で、吾妻線の長野原草津口駅から高崎線・武蔵野線・中央線を経由し八王子駅まで運転されます。乗車券に加えて520円の指定席券を買えば乗車できるので、特急やグリーン車よりもお得感があり、なにより運転日も限られているのでなかなか乗れません。ちょうど日程が合ったのでこの「はちおうじやまどり」に乗って東京まで戻ります。
車内はすべて1+2列のシートで、シートピッチも非常に余裕がありました。新幹線のグリーン車よりも広かったと思います。列車内には小さな子供が遊べるプレイルームや畳のあるブースなどがあり、さらに運転席のすぐ後ろには展望スペースがあって運転士気分になれます。日曜日の夕方、マイカーであれば関越自動車道の地獄の渋滞にハマるところですが電車であればラクラク。群馬方面の外出であればまた活用したいと思いました。
この旅の締めは、立川駅の駅ナカの焼きそばでした。久しぶりに行ったのですが、ここの焼きそばが美味しいのです。
というわけで2日間かけて谷川岳に登って、寄り道しながら帰ってきました。温泉に登山、鉄道に写真撮影と自分の趣味を完全に詰め込んだ、ロマンあるものになったと思っています(笑)
温泉だけを巡る黒部峡谷の旅②：川の中に湧くワイルド過ぎる温泉
川と一体化した天然温泉へ
以前の記事の続きです。
黒部峡谷鉄道の欅平駅から歩きに歩いて、祖母谷温泉と名剣温泉に入浴しました。今回は欅平駅から戻りつつ途中にある温泉を攻略していきます。
欅平駅から2駅の鐘釣駅で下車し、15分ほど歩いて河原に降りていったところにある鐘釣温泉に向かいました。
この温泉は近くにある旅館が日帰り用に日中のみ開放しているもので、無料で利用できます。ただこの温泉、普通の温泉とは全く違うのが、川のすぐそばから温泉湧き出していて、川の水と混ざり合っているところ。河原にいくつか岩で仕切った「浴槽」があり、そこに入浴します。
テントの簡易的な男女別の脱衣所がありますが、お風呂自体は外から丸見えでさすがに裸になるのはハードルが高かったので水着で入浴しました。お湯の温度は川の水がかなり混じっているとはいえ結構温かく、体が温まりました。それ以上に、大自然に囲まれたワイルド過ぎる温泉に一人興奮してしまいました。
お風呂に入らずにただ見に来る観光客の人もいたりするので、できるだけ人がいない時間帯を狙って行くのがよさそうです（幸い、僕が行ったときは貸切状態でした）。
宇奈月温泉の源泉を目指すも…
鐘釣駅に戻ったら再びトロッコ列車に乗り、今度は黒薙（くろなぎ）駅へ。駅からは黒部峡谷ににかかる鉄橋を渡るトロッコ列車がよく見えます。
ただ、黒薙駅にやってきたのはトロッコ列車撮影の為ではなく温泉に入るため。駅から山道を20分ほど歩いたところには黒薙温泉旅館があります。ここは宇奈月温泉の源泉で、江戸末期から歴史のある秘湯の温泉旅館です。
この旅館には川沿いに大きな混浴露天風呂があり日帰り入浴も受け付けています。本当はこれに行きたかったのですが、受付時間終了(15:15)にどう頑張っても間に合わなかったので駅で下車しただけで今回は諦め…。今度北陸に行くときは絶対ここに泊まります。
富山ブランドの宇奈月温泉でシメる
黒薙駅から再度トロッコに乗り込んで、終点の宇奈月温泉駅へ。ここから地鉄電車で富山に戻る前に、宇奈月温泉でも日帰り入浴施設を探してみることに。ただ、宇奈月温泉は宿泊する旅館で温泉に入るのがスタンダードなので、有名な温泉地とはいえ日帰り入浴施設は少ないです。
そんな中、2016年に駅から徒歩すぐのところに「湯めどころ宇奈月」という施設がオープンしました。宇奈月温泉の公衆浴場的な位置づけです。今回はここに立ち寄ってみることにしました。
オープンしたてということもあり施設内のどこをとっても清潔で、デザインもモダンで明るい感じでした。温泉に関しては内風呂と露天風呂に加えていくつか小ネタが用意されていました。訪れた夕方ということもあってかガラガラでした。もし宇奈月温泉を通ることがあっても旅館には宿泊しないというときは（かなり稀なケースでしょうが）、かなりおススメです。
富山湾の寿司を食べて帰るだけ
一日でこれでもかと言うほど温泉には入ったので、あと富山でやり残したことは寿司を食べることだけです。富山の寿司は魚の鮮度が素晴らしいのです。
富山市内には星の数ほど寿司屋がありますが、一人だとわざわざ遠くに行くのも面倒なので富山駅の中に入っているお寿司屋さんで食べることにしました。「すし玉」という回転寿司店で、石川県や富山県で水揚げされた新鮮なネタがウリです。立地が良いこともあり恒常的に混雑していました。おかわりし放題のお味噌汁を飲みながら富山の白エビやホタルイカのお寿司を頂きました。
帰りは新幹線で爆睡。一日でこんなにストイックに温泉を廻ったのは初めてでした。
