うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

TOJ Extra Problems Contest #1

これはなに

大学で学部 2 年生向けの C 言語の実習授業の TA をしていて、そこで普通の課題だと物足りないプロ向けに extra 問題を作って置いといたやつです（もちろん、成績には反映されない本当にただのおまけです）（一部改題しています）。
ジャッジシステムは学内からしかアクセスできないので、ジャッジは公開していません。

難易度はどれも ABC-D 前後だと思います。
答えが知りたい方は @rian_tkb とかいう人が twitter で解法を呟いていたりするので探していただいても良いですし、近いうちに解説記事も書くと思います。
半分くらい手で写しているので、間違っていそうなところがあったら教えてください。

twitter.com

ちなみに、受講生は以下の言語縛りで解いて（解かされて）いました。

  • C89 に 1行コメント（// ... ）と long long型 を足したもの（GCC 拡張は使用不可）



A - Counting Triangles

実行時間制限 : 1 sec

問題文

入力された正整数 {X} に対して、以下の 2 つの値を半角スペース区切りで出力してください。

  • 全ての辺の長さが正整数かつ一番長い辺の長さが {X} であるような三角形の個数
  • 全ての辺の長さが正整数かつ互いに異なり、一番長い辺の長さが {X} であるような三角形の個数

ただし、回転させたり反転させたりすることで同じ三角形となるものは重複して数えないものとします。

入力

X

制約

  • {1 \le X \le 2 \times 10^9}

出力

  • 入力された整数に対応する 2 つの値を半角スペース区切りで出力してください。

入出力例

入力例 1:

1

出力例 1:

1 0

入力例 2:

5

出力例 2:

9 2

入力例 3:

987654321

出力例 3:

243865264941319921 243865263459838440



B - Contiguous Sum

実行時間制限 : 1 sec

問題文

正整数 {N} に対し、和が {N} になる連続した {1} 以上 {N} 未満の整数の組合せを全て出力してください。

入力

T
(case_1)
(case_2)
:
(case_T)

  • 入力は {T} 個のケースからなり、各ケースでは整数 {N} が与えられます。

制約

  • {1 \le T \le 1{,}000}
  • 各ケースに対し、
    • {2 \le N \le 10^8}

出力

  • 各ケースの答えを改行で区切って出力してください。
    • それぞれの解は、{\displaystyle \sum_{k=l}^{r}k = N} なる {(l, r)} に対し、 l-r という形で出力してください。
      • 解が複数ある場合は、 {l} の小さい順に出力してください。
      • 解が存在しない場合は何も出力しないでください。

入出力例

入力例 1:

3
27
8
9

出力例 1:

2-7
8-10
13-14
2-4
4-5

入力例 2:

1
99999999

出力例 2:

309-14145
592-14154
4999-14999
5002-15000
6539-15580
9877-17249
10224-17450
11669-18334
18347-23164
19859-24379
28337-31669
31672-34685
39319-41784
40307-42715
43894-46115
54097-55914
61464-63069
65604-67110
75447-76760
80487-81719
89454-90564
109557-110465
121244-122065
124132-124934
151879-152535
164714-165319
228092-228529
243104-243514
329882-330184
364827-365100
456512-456730
494949-495150
504952-505149
684859-685004
729859-729995
990049-990149
1010052-1010150
1369827-1369899
1515119-1515184
3030287-3030319
4545444-4545465
5555547-5555564
9090904-9090914
11111107-11111115
16666664-16666669
33333332-33333334
49999999-50000000



C - Dividing Combination

実行時間制限 : 1 sec

問題文

{{}_N \mathrm{C}_K} が整数 {P \ (P \ge 2)} で何回割れるかを求めてください。
より正確には、{P^X \mid {}_N \mathrm{C}_K \ \land \ P^{X + 1} \nmid {}_N \mathrm{C}_K} を満たすような非負整数 {X} を求めてください。

入力

T
(case_1)
(case_2)
:
(case_T)

  • 入力は {T} 個のケースからなり、各ケースでは整数 {N, K, P} がこの順に半角スペース区切りで与えられます。

制約

  • {1 \le T \le 2{,}000}
  • 各ケースに対し、
    • {0 \le K \le N \le 10^9}
    • {2 \le P \le 10^9}

