C言語で競プロは苦行だった話
こんちか、たくみんです。 今日は、2018年09月08日に行われたAtCoder Beginner Contest 109に挑戦してみました。 時間が取れなかったので、競技時間外に行いました。 A問題とB問題は解くことができましたが、C問題とD問題は解けませんでした。 C言語で解いたのですが、かなり苦行だったので、WriteUpを兼ねてお話しします。
AtCoder Beginner Contest 109 - AtCoder
以下が結果となります。
A問題 ABC333
問題文 1以上3以下の整数A,Bが与えられます。 A×B×Cが奇数となるような1以上3以下の整数が存在するか判定してください。
制約 入力はすべて整数である 1≦A, B≦3
入力
A B
出力
存在するならYes、存在しないならNo
解法
では、解いていきましょう。問題文ではごちゃごちゃ言っていますが、ようするにAとBを入力して、A×B×C=奇数になるようなCが存在するかどうかを判定しろということです。
掛け算の性質として、偶数×偶数の答えは必ず偶数、偶数×奇数の答えは、偶数、奇数×奇数の答えは奇数となります。つまり、2つの値のうち、片方が偶数だと、絶対に奇数にはならないということです。
ではここで、A×B×CのA×BをDとおき、D×Cとします。
掛け算の性質から、この式の答えが奇数になるかどうかは、Dが偶数か奇数かどうかで判定することができます。
このプログラムをCで書くと以下のようになります。 A×Bの答えが偶数か奇数かによって出力をわけているだけですね。このくらいならCでも問題なく書けます。
#include<stdio.h> int main(void) { int a,b; scanf("%d %d", &a, &b); if (((a*b) % 2) == 0 ) { printf("No"); } else { printf("Yes"); } return 0; }
B問題 Shiritori
問題文
高橋くんは今日も1人でしりとりの練習をしています。 しりとりとは以下のルールで遊ばれるゲームです。
はじめ、好きな単語を発言する
以降、次の条件を満たす単語を発言することを繰り返す
その単語はまだ発言していない単語である
その単語の先頭の文字は直前に発言した単語の末尾の文字と一致する
高橋くんは、10秒間にできるだけ多くの単語を発言する練習をしています。 高橋くんが発言した単語の個数 Nと i番目に発言した単語 Wiが与えられるので、どの発言もしりとりのルールを守っていたかを判定してください。
制約 Nは2≦N≦100を満たす整数である Wiは英小文字からなる長さ1以上10≦の文字列である
入力
N W1 W2 : Wn
出力
しりとりのルールを守っているならYes、守っていないならNo
解法 では、解いていきましょう。これは、文字列検索の問題ですね。チェックしなければならないのは、同じ文字列が出現していないかという点と、文字列の先頭が、一つ前の文字列の末尾と同じかどうかという点です。 前者はCでも簡単に書けます。チェックする関数は以下のようになります。 愚直に、2重for文を用いました。入力する文字列は2次元配列のchar型変数wordsとして定義しています。stecmp関数ですべての組み合わせをチェックし、同じ文字列があれば0(No)を返しています。
int check_shiritori1(int n) { int k1,k2; for (k1 = 0; k1 < n; k1++) { for (k2 = 0; k2 < n; k2++) { if (k1 == k2) { continue; } if (strcmp(words[k1], words[k2]) == 0) { return 0; } } } return 1; }
では、後者の点をチェックしてみます。このチェックに必要なのは、文字列の先頭と末尾です。先頭は[0]で表せますが、末尾をCで表そうとするとかなりめんどくさいです。(RubyとかPythonだと[-1]でいけるらしい。いいなぁ) 悩んだ結果、strlenで文字列の長さを取得し、-1することで末尾を表しました。 以下のような関数になりました。いまみてもif文の条件がひどいですね… for文を回し、文字列の先頭と一つ前の文字列の末尾が違う文字の場合0(No)を返しています。
int check_shiritori2(int n) { int k; for (k = 1; k < n; k++) { if (words[k][0] != words[k-1][strlen(words[k-1])-1]) { return 0; } } return 1; }
最後にmain文です。set_words関数は、入力した文字列を変数wordsに格納する関数です。
check_shiritori1関数と、check_shiritori2関数の両方が1を返したときにYesと表示します。
一応、正解することはできましたが、Cで競プロは厳しいと思った問題でした。
#include<stdio.h> #include<string.h> #define MAX_N 100 #define MAX_L 10 void set_words(int n); int check_shiritori1(int n); int check_shiritori2(int n); char words[MAX_N][MAX_L+1]; int main(void) { int n; int result1, result2; scanf("%d", &n); set_words(n); result1 = check_shiritori1(n); result2 = check_shiritori2(n); if ( (result1 * result2) == 0) { printf("No"); } else { printf("Yes"); } return 0; }
おわりに
Cで競プロをしようとする場合、文字列検索や、ソートなどを自分で実装しないといけないため、かなり厳しいと感じました。次は、Rubyとかでやってみようかと思います。ではでは。
P.S.
ブログって日本語力が試される
Pythonのmatplotlibを使ってみた
こんちか、たくみんです。 今日は、Pythonのグラフ描画ライブラリであるmatplotlibを使ってみます。 Wikipediaによると、numpyと呼ばれるライブラリのためのグラフ描画ライブラリらしいです。 このmatplotlibを使うことで、巡回セールスマン問題の可視化ができそうですね。
ウィンドウを出してみる
初めに、グラフを描画するためのウィンドウを表示してみましょう。実は、初めてのPythonだったりします。 なので、Python2とかPython3とかまだよくわかってませんが、今回はPython3を使います。 test.pyを作成し、以下のようなコードを記述します。
import numpy as np import matplotlib.pyplot as plt def plot_start(): plt.figure() # ウィンドウを作成 plt.show() # ウィンドウを描画 if __name__ == '__main__': print("plot start") plot_start()
そして、test.pyを実行すると次のような何もないウィンドウが表示されます。 たった２行の処理を書くだけでウィンドウを表示することができました。
グラフを表示してみる
では、次にグラフを表示してみましょう。 test.pyを以下のように書き換えます。グラフに使用する値をnumpyライブラリを用いて設定し、反映させました。
import numpy as np import matplotlib.pyplot as plt def plot_start(): plt.figure() # ウィンドウを作成 #---- グラフに使用する値を設定 x = np.asarray([1,2,3]) y = np.asarray([1,2,3]) plt.plot(x,y) # 値をグラフに反映 plt.show() # ウィンドウを描画 if __name__ == '__main__': print("plot start") plot_start()
実行すると以下にような、グラフが表示されました。なんとかグラフを表示するところまでたどり着くことができました。
おわりに
matplotlibはオブジェクト指向を意識してグラフを描画することができ、更に細かい設定もできるようです。 まだまだ先は長そうなので、ゆっくり進んでいこうかと思います。ではでは。
P.S.
こんなしょぼい内容でいいのかと思ってみたり。
巡回セールスマン問題に興味を持つ
継続してブログを書くといいつつ、２回めの記事が２ヶ月後となってしまいました。論文とかもあったので許してください。
巡回セールスマン問題
巡回セールスマン問題とは、複数の点とその距離が与えられたとき、すべての点を通りつつ、最初の点に戻ってくる総移動距離を最小にする最適化問題のことです。(巡回セールスマン問題 - Wikipedia) ようするに、以下の図のような６点が与えられた時に、移動距離が最小となるような経路を探せという問題ですね。この例だとこの経路が一番移動距離が短いようです。
この問題は、点の数が多くなるほど、総当りで解くのが困難になります。なぜならば、nの点に対する経路の組み合わせはn!通りとなるからです。以下の表にnとn!の関係を表してみたところ、点の数が１５の時点で１兆パターンを超えてしまっています。 このことを考えると５０個や１００個の点の経路を総当りで解くのは不可能ですね。そのせいかはわからないですが、この巡回セールスマン問題はNP困難とかいうとてもむずかしい問題のひとつとなっています。
| n | n! |
|---|---|
| 1 | 1 |
| 5 | 120 |
| 10 | 3628800 |
| 15 | 1307674368000 |
| 20 | 2432902008176640000 |
巡回セールスマン問題に興味を持ったきっかけ
私が、巡回セールスマン問題に興味を持ったきっかけは、「理系が恋をしたので証明してみた」という漫画を読んだからです。漫画では、遊園地のアトラクションを効率よく回るルートを調べる方法として、巡回セールスマン問題が登場していました。
巡回セールスマン問題を応用したアプリの構想
これを見た時に、自分の周りでも巡回セールスマン問題を応用できるのではないかと考えたところ、あるひとつの解を思いつきました。 そう、聖地巡りです。 というわけで、アニメ聖地の緯度経度情報から、最適な聖地巡りのルートを算出するアプリケーションを作っていきたいなと思います。
おわりに
まだ概要しかきまっていないため、いつになるかはわかりませんが、開発が進めば記事として紹介していきます。 おそらく、まだまだ進まないので、当分の記事は、今まで作ってきたアプリの紹介や、いま興味を持っているものなどになりそうです。 ではでは
はてなブログデビュー
初めてのブログに挑戦
大学4年生にして、ブログを書くことにしました。
私自身、忘れやすい性格で、自分が実装したコードが理解できないということよくがあります。
なので、自分がやったことを文章化し、後々ドキュメントとして役立てたいという思いでブログを書くことにしました。
しかし、ここで一つ問題があります。
それは、開発の記事しか書かないという縛りを行った場合、記事数が少なくなってしまうということです。開発すればいいじゃんというツッコミは受け付けていませんよ。なので、開発に関すること以外の記事、例えば趣味の話なども記事にしていきたいと思います。
ラブライブと私
アイコンを見てもわかる通り、ラブライブにはまっています。開発しているアプリケーションもラブライブに関係するものが多く、これからもラブライブ関連のアプリを作っていきたいと思っています。
抱負
とりあえず、継続してブログを書くということを心がけていきたいと思います。また、自分の開発したアプリや、学んだ技術もなるべく記事として残し、アウトプットしていきます。
PS
ラブライブエンジニアとして、有名になりたいなぁ