出力

  • 各ケースの答えを改行で区切って出力してください。

入出力例

入力例 1:

6
5 3 5
5 3 10
18 4 6
0 0 2
1000000000 1000000 24
1000000000 500000000 998244353

出力例 1:

1
1
2
0
3
1



D - Palindromic Numbers

実行時間制限 : 1 sec

問題文

{L} 以上 {R} 以下の整数のうち、十進法における回文数であるような整数の個数を求めてください。

入力

T
(case_1)
(case_2)
:
(case_T)

  • 入力は {T} 個のケースからなり、各ケースでは整数 {L, R} がこの順に半角スペース区切りで与えられます。

制約

  • {1 \le T \le 10{,}000}
  • 各ケースに対し、
    • {0 \le L \le R \le 10^{16}}

出力

  • 各ケースの答えを改行で区切って出力してください。

入出力例

入力例 1:

6
0 100
101 101
12345 67890
1234333 1234999
99999999 9999999999999999
0 10000000000000000

出力例 1:

19
1
555
0
199980001
199999999

立命館大学競技プログラミング合宿2019 (RUPC2019) 参加記 part 1

RUPC


どうしてあんなことになってしまったのか


2/17 (day -16)

この日は日経コンがありました。

懇親会が超大人数でヤバかった

ここでせいかしゃんとめるしゃんから、RUPC day2 でコスプレしてチームを組まないか、というお誘いを受ける。この日本語わけわからないな
（これは重要なことなのですが、誘われたからやっただけなので riantkb は何にも悪くないです（？））

念の為 Amazon で検索をしてみる riantkb


2/19 (day -13)

通常配送を利用した場合、最短で 2/28~3/7 のお届け予定です。

これ、いま注文してもワンチャン間に合わなくないか、となり、とりあえず思考を止めて注文ボタンを押す


2/22 (day -10)

往路と宿を確保する（宿については漫喫とかでも良いかなぁと思っていたんですが、コスプレをするならさすがにホテルを取ったほうが良さそうという気持ちになり）


2/26 (day -6)

衣装が届く。思ったより早く届いてよかった
思ったよりスカートの丈が短くて困る。

あとこれも買いました
https://www.amazon.co.jp/dp/B079QGXKWT


3/4 (day 0)

荷造りをして出家する



TL にせいかしゃんとめるしゃんがいたので、一応なんとなく伝わるようにツイートをする

二人からやる感じの雰囲気を感じたので覚悟を決める


3/5 (day 1)

夜行バスに乗り、朝8時に京都に着く

せいかしゃんとふぇりんくんと銭湯に入る


コンテストの中身はぐってぃさんの記事をみると良いと思います
pomupomu.hatenadiary.jp

D がこれで死んでいたのと、G のグラフを構築し切れなかったのが痛かった…

夜行バスのせいで疲労が溜まっていたのでホテルに着いたら即寝た


3/6 (day 2)

前日寝落ちしたので、5時半に起きる
ウィッグの髪が長くてボサボサになることが目に見えていたので、ウィッグオイルと櫛とヘアワックスでなんとかしようと頑張る（でも結局荷物に詰めて立命まで行く間にボサボサになってしまった、かなしい）
2時間くらいかけてなんとか納得いく感じになった写真がこれでした（会場で着たときは用意する時間が eps しかなかったため、おそらくこの写真のときの方がクオリティが高い、かなしい）


会場での様子（完全にやばいチームですねこれは）


コンテストは J で誤差に殺されてもっと他に何も考えられないくらい競プロのことを考えなくちゃいけなかった雛鶴あいになった




この日は懇親会があったんですが、ブラックニッカのせいで記憶が飛びました、やばい
（めっちゃ陽気だったらしいです）（まぁ酔うとだいたいそんな感じになるのでわかる）
皆様に迷惑をかけてなかったら良いのですが…







本当に全く記憶がない

めっちゃ「わかるなぁ〜」って言っていたらしい



ここら辺は記憶が戻り次第追記するかもしれません（これは罠で、失った記憶は戻らない）


3/7 (day 3)

二日酔いで死んでいたんですが、集合時間から20分遅れくらいでなんとか会場にたどり着きました








コンテストは D と E で色々バグってしまい大変だった





解散後は音ゲー勢とにぼからのゲーセンに行きました



色々な人（主にらてあさん）とめっちゃ色々音ゲーをした
f:id:riantkb:20190309001936j:plainf:id:riantkb:20190309002007j:plainf:id:riantkb:20190309002013j:plainf:id:riantkb:20190309002017j:plainf:id:riantkb:20190309002023j:plainf:id:riantkb:20190309002027j:plain



そのあと21時すぎに京都駅から新幹線に乗ったんですが、こいつ次の日の朝9時半羽田発の飛行機に乗って石川まで学会に行かなきゃいけないんだよなぁ




まとめ

RUPC2019 めっちゃ楽しかったです。雛鶴あいのクオリティはもう少し上げていきたいですね（？）
来年はいけるかわからんけど行けたら行きたい



RUPC2019 参加記 part 2 (day 4 - day 6) に続く

IQ1 の一人暮らし（引越し編）

IQ1

この記事は「IQ1 Advent Calendar 2018」の 20日目の記事です。もうすぐ 2018年も終わりですね。
adventar.org

あらすじ

この前の記事で卒論時期の限界っぷりをみていただきましたが、
rian.hatenablog.jp

「こいつ、大学のそばに家を借りるべきでは……？」と思った人もいるはずです。まぁ私なんですが。

というわけで、晴れて大学院に進学できたのを機に、大学のそばに家を借りて一人暮らしを始めた、という話です。

4月中旬

家を決める。
ちなみに家を探す際は1月下旬までか4月入ってからがオススメです（2, 3月は大大大人気なので）。

5月1日

入居。



大学からめっちゃ近い



ダンボールは優秀

5月3日

カーシェアで車を借りて、実家から荷物を移す。


5月4日

ニトリで色々買い物をし、けっこう人間的になってくる。
なお、机が届くのは10日後なのでそれまではダンボール机です。


洗濯機と冷蔵庫も買う。


5月7日

新居で初の飲み会が行われる。


多分この日に冷蔵庫洗濯機が届いたんじゃなかったかなぁ

5月11日

一人暮らしにより飢えるタイプのおたく。

5月14日

まだダンボール。

5月15日

ネット回線とこたつを得てめっちゃ人間的になる。


5月19日

モニタを買う。

これは料理です。

5月20日

麻雀牌が届く。

これも料理です。

5月24日

麻雀。



その他


よくある


よくある


まとめ

IQ1 でもなんとか生き延びるくらいはできる。


IQ1 の一人暮らし（生活編） に続きます（ほんまか？）

IQが1なので計画的に卒論が書けない

IQ1

この記事は「IQ1の2まいめっ Advent Calendar 2018」の 18日目の記事です。
adventar.org



IQが1なので学士論文研究で1週間で100万円溶かす。


2017年11月上旬

学士研究でやることが大体決まる。
なぜか1月中旬に英語でポスター発表をすることになる。

2017年11月中旬

ポスターのアブストを submit する。
全く何も成果が出ていない、ないことないことを書く。

2017年11月下旬

実装を頑張る。

2017年12月上旬

めっちゃ実装を頑張る。

2017年12月中旬

卒論スケジュールが提示される

  • 年内中　目次を作ってみる
  • 1月　卒論を書く
    • 1/10　第1稿締切
    • 1/18　第2稿締切
    • 1/25　第3稿締切
  • 2/1　論文題目・100字概要提出
  • 2/2　卒論提出
  • 2/13-14　卒論発表


さて問題です、りあんさんの実際のスケジュールはどんな感じになるでしょうか？？？


2017年12月下旬

めっちゃめっちゃ実装を頑張る。
（目次さん……どこ……？）

2018年1月7日

めっちゃめっちゃめっちゃ実装を頑張った結果、なんとか実装が終わる。
ポスター用の実験を回し始める。
実験結果は全く出ていないがとりあえずポスターを作り始める。











2018年1月10日

卒論を書き始める。
卒論進捗：191 KB（17 ページ）






2018年1月11日

出てきた実験結果がそこそこ悪くない感じで、希望が見えてくる。





2018年1月12日

実験結果を回収しながらめっちゃポスターを書いていた気がする。



2018年1月15 - 17日

学会に行きポスター発表をする。
疲れる。





2018年1月18 - 20日

燃え尽きてお布団に倒れこむ。
そろそろ本格的に進捗がやばくなってくる。




2018年1月22日

卒論進捗：284 KB（23 ページ）
え、これ普通にどう考えてもやばくない？？？






2018年1月24日 14時

卒論進捗：308 KB（27 ページ）
こりゃもう（客観的に見て）ダメでしょ



2018年1月24日 23時

f-node ジョブを 1530 個投げる。
ちなみに東工大のスパコン TSUBAME には、計算ノードは 540 個しかないです。



2018年1月25日 17時

自分のジョブが 400 並列で走る。





2018年1月26日 10時

new 2018.1.26 10:10 本日、0:32ごろに水冷クーリングラックで漏水センサーが反応し、7:39にRack1において漏水を確認したため、最小単位となる計算ノード72台を緊急停止しました。これらのノードで稼働中のジョブが強制終了されております。詳細は後ほどお知らせに掲載します。


私、魔女のキキです。こっちは卒業の危機。


2018年1月26日 18時

強制終了の被害を調べていたらジョブにミスを発見して、全ケース投げなおしになる。

私、魔女のキキです。こっちは卒業の危機（2nd season）。


2018年1月26日 22時

卒論進捗：623 KB（34 ページ）
えーっと、第3稿締切って知っていますか



2018年1月27日 15時

少しケースを削って、1170 ジョブ投げる。





2018年1月29日 3時

卒論進捗：897 KB（38 ページ）





2018年1月29日 23時

卒論進捗：1.0 MB（43 ページ）






2018年1月31日 17時

卒論進捗：1.0 MB（45 ページ）

ここで初めてボスに卒論を見せる（！？！？！？）
つまりこれが初稿です。






2018年2月1日 9時

卒論進捗：1.8 MB（68 ページ）
付録に無限に実験結果を載っけた結果、ページ数が爆発する。



2018年2月1日 17時

卒論進捗：3.2 MB（71 ページ）
なんでこんなに容量増えているんだろう、わからん。


2018年2月2日 5時

卒論進捗：3.2 MB（72 ページ）


2018年2月2日 11時

卒論進捗：3.2 MB（73 ページ）


2018年2月2日 12時

卒論進捗：3.2 MB（74 ページ）


2018年2月2日 14時

卒論を提出する。





というわけで、りあんさんの実際のスケジュールはこんな感じでした！ みんな正解できたかな〜？

  • 1/31　第1稿提出
  • 2/1　論文題目・100字概要提出
  • 2/2　卒論提出
  • 2/13-14　卒論発表


（卒論提出後の卒論発表までの時期はそこまで限界じゃなかったのでここでは割愛します）

まとめ

卒論は計画的に！

これは本当にそうで、どれだけやばい生活をしても体調を崩さない強靭な肉体と精神がないとこういうことはできないし、たとえその二つがあっても結局運ゲーなので、IQ が 2 以上あるならば絶対にやらないほうがいいです。


（ちなみに、現在は同時実行ジョブ数に制限が設けられているので、上と同じことをしようとすると確実に卒業失敗します）


謝辞

りあんさんの卒論は、りゅうおうのおしごと！ と 三ツ星カラーズ と ゆるキャン△ に支えられました。深く感謝申し上げます。

anime.dmkt-sp.jp
anime.dmkt-sp.jp
anime.dmkt-sp.jp

2018 ICPC Asia Hanoi Regional Contest

ICPC




ベトナムのハノイに行ってきました。

チーム名は narianZ で、メンバーは なり、りあん、ぴろず です。


コンテスト中の話は多分なりくんが書いてくれると思うので、自分は ICPC 海外地区予選に参加するためにした（事務的な）こととかも書きます。
コンテストの話だけ知りたい場合はこの記事はあまりおすすめできません。

国内予選

国内予選で良さげな成績を上げ、財団から 20万円の海外遠征費用を援助していただけることになる。

10月中旬〜後半

ハノイに行くことを決める。理由はたしかレベルがそこまで高くなさそうかつ治安がそこまで悪くなさそう、とかだったような気がする。

10月22日

飛行機の予約を取る。

（この記事を下まで読むとわかるんですが、本当に最短弾丸スケジュールです）


10月後半

東工大 情報理工学院の学院長奨励賞に（しもみれさん（narianZ のコーチ）が）申し込む。
学院長奨励賞については、自分は「ICPC で海外に行くときに申請しておくと高確率でお金が降ってくる仕組み」と認識しています（もちろんそんな仕組みではないんですが）。
hadrori.jp

10月後半〜11月前半

ハノイ大会の登録料 ($200) とホテル代を海外送金で振り込む。
ICPC 地区予選では登録料がかかる大会も存在し、ハノイ大会はそのうちの一つでした。
海外送金は慣れていないと普通に大変なので早め早めにやっておいた方が良いです。


11月前半〜中旬

そろそろチーム練をしたいよね。


11月22日

やっと夏合宿以降初のチーム練をする。

2017年のベトナム大会のセットを使って本番4位相当。

Problems from The 2017 ACM - ICPC Asia Ho Chi Minh City Regional Contest – Kattis, Kattis


11月27日（出発前日）

ライブラリをまとめて、印刷をする。

朝8時台の飛行機を取ったことを後悔する（ちなみに帰国の飛行機も朝8時台）。

起きる自信がなかったため徹夜をする

11月28日（コンテスト2日前）

5時半に家を出る。暗い。寒い。

羽田に着いたら WAsedAC の方々がいてびっくりする。



ベトナムに到着する（6時間のフライトはとてつもなく暇だった）。

タクシーガチャはまぁ悪くないものを引けた気がした。

海外からだと結構いろんなアプリやサービスが使えなかったりします。



日本からなくなると話題のサークルKがわりと存在した。



ハノイなので。

11月29日（コンテスト1日前）

7時起き。

ごはんは普通に美味しかった。

Registration をする。

結局おなかは壊さなかった、ベトナムすごい。


コンテストのホスト校である PTIT に移動する。






この後 Practice があった、国内予選の問題（の一部）が使われていた。
ベトナムの国内予選、普通に問題のレベルが高かったので練習に良さそうでした。

11月30日（コンテスト当日）

5時半起き。

かの有名な書類にサインをもらう（上で紹介した学院長奨励賞のために必要）。

ベトナムは街のいたるところに LED が輝いており、いわゆるネオン街みたいなものかなという気持ちになった（めっちゃ眩しかった）。


コンテストが始まる。

冷える。


ツアーが始まり、陶器で有名らしいバッチャン村に連れていかれる。



その後 PTIT に戻り Yes/No が始まる。WAsedAC 強すぎ。



その後ディナー。まさかの屋外だった。
この時に限らず、なりくんとぴろずさんの2人の食べる量の和くらいの量を食べていて、私の燃費、悪すぎ……？ となった。


12月1日

5時半起き。微妙に絶起した。


だいたい 200ドン = 1円くらいです。

帰国。

反省とか

ふざけた主張なんですがあながちなしではなくて困る（タイピングが死ぬほど遅いため）。

これの原因の半分くらいは L の clar に気づかず 1時間くらい溶かしたことがあたるんですが（どういう clar だったのかというのは多分なりくんが書いてくれます）。


横浜でのコンテスト中の動き方の作戦も固めたので、横浜でうまくいけば、ハノイでどういうことを学んで横浜でどういう動きをしたのかをぜひ書きたいですね。


お金の話

今回はコーチのしもみれさんが行けなかったのでコンテスタント 3人での旅立ったのですが、お金は 3人分でこれくらいかかりました（日本円です）。
f:id:riantkb:20181202180550p:plain

これにプラスして現地での食費、タクシー代などがかかるので、+ 1,2 万円という感じだと思います。
うちのチームは財団と大学から支援をしてもらったので現地での食費くらいしかかかりませんでしたが、完全自費で行くのはやはり大変そうという気持ちになりました（もちろん、飛行機代やホテル代はもっと抑えようと思えば抑えられるとは思いますが…）。


感想とか



あと、international のチームにはおそらく 1チームにつき 1人その国の言語がある程度わかるボランティアのガイド学生がついてくれていたんですが、めちゃくちゃ親切でとてもありがたかったです。